Demystifying Map Space Exploration for NPUs

Sheng-Chun Kao, Angshuman Parashar, Po-An Tsai, Tushar Krishna

Abstract

Efficient execution of Deep Neural Networks (DNNs) on specialized hardware accelerators (NPUs) depends heavily on Map Space Exploration (MSE)—the process of determining optimal data tiling, loop ordering, and parallelization strategies. Despite the proliferation of various "mappers," the research community has lacked a systematic comparison of their efficacy and underlying principles. This paper provides a comprehensive evaluation of search techniques for MSE and introduces two novel enhancements: warm-start and sparsity-aware mapping. Our findings demonstrate that warm-starting can accelerate search convergence by up to 7.3x, while sparsity-aware techniques ensure robust performance across varying data densities, achieving 99.7% of the performance of custom-tuned mappings.

Introduction

Modern NPUs offer significant flexibility in how workloads are executed. Compilers must navigate a massive "map space" to decide how to partition data into local SRAM (tiling), the sequence of operations (loop order), and the distribution of tasks across processing elements (parallelization). For a standard layer in a network like ResNet-50, the number of valid mappings can reach an astronomical $O(10^{24})$.

Finding the optimal configuration within this space is critical for performance and energy efficiency. However, existing mappers—ranging from simple random heuristics to complex reinforcement learning agents—have largely been evaluated in isolation. Furthermore, most existing tools assume dense data, failing to account for the increasing prevalence of sparsity in pruned or compressed models. This work seeks to demystify the MSE landscape and provide actionable strategies for more efficient hardware utilization.

A Taxonomy of Mapping Strategies

To evaluate the state of the art, we categorize existing mappers into three primary classes:

  1. Random-based Mappers: These utilize heuristic pruning to narrow the search space before performing random sampling. An example is the default mapper in the Timeloop framework.
  2. Feedback-based Mappers: These employ iterative optimization algorithms, such as Genetic Algorithms (GA) or Reinforcement Learning, to refine solutions based on performance feedback from a hardware model (e.g., Gamma).
  3. Gradient-based Mappers: These involve training a differentiable "surrogate model" of the hardware. Optimization is then performed via gradient descent to find the best mapping (e.g., Mind Mappings).

Proposed Enhancements

Beyond evaluating existing methods, we introduce two techniques to address common bottlenecks in MSE:

  • Warm-start: Rather than initiating a search from scratch for every new layer, we utilize a "replay buffer" of successful mappings from previous tasks. By using an editing distance metric, the mapper identifies a previously optimized workload similar to the current one and scales its mapping to fit the new dimensions. This leverages the inherent repetitiveness of DNN architectures.
  • Sparsity-aware Search: Standard mappers often optimize for a single density level (usually 100% dense). However, a mapping optimized for dense data often performs poorly as sparsity increases. Our approach scores mappings based on a weighted sum of performance across a spectrum of sparsities (from 10% to 100% density), ensuring the resulting configuration is robust to runtime data variations.

Experimental Methodology

We evaluated these strategies using Timeloop and Sparseloop, industry-standard analytical cost models for NPUs. The study focused on NVDLA-like accelerator architectures across a diverse set of workloads:

  • Computer Vision: ResNet-18/50, VGG16, Mnasnet, MobileNetV2, and Inception.
  • Natural Language Processing: BERT-large, specifically focusing on Attention, KQV, and Fully-Connected layers.

Key Insights and Results

The Dominance of Tile Size

Our sensitivity analysis reveals that tile size—the determination of how much data is buffered in local memory—is the most critical factor in the map space. Changes in tile size have a significantly higher impact on energy and latency than variations in loop order or parallelization strategies. This suggests that mappers should prioritize the exploration of tiling factors.

The Brittleness of Gradient-based Models

While gradient-based mappers are computationally fast during the inference phase, they are remarkably brittle. If the underlying hardware configuration is modified even slightly, the surrogate model loses accuracy and requires millions of new data points for retraining. In contrast, feedback-based mappers (like GA) proved to be the most adaptable and sample-efficient for global optimization across different hardware targets.

Overcoming the "Sparsity Wall"

We confirmed that mappings optimized for dense layers rarely translate well to sparse execution. However, our sparsity-aware approach successfully identified fixed mappings that achieved 99.7% of the performance of mappings that were individually custom-tuned for every specific density level. This provides a path toward "set-and-forget" configurations that remain efficient throughout a model's lifecycle.

Search Acceleration via Warm-starting

By implementing the warm-start technique, we observed a significant reduction in the time required to find optimal mappings. Mappers reached the optimal performance point 3.3x to 7.3x faster than those starting from a cold state. This is particularly valuable for compilers that must optimize large models with hundreds of layers under tight time constraints.

Conclusion and Future Work

This study clarifies the strengths and weaknesses of current MSE techniques. We demonstrate that while the search space is vast, focusing on tile size and leveraging similarity between layers can drastically improve search efficiency. Furthermore, we show that sparsity must be integrated into the search process rather than treated as an afterthought.

Future research will focus on extending these insights to operator fusion, where multiple layers are optimized simultaneously to minimize off-chip memory traffic. Additionally, we aim to apply these "demystified" mapping principles to irregular workloads such as Graph Neural Networks (GNNs) and Point Cloud processing, where the map space is even more complex.

Summary updated

Abstract

Map Space Exploration is the problem of finding optimized mappings of a Deep Neural Network (DNN) model on an accelerator. It is known to be extremely computationally expensive, and there has been active research looking at both heuristics and learning-based methods to make the problem computationally tractable. However, while there are dozens of mappers out there (all empirically claiming to find better mappings than others), the research community lacks systematic insights on how different search techniques navigate the map-space and how different mapping axes contribute to the accelerator’s performance and efficiency. Such insights are crucial to developing mapping frameworks for emerging DNNs that are increasingly irregular (due to neural architecture search) and sparse, making the corresponding map spaces much more complex. In this work, rather than proposing yet another mapper, we do a first-of-its-kind apples-to-apples comparison of search techniques leveraged by different mappers. Next, we extract the learnings from our study and propose two new techniques that can augment existing mappers — warm-start and sparsity-aware — that demonstrate speedups, scalability, and robustness across diverse DNN models1.1.Code avaliable at https://github.com/maestro-project/gamma-timeloop.
BibTeX
@inproceedings{kao2022demystifying,
  author = {Sheng-Chun Kao and Angshuman Parashar and Po-An Tsai and Tushar Krishna},
  title = {{Demystifying Map Space Exploration for NPUs}},
  booktitle = {IISWC},
  year = {2022},
  url = {https://openreview.net/forum?id=iQDuXO91W4},
}
Figure