In high-performance and embedded computing, the "memory wall" remains a fundamental bottleneck: processors execute instructions at blistering speeds, but fetching data from main memory is orders of magnitude slower. To mitigate this, hardware relies on fast, local cache hierarchies. Compilers are tasked with orchestrating code so that data resides in these caches exactly when the processor needs it.
Traditionally, compilers approach this problem through a narrow keyhole. They optimize data locality within isolated units—focusing on a single loop nest (intra-nest optimization) or a single function (intra-procedural optimization). However, real-world applications process large datasets sequentially across multiple loops, statements, and functions. When a compiler optimizes each unit in isolation, it misses the "big picture." Data loaded into the cache by one loop is frequently evicted before a subsequent loop can reuse it, leading to redundant memory transfers and wasted energy.
To overcome this, a major research direction focuses on breaking down these structural boundaries. By analyzing and reordering programs holistically, compilers can exploit data reuse across loops, statements, procedures, and even hardware cores.
Reorienting Execution Around Data Spaces
The fundamental limitation of traditional loop optimization is its adherence to control-flow order. If a program dictates executing Loop A entirely, followed by Loop B, a traditional compiler will optimize Loop A's internal iterations, then Loop B's internal iterations. If both loops operate on the same large array, the data loaded by Loop A will likely be long gone by the time Loop B begins.
To solve this, compilers can pivot from an iteration-centric view to a data-centric view. In Data Space Oriented Tiling, Mahmut Kandemir et al. introduce the concept of inter-nest iteration interleaving. Instead of executing loops sequentially, the compiler partitions the underlying data into tiles. It then interleaves the iterations of multiple distinct loop nests so that all operations from both loops requiring a specific data tile are executed consecutively. By grouping operations around data residency rather than loop boundaries, the system ensures a block of data is fully utilized before it is evicted.
Traditional Control-Centric Execution:
[Loop 1: Process All Data] ---> Eviction ---> [Loop 2: Process All Data]
Data-Centric Interleaved Execution:
[Tile 1: Run Loop 1 & Loop 2] ---> [Tile 2: Run Loop 1 & Loop 2]
Even simpler structural adjustments can yield significant benefits. In Optimizing inter-nest data locality, Mahmut T. Kandemir et al. demonstrate that reversing the data traversal direction of a subsequent loop relative to a preceding one can capture "hot" data. If Loop A finishes by processing the end of an array, Loop B can begin by processing that same end section backward, maximizing cache hits for data that is already resident.
For finer-grained sequences of operations, Orhan Kislal et al. utilize a sliding window approach in Data movement aware computation partitioning. By analyzing multiple consecutive program statements simultaneously, the compiler schedules related subcomputations to share a local L1 cache, preventing redundant data fetches across sequential operations.
Dissolving Function and Layout Boundaries
Data reuse is not merely interrupted by loop boundaries; it is frequently severed by function calls and fragmented memory layouts. When arrays are passed between functions, independent optimization of each function leads to suboptimal memory layouts and missed performance opportunities.
To bridge this gap, Wei Zhang et al. developed an interprocedural optimization framework in Interprocedural optimizations for improving data cache performance of array-intensive embedded applications. By analyzing array access patterns across function boundaries, the framework enables global loop and data transformations that are impossible when viewing functions as black boxes.
Furthermore, data locality can be improved by restructuring how data is physically stored in memory. Even if loops are perfectly aligned, accessing multiple independent arrays simultaneously can cause "inter-variable conflict misses," where elements from different arrays map to the same cache lines and repeatedly evict each other.
In Array Unification: A Locality Optimization Technique, Mahmut Kandemir et al. introduce a technique that automatically interleaves independent arrays into a single data space. By physically placing data elements that are accessed together into adjacent memory locations, they guarantee high spatial locality. This strategy works even in irregular codes where traditional loop transformations fail. This is complemented by work from Mahmut T. Kandemir et al. in A compiler technique for improving whole-program locality, which unifies loop and data layout transformations globally across the entire codebase.
Scaling to Multi-Core and Distributed Architectures
As we move from single-core processors to multi-core and distributed systems, managing cross-boundary data reuse becomes critical for minimizing inter-processor communication—the costliest operation in parallel computing.
In Multi-Processor Systems-on-Chip (MPSoCs), optimizing individual loops in isolation can cause processors to access completely different data elements in consecutive loops. Feihui Li et al. address this in Locality-conscious workload assignment for array-based computations in MPSOC architectures by considering all loop nests simultaneously. This global view ensures that workload assignments across computational phases maintain data continuity for each processor.
On multicore architectures with shared caches, compilers must also account for "inter-core data reuse"—instances where one core can reuse data recently fetched by another. As Yuanrui Zhang et al. demonstrate in Studying inter-core data reuse in multicores, cross-core reuse operates over much longer distances than intra-core reuse. Capturing it requires specialized scheduling strategies that balance both local and shared cache locality.
For distributed-memory systems, Mahmut T. Kandemir et al. propose a global parallelization scheme in Slicing based code parallelization for minimizing inter-processor communication. Instead of optimizing forward, their approach uses backward "iteration space slicing." It begins by partitioning the final output arrays and works backward through the program's entire loop pipeline, aligning data and computation distributions globally to eliminate communication bottlenecks.
Formalizing and Modernizing Data-Centric Execution
To fully realize the benefits of cross-boundary optimization, modern frameworks are moving away from traditional control-flow intermediate representations entirely, opting instead for representations that treat data movement as a first-class citizen.
A prominent example is the DaCe framework developed by Alexandros Nikolaos Ziogas et al. in Productivity, Portability, Performance: Data-Centric Python. By translating high-level Python and NumPy code into a Stateful DataFlow Multigraph (SDFG), the framework gains a global view of data dependencies. This representation exposes hidden data reuse opportunities across distinct operations, allowing the compiler to eliminate redundant memory allocations, minimize data copies, and fuse operations seamlessly across the entire program graph.
This holistic perspective has also enabled researchers to establish rigorous mathematical foundations for data reuse. In Pebbles, Graphs, and a Pinch of Combinatorics: Towards Tight I/O Lower Bounds for Statically Analyzable Programs, Grzegorz Kwaśniewski et al. introduced the SOAP (Simple Overlap Access Programs) framework. By modeling data flow across multiple statements as parametric graphs, they proved that accounting for inter-statement data residency drastically lowers the theoretical I/O bounds of programs.
Ultimately, this research direction demonstrates that the key to overcoming the memory wall is not just optimizing loops or functions faster, but dissolving the structural boundaries between them to let data flow efficiently through the hardware.
Key Foundational Work
Optimizing inter-nest data locality (2002) — contributed 4 concept elements to this direction.
Data Space Oriented Tiling (2002) — contributed 3 concept elements to this direction.
Array Unification: A Locality Optimization Technique (2001) — contributed 1 concept elements to this direction.