PaperlayerView exact revision on arXiv

Source-linked AI summary

Revisiting Co-Processing for Hash Joins on the Coupled CPU-GPU Architecture

Jiong He, Mian Lu, Bingsheng He

arXiv:1307.1955v1cs.DC

TL;DR

PCI-e transfer overhead is a bottleneck for GPU co-processing, so this paper experimentally revisits hash joins on coupled CPU-GPU architectures. It explores fine-grained co-processing and uses cost models to guide design choices. Fine-grained co-processing achieves up to 53%, 35%, and 28% performance improvement over CPU-only, GPU-only, and conventional CPU-GPU co-processing, respectively.

  • Problem

    Low PCI-e bandwidth and high latency are bottlenecks for GPU co-processing.

    Source: §1 · p. 1

  • Method

    The study examines fine-grained co-processing for hash joins with and without partitioning and extends cost models to guide design choices.

    Source: §1 · p. 2

  • Results

    Fine-grained co-processing achieves up to 53%, 35%, and 28% performance improvement over CPU-only, GPU-only, and conventional CPU-GPU co-processing, respectively.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Conventional co-processing yields only marginal improvement on coupled architectures, while fine-grained scheduling can assign suitable workloads to both processors.

    Source: §5.6 · pp. 11–12

    Coarse-grained DD scheduling may under-utilize the CPU and GPU when some steps perform better on the other processor.

    Source: §3.2 · p. 5

Abstract

from arXiv · show

Query co-processing on graphics processors (GPUs) has become an effective means to improve the performance of main memory databases. However, the relatively low bandwidth and high latency of the PCI-e bus are usually bottleneck issues for co-processing. Recently, coupled CPU-GPU architectures have received a lot of attention, e.g. AMD APUs with the CPU and the GPU integrated into a single chip. That opens up new opportunities for optimizing query co-processing. In this paper, we experimentally revisit hash joins, one of the most important join algorithms for main memory databases, on a coupled CPU-GPU architecture. Particularly, we study the fine-grained co-processing mechanisms on hash joins with and without partitioning. The co-processing outlines an interesting design space. We extend existing cost models to automatically guide decisions on the design space. Our experimental results on a recent AMD APU show that (1) the coupled architecture enables fine-grained co-processing and cache reuses, which are inefficient on discrete CPU-GPU architectures; (2) the cost model can automatically guide the design and tuning knobs in the design space; (3) fine-grained co-processing achieves up to 53%, 35% and 28% performance improvement over CPU-only, GPU-only and conventional CPU-GPU co-processing, respectively. We believe that the insights and implications from this study are initial yet important for further research on query co-processing on coupled CPU-GPU architectures.

1. INTRODUCTION

The paper revisits hash-join co-processing because PCI-e transfer and separate CPU/GPU caches constrain discrete systems, while coupled architectures offer new opportunities. It studies fine-grained designs and cost-model-guided choices, reporting performance gains over three baselines.

  • Discrete systems face PCI-e transfer overhead and limited cache reuse, whereas coupled systems integrate CPU and GPU and can share memory and cache.The integrated architecture avoids PCI-e data transfer; the APU example shares the L2 data cache.Source: §1 · pp. 1–2
  • The study examines fine-grained co-processing for hash joins with and without partitioning, including shared or separate hash tables and different co-processing granularities.It extends existing cost models to guide choices across this design space.Source: §1 · p. 2
  • Coupled architectures enable fine-grained co-processing and cache reuse, while conventional co-processing provides only marginal performance improvement there.The evaluation also finds that the cost model can guide optimization choices and examines design tradeoffs.Source: §1 · p. 2
  • Across evaluated co-processing variants, fine-grained co-processing achieves up to 53%, 35%, and 28% performance improvement compared with CPU-only, GPU-only, and conventional CPU-GPU co-processing, respectively.Source: §1 · p. 2

2. PRELIMINARIESAND RELATED WORK

This section introduces CPU-GPU architectures, OpenCL, and prior hash-join work, with attention to how coupled hardware changes co-processing opportunities.

2. PRELIMINARIESAND RELATED WORK

  • The preliminaries introduce CPU-GPU architectures and OpenCL before reviewing related work on hash joins.Source: §2 · p. 2

2.1 Coupled CPU-GPU Architecture

  • Discrete systems connect CPU and GPU through PCI-e and separate memory paths, while coupled systems share main memory and L2/L3 cache.The study uses an AMD APU and stores data in its zero-copy buffer; its coupled GPU has fewer cores and a lower clock than the discrete reference GPU.Source: §2.1 · p. 2, Table 1 · p. 3

2.2 OpenCL

  • OpenCL provides a common programming model in which the same code can run on CPU and GPU devices, with kernels executed through work groups and work items.Its logical global, local, and private memory levels map to the target processor's physical memory hierarchy.Source: §2.2 · p. 3

2.3 Architecture-aware Hash Joins

  • The study focuses on single simple and partitioned hash joins, building on work addressing memory stalls, cache-aware algorithms, prefetching, and GPU co-processing.It also positions its coupled-architecture design-space and cost-model study against prior coupled-system work.Source: §2.1 · pp. 2–3, §2.3 · p. 3

3. HASH JOIN CO-PROCESSING

The section defines tuple-level steps for simple and partitioned hash joins, then examines co-processing mechanisms and implementation tradeoffs for coupled CPU-GPU systems. It considers memory and OpenCL optimizations alongside choices in scheduling and workload division.

3.1 Fine-grained Steps in Hash Joins

  • Fine-grained steps decompose simple hash joins into build and probe series, while partitioned joins add partitioning series before joining each partition pair.A simple hash join builds a table for R and probes it with S; partitioned hash joins use radix partitioning before applying simple joins to partition pairs.Source: §3.1 · p. 4

3.2 Revisiting Co-processing Mechanisms

  • Off-loading assigns each step to one processor, while data dividing runs both processors simultaneously on portions of the same step's input.Data dividing uses one workload ratio across the step series, but coarse-grained assignment can still underuse a processor when individual steps favor the other.Source: §3.2 · pp. 4–5
  • Pipelined execution assigns a separate CPU workload ratio to each step, balancing processor efficiency against intermediate results and dependencies between steps.The model searches workload ratios to estimate execution time; off-loading and data dividing are special cases of pipelined execution.Source: §3.2 · p. 5

3.3 Implementations and Design Tradeoffs

  • The implementations examine step granularity, shared versus separate hash tables, workload grouping, and a software allocator that reduces GPU contention through block allocation.The optimized allocator also reduces CPU allocation overhead; shared hash tables improve cache performance, while separate tables reduce CPU-GPU latch contention.Source: §3.3 · p. 6
  • Very fine-grained steps are not the only option, and partition-pair joins with separate hash tables may lose cache reuse available to fine-grained variants.The basic allocator's atomic latch may contend under massive GPU parallelism, motivating the block-based allocator.Source: §3.3 · pp. 5–6

4. PERFORMANCE MODEL

The performance model predicts hash-join co-processing time on a coupled CPU-GPU architecture and uses those predictions to select parameter values. It combines a step-based model of processor execution, memory costs, and synchronization delays with profiling and algorithm-specific modeling.

4.1 The Abstract Model

  • The model estimates total elapsed time as the longer of the CPU and GPU execution times across the step series.Each processor's time sums the execution times of all steps.Source: §4.1 · p. 7
  • Per-step time includes computation, global-memory access, and pipelined delay, with computation estimated from instruction execution under an ideal-pipeline, optimal-IPC assumption.The model also assumes uniform data distributions for hash joins.Source: §4.1 · p. 7
  • Memory-stall costs are calibrated per data item, excluding caching effects and thread parallelism, for random and sequential access patterns.The model instantiates costs according to each step's access pattern.Source: §4.1 · p. 7
  • A workload-ratio change between consecutive steps can create a synchronization delay while one processor waits for data produced by the other.The model treats the CPU-wait and GPU-wait cases separately according to which workload ratio is larger.Source: §4.1 · p. 7
  • When consecutive steps use different workload ratios, the model estimates intermediate data from their ratio difference, assuming a uniform distribution.The estimated item count is (r_i − r_(i−1)) × x_i.Source: §4.1 · p. 7

4.2 Model Instantiation

  • For SHJ variants, the model combines profiling and calibrated memory costs with the abstract model; workload-dependent instruction costs use per-key-search units and average key-list length.The SHJ-DD build-phase example instantiates the model for four steps and estimates total phase time.Source: §4.2 · p. 7

5. EVALUATION

The evaluation tests hash-join co-processing on an AMD APU, covering discrete-architecture costs, cost-model accuracy, design tradeoffs, and end-to-end performance.

5.1 Experimental Setup

  • Experiments use an AMD APU, synthetic four-byte integer relations, and tuned OpenCL implementations, with 16 million tuples per relation by default.The study also varies data size, skew, and join selectivity.Source: §5.1 · p. 8

5.2 Evaluations on Discrete Architectures

  • On discrete systems, PCI-e transfers cost 4–10% and DD merging 14%/18%; GPU acceleration varies by step, making fine-grained assignments preferable to whole-join offload.Different step ratios can also create intermediate transfers and pipeline divergence; in one example, differing assignments require transferring 56% of a step's output.Source: §5.2 · pp. 8–9

5.3 Cost Model Evaluation

  • Cost-model estimates stay close to measurements across tuned ratios and Monte Carlo trials, with prediction error below 15% in most cases.The model's estimates are slightly low for SHJ-DD because they omit lock contention; it predicts a near-best setting in the reported trials.Source: Figure 7 · p. 9, §5.3 · pp. 9–10, Figure 8 · p. 9

5.4 Design Tradeoffs on Coupled CPU-GPU Architectures

  • Shared hash tables cut SHJ-DD/PHJ-DD build time by 16%/26%; optimized allocation improves SHJ/PHJ performance by up to 36%/39%.A 2KB allocation block is selected in the experiments; larger blocks reduce lock overhead, while shared tables also reduce cache misses.Source: Figure 10 · p. 10, §5.4 · p. 10, Figure 11 · p. 10
  • Grouping improves overall performance by 5–10%; coarse-grained PHJ-PL’ is much slower than PHJ-PL and has more cache misses.The coarse-grained definition introduces separate hash tables, unlike the fine-grained version.Source: §5.4 · pp. 10–11, Table 3 · p. 11

5.5 End-to-End Performance Comparison

  • Up to 53%, 35%, and 28% improvement over CPU-only, GPU-only, and DD, respectively, comes from optimized fine-grained PL; PHJ-PL is usually 2–6% faster than SHJ-PL.Performance trends are similar across uniform and skewed datasets; high-skew execution can match or beat uniform execution, while increasing selectivity has marginal impact on PL.Source: Figure 13 · p. 11, Figure 14 · p. 11, §5.5 · p. 11

5.6 Summary and Lessons Learnt

  • The authors conclude that co-processing schemes should fit the target architecture, with fine-grained scheduling and cost-based tuning suited to coupled systems.They also identify memory and OpenCL optimizations as important and argue that query processors should expose fine-grained data parallelism.Source: §5.6 · pp. 11–12

6. CONCLUSION

The study revisits fine-grained co-processing for hash joins on coupled CPU-GPU architectures, reporting improvements over single-processor and conventional co-processing baselines. It frames the work as an initial step toward efficient query co-processing on coupled architectures.

  • Up to 53%, 35%, and 28% improvement over CPU-only, GPU-only, and conventional CPU-GPU coprocessing, respectively.Source: §6 · p. 12
  • The study revisits fine-grained co-processing for hash joins with and without partitioning on a coupled CPU-GPU architecture.Source: §6 · p. 12
  • The paper presents its findings as a key first step in designing efficient query co-processing on coupled architectures.Source: §6 · p. 12

A. MORE EXPERIMENTAL RESULTS

These additional experiments compare fine-grained methods with coarse-grained scheduling, examine joins on data beyond the zero-copy buffer, and measure latch overhead. They report performance differences, scaling behavior, and workload-ratio mismatches for the tested approaches.

Comparison with A Coarse-Grained Scheduling Approach

Large datasets that cannot fit into the zero copy buffer

  • For larger inputs, PHJ-PL is up to 9% faster than SHJ-PL, while partition and join times increase almost linearly with input size.For inputs that cannot fit in the zero-copy buffer, relations are partitioned so each partition-pair join fits in the buffer; data copy is around 4% of total time.Source: A. MORE EXPERIMENTAL RESULTS · p. 13, Figure 19 · p. 13

Locking overhead

  • Latch overhead decreases as array size grows until the array exceeds the 4MB cache; beyond that, high-skew execution is slightly faster than uniform execution.The authors attribute the latter result to high-skew data locality compensating for latch overhead.Source: A. MORE EXPERIMENTAL RESULTS · p. 14, Figure 20 · p. 14
Loading 1307.1955v1…