Performance Evaluation of Different Vector Lengths on an Implementation of Merge Sort Using ARM Scalable Vector Extension (SVE)

Sammanfattning

Modern day research and technology require calculations on large data sets. Groundbreaking technology like artificial intelligence and machine learning are just two examples of technologies that requires computation on large data sets. To increase the speed of the computations, parallelism is needed. While multi-threading works well, it has limitations that some say will be more prominent in the future. Because of these limitations, alternative ways of parallelism such as vectorization needs to be considered. Vectorization has its own limitations, one limitation being the fixed vector length determined at compile time. The introduction of ARM’s Scalable Vector Extension (SVE) allows scalable vectors from 128 to 2048 bits which is determined at runtime. This thesis investigates the efficiency of increasing the vector length on a bitonic merge sort using SVE. We found that a vectorization of the scalar implementation yielded a speedup efficiency of up 55%. Increasing the vector length yielded a speedup of up to 7 times. The increase in performance for larger vector lengths scales in a similar way to known formulas commonly used for multi-processing. Furthermore the result indicate that the performance benefit from larger vector lengths are more prominent on larger problems sizes.