| The memory system of modern computer are becoming increasingly sophisticated, which is a hierarchy consisting of multilevel caches,main memory and disk, also instructions are not executed sequentially and in constant time. Accessing words in the lower, faster levels of this memory hierarchy can be done virtually immediately, but accessing the upper levels may cause delays of millions of processor cycles.Consequently, recent developments in algorithm design have had a focus on developing algorithms that sought to minimize accesses to the higher levels of the hierarchy. Now, a number of optimal algorithms have been designed. However, these algorithms are designed and implemented with a very specific level in mind, making it infeasible to adapt them to multiple levels or use them efficiently on different architectures.To alleviate this, the notion of cache-oblivious algorithm and the ideal-cache model were developed by Prokop etc. in 1999. The goal of a cache-oblivious algorithm is to be optimal in the use of the memory hierarchy, but without knowing any parameters of the hierarchy. This automatically makes the algorithm efficient on all levels of the hierarchy. The experimental work done with these types of algorithms remain sparse, however.In this thesis, we present a thorough theoretical analysis and explanation of optimal cache-oblivious algorithms. We then do a performance investigation, comparing cache-oblivious algorithms with traditional RAM-model algorithms. In the last, on the basis of thorough research, we present an optimal sub-linear working space cache-oblivious sorting algorithm.We conclude that cache-oblivious algorithms do outperform traditional RAM-model algorithms when working on large data sets. |
