A Platform for Engineering Cache-Oblivious Algorithms and Data Structures: The Architecture

Cache-oblivious algorithms are designed to be executed on the ideal-cache machine, an abstract machine which faithfully models real-world machines with hierarchical memory. Algorithms for the ideal-cache machine, as well as algorithm for the RAM, work with a semi-infinite memory space. But while in the uniform RAM model it is assumed that every memory access has the same cost, which is incorrect for large data sets, the semi-infinite memory of the ideal-cache machine models the virtual memory space of a computer, and block transfers to a faster memory level are taken into account by the model. Nevertheless, implementing cache-oblivious algorithms and data structures is not an easy task, because they use peculiar techniques that are not (easily) supported by general purpose programming languages and environments such as C, C++, or Java.