Heterogeneous CPU-GPU Epsilon Grid Joins: Static and Dynamic Work Partitioning Strategies
Heterogeneous CPU-GPU Epsilon Grid Joins: Static and Dynamic Work Partitioning Strategies
复制标题
DOI：
10.1007/s41019-020-00145-x
复制
发表时间：
2020-10
影响因子：
4.2
通讯作者：
Benoît Gallet;M. Gowanlock
中科院分区：
文献类型：
--
作者：
Benoît Gallet;M. Gowanlock
给定两个数据集（或表）和一个搜索距离，距离相似连接（表示为）找到点对（,），其中和，并且使得两者之间的距离为。如果，则相似性连接等价于相似性自连接，表示为。本文提出了异构Epsilon网格连接算法（HEGJoin），这是一种异构CPU-GPU距离相似连接算法。有效地在CPU和GPU之间划分工作是一个挑战。实际上，工作分区策略需要考虑处理器（CPU和GPU）的不同特征和计算吞吐量，以及在总体执行时间中考虑的相似连接的数据依赖性（例如，查询的数量、它们的分布、维度等）。除了hegjoin之外，本文还设计了一种动态和两种静态工作分区策略。我们还为每个静态分区策略提出了一个性能模型，以便在处理器之间执行工作分配。我们通过考虑执行时间和CPU和GPU之间的负载不平衡作为性能指标来评估所有三种分区方法的性能。在我们的第一个测试平台上，hegjoinone在仅gpu （CPU-only）算法上实现了高达（）的加速，而在第二个测试平台上，hegjoinone在仅gpu （CPU-only）算法上实现了高达（）的加速。
Given two datasets (or tables)AandBand a search distance, the distance similarity join, denoted as, finds the pairs of points (,), whereand, and such that the distance betweenandis. If, then the similarity join is equivalent to a similarity self-join, denoted as. We propose in this paper Heterogeneous Epsilon Grid Joins (HEGJoin), a heterogeneous CPU-GPU distance similarity join algorithm. Efficiently partitioning the work between the CPU and the GPU is a challenge. Indeed, the work partitioning strategy needs to consider the different characteristics and computational throughput of the processors (CPU and GPU), as well as the data-dependent nature of the similarity join that accounts in the overall execution time (e.g., the number of queries, their distribution, the dimensionality, etc.). In addition toHEGJoin, we design in this paper a dynamic and two static work partitioning strategies. We also propose a performance model for each static partitioning strategy to perform the distribution of the work between the processors. We evaluate the performance of all three partitioning methods by considering the execution time and the load imbalance between the CPU and GPU as performance metrics.HEGJoinachieves a speedup of up to() over the GPU-only (CPU-only) algorithms on our first test platform and up to() on our second test platform over the GPU-only (CPU-only) algorithms.