Cache Oblivious Algorithms and Data Structures (Demaine 2002) 计算机科学

Cache-Oblivious Algorithmsand Data StructuresErik D. DemaineMIT Laboratory for Computer Science, 200 Technology Square, Cambridge, MA 02139, USA, edemaine@mit.eduAbstract. A recent direction in the design of cache-efficient and disk- efficient algorithms and data structures is the notion of cache oblivi- ousness, introduced by Frigo, Leiserson, Prokop, and Ramachandran in 1999. Cache-oblivious algorithms perform well on a multilevel memory hierarchy without knowing any parameters of the hierarch