Search code examples
cudathrust

Which algorithm does thrust::merge use internally?

I want to know which merge algorithm thrust::merge uses internally.

For example, mgpu::merge (Modern GPU Merge) is based on GPU Merge Path - A GPU Merging Algorithm.

Which algorithm does thrust::merge use and how does it differ from GPU Merge Path?

Solution

  • Sadly, Thrust does not explicitly describe the algorithm they actually use. However, you can find the CUDA implementation here and understand what the algorithm does. At the time of writing, they use a tiled-based partitioned merge.

    The algorithm is divided in 3 steps:

    • partitioning: use a binary search in shared memory to find merge path for each of thread;
    • merging: execute an independent serial merge in each thread;
    • joining: write data back into the global memory.

    The current Thrust implementation seems to be close to the one in your provided research paper.