A fast vectorized sorting implementation based on the ARM scalable vector extension (SVE).

Area of Science:

• Computer Science
• High-Performance Computing (HPC)
• Algorithm Optimization

Background:

• Modern CPUs rely on vectorization units (SIMD) for performance, with x86 architectures dominating HPC for decades.
• The emergence of ARM Scalable Vector Extension (SVE) presents new challenges due to its distinct features like runtime vector size and predicate-based control.
• Adapting existing, optimized algorithms for SVE is crucial for future supercomputing architectures.

Purpose of the Study:

• To port and optimize a hybrid sorting algorithm (Quicksort and Bitonic sort) for ARM SVE processors.
• To address the challenges posed by SVE's unique features, including predicate usage and variable vector lengths.
• To evaluate the performance of the SVE-optimized sorting algorithm on a modern ARM CPU.

Main Methods:

• Implemented a hybrid sort using Bitonic sort for small partitions and a vectorized partitioning approach.
• Managed SVE's runtime vector size and utilized predicate registers for efficient operation control.
• Developed efficient sorting kernels tailored for the ARMv8.2 (A64FX) architecture.

Main Results:

• The SVE-optimized hybrid sort achieved an average speedup factor of 4 compared to GNU C++ sort.
• The approach demonstrated efficient sorting of integers, double-precision floating-point numbers, and key/value pairs.
• The partitioning phase required only O(log N) auxiliary space, applicable to both sequential and parallel implementations.

Conclusions:

• The developed hybrid sorting algorithm effectively leverages ARM SVE capabilities for significant performance gains.
• This work provides a viable strategy for adapting high-performance algorithms to the evolving landscape of HPC processors.
• The optimized implementation offers a faster alternative to standard sorting routines on ARM-based supercomputers.