AQsort: Scalable Multi-Array In-Place Sorting with OpenMP

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F16%3A00300849" target="_blank" >RIV/68407700:21240/16:00300849 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.scpe.org/index.php/scpe/article/view/1207" target="_blank" >http://www.scpe.org/index.php/scpe/article/view/1207</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.12694/scpe.v17i4.1207" target="_blank" >10.12694/scpe.v17i4.1207</a>

Jazyk výsledku

angličtina

Název v původním jazyce

AQsort: Scalable Multi-Array In-Place Sorting with OpenMP

Popis výsledku v původním jazyce

A new multi-threaded variant of the quicksort algorithm called AQsort and its C++/OpenMP implementation are presented. AQsort operates in place and was primarily designed for high-performance computing (HPC) runtime environments. It can work with multiple arrays at once; such a functionality is frequently required in HPC and cannot be accomplished with standard C pointer-based or C++ iterator-based approach. An extensive study is provided that evaluates AQsort experimentally and compares its performance with modern multi-threaded implementations of in-place and out-of-place sorting algorithms based on OpenMP, Cilk Plus, and Intel TBB. The measurements were conducted on several leading-edge HPC architectures, namely Cray XE6 nodes with AMD Bulldozer CPUs, Cray XC40 nodes with Intel Hasswell CPUs, IBM BlueGene/Q nodes, and Intel Xeon Phi coprocessors. The obtained results show that AQsort provides good scalability and sorting performance generally comparable to its competitors. In particular cases, the performance of AQsort may be slightly lower, which is the price for its universality and ability to work with substantially larger amounts of data.

Název v anglickém jazyce

AQsort: Scalable Multi-Array In-Place Sorting with OpenMP

Popis výsledku anglicky

A new multi-threaded variant of the quicksort algorithm called AQsort and its C++/OpenMP implementation are presented. AQsort operates in place and was primarily designed for high-performance computing (HPC) runtime environments. It can work with multiple arrays at once; such a functionality is frequently required in HPC and cannot be accomplished with standard C pointer-based or C++ iterator-based approach. An extensive study is provided that evaluates AQsort experimentally and compares its performance with modern multi-threaded implementations of in-place and out-of-place sorting algorithms based on OpenMP, Cilk Plus, and Intel TBB. The measurements were conducted on several leading-edge HPC architectures, namely Cray XE6 nodes with AMD Bulldozer CPUs, Cray XC40 nodes with Intel Hasswell CPUs, IBM BlueGene/Q nodes, and Intel Xeon Phi coprocessors. The obtained results show that AQsort provides good scalability and sorting performance generally comparable to its competitors. In particular cases, the performance of AQsort may be slightly lower, which is the price for its universality and ability to work with substantially larger amounts of data.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Scalable Computing: Practice and Experience

ISSN

1895-1767

e-ISSN

—

Svazek periodika

17

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

RO - Rumunsko

Počet stran výsledku

23

Strana od-do

369-391

Kód UT WoS článku

000389146100008

EID výsledku v databázi Scopus

2-s2.0-84992745493