Knihovna pro tvorbu grafových algoritmů z operací lineární algebry

Místo
Název práce anglicky
A Library for Building Graph Algorithms from Linear Algebra Operations
Anotace

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:
1. Seznamte se s metodami implementace grafových algoritmů pomocí operací lineární algebry.

2. Seznamte se s architekturou instrukční sady AMD64 a zejména s jejími vektorovými rozšířeními AVX.

3. Seznamte se s technikami návrhu optimalizujících kompilátorů.

4. Navrhněte a implementujte knihovnu základních stavebních bloků pro grafové algoritmy používajících operace lineární algebry.

5. Výsledky dosažené touto knihovnou porovnejte s existujícími implementacemi.