PhD student Ing. Gabriel Hévr from FIT CTU won the "Best Student Paper" award at the 2024 Parallel Programming and Applied Mathematics (PPAM) conference for his work on the PPQSort algorithm. PPAM is an international conference that has been held for 30 years, focusing on parallel programming and applied mathematics with an emphasis on high-performance computing (HPC). This year's conference took place in Ostrava, where Gabriel Hévr presented his paper "PPQSort: Pattern Parallel Quicksort," which builds on his master's thesis and was awarded as the best student contribution.
Sorting algorithms are a key part of computer science. They are used in many programs and systems, and their efficiency and speed are crucial. Although sorting is one of the oldest problems in computer science, it remains a very active area of research and development. Modern approaches focus on parallelizing sorting algorithms. This technique maximizes the use of multi-core processors, leading to significant performance improvements compared to sequential methods.
"In the paper, we address the problem of parallel sorting of elements, with a primary focus on quicksort and its possible optimizations and efficient parallelization. Our experimental results show that the newly designed PPQSort algorithm outperforms all previous parallel implementations of quicksort, which likely contributed to the success of our paper," says Gabriel Hévr. "In the future, we would like to explore other sorting algorithms and ways to improve them. From these insights, we hope to create a new hybrid sorting algorithm. Sorting algorithms remain a very active research and development area, and new approaches like PPQSort show that there is still room for improvement," he adds.
The new innovative control algorithm PPQSort is based on the traditional sorting algorithm called Quicksort and further incorporates modern research and improvements in sorting algorithms. One of the main enhancements is that the algorithm is written to eliminate as much conditional code as possible. Conditional code is part of the program code that is executed only if a certain condition is met. Modern processors provide pipelining, which allows speculative processing of subsequent instructions simultaneously. However, conditional code significantly slows down pipelining, as the processor cannot easily predict which instruction will be executed until the condition is evaluated. The modern approach is to write "branchless" code, and this approach is used in the PPQSort algorithm.
PPQSort excels in both performance and ease of use. It has several advantages over other sorting algorithms. PPQSort is written in C++ and does not use any external libraries or special tools. As a result, it can be easily used in various environments. PPQSort also enables efficient use of multi-core processors and thus provides excellent performance on supercomputers. Supercomputers are high-performance computing machines typically used in the HPC field.
Tests have shown that PPQSort is faster and more reliable than other existing sorting methods. Tests were conducted on various supercomputers and with different types of data, and PPQSort performed excellently in all cases.
