Student FIT získal ocenění na prestižní konferenci PPAM
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.
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.
