Cache-Oblivious Traversals of an Array’s Pairs

Cache-obliviousness is a concept first introduced by Frigo et al. in [1]. We follow their model and develop a cache-oblivious algorithm for traversing all pairs of elements in a one-dimensional array and prove that it is optimally cache-efficient. Though the the traversal is recursive in nature, we demonstrate how to implement the algorithm nonrecursively, and we give experimental results.