Global Data Layout Optimization via Graph Search

15 concepts12 papers1 proposal

When compiling or executing high-performance computational pipelines—such as deep neural networks (DNNs) or distributed array operations—hardware accelerators require specific data layouts to maximize throughput. For instance, a GPU kernel might run fastest when data is structured as a Structure of Arrays (SoA), while a CPU or DSP might prefer an Array of Structures (AoS), specific tensor dimension orderings, or custom tiling configurations.

However, optimizing each operation or kernel in isolation creates a hidden performance trap. If an operator selects an execution primitive solely because it is the fastest local choice, it dictates a specific output data layout. If the subsequent operator requires a different layout to achieve its own peak speed, the system must inject a data layout transformation (such as a tensor transpose or memory reshuffling) between them.

These data movement overheads, often called conversion penalties, can easily dwarf the local performance gains of the individual kernels. To achieve true end-to-end efficiency, modern systems must shift from local, operator-isolated decisions to a holistic, network-wide strategy: Global Data Layout Optimization.

The Local Optimization Trap

To understand why local optimization fails, consider a simple two-layer execution pipeline. As de Prado et al. demonstrate in Learning to infer: RL-based search for DNN primitive selection on Heterogeneous Embedded Systems, selecting the fastest standalone implementation for individual neural network layers frequently degrades global performance. The latency penalties incurred by transforming data formats between layers can outweigh the speedups of the individual primitives.

This tension is a fundamental characteristic of modern hardware. As Ivanov et al. argue in Data Movement Is All You Need: A Case Study on Optimizing Transformers, the primary bottleneck in workloads like Transformers is often data movement rather than raw computation. When memory layouts are optimized in isolation, the cost of transposing data between steps outweighs local gains.

Furthermore, local changes can have cascading effects on hardware state. Sereda et al. show in KForge: A Multi-Agent System for Cross-Platform Kernel Synthesis that a kernel optimized in isolation might execute faster on its own but inadvertently leave the GPU in a state that degrades resource occupancy and performance for subsequent operations.

Modeling Layout Selection as a Shortest-Path Problem

The core insight that makes global layout optimization tractable is representing the entire computation as a graph. By mapping the combinatorial explosion of layout choices to a Directed Acyclic Graph (DAG), the problem of finding the fastest execution plan becomes mathematically equivalent to finding the shortest path through the graph.

In this formulation:

  • Nodes represent a specific operation or code section executing with a particular data layout configuration.
  • Edges connect sequential operations, and their weights represent the transition cost—the precise time or memory overhead required to remap data from the source layout to the destination layout.
[Layer 1: Layout A] --(No cost)---> [Layer 2: Layout A]
       \                                   ^
        \--(Layout Transpose Cost)--------/

This elegant framework was pioneered by Majeti et al. in ADHA: Automatic Data layout framework for Heterogeneous Architectures. By modeling layout transitions as edges in a DAG, the authors successfully navigated the exponential search space of potential configurations, automatically balancing local kernel performance against global data remapping costs. The authors extended this graph-based modeling in Automatic data layout generation and kernel mapping for CPU+GPU architectures to automate layout generation across heterogeneous architectures.

Similarly, Ivanov et al. model an entire Transformer network as a graph of possible configurations where edges represent the cost of data transposes. A shortest-path algorithm then determines the exact sequence of layouts that minimizes total execution time across the complete sequence of operations.

Algorithmic Strategies for Global Optimums

Depending on the structure of the computation and the hardware constraints, researchers deploy different algorithmic tools to solve these global graph formulations.

Dynamic Programming and Heuristics

For sequential or tree-structured execution flows, dynamic programming offers an exact solution in polynomial time. In Optimizing CNN Model Inference on CPUs, Liu et al. introduce a two-stage search process. It optimizes individual operation parameters locally while using dynamic programming or heuristic solvers to select a globally optimal sequence of data layouts, ensuring that local speedups are not negated by adjacent layer requirements.

This approach is powerful enough to solve foundational memory-partitioning problems. For example, Ganian et al. demonstrate in Polynomial-Time Construction of Optimal MPI Derived Datatype Trees that partitioning a memory layout into structured sub-layouts can be solved via a bottom-up dynamic programming approach paired with shortest-path graph queries, disproving long-standing assumptions that such hierarchical descriptions are NP-hard.

Integer Linear Programming (ILP)

When optimization must respect a strict, network-wide resource constraint—such as a fixed hardware memory capacity—the problem becomes more complex. In Accelerating Deep Learning Frameworks with Micro-Batches, Oyama et al. treat GPU workspace memory as a single, globally shared pool. By formulating the inter-dependencies of all layers and a global memory limit as a 0-1 integer linear programming problem, their system optimizes micro-batch sizes and algorithm selection globally, outperforming isolated per-layer allocations.

Graph-Based Co-Optimization

For specialized hardware like mobile Digital Signal Processors (DSPs), layout selection must be tightly coupled with low-level instruction scheduling. Niu 0002 et al. address this in GCD2: A Globally Optimizing Compiler for Mapping DNNs to Mobile DSPs. By formulating instruction and data layout selection as a global optimization problem over a computational graph, they minimize the combined cost of computation and data transformation, achieving execution efficiency close to an exhaustive search within practical compilation times.

System-Model Co-Design and Topology Awareness

Global layout optimization is not restricted to single-device execution; it scales up to distributed systems and down to ultra-low-power microcontrollers.

In distributed environments, representing computations as holistic expression graphs allows frameworks to optimize data partitioning across multiple machines. As Huang et al. show in Spartan: A Distributed Array Framework with Smart Tiling, a unified view of the entire computation graph enables an optimizer to identify optimal n-dimensional array tiling strategies, minimizing communication costs by accounting for complex interactions like array duplication across multiple expressions.

On highly resource-constrained Internet of Things (IoT) devices, global optimization becomes a necessity for viability. de Prado et al. demonstrate in Automated Design Space Exploration for Optimized Deployment of DNN on Arm Cortex-A CPUs that modeling conversion penalties between layers prevents local speedups from being negated by data reshuffling on low-power mobile CPUs.

Taking this concept to its extreme, Lin et al. introduce a system-model co-design framework in MCUNet: Tiny Deep Learning on IoT Devices. Instead of allocating memory layer-by-layer, their framework features a global memory scheduler that analyzes the entire network topology. This global view allows the system to aggressively reuse memory buffers across the execution graph, shrinking the peak memory footprint enough to run complex deep learning models on microcontrollers with only kilobytes of memory.

Key Foundational Work

ADHA: Automatic Data layout framework for Heterogeneous Architectures (2014) — contributed 1 concept elements to this direction.
Spartan: A Distributed Array Framework with Smart Tiling (2015) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_global_memory_layout_optimization_c53a26bc,
  title = {global memory layout optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-memory-layout-optimization/rdr_c53a26bc0928490f881711bad1f4ee77},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_global_memory_layout_optimization_c53a26bc_v1,
  title = {global memory layout optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-memory-layout-optimization/rdr_c53a26bc0928490f881711bad1f4ee77/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake