HotSort 2.0

- 5 mins read

I hadn’t touched my HotSort codebase in a long time but recently was able to spend a couple weeks developing a generalized version of the sorting algorithm that can be “tuned” for a specific GPU architecture.

After more than a couple years of thinking about the algorithm, I had accumulated a number of performance and portability ideas. The most important idea generalized the HotSort sorting algorithm so that it could run well on some of the newer resource-rich but architecturally different “shaped” OpenCL GPUs.

The original HotSort algorithm took a rather long time to develop and made heavy use of preprocessing. Although it ran on every (5?) CUDA architecture, the algorithm was very tied to a SIMD width of 32 and a CUDA-specific registers-per-SMEM ratio. Additionally, to keep everything simple, many internal parameters were chosen to be powers of two.

I was (and still am) pleased with the original algorithm’s performance on CUDA but I was unable to explore the algorithm’s parameter space as new GPU architectures appeared.

More registers per thread, larger block sizes and more shared memory were all resources that HotSort could exploit but the existing codebase was solid and performance on CUDA was still great so a time consuming rewrite was a nonstarter.

The solution to my problem was writing a program that would let me quickly generate and tune a set of HotSort kernels to fit any GPU architecture and platform.

Two years of sporadically thinking about the algorithm plus two weeks of focused coding produced a HotSort kernel code generator (and even more ideas) that could emit both CUDA and OpenCL kernels.

In future posts I’ll describe the updated performance on CUDA devices but the first test case was getting the HotSort algorithm running on Intel’s integrated OpenCL GPUs.

There is already plenty of detail on the Intel compute architecture but, with my HotSort kernel code generator in hand, the most appealing trait of the architecture is its generous amount of shared memory and large register files. The Intel IGPs have very high SMEM-to-ALU and register-to-ALU ratios. The new HotSort kernels can exploit these resources!

One puzzling feature of the architecture is that the very largest cooperating thread array (CTA) is relatively small and can’t completely utilize all of the executing subslice’s hardware threads. You must launch two CTAs. Some GPU compute kernels perform best with a single CTA per multiprocessor. This capability is on my wish list.

Intel’s Haswell Gen7.5 IGPs can launch a maximum CTA of 512 work items. The CTA’s executing subslice has 70 SIMD8 hardware threads and can execute up to 560 OpenCL work items – but not in a single CTA.

Similarly, the Broadwell Gen8 IGP supports CTAs of up to 256 work items running on a 56 x SIMD8 subslice (448 work items).

So, for now, no large CTAs:

But as we’ll see below, these CTAs have access to a surprising amount of registers and shared memory.

The most critical “building block” kernel used by the HotSort algorithm is a “block sorter”. The block sorter is a CTA that loads a block of keys once from global memory, sorts and/or merges them and writes the sorted block back to global memory. Other HotSort kernels merge sorted blocks but that’s a slightly less sexy engineering challenge.

What resources can a maximum-sized Gen7.5 CTA provide to a HotSort block sorting kernel? It’s very generous:

  • Registers: 512 x 128 = 64K 32-bit registers.
  • Local memory: 64KB
  • Cores: 80

Armed with an understanding of the Intel Gen compute architecture and the new HotSort kernel generator (and some scripting) I generated about 19,000 kernels of various shapes and sizes. Kernels were generated that varied their exploitation of the register file, shared memory utilization and CTA size.

Let’s see how the generated block sort kernels did for 32-bit keys:

And here are the 64-bit key block sort kernels:

The facts and takeaways on the 32-bit key block sorter plot are:

  • The “best” kernel configurations are on the upper frontier of the red scatter plot.
  • A Haswell subslice has 10 SIMD8 EUs (80 FPUs).
  • The HD4600 IGP runs at a peak of 1.2 GHz.
  • Keys are loaded from global memory and stored back only once.
  • 44K 32-bit keys can be squeezed into an Intel IGP subslice and sorted at 73 Mkeys/sec (0.61 ms).
  • Sorting 8-16K 32-bit keys approaches 100 Mkeys/sec (0.12-0.16 milliseconds).
  • The “dips” in throughput are block sort configurations with very narrow CTAs and very high register-per-thread counts. Using ~120 registers/thread results in spills and a narrow CTA can’t hide the latency. Thanks to the autotuning step, these kernel configurations can be discarded.
  • Using these results, a few of the best kernel configurations will be used to sort larger arrays.
  • There are typically 2-4 subslices and 20-40 EUs in a Haswell processor and merging is cheap so the expectation is the peak sorting rate for ~250K keys is going to be excellent. The 64-bit results are also excellent!

Next time I’ll show off some additional performance improvements to the algorithm and maybe some CUDA or Intel Broadwell Gen8 IGP benchmarks.

Let me know if you have any questions!