Cache-oblivious algoritmus
V informatice, cache-oblivious algoritmus, česky asi kešově průhledný algoritmus, je algoritmus navržený tak, aby využil výhod CPU cache, aniž by znal její velikost a charakteristiky. Algoritmus je navržený tak, aby se choval dobře na strojích s různou velikostí 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ší.
![]() | Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty. |