Cache-sensitive optimization of immutable graph traversals (CS745 Project Proposal)

Abstract

This project tries to improve the cache-locality of programs which frequently traverse an immutable graph data structure. In our approach, the compiler generates code to fold the inherently noncontiguous representation of vertices in a mutable graph into a more contiguous representation possible only for immutable graphs. In addition to this internal reorganization, the generated code will also try to change the external organization of vertices that are likely to be accessed sequentially in order to increase the likelihood of them residing a single cache line. Our implementation plans include laying the infrastructure, and testing a simple clustering algorithm.

Topics

    4 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)