Grafové algoritmy hrají velkou roli v moderní informatice. Vzhledem k neustále rostoucím objemům dat se je snažíme paralelizovat, a jednou z možností je jejich zápis pomocí operací lineární algebry nad vhodnými polookruhy, který dovoluje nejen čitelně implementovat paralelně mnohé algoritmy klasické, ale i snáze experimentovat s novými. V posledních letech umožňují procesory provádět takové operace nad řídkými maticemi nejen ve více vláknech, ale i paralelně v rámci každého vlákna s využitím vektorových instrukcí. Tématem práce je návrh knihovny, která umožní ze strany koncových uživatelů efektivně provádět takto zapsané grafové algoritmy pomocí dynamické kompilace do vektorového strojového kódu, a navíc také poslouží jako experimentální platforma pro vývoj lepších technik dynamické kompilace v budoucnu.
Osnova:
- Seznamte se s metodami implementace grafových algoritmů pomocí operací lineární algebry.
- Seznamte se s architekturou instrukční sady AMD64 a zejména s jejími vektorovými rozšířeními AVX.
- Seznamte se s technikami návrhu optimalizujících kompilátorů.
- Navrhněte a implementujte knihovnu základních stavebních bloků pro grafové algoritmy používajících operace lineární algebry.
- Výsledky dosažené touto knihovnou porovnejte s existujícími implementacemi.
