DAEDALUS: Improving Data Locality and Scalability

Objective  Description  Publications  Presentations  Collaborators


The Daedalus project has two main goals:
  • To produce tools for quantifying, analyzing, and improving a program's data reference locality and scalability.
  • To build an optimization framework for automatically improving a program's data reference locality and scalability.


    With the growing processor-memory performance gap, understanding and optimizing a program's reference locality, and consequently, its cache performance, is becoming increasingly important. Unfortunately, current reference locality optimizations rely on heuristics and are fairly ad-hoc. In addition, while optimization technology for improving instruction cache performance is fairly mature (though heuristic-based), data cache optimizations are still at an early stage. We believe the primary reason for this imbalance is the lack of a suitable representation of a programs dynamic data reference behavior and a quantitative basis for understanding this behavior.

    We address these issues by proposing a quantitative basis for understanding and optimizing reference locality, and by describing efficient data reference representations and an exploitable locality abstraction that support this framework. Our data reference representations (Whole Program Streams and Stream Flow Graphs) are compact--two to four orders of magnitude smaller than the programs data reference trace--and permit efficient analysis--on the order of seconds to a few minutes--even for complex applications. These representations can be used to efficiently compute our exploitable locality abstraction (hot data streams). We demonstrate that these representations and our hot data stream abstraction are useful for quantifying and exploiting data reference locality. We applied our framework to several SPECint 2000 benchmarks, a graphics program, and a commercial Microsoft database application. The results suggest significant opportunity for hot data stream-based locality optimizations.

    Unfortunately, traditional optimization frameworks rely heavily on static analysis and are ill suited to such memory system optimizations, which primarily use program profiles. Consequently, current data layout techniques use profile information in a fairly ad hoc manner to guide data placement decisions.

    To address this, we propose a data layout optimization framework that replaces the current profile-directed approach with an iterative profile-feedback approach, which prototypes and evaluates a transformation before it commits to it. Our framework unifies and strengthens current optimizations and also enables a new style of optimization. The salient feature of our framework is that it relies neither on static analysis, nor uses the profile for merely assisting in tuning a single, hard-coded transformation, as is common in traditional profile-directed optimizations. Instead, the framework uses run-time information to explore a broad space of possible optimizations, synthesizing a good one.


    Trishul Chilimbi and Ran Shaham, "Cache-conscious Coallocation of Hot Data Streams"
    to appear in Programming Languages Design and Implementation '06 (PLDI), June 2006.

    Wenke-Chen, Sanjay Bhansali, Trishul Chilimbi, Xiaofeng Gao, and Weihaw Chuang, "Profile-guided Proactive Garbage Collection for Locality Optimization", to appear in Programming Languages Design and Implementation '06 (PLDI), June 2006.

    Trishul M. Chilimbi, and Martin Hirzel "Dynamic Hot Data Stream Prefetching for General-Purpose Programs"
    Appears in Programming Languages Design and Implementation '02 (PLDI) , June 2002.

    Shai Rubin, Rastislav Bodik, and Trishul M. Chilimbi, " An Efficient Profile-Analysis Framework for Data-Layout Optimizations",
    Appears in Principles of Programming Languages 2002 (POPL), Jan. 20 02.

    Martin Hirzel and Trishul M. Chilimbi " Bursty Tracing: A Framework for Low-Overhead Temporal Profiling"
    Appears in 4th ACM Workshop on Feedback-Directed and Dynamic Optimization '01 (FDDO) , Dec. 2001.

    Trishul M. Chilimbi "Efficient Representations and Abstractions for Quantifying and Exploiting Data Reference Locality"
    Programming Languages Design and Implementation '01 (PLDI), 2001

    Trishul M. Chilimbi, "On the Stability of Temporal Data Reference Profiles"
    International Conference on Parallel Arhitectures and Compilation Techniques '01 (PACT), 2001

    Trishul M. Chilimbi, Mark D. Hill, and James R. Larus, "Making Pointer-Based Data Structures Cache Conscious" (Expanded version),
    IEEE Computer , December 2000.


    Efficient Representations and Abstractions for Quantifying and Exploiting Data Reference Locality ,
    PLDI 2001


  • Prof. Ras Bodik
  • Shai Rubin (summer intern '00)
  • Martin Hirzel (summer intern '01)
  • Ran Shaham (summer intern '01)