Doktorand Ing. Gabriel Hévr z FIT ČVUT získal ocenění “Best Student Paper” na prestižní konferenci PPAM 2024 (Parallel Programming and Applied Mathematics) za svou práci na algoritmu PPQSort. PPAM je mezinárodní konference, která se koná již 30 let a zaměřuje se na paralelní programování a aplikovanou matematiku, s důrazem na high-performance computing (HPC). Letošní konference se konala v Ostravě, kde Gabriel Hévr představil svůj článek “PPQSort: Pattern Parallel Quicksort”, který navazuje na jeho diplomovou práci a byl oceněn jako nejlepší studentský příspěvek.
Třídicí algoritmy jsou klíčovou součástí informatiky. Používají se v mnoha programech a systémech a jejich efektivita a rychlost jsou zásadní. I když je třídění jedním z nejstarších problémů v informatice, stále je to velmi aktivní oblast výzkumu a vývoje. Moderní přístup je algoritmy třídění paralelizovat. Tato technika maximalizuje využití vícejádrových procesorů, což vede k významnému zlepšení výkonu ve srovnání se sekvenčními metodami.
„V článku se zabýváme problematikou paralelního řazení prvků, přičemž hlavním zaměřením je quicksort a jeho možné optimalizace a efektivní paralelizace. Výsledky našich experimentů ukazují, že nově navržený algoritmus PPQSort překonává všechny dosavadní paralelní implementace quicksortu, což patrně přispělo k úspěchu našeho článku,” říká Gabriel Hévr. „V budoucnu bychom chtěli prozkoumat další třídicí algoritmy a možnosti jejich vylepšení. Z těchto poznatků bychom chtěli vytvořit nový hybridní třídící algoritmus. Třídicí algoritmy jsou stále velmi aktivní oblastí výzkumu a vývoje, a nové přístupy jako PPQSort ukazují, že je stále co zlepšovat,” doplňuje.
Nový inovativní řídící algoritmus PPQSort vychází z tradičního třídicího algoritmu zvaného Quicksort a dále využívá novodobých výzkumů a vylepšení v oblasti třídících algoritmů. Jedním z hlavních vylepšení je, že je algoritmus napsán tak, aby se eliminovalo co nejvíce podmíněného kódu. Podmíněný kód je část programového kódu, která se vykoná pouze tehdy, pokud je splněna určitá podmínka. Moderní procesory poskytují tak zvaný pipelining, tedy spekulativní zpracovávání následujících instrukcí najednou. Nicméně právě podmíněný kód pipelining velmi zpomaluje, protože procesor nemůže jednoduše předvídat, jaká další instrukce se bude vykonávat dokud se nevyhodnotí podmínka. Moderním přístupem je tedy psát tak zvaný “branchless” kód a tento přístup je použit i v PPQSort algoritmu.
PPQSort tedy vyniká svým výkonem i snadným použitím. Má tak několik výhod oproti jiným třídícím algoritmům. PPQSort je napsán v programovacím jazyce C++ a nevyužívá žádné externí knihovny ani speciální nástroje. Díky tomu může být snadno použit v různých prostředích. PPQSort také umožňuje efektivní využití vícejádrových procesorů a díky tomu také poskytuje velmi dobrý výkon na superpočítačích. Superpočítače jsou velmi výkonné výpočetní počítače, typicky používané právě v oblasti HPC.
Testy ukázaly, že PPQSort je rychlejší a spolehlivější než jiné existující metody třídění. Testy byly provedeny na různých superpočítačích a s různými typy dat, a PPQSort si vedl skvěle ve všech případech.
