betaFeedback

WorksComputer Science

IMPACT: Constraint-Aware Search for Imperfectly Factorized Accelerator Mappings

Abstract

The efficiency of Deep Neural Network (DNN) accelerators depends on how each tensor operation is mapped onto the hardware. A mapping specifies how the computation is tiled across the memory hierarchy, ordered, and parallelized across the processing elements. These choices form a combinatorially large search space, where efficient mappings are hard to find. Most violate hardware constraints, and most remaining mappings underutilize the hardware. Existing mappers either search only part of this space to keep the search tractable, excluding the most efficient mappings, or sample the full space randomly, so most mappings they evaluate are infeasible. We present IMPACT, a mapper that searches the full space. IMPACT pairs a genetic algorithm with a constraint-aware repair operator that converts each infeasible mapping into a feasible one instead of discarding it. On a flexible accelerator, IMPACT outperforms state-of-the-art mappers in EDP, latency, and energy on every DeepBench workload. On a compute-in-memory (CIM) accelerator, whose constraints leave few mappings feasible, it reduces EDP by 66%, latency by 47%, and energy by 18% over the strongest prior mapper across five networks, and rivals hand-crafted expert mappings. Across flexible and highly constrained accelerators, IMPACT finds efficient mappings automatically. IMPACT will be released as open source.

Introduction

DNN workloads are dominated by tensor operations, such as convolutions and matrix multiplications, that demand extreme compute throughput and memory bandwidth [21, 24]. DNN accelerators meet these demands with arrays of processing elements (PEs) that compute in parallel, and a hierarchy of memory buffers that keep data close to the PEs to maximize reuse [3, 13]. These buffers, however, hold only a small fraction of data at a time, so the computation must be split into tiles that fit each memory level and distributed across the PEs. Executing an operation therefore requires assigning the computation to the hardware: how large a tile each level holds for each dimension of the operation (tiling factors), how many PEs process each dimension in parallel (spatial unrolling), the order each level steps through its tiles (loop order), and which tensors each level retains (keep/by-pass). This assignment is called a mapping. Once the hardware is fixed, the mapping determines how effectively its resources are used. Two mappings of the same operation can produce very different memory traffic and PE utilization, and thus may differ by orders of magnitude in latency and energy [10, 20].

Selecting the best mapping is a combinatorial optimization problem. Because every choice is made per dimension and memory level, the number of possible mappings grows exponentially with both; for a single convolution on a realistic accelerator, the search space contains at least 102010^{20} candidates [20]. Most of these candidates are infeasible, because every choice must simultaneously satisfy every hardware constraint, such as buffer capacities and PE array dimensions. The feasible mappings, therefore, are only a small part of this larger space, yet too large to enumerate, and they are not equally efficient. A spatial unrolling that occupies only part of the PE array leaves the remaining PEs idle, and tiling factors that capture little reuse force the same data to be re-fetched, inflating latency and energy [4, 11]. Efficient mappings are therefore a small fraction of the already small feasible subspace. As a result, an effective mapper must satisfy three requirements. It must search the entire space, isolate the feasible subspace, and identify the most efficient mappings within it.

Existing mappers meet these requirements only in part. Timeloop [20] and ZigZag [18] restrict the space to tiling factors and spatial unrollings that perfectly divide the tensor dimensions, and randomly sample the reduced search space. SALSA [14] restricts it further, fixing the spatial unrolling as input and annealing over loop orderings and tiling factors. This reduced space, however, excludes the most efficient mappings: when the tensor dimensions and the PE array

This work is licensed under a Creative Commons Attribution 4.0 International License. ASPDAC ’27, Tokyo, Japan

© 2027 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-2923-2/2027/01 https://doi.org/10.1145/3848044.3848237 are misaligned, the mappings that fill the array are exactly those excluded, and they remain out of reach however long the reduced space is searched. GAMMA [15] searches the same reduced space with a genetic algorithm, but its operators recombine mappings without regard for hardware constraints, so it spends most evaluations on infeasible offspring. Ruby [10] expands the space, extending Timeloop’s model with tiles and spatial unrollings that need not divide the tensor dimensions, recovering utilization the other mappers sacrifice. However, Ruby samples the expanded space randomly, with no mechanism to only search within the feasible subspace, so nearly all its evaluations are spent on mappings that are infeasible. In short, the most efficient mappings are either excluded to keep the search tractable, or admitted into a space that no existing search can navigate. No existing mapper searches the entire space, keeps its evaluations feasible, and finds the most efficient mappings within it.

To address this, we propose IMPACT, a mapping framework that searches the full mapping space while keeping every candidate feasible, through a constraint-aware repair operator that steers infeasible mappings toward feasible ones. Our key contributions are:

  • Higher mapping quality: IMPACT’s genetic search finds more efficient mappings than prior automated mappers. On Eyeriss [3], a flexible accelerator, it outperforms both Timeloop and Ruby on every DeepBench [2] workload and efficiency metric.

  • Search under tight constraints: IMPACT’s repair operator keeps the search inside the feasible region even where few mappings are valid. On a CIM-based accelerator, it lowers EDP by 66%, latency by 47%, and energy by 18% compared to Timeloop across five networks, and rivals expert hand-crafted mappings.

  • Efficient search: By steering infeasible candidates to nearby feasible mappings instead of discarding them, IMPACT spends its budget on mappings that can execute. On Eyeriss, 83% of attempts yield a feasible mapping, against Timeloop’s 10% and Ruby’s 5%.

The remainder of this paper is organized as follows. Section 2 introduces the mapspace and feasibility constraints, and Section 3 formulates the constrained search problem. Section 4 presents IMPACT, and Section 5 details its repair operator. Section 6 evaluates IMPACT against state-of-the-art mappers. Sections 7 and 8 discuss implications and conclude.

Background

Mappings. Figure 1b illustrates such a mapping, using a simpler 1D convolution with dimensions RR and PP on a DRAM–Global Buffer (GLB)–PE hierarchy, and marks the four decisions a mapping specifies. For every dimension and every memory level, a tiling factor (1) sets the size of the tile that level holds. Within each level, the loop order (2) fixes the sequence in which its tiles are traversed. At the PE level, the spatial unrolling (3) selects the dimensions whose tiles execute in parallel across the array, up to its fanout. For every tensor and every level, a keep/bypass (4) decision sets whether that level buffers the tensor. The four decisions are coupled through the tiling factors. The product of a dimension’s factors across all levels must equal the dimension itself. This product constraint ties the choices of every memory level together. The set of all mappings consistent with a hardware target is the mapspace, and it grows combinatorially with the number of dimensions and memory levels [20].

Figure 1. (a) A 2D convolution as a 7-dimensional loop nest, with common layers as special cases. (b) Mapping onto a DRAM–GLB–PE hierarchy through tiling factors, loop order, spatial unrolling, and keep/bypass. (c) Perfect versus imperfect factorization for D=14 on 6 PEs.

Imperfect factorization. Standard mappers satisfy the product constraint with tiling factors that divide each dimension exactly, a condition called perfect factorization [18, 20]. When no divisor of a dimension matches the PE count, some PEs remain idle in every iteration. Figure 1c illustrates this for a dimension D=14 on 6 PEs. The closest divisor is 2, leaving 4 of the 6 PEs idle throughout all iterations. Imperfect factorization relaxes the divisibility requirement by allowing a remainder tile [10]. The main tile is sized to fill the PE array, and only the final iteration executes a smaller remainder tile. In the same example, a tile size of 6 occupies all PEs for two iterations and 2 PEs for the last, reducing idle cycles. This improves PE utilization, but enlarges the mapspace, since tile sizes are no longer restricted to divisors of D.

Feasibility Constraints. Imperfect factorization expands the mapspace with candidates that may leave loop iterations incomplete, exceed PE fanout, or overflow memory capacity [10]. Feasibility constraints identify the subset of this expanded space that is valid and executable [20]. Workload coverage constraints require that all loop iterations complete and bound any dummy work introduced by remainder padding. Spatial fanout constraints require that the spatially unrolled tile fits within the available PE array and interconnect fanout. Storage capacity constraints require that the tensor tiles resident at each memory level fit within its physical capacity; bypassed tensors do not consume capacity at that level and are excluded from this check. A mapping that satisfies all three constraints is feasible. The feasible mapspace is the search domain for any mapping framework operating under imperfect factorization.

Workloads. Several DNN layers map directly to a loop nest: each dimension of the layer defines one loop, and each iteration of the loop body performs one multiply-accumulate (MAC)[20]. Figure 1a shows a 2D convolution expressed as a seven-dimensional loop nest. As the accompanying table shows, common layer types, such as matrix multiplications and depthwise convolutions, reduce to the same nest with some dimensions fixed to one. A single loop-nest form therefore covers all these workloads. Executing one on an accelerator requires mapping its loops to the hardware.

The Mapping Optimization Problem

Problem Formulation. A hardware target HH is defined by its memory hierarchy, PE array dimensions, buffer capacities, and fanout limits at each level. A workload WW is defined by its per-dimension loop bounds. A mapping MM is a tuple of tiling factors per dimension per level, loop order per level, spatial unrolling, and keep/bypass decisions per tensor per level. The feasible mapspace F(W,H)\mathcal{F}(W,H) is the set of all MM that simultaneously satisfy workload coverage, spatial fanout, and storage capacity constraints. The mapping problem is to solve:

M∗=argmin⁡M∈F(W,H)  C(M,W,H)M^* = \underset{M \in\mathcal{F}(W,H)}{\operatorname{argmin}}\; C(M,W,H)

where C(M,W,H)C(M,W,H) is a cost function over energy, latency, or a weighted combination of both. The decision variables are discrete, the constraints couple them non-locally across memory levels, and CC is non-convex over MM. Enumerating F(W,H)\mathcal{F}(W,H) exhaustively is therefore intractable at realistic problem scales.

Search Complexity. Finding an efficient mapping is hard for two compounding reasons. First, the feasibility constraints must hold simultaneously and couple decisions non-locally. A tiling factor at one level determines tile sizes at all levels below, jointly determining whether storage and fanout limits are met [20]. The feasible mapspace F(W,H)\mathcal{F}(W,H) therefore occupies a small, irregularly shaped fraction of the full expanded space. Second, within F(W,H)\mathcal{F}(W,H), cost is highly non-uniform. Two feasible mappings can differ by orders of magnitude in energy and latency [20]. The high-quality region is consequently a small fraction of F(W,H)\mathcal{F}(W,H). Exhaustive search is intractable and random sampling wastes most evaluations on infeasible or dominated candidates. Finding M∗M^*, or a close approximation, requires a search strategy that can navigate a large, sparsely feasible, and highly non-uniform space.

Optimization Framework

Architecture and Design Rationale

Section 3 characterized the mapping problem as a search over a large, discrete space that is sparsely feasible and non-uniform in cost. Efficient mappings are rare and scattered, and the space offers no gradient to follow, so IMPACT searches it globally with a genetic algorithm that explores broadly while concentrating on the strongest mappings it finds. A genetic algorithm alone cannot keep that search feasible. Loop orders are independent choices, so recombining them preserves feasibility. The tiling factors of a dimension and the keep/bypass flags, however, are coupled through the storage capacity constraint, and any change at one level can invalidate the factorization as a whole. IMPACT therefore repairs the factors of each mapping with a dedicated local operator before it is scored. The framework has three components:

  • A genetic algorithm evolves the global structure of each mapping across generations.

  • A constraint-aware operator expresses constraint violation as a feasibility score and uses a Metropolis-style acceptance rule [8, 19] with simulated annealing [16] to repair the tiling factors of each offspring toward a feasible configuration.

  • Timeloop evaluates each mapping analytically and returns energy, latency, and EDP [26].

Figure 2 shows the pipeline, which maps a DNN workload and a hardware specification to a Pareto-optimal set of mappings. IMPACT samples an initial population across the mapspace without enforcing validity, since the operator repairs every offspring before it is scored. Each generation applies crossover and mutation, repairs the tiling factors of the offspring, evaluates the repaired mappings with Timeloop, and selects the next generation with NSGA-II [6]. Since energy and latency trade off and no single mapping minimizes both, NSGA-II keeps a population of individuals close to the Pareto frontier. The loop repeats until the evaluation budget is spent.

Figure 2. IMPACT framework overview. A genetic algorithm and an annealed Metropolis-like repair operator map a DNN workload and accelerator specification to a Pareto-optimal mapping set, evaluated by Timeloop.

Representation and Genetic Operators

Mapping Encoding. IMPACT encodes each candidate as a chromosome that captures the complete mapping. A mapping is a loop nest, the same form that the analytical model evaluates, so each gene corresponds directly to a loop bound, a loop order, or a buffering choice in the evaluated mapping. At each memory level, each workload dimension maps to a loop whose bound sets the tile size at that level, and at the PE level, selected dimensions are unrolled spatially across the array. The chromosome carries three gene classes: loop-order genes fix the nesting order at each level, factor genes set the loop bounds at each level, and keep/bypass genes select which tensors each level buffers. Each gene also records the hardware restrictions on its decision, such as a level that cannot buffer a given tensor, so the operators never violate these restrictions during search.

Crossover. Crossover recombines and perpetuates the structural traits that high-performing mappings share. Keep/bypass and loop-order genes recombine independently under a uniform scheme, making no structural assumption about gene cross-correlation [23]. The tiling factors of a dimension are interdependent through the product constraint, so they recombine as a single unit that preserves the dimension’s factorization.

Mutation. Mutation introduces the variation that recombination alone cannot reach, keeping the search from stalling. It handles the discrete genes directly, permuting a loop order or flipping a keep/bypass flag. The legal values of a dimension’s tiling factors, however, form a thin, irregular set that a random perturbation almost always misses, so mutation cannot explore them, and the offspring it produces are almost all infeasible.

Constraint-Aware Factor Search

After crossover and mutation, most offspring carry infeasible tiling factors. IMPACT pairs its genetic search with a repair operator that moves these factors to a nearby feasible set before the mapping is scored. The feasible set, however, is fragmented into disconnected regions, so moving only through feasible factors cannot cross between them. The operator therefore uses an annealed Metropolis-style walk that steps through infeasible ground between the regions. Figure 2 depicts the walk. Starting from the offspring’s factors, each step proposes a new factor set, scores it by its distance from feasibility, and accepts or rejects it, until the walk settles on a feasible set.

Proposal Distribution. Given the factors of an offspring after crossover and mutation, each step proposes a new factor set by scaling the current factors. IMPACT draws each proposal from a log-normal centered on the current factors and rounds to the nearest positive integer, since factors are integer-valued. Because the factors combine multiplicatively and range over orders of magnitude, the proposal scales them rather than adding to them; the log-normal is symmetric in log-space, so an up- or down-scaling by the same ratio is equally likely.

Constraint Model. To compare a proposal of factors with the current factors, the operator scores each by its distance from feasibility, so it can rank two infeasible sets and move toward the feasible region. We write fl,df_{l,d} for the factor at level l∈Ll \in\mathcal{L} and dimension d∈Dd \in\mathcal{D}, and define feasibility by three constraints:

(1) Workload coverage. The factors of a dimension must cover the workload dimension FdF_d, with a bounded remainder under imperfect factorization

Fd≤∏l∈Lfl,d≤Fd,max⁡F_d \le\prod_{l \in\mathcal{L}} f_{l,d} \le F_{d,\max}

(2) Spatial fanout. The factors at a spatial level ll must fit the NlN_l hardware components

∏d∈Dfl,d≤Nl\prod_{d \in\mathcal{D}} f_{l,d} \le N_l

(3) Storage capacity. The resident tensor tiles at a memory level ll must fit within its capacity ClC_l:

Sl≤ClS_l \le C_l

Hard limits would give the search no direction [5], so the operator turns each violation into a penalty, such that an infeasible factor set carries a graded score. The feasibility score:

π(x)=exp⁡(−∑c∈Cc(x)2)\pi(\mathbf{x}) = \exp\left(-\sum_{c \in\mathcal{C}} c(\mathbf{x})^2\right)

sums the squared margins, peaking at feasibility and decaying smoothly as the total violation grows.

Acceptance. This soft score lets the operator repair factors with a Metropolis-style acceptance rule. The operator always accepts a proposal that lowers the violation, and accepts one that raises it with a probability equal to the score ratio of the proposal to the current set. Only the final set need be feasible, so the operator may accept steps through infeasible ground, crossing between the disconnected regions that a feasibility-preserving move could not. Because the feasibility score falls exponentially with violation, large moves into infeasibility are rarely accepted. The walk therefore stays near the feasible regions and reaches a feasible set even where several constraints are tight.

Annealing and Termination. A fixed acceptance rule would either converge prematurely or fail to converge, so a simulated annealing schedule at temperature 1/β1/\beta sharpens it. Exploration runs at high temperature for a fixed number of steps, then β\beta grows and steepens the penalties, funneling the steps onto the feasible region. The walk stops at the first feasible set it reaches. Local minima in the constraint space can still trap it, so the sharpened phase is bounded: a

walk that exhausts its steps restarts from the offspring’s factors. This way, the repair stays near the factor choices the search is optimizing. Figure 3 shows the complete operator on the two factors x1x_1 and x2x_2 of a single dimension. The vertical lines bound x1x_1 by fanout, the horizontal line bounds x2x_2 by storage, and the curved band bounds their product by coverage; together they leave only the narrow feasible sliver where all three hold. From a feasible start, the operator proposes an infeasible step, the penalty scores it, and the acceptance rule carries the walk toward the feasible region. The walk moves through infeasible ground rather than navigating the thin sliver, since only the final set must be feasible. It stops at the first feasible point, a few steps from its start. Applied to every offspring, this repair makes the imperfect-factorization search tractable.

Repair walk toward the feasible region

Figure 3. Repair walk toward the feasible region

Evaluation

The evaluation tests whether (i) IMPACT finds better mappings than prior automated mappers, and (ii) whether it sustains that quality on hardware whose constraints leave few mappings valid. We compare against Timeloop[20], which defines the mapspace and cost model, and Ruby[10], the only prior mapper that searches the imperfect-factorization space. GAMMA[15], ZigZag[18], and SALSA[14] are built on different cost models that only evaluate perfectly factorized mappings, and cannot score the mappings this work targets. The first experiment evaluates the mappers on Eyeriss, a flexible architecture on which prior mappers already perform well, and isolates the quality of the search itself. The second moves to a compute-in-memory architecture, where a deep memory hierarchy and rigid tiling rules make feasible mappings rare, and adds expert hand-crafted mappings to test whether IMPACT remains effective where constraint-unaware search breaks down. The third measures each method’s valid-mapping yield, characterizing how each search navigates the feasible region under the same time constraint.

DeepBench Evaluation on Eyeriss

We compare IMPACT against Timeloop and Ruby on Eyeriss, evaluating on the DeepBench suite used in Ruby for direct comparison.

Each mapper runs 32 times per layer with independent seeds under the same per-run wall-clock budget of 15 minutes, and we report the mean across runs for each objective, so the results do not depend on a favorable seed. All three use the same analytical cost model, so any difference in mapping quality reflects the search alone. Energy, latency, and EDP are normalized to the Timeloop baseline. IMPACT uses the same search configuration throughout, listed in Table 1.

SearchRepair
Population size100Proposal width σ\sigma0.15
Initial candidates400Inverse temp. β0\beta_01
Elite survivors50Cooling factor1.3
Exploration / max steps3 / 5000

Table 1. IMPACT search configuration.

Comparison to automated mappers. IMPACT outperforms both Timeloop and Ruby on every workload family and every objective. As shown in Figure 4, the largest reduction is in energy. IMPACT lowers it by 33% over Timeloop at the mean across workloads, while Ruby lowers it by 1%. Latency falls by 14%, and EDP by a more modest 5%.

Figure 4. Energy, latency, and EDP on Eyeriss across DeepBench workloads for IMPACT and Ruby, normalized to Timeloop.

Effect of workload shape. IMPACT’s gains for EDP and latency concentrate on layers where perfect factorization cannot fill the PE array. Vision layers whose dimensions align with Eyeriss’s 14x12 PE array map well under Timeloop, so Ruby and IMPACT add little. On Face and DeepSpeech, filling the array requires imperfect factorization. Here Ruby reduces latency below Timeloop, and IMPACT reduces it further. For minimum-energy mappings, IMPACT strongly outperforms both. By uniquely exploring the imperfectly factorized tilings space, it finds mappings with lower data movement.

Source of the gains. IMPACT’s advantage on Eyeriss comes from the structure of its search. Eyeriss is a flexible architecture, and its loose constraints leave many mappings valid, so Timeloop and Ruby already sample good ones. IMPACT searches the wider valid space and covers it. The repair operator keeps its evaluations feasible across the imperfectly factorized region, and the genetic algorithm concentrates those evaluations around the strongest mappings it finds. Random sampling stops at the good mappings; this coverage is what finds the better ones.

finds competitive solutions and IMPACT’s margin is modest. On a constrained architecture, Timeloop is confined to perfect factorization and cannot fill the array, while Ruby searches an expanded space without structure and mostly evaluates invalid or inefficient candidates. IMPACT’s constraint-aware repair lets the genetic algorithm keep exploring and exploiting the sparse feasible region throughout the search. On constrained hardware, this reaches the quality that until now required hand-tuning.

Evaluation on CIM Architecture

We next evaluate IMPACT on a compute-in-memory architecture whose dataflow is far more constrained than the Eyeriss spatial array. We use a provided CimLoop[1] architecture, based on the analog RRAM crossbar of [25], whose fixed reduction dataflow is representative of CimLoop’s CIM models. This dataflow imposes rigid tiling rules, so feasible mappings are sparse and most candidates are infeasible. We compare IMPACT against Timeloop and Ruby on five networks: a Vision Transformer (ViT)[7], VGG-16[22], AlexNet[17], ResNet-18[9], and MobileNetV3[12]. For this architecture we additionally compare against the hand-crafted mappings provided by CimLoop. Each mapper searches every layer for the same wall-clock time, following the same 32-run protocol as § 6.1, reporting the mean across runs. Network energy and latency are summed across layers, while network EDP is computed as their product. All metrics are normalized to the Timeloop baseline.

Comparison to automated mappers. IMPACT is the only automated mapper that improves on Timeloop across every network and every metric. As Figure 5 shows, averaged over the five workloads, it reduces EDP by 66%, latency by 46.6%, and energy by 18.2% relative to Timeloop. Ruby searches a larger space than Timeloop but a smaller one than IMPACT; even so, without a structured search it reaches no high-quality mappings. On this architecture it underperforms even Timeloop, inflating EDP by 4× to 15× and failing for several AlexNet layers.

Figure 5. Energy, latency, and EDP across five networks on a CIM architecture, normalized to Timeloop.

Comparison to hand-crafted mappings. IMPACT outperforms the hand-crafted expert mappings on most configurations, without any manual tuning. It improves on the experts in 11 of the 15 metric-workload cases. The expert mappings are tuned to minimize EDP, and they improve on IMPACT in only four cases, three in EDP and one in energy, with an average discrepancy of 4.2% and a maximum of 17% on VGG-16. IMPACT reaches the lowest latency on all five networks and lower energy on four of the five, improving on the experts by 32% and 20% on average, respectively. IMPACT therefore matches the experts on the objective they are tuned for, and outperforms them on the objectives they are not.

Key takeaway. IMPACT’s advantage over prior mappers widens as the architecture becomes more constrained. On a flexible architecture, loose constraints leave many mappings valid, so every mapper finds competitive solutions and IMPACT’s margin is modest. On a constrained architecture, Timeloop is confined to perfect factorization and cannot fill the array, while Ruby searches an expanded space without structure and mostly evaluates invalid or inefficient candidates. IMPACT’s constraint-aware repair lets the genetic algorithm keep exploring and exploiting the sparse feasible region throughout the search. On constrained hardware, this reaches the quality that until now required hand-tuning.

Valid-Mapping Yield

We characterize each search by its feasible-sample rate on Eyeriss. Alongside the three mappers, we measure a plain genetic algorithm, obtained by removing the repair operator from IMPACT. Like GAMMA, it searches without constraint awareness, and isolates the repair operator’s contribution to the yield. The yield is the fraction of candidates that produce a mapping satisfying all workload-coverage, spatial-fanout, and storage-capacity constraints. A candidate is one attempt at a feasible mapping: a sampled mapping for Timeloop and Ruby, an offspring for the plain GA, and one repair walk for IMPACT, whose yield is therefore the fraction of walks that reach a feasible set rather than restart. We report it per DeepBench workload, under the same wall-clock budget as in § 6.1.

Valid-mapping yield. IMPACT spends its budget on feasible mappings, while the baselines spend most of theirs on infeasible ones. As Figure 6 shows, it reaches 83%, against 10% for Timeloop, 5% for Ruby, and 5% for the plain genetic algorithm. The yields separate the search strategies. Ruby samples the imperfect-factorization space without checking feasibility, and 95% of its candidates are invalid. The plain GA reaches only 5%. Its recombination barely preserves feasible structure, so most offspring violate constraints and are discarded. A genetic algorithm without repair produces no more feasible mappings than random sampling. The repair operator lifts the yield to 83% by steering each offspring to the feasible set, and is what makes search possible in this space.

Figure 6. Valid-mapping yield on Eyeriss across DeepBench workloads for Ruby, Timeloop, GA (without repair), and IMPACT.

Key Takeaway. The repair operator’s feasibility yield explains the quality gains of the previous experiments. In Sections 6.1 and 6.2, IMPACT ran under the same budget as the baselines, yet found better mappings. With its budget spent on feasible candidates rather than invalid ones, IMPACT’s search covers far more of the real mapspace in the same time, and finds the better mappings within it.

FrameworkStrategyImperfect FactorizationLoop OrderingTile SizeSpatial UnrollingDataflow ConfigurabilityConstraint Awareness
Timeloop[20]Random×✓✓✓✓×
Ruby[10]RandomSpatial✓✓✓✓×
GAMMA[15]GA×✓✓✓Flexible Only×
ZigZag[18]Random×✓✓×✓×
SALSA[14]SA+Random×✓✓×✓×
IMPACTGA+RepairFull✓✓✓✓✓

Table 2. Comparison between state-of-the-art mappers

Discussion

Comparison to prior work. Table 2 shows that no prior mapper handles both difficulties of mapping search: imperfect factorization and hardware constraints. Timeloop[20], ZigZag[18], GAMMA[15], and SALSA[14] all restrict search to perfectly-factorized mappings; SALSA further fixes spatial unrolling as an input. GAMMA’s genetic operators do not enforce dataflow constraints, confining its search to fully flexible accelerators. Ruby[10] comes closest, opening the imperfect-factorization space that holds the best mappings, but searches without structure or constraint awareness, so most candidates are invalid or low-quality. Unlike these, IMPACT pairs a genetic algorithm with a constraint-aware repair operator, addressing both imperfect factorization and hardware constraints, and reaches the high-quality mappings the others miss.

Practical impact. IMPACT’s ability to find high-quality mappings for a given tensor accelerator enables systematic design-space exploration across the software-hardware stack. Hardware engineers can measure how a change in the architecture affects performance, without manually searching for the best mapping at each configuration. Compiler engineers can retarget a workload to a new accelerator with an IMPACT-generated mapping, instead of re-tuning the mapping for every architecture by hand.

Conclusion

In this work, we present IMPACT, a framework for finding high-quality mappings on tensor accelerators, including highly constrained ones. It uses a genetic algorithm for structured search of the imperfect-factorization space, and a repair operator that keeps the search feasible as constraints tighten. IMPACT consistently outperforms prior automated mappers, and on constrained accelerators it rivals hand-crafted expert mappings. In practice, IMPACT decouples automated mapper performance from how constrained the hardware is. It therefore extends automated mapping to specialized accelerators, which until now depended on expert tuning.

Acknowledgments

This work was supported by the European Union’s Horizon Europe programme through Ferro4EdgeAI (Grant Agreement No. 101135656). The views expressed are solely those of the authors and do not necessarily reflect those of the European Union or the granting authority, neither of which can be held responsible for them.

References

  1. [1]Tanner Andrulis, Joel S. Emer, and Vivienne Sze. 2024. CiMLoop: A Flexible, Accurate, and Fast Compute-In-Memory Modeling Tool. In 2024 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 10–23. doi:10.1109/ISPASS56141.2024.00012DOI
  2. [2]Baidu Research. 2017. DeepBench: Benchmarking Deep Learning Operations on Different Hardware. https://github.com/baidu-research/DeepBench. Accessed: 2026-07-04.
  3. [3]Yu-Hsin Chen, Joel S. Emer, and Vivienne Sze. 2016. Eyeriss: A Spatial Architecture for Energy-Efficient Dataflow for Convolutional Neural Networks. In 2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA). 367–379. doi:10.1109/ISCA.2016.40DOI
  4. [4]Yu-Hsin Chen, Joel Emer, and Vivienne Sze. 2017. Using Dataflow to Optimize Energy Efficiency of Deep Neural Network Accelerators. IEEE Micro 37, 3 (2017), 12–21. doi:10.1109/MM.2017.54DOI
  5. [5]Carlos A Coello Coello. 2002. Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art. Computer methods in applied mechanics and engineering 191, 11-12 (2002), 1245–1287.DOI
  6. [6]K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (2002), 182–197. doi:10.1109/4235.996017DOI
  7. [7]Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. 2020. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929 (2020).
  8. [8]W Keith Hastings. 1970. Monte Carlo sampling methods using Markov chains and their applications. (1970).
  9. [9]Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. 770–778.arxiv.org/abs/1512.03385
  10. [10]Mark Horeni, Pooria Taheri, Po-An Tsai, Angshuman Parashar, Joel Emer, and Siddharth Joshi. 2022. Ruby: Improving Hardware Efficiency for Tensor Algebra Accelerators Through Imperfect Factorization. In 2022 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 254–266. doi:10.1109/ISPASS55109.2022.00039DOI
  11. [11]Mark Horowitz. 2014. 1.1 Computing’s energy problem (and what we can do about it). In 2014 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC). 10–14. doi:10.1109/ISSCC.2014.6757323
  12. [12]Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al. 2019. Searching for mobilenetv3. In Proceedings of the IEEE/CVF international conference on computer vision. 1314–1324.
  13. [13]Norman P. Jouppi, Cliff Young, Nishant Patil, David Patterson, et al. 2017. In-Datacenter Performance Analysis of a Tensor Processing Unit. arXiv:1704.04760 [cs.AR] https://arxiv.org/abs/1704.04760
  14. [14]Victor J.B. Jung, Arne Symons, Linyán Mei, Marian Verhelst, and Luca Benini. 2023. SALSA: Simulated Annealing based Loop-Ordering Scheduler for DNN Accelerators. In 2023 IEEE 5th International Conference on Artificial Intelligence Circuits and Systems (AICAS). 1–5. doi:10.1109/AICAS57966.2023.10168265
  15. [15]Sheng-Chun Kao and Tushar Krishna. 2020. GAMMA: Automating the HW Mapping of DNN Models on Accelerators via Genetic Algorithm. In 2020 IEEE/ACM International Conference On Computer Aided Design (ICCAD). 1–9.
  16. [16]Scott Kirkpatrick, C Daniel Gelatt Jr, and Mario P Vecchi. 1983. Optimization by simulated annealing. science 220, 4598 (1983), 671–680.
  17. [17]Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems 25 (2012).
  18. [18]Linyan Mei, Pouya Houshmand, Vikram Jain, Sebastian Giraldo, and Marian Verhelst. 2021. ZigZag: Enlarging Joint Architecture-Mapping Design Space Exploration for DNN Accelerators. IEEE Trans. Comput. 70, 8 (Aug 2021), 1160–1174. doi:10.1109/TC.2021.3059962DOI
  19. [19]Nicholas Metropolis, Ariaanna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller. 1953. Equation of state calculations by fast computing machines. The journal of chemical physics 21, 6 (1953), 1087–1092.
  20. [20]Angshuman Parashar, Priyanka Raina, Yakun Sophia Shao, Yu-Hsin Chen, Victor A. Ying, Anurag Mukkara, Rangharajan Venkatesan, Bruce Khailany, Stephen W. Keckler, and Joel Emer. 2019. TimeLoop: A Systematic Approach to DNN Accelerator Evaluation. In 2019 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 304–315. doi:10.1109/ISPASS.2019.00042DOI
  21. [21]Jaime Sevilla, Lennart Heim, Anson Ho, Tamay Besiroglu, Marius Hobbhahn, and Pablo Villalobos. 2022. Compute Trends Across Three Eras of Machine Learning. In 2022 International Joint Conference on Neural Networks (IJCNN). IEEE, 1–8. doi:10.1109/IJCNN55064.2022.9891914DOI
  22. [22]Karen Simonyan and Andrew Zisserman. 2014. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 (2014).DOI
  23. [23]Gilbert Syswerda. 1989. Uniform Crossover in Genetic Algorithms. In Proceedings of the 3rd International Conference on Genetic Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2–9.
  24. [24]Vivienne Sze, Yu-Hsin Chen, Tien-Ju Yang, and Joel Emer. 2017. Efficient Processing of Deep Neural Networks: A Tutorial and Survey. arXiv:1703.09039 [cs.CV] https://arxiv.org/abs/1703.09039
  25. [25]Wieer Wan, Rajkumar Kubendran, Clemens Schaefer, Sukru Burc Eryilmaz, Wen-qiang Zhang, Dabin Wu, Stephen Deiss, Priyanka Raina, He Qian, Bin Gao, et al. 2022. A compute-in-memory chip based on resistive random-access memory. Nature 608, 7923 (2022), 504–512.
  26. [26]Yannan Nellie Wu, Joel S. Emer, and Vivienne Sze. 2019. Accelergy: An Architecture-Level Energy Estimation Methodology for Accelerator Designs. In 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). 1–8. doi:10.1109/ICCAD45719.2019.8942149

Paper details

vlnc:W_sf4c7xwy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents