ACM SIGPLAN Notices · 2002 · 47 citations · 18 references
ComputingComputer EngineeringComputer ScienceCompilersData StructuresDesign OptimizationData Locality OptimizationLayout EvaluationLayout OptimizationMemory HierarchyMemory Hierarchy DesignMemory Hierarchy OptimizationData Layout OptimizationFeedbackLayout ParameterizationMemory Layout OptimizationMemory LocalityMemory Locality OptimizationProfile-guided OptimizationSpatial Locality
Data-layout optimizations rearrange fields within objects, objects within objects, and objects within the heap, with the goal of increasing spatial locality. While the importance of data-layout optimizations has been growing, their deployment has been limited, partly because they lack a unifying framework. We propose a parameterizable framework for data-layout optimization of general-purpose applications. Acknowledging that finding an optimal layout is not only NP-hard, but also poorly approximable, our framework finds a good layout by searching the space of possible layouts, with the help of profile feedback. The search process iteratively prototypes candidate data layouts, evaluating them by "simulating" the program on a representative trace of memory accesses. To make the search process practical, we develop space-reduction heuristics and optimize the expensive simulation via memoization. Equipped with this iterative approach, we can synthesize layouts that outperform existing non-iterative heuristics, tune application-specific memory allocators, as well as compose multiple data-layout optimizations.
18
A data locality optimizing algorithm
Michael E. Wolf, Monica S. Lam · 1991 · 1.3K citations · Full text
Parametric shape analysis via 3-valued logic
Mooly Sagiv, Thomas Reps, Reinhard Wilhelm · 1999 · 338 citations
Cache-conscious structure layout
Trishul Chilimbi, James R. Larus · 1999 · 337 citations · Full text
Compiler optimizations for improving data locality
Steve Carr, Kathryn S. McKinley, Chau‐Wen Tseng · 1994 · 294 citations · Full text