Department of Computer Science, UNC Chapel Hill

Introduction

A major computing trend over the last few decades has been the widening gap between processor speed and main memory speed. As a result, system architectures increasingly use caches and memory hierarchies to avoid memory latency. The access times of different levels of a memory hierarchy typically vary by orders of magnitude. Therefore, it is desirable to have cache-coherent layout to reduce the access times. We have designed a novel algorithm to compute cache-oblivious layouts of data elements to minimize the access time of applications on the layouts. Our algorithm only requires an input graph that represents runtime access patterns of an application on the data elements. Our algorithm probabilistically measures the expected number of cache misses of a layout and computes a cache-oblivious layout that minimizes the expected number of cache misses. Moreover, the cache-oblivious layout is not optimized for any particular cache, block sizes, or replacement policies; it is constructed to work well under any cache parameters. Please refer to the documentation for details regarding the API and the contents of the distribution.

OpenCCL is an open source code to compute cache-oblivious layouts of graphs and polygonal meshes to improve performances of a wide variety of applications including geometric processing and visualization applications.

• Generality: OpenCCL can be used to compute cache-oblivious layouts of any graphs and any polygonal meshes including hierarchies and multi-resolution meshes.
• Cache-Obliviousness: OpenCCL requires no knowledge of cache parameters or block sizes of the memory hierarchy involved in the computation.
• Performance: Applications can experience significant improvements on performances by using cache-oblivious layouts of OpenCCL. For example, we observed 2 - 20 speedup on performances on isocontour extraction, view-dependent rendering, and collision detection. However, there is no guarantee to improve performances of any applications.
• Usability: Cache-oblivious layouts computed by OpenCCL can improve performances of applications without modifying any algorithms and runtime applications.