Cache-oblivious algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

V informatice, cache-oblivious algoritmus, česky asi kešově průhledný algoritmus, je algoritmus navržený tak, aby využil výhod CPU cache bez toho, aby znal její velikost a charakteristiky. Algoritmus je navržený tak, aby se choval dobře na strojích s různou velkikostí keše nebo když má paměťová hierarchie různý počet úrovní.

Cache-oblivious algoritmy jsou dávány do protikladu k algoritmům s dělením na bloky, které problém dělí na bloky vhodné pro danou velikost keše.

Tyto algoritmy jsou obvykle navrhovány pomocí rekurzivního dělení (rozděl a panuj). Na určité úrovni se celý vstup vejde do keše a výpočet probíhá v ní. Jako optimální cache-oblivious byly navrženy například algoritmy: rychlá Fourierova transformace, násobení matic, třídicí algoritmus, transpozice matice a další.