Compiler Optimization of Data Storage

Gupta, 1991

Category: Compilers

Overall Rating

2.3/5 (16/35 pts)

This thesis presents a compelling argument for compiler-driven data layout optimization based on formal analysis of access patterns and proves NP-completeness for optimal solutions.
However, its specific technical contributions, including the proposed models and algorithms, are largely tied to the memory hierarchy assumptions and computational contexts of 1991.
While the core idea of data-aware compilation remains relevant, modern hardware complexities (multi-level caches, NUMA) and sophisticated software techniques (loop transformations, specialized libraries, PGO) have evolved significantly, often addressing memory locality challenges through different, more effective paradigms that render the paper's specific approach less directly actionable for impactful modern research.

This thesis explores the optimization of data layout in memory based on program access patterns, arguing for it as a compiler responsibility rather than a user one.
It also uniquely suggests that data distribution criteria can motivate new code optimizations ('Constraint Splitting', 'Dynamic Restructuring') rather than just being optimized after code transformations.
This specific approach and formal analysis have high latent novelty potential for modern research, particularly in optimizing memory access for large-scale Machine Learning workloads.
The idea that data distribution constraints could drive novel tensor computation graph transformations (akin to 'Constraint Splitting' or 'Dynamic Restructuring' for tensors) is particularly powerful and underexplored in ML compilers.

The paper's core assumptions about the memory hierarchy and dominant performance bottlenecks are significantly outdated.
The simplistic hit/miss model based on contiguous access patterns captured by a reference string or program graph does not adequately reflect the costs and behaviors of these complex hierarchies...
This paper likely fell into obscurity due to a combination of inherent complexity, limited practicality for general application, and the emergence of alternative, more impactful techniques.
The techniques are primarily static. They struggle with dynamic memory allocation, pointer-based access, and access patterns that depend heavily on runtime inputs or complex data structures that cannot be fully analyzed at compile time.

Watch