DAEDALUS: Improving Data Reference Locality

Objective

The Daedalus project has two main goals:
  • To provide tools for quantifying, analyzing, and exploiting a program's data reference locality.
  • To develop an optimization framework that automatically improves a program's data reference locality.

    Description

    With the growing processor-memory performance gap, understanding and optimizing a program's memory system performance is becoming increasingly important. While optimization technology for improving the memory system behavior of program instructions is fairly mature, similar techniques for optimizing a program's data accesses are still at an early stage. We believe the primary reason for this imbalance is the lack of a suitable representation of a program's dynamic data reference behavior, and effective abstractions for analyzing data accesses. Cache-level layout optimizations typically require accurate temporal information about data reference sequences, which static analysis cannot provide. Unfortunately, profiling all program loads and stores to obtain this information generates gigabytes of trace, making analyses impractical. Unlike control flow graphs and program paths, which are a convenient and compact abstraction of a program's control flow, no corresponding analogue exists for a program's data accesses.

    We address this issue by proposing data reference representations--Whole Program Streams and Hot Program Streams--and an abstraction for temporal data reference sequences--hot data streams. These representations 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. We show that these representations and our data abstraction are useful for quantifying as well as exploiting data reference locality. We applied our techniques 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.

    Publications

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

    Shai Rubin, Rastislav Bodik, and Trishul M. Chilimbi, "A Profile-Feedback Framework for Data Layout Optimization"
    Submitted for publication

    Collaborators
  • Prof. Ras Bodik
  • Shai Rubin (summer intern '00)