Parallel hybrid dual pivot sorting algorithm
| Autor: | Surin Kittitornkun, Surapong Taotiamton |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
020203 distributed computing
Multi-core processor Sorting algorithm Speedup Computer science Sorting 02 engineering and technology Parallel computing Dual (category theory) 0202 electrical engineering electronic engineering information engineering Data analysis sort 020201 artificial intelligence & image processing Branch misprediction |
| Zdroj: | 2017 14th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON). |
| DOI: | 10.1109/ecticon.2017.8096252 |
| Popis: | Sorting is one of the common problems in Computer Science and data analytics. This paper presents empirical results of parallel Hybrid Dual Pivot Sort (HDPSort) for multicore/manycore CPU systems. HDPSort makes use of both classic Lomuto and Hoare partioning algorithms with two pivot values in parallel. It is developed in C++ with OpenMP 3.0 or better. HDPSort is benchmarked with the sequential STLSort in terms of run time, instruction count and branch load. The Speedups of HDPSort are up to 3.02× and 2.79× faster than the STLSort on 8-core AMD FX-8320 and 4-core Intel i7-2600 Linux systems, respectively. An indepth analysis shows that HDPSort gains the Speedup by 300% over STLSort at the expense of 1%–4% of branch mispredictions. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|