|
|
Applications of Gray codes in cache-oblivious algorithms
Mička, Ondřej ; Fink, Jiří (vedoucí práce) ; Gregor, Petr (oponent)
Moderní počítače využívají sofistikovanou hierarchii keší, aby snížily latenci přístupů k paměti. Tento fakt vedl ke vzniku cache-oblivious algoritmů, jejichž cílem je dosáhnout co nejlepšího výkonu na takovýchto paměťových hierarchiích, a to s pouze minimální znalostí přesných parametrů dané hierarchie. Při návrhu cache-oblivious algoritmů je velmi často využívána metoda rozděl a panuj, založená na rekurzi. V této práci předvedeme alternativní techniku návrhu cache- oblivious algoritmů, založenou na Grayových kódech. Ukážeme, jak pomocí binárního reflektovaného Grayova kódu procházet pole způsobem, který je přívětivý ke keším. To nám umožní vytvořit alternativní algoritmy pro problémy jako transpozice matice, naivní násobení matic či naivní konvoluce, jež mají stejnou asymptotickou složitost jako je jejich na rekurzi založené protějšky. Výhodou našeho přístupu je, že umožňuje implementovat algoritmy bez rekurze (či rekurzi simulujícího zásobníku) pomocí loopless algoritmu. Taktéž v navrhneme variantu binárního reflektovaného Grayova kódu, upravenou speciálně pro použití v naší technice a téměř loopless algoritmus pro generování tohoto kódu. Kromě teoretické analýzy naší techniky zkoumáme její chování na reálných počítačích, a to konkrétně na problému transpozice matice.
|
host ::
RSS.