Fast and Fusiest: An Optimal Fusion-Aware Mapper for Accelerator Modeling and Evaluation Tanner Andrulis ∗, Michael Gilbert ∗, Vivienne Sze, Joel S. Emer Abstract The latency and energy of tensor algebra accelerators depend on how data movement and operations are scheduled ( i.e., mapped ) onto accelerators, so determining the potential of an accelerator architecture requires both a performance model and a mapper to search for the optimal mapping. A key optimization that the mapper must explore is fusion , meaning holding data on-chip between computation steps, which has been shown to reduce energy and latency by reducing DRAM accesses. However, prior mappers cannot find optimal mappings with fusion ( i.e., fused mappings ) in a feasible runtime because the number of fused mappings to search increases exponentially with the number of workload computation steps. In this paper, we introduce the Fast and Fusiest Mapper ( FFM ), the first mapper to quickly find optimal mappings in a comprehensive fused mapspace for tensor algebra workloads. FFM shrinks the search space by pruning subsets of mappings ( i.e., partial mappings ) that are shown to never be a part of optimal mappings, quickly eliminating all suboptimal mappings with those partial mappings as subsets. Then FFM joins partial mappings to construct optimal fused mappings. We evaluate FFM and show that, although the mapspace size grows exponentially with the number of computation steps, FFM’s runtime scales approximately linearly. FFM is orders of magnitude faster ( > 1000 × >1000\times ) than prior state-of-the-art approaches at finding optimal mappings for Transformers. I Introduction * * footnotetext: These authors contributed equally to this work Evaluating a tensor algebra accelerator architecture requires optimizing how data movement and operations are scheduled ( i.e., mapping ) to the accelerator [ 24 ] . Architecture evaluation frameworks [ 24 , 21 , 19 , 31 , 4 ] do so by incorporating a mapper to explore the space of mappings ( i.e., the mapspace ) and minimize an objective of choice ( e.g., energy, latency, energy-delay-product). To optimize the mapping, the mapper must consider various optimizations, one of which is fusion , which keeps data on-chip across computation steps, to reduce high-energy, high-latency off-chip accesses [ 20 , 9 , 26 , 1 , 30 , 4 , 31 , 5 , 29 ] . We define an optimal mapping as one that is valid and has lower objective metrics ( e.g., energy) than any other mapping in the mapspace. 1 1 1 While the optimal definition is mapspace-dependent, our mapspace is a superset of the mapspaces in many prior works [ 24 , 19 , 21 , 5 , 26 , 1 , 20 , 17 , 4 , 31 ] . Finding an optimal fused mapping is challenging because the space of fused mappings ( i.e., the mapspace ) is large [ 9 , 31 , 4 ] . The mapspace is large because of exponential scaling: (1) tensor algebra workloads include many computation steps, which we describe using Einsums [ 8 ] ; (2) each Einsum can be mapped in many ways, each of which we call a partial mapping ( i.e., a pmapping ) because it maps only a subset of the workload; and (3) a full mapping is the combination of pmappings (one for each Einsum). Evaluating all mappings is a challenge because the total number of mappings grows exponentially with the addition of more Einsums. † † FFM is integrated into the AccelForge framework, available at https://accelergy-project.github.io/accelforge/ . Please direct all questions on this work to AccelForge. Mapper Can fuse? Optimal Time to Optimal Timeloop [ 24 ] Maestro [ 19 ] Zigzag [ 21 ] No No N/A Optimus [ 5 ] ConvFusion [ 26 ] FusedCNN [ 1 ] DeFiNES [ 20 ] FLAT [ 17 ] Limited No N/A SET [ 4 ] Tileflow [ 31 ] Yes Near* Slow* This work Yes Yes Fast** *Within 2\% of optimal after approx. 30,000 CPU hours (Section VII ). **Optimal after approx. 30 CPU hours (Section VII ). TABLE I: Comparison of mappers. Only this work is fast and optimal. Many prior works only explore a narrow mapspace. Specifically, they constrain the space of pmappings (often while assuming certain types of Einsums, e.g., convolutions) and/or the ways pmappings for different Einsums can be joined [ 20 , 26 , 1 , 5 , 17 , 7 ] . This presents two problems. First, it has been shown that constrained mapspaces result in worse mappings [ 31 , 9 ] . Second, because the constraints are often tailored to specific types of Einsums, these works cannot be applied to other workloads [ 5 , 26 , 1 , 20 , 17 , 7 ] . More-recent mappers [ 31 , 4 ] explore a more comprehensive mapspace, but have not addressed the exponential mapspace size. These mappers often use black-box search algorithms ( e.g., genetic algorithms [ 31 ] or simulated annealing [ 4 ] ), which achieve better-than-random results. These approaches can not guarantee finding optimal mappings, and their runtime increases exponentially with more Einsums, making them slow for workloads with reasonable numbers of Einsums ( e.g., failing to converge with a 10-Einsum attention head). In this paper, we introduce the Fast and Fusiest Mapper (FFM), a fast mapper that can find optimal fused mappings in a large mapspace and for many tensor algebra workloads. FFM constructs fused mappings one Einsum at a time, pruning at each step to keep the search space small. We show that pruning at each step lets FFM explore the exponential mapspace in approximately linear time. To illustrate how FFM constructs mappings one Einsum at a time, Fig. 1 shows an analogy. We are constructing a jigsaw puzzle (a full mapping) by selecting a subset of pieces from a large collection of puzzle pieces (pmappings). Our full puzzle (full mapping) must have one piece of each color (one pmapping for each Einsum) in a specified order (that satisfies inter-Einsum data dependencies). Pieces (pmappings) can be joined if tabs and sockets match (pmappings are compatible if the ways they exchange shared data match). Our objective is to minimize the sum of the numbers, representing cost, on the pieces (the sum energy of pmappings). Fig. 1 (b) shows that the best combination of puzzle pieces is “red 3” and “blue 1.” We can find this solution by checking all 3\times 3=9 combinations. But as we increase the number of colors of pieces in the puzzle (number of Einsums in the workload), the runtime of this brute-force approach would grow exponentially, and this approach becomes unfeasible. We can apply two optimizations to reduce the number of combinations to consider. First, we consider compatibility . Many puzzle piece pairs will not interlock (many pmapping combinations are incompatible). In Fig. 1 (c), we group pieces with the same tab and socket shapes (group pmappings by compatibility). Then, we need only consider combinations between compatible groups. In the example, this optimization reduces the possible combinations from 9 to 2\times 2+1\times 1=5 . Next we consider objectives . Fig. 1 (d) shows that we can maintain overall optimality while greedily selecting puzzle pieces (pmappings) with the lowest numbers (lowest energy pmappings) within each group because they are the same shape (have the same interactions between pmappings). This pruning of pieces (pmappings) dramatically reduces the number of combinations to try; in the example, pruning two pieces reduces possible combinations from 5 to 2. For workloads with more Einsums, we can extend the analogy to include yellow pieces coming after blue, and blue pieces with have a socket on one side (pmapping consuming data) and tab on the other (producing data). After joining red and blue pieces, we repeat this process using red+blue combinations as new pieces. Pruning at each step limits the growth in the number of combinations. Fig. 1: An analogy of pmappings as puzzle pieces. (a) Tabs and sockets represent compatibility. Numbers represent a cost metric. (b) Pieces can be joined in several ways. (c) Pieces can be grouped by tabs/sockets and (d) pruned per-group. In this work, we introduce the concepts of compatibility between pmappings and criteria that capture objectives ( e.g., minimize energy) and constraints ( e.g., keep global buffer footprint within available capacity). Using these concepts, we create a mapper that finds optimal mappings in a large mapspace by constructing mappings one Einsum at a time and pruning at each step. In summary, this paper makes the following contributions: • We introduce the Fast and Fusiest Mapper (FFM), a fast algorithm to find optimal fused mappings in a large mapspace for a wide variety of workloads. FFM constructs mappings one Einsum at a time, pruning at each step to keep the search space small. • To enable pruning, we introduce partial mappings ( pmappings ) and criteria that capture which pmappings can be joined ( e.g., compatibility between pmappings) and how they satisfy system constraints ( e.g., keep global buffer footprint within available capacity) and affect objective metrics ( e.g., overall energy and latency). These let us prune suboptimal pmappings without seeing full mappings, while guaranteeing that we will have the optimal mapping after joining. • We demonstrate that the runtime of FFM increases approximately linearly with the number of Einsums, despite the exponentially increasing mapspace size, making FFM effective for large cascades of Einsums. • We evaluate FFM against state-of-the-art mappers. FFM yields mappings with 1.3-37\times lower latency (of the resulting mapping, not the mapper) than prior mappers. Furthermore, prior works do not find optimal mappings even with 1000\times more runtime than FFM. II Background We briefly discuss the Einstein summation (Einsum) notation [ 8 , 12 , 22 , 23 ] , which precisely describes a wide range of tensor algebra computation steps, and the LoopTree notation [ 9 ] , which precisely describes a wide variety of fused (and unfused) multi-Einsum mappings. II-A The Einsum Notation Computation steps in a tensor algebra workload ( e.g., a matrix multiplication or a convolution step in a DNN layer) can be described using the extended Einsum notation [ 8 , 12 , 22 , 23 ] . In the Einsum notation, input and output multi-dimensional data are tensors , and the dimensions of the tensors are called ranks [ 25 ] . For example, in a matrix multiplication Z=A\times B , the matrices A , B , and Z are the tensors, the dimensions M , K , N are the ranks and the Einsum is Z_{m,n}=A_{m,k}\times B_{k,n} . The variables m , n , k , which index into ranks, are referred to as rank variables , and a summation is implied over rank variables that are present in the right-hand side of the equation but not in the left-hand side ( k in this example). As a convention, rank variables are often the lowercase letters of the ranks. A more complete explanation of Einsums as we use them can be found in [ 22 ] . II-B The LoopTree Notation We explain the LoopTree notation [ 9 , 10 ] using an example mapping of a workload with two computation steps, each a matrix-vector multiplication: (Step 1) Einsum A: \displaystyle A_{nA}=I_{nI}\times WA_{nI,nA} (1) (Step 2) Einsum B: \displaystyle B_{nB}=A_{nA}\times WB_{nA,nB} (2) Fig. 2 (a) shows pseudocode for a fused mapping for these Einsums, and Fig. 2 (b) is the equivalent LoopTree mapping. Fig. 2: (a) Pseudocode of a mapping for two matrix-vector multiplications and (b) the equivalent LoopTree mapping. A LoopTree mapping consists of the following nodes: • Loop nodes (rectangles) contain for-loops that iterate over rank variables in the workload. A loop may be shared by multiple fused Einsums ( i.e., an inter-Einsum loop). For example, see the nA loop, which represents co-iteration of multiple Einsum computations. • Storage nodes (cylinders) represent tensor tiles in memory. A storage node is annotated with the memory level ( e.g., DRAM or GLB) and the tensor stored in that memory level. Loops above the storage node determine the tile shape and iteration order. In our example, the placement of storage node “GLB: I ” indicates that the NA rank is divided into four and the NI rank into three to create twelve tiles of I . At each loop iteration, one such tile is fetched into GLB. • Compute nodes (ovals) indicate processing of one computation in the Einsum ( e.g., multiply-accumulate operations in this example). In a LoopTree, important characteristics include the relative placement of nodes ( e.g., storage node over a loop node means tensor is reused across loop iterations) and splits ( e.g., loop above split means all Einsums below split interleave execution, storage nodes above splits means all Einsums under the split can use the same stored tensor tile). III Puzzle Pieces to Pmappings In this section, we present an overview of pmapping attributes in a taxonomy (what they are and what is their impact), and connect these attributes to an augmented version of the introduction’s puzzle analogy that better reflects the idea underlying FFM. Table II points to the sections with more specific examples, and details on pruning opportunities, challenges, and solutions. III-A Pmapping Joining Example using LoopTree Notation FFM constructs full mappings by repeatedly joining compatible pmappings. For example, suppose we have as workload a cascade of three vector-matrix multiplications (insert after Eq. 2 , a new Einsum C , C_{nC}=B_{nB}\times WC_{nB,nC} ), Fig. 3 shows a two-step process for joining three pmappings, one pmapping for each Einsum. In Fig. 3 (a), a pmapping for Einsum A is joined with a pmapping for Einsum B . In Fig. 3 (b), the (joined) pmapping from the previous step is joined again with a pmapping for Einsum C . For pmappings to be compatible for joining, they must have the same (1) tile shape for the shared tensor, (2) iteration order of the tiles (dataflow), and (3) memory level that keeps the tile (details in Section IV ). In a LoopTree, this means that the storage node and the loops above the node must match. For example, Einsum A and B share the tensor A , and in Fig. 3 (a), the storage node “GLB: A ” and the loop “for nA in [0,4)” match (the node “GLB: B ” is not relevant yet at this step). To join pmappings, we merge their compatible portions, making it one shared portion, and place a split underneath that shared portion ( i.e., under “GLB: A ”). Fig. 3: A two-step example of joining pmappings with puzzle analogy. Only storage nodes for shared tensors matter to joining compatibility, so other storage nodes are omitted for clarity. (a) Joining pmappings for Einsums A and B . (b) Joining the pmapping for Einsums A,B and the pmapping for Einsum C . The storage node of shared tensor (tensor A between Einsums A and B , and tensor B between Einsums B and C ) and loops above the storage nodes must match, analogous to tabs/sockets in the puzzle. This process is repeated to create full mappings. For example, Fig. 3 (b) shows the result from Fig. 3 (a) being joined with a third pmapping for Einsum C . The shared tensor is now B , and the process from before can be applied in this step. Finally, this process can construct a comprehensive mapspace: Any LoopTree can be decomposed into individual pmappings, and conversely, there exist pmappings that join to create any given LoopTree. Furthermore, there is a one-to-one correspondence between a LoopTree and a loop nest, so this procedure can be used to realize arbitrary loop nest mappings. III-B A Taxonomy of Pmapping Attributes Table II shows a taxonomy of attributes that completely describe how pmappings can be joined and how they affect the overall mapping. This taxonomy lets us compare pmappings with each other to find dominated pmappings to prune. Criterion (Section) Example Puzzle Analogy FFM Use Overall Goal Objective ( III ) Pmapping Energy Piece cost Pruning within group Minimize Compatibility ( IV ) Shared tensor exchange location (backing storage node) and tile shape/order (loops above storage node) Tab/socket shape Grouping Satisfy data dependencies Reservation ( V ) Tensor X memory usage and for how long Tensor X is alive Piece weight Pruning within group Ensure below resource limits TABLE II: A taxonomy of criteria that we use to compare and prune pmappings. Examples are illustrative, not full descriptions. III-B 1 Objective Criteria The objective criteria are a vector (a number for each objective) that represents pmapping quality ( e.g., latency and energy). Objectives do not constrain pmapping choices, but they affect the mapping quality. They are analogous to the cost numbers on the puzzle pieces, where we want to find a jigsaw puzzle with the lowest sum overall. If an objective can not be summed, we express it as a combination of summable attributes ( e.g., energy and latency as objectives, calculate EDP at the end). III-B 2 Compatibility Critera The compatibility criteria, which include dataflow and backing storage, determine whether two pmappings are compatible (analogous to the tabs and sockets in the puzzle analogy). Dataflow is the order of operations that produce and consume data tiles. Because fused computation steps must agree in the order of production and consumption of data tiles, dataflow choices determine compatibility of pmappings. Backing Storage specifies, for each shared tensor, what tiles are exchanged and in what memory level. Pmappings for producer and consumer Einsums must agree on the backing storage used to exchange shared tensors. III-B 3 Reservation Criteria The reservation criteria captures the resource usage ( e.g., memory or PE usage 2 2 2 The ideas described in this paper apply to both; we will mainly discuss memory usage to avoid repetition. ) of a pmapping, which will be used to compute overall resource usage of the full mapping and are used, for example, to eliminate mappings that require more resource than available on the hardware. The next subsection presents an updated puzzle analogy that incorporates such a resource constraint. The reservation criteria are multidimensional, and they capture three aspects: (1) which resource is being reserved, (2) how much is reserved, and (3) for how long ( e.g., a pmapping may require a peak of 60MB of global buffer capacity while processing an Einsum). III-C Grouping and Pareto Pruning Under Resource Constraints Here, we give an intuitive overview of how FFM’s grouping and pruning guarantee optimality when resource constraints are included (details in Sections IV and V ). As we have seen in the puzzle analogy, grouping the pieces based on compatibility lets us prune within each group (details in Section IV ). This pruning must simultaneously take into account all criteria, including objective, reservation, and compatibility criteria. For example, one pmapping may have low energy because it greedily uses up most of the on-chip memory. This pmapping would be a great choice if later pmappings use little on-chip memory, but not if they need more on-chip memory to achieve low energy as well. Fig. 4 incorporates simplified reservation criteria into an augmented puzzle analogy. Each puzzle piece has two numbers: an objective to minimize and a reservation. The goal is still to find a combination that minimizes the sum of costs, but now keeping the sum of reservations less than or equal to 4 (analogous to a resource limit). We guarantee optimality by pruning only when a piece is worse than another in all criteria. For example, in Fig. 4 (b), group G0 contains two pieces with criteria (2,3) and (3,3). In this group, we can prune the piece with (3,3) because (2,3) is always better, with a lower objective and the same reservation. On the other hand, no piece in the group G1 can be pruned because one has a lower objective while the other has a lower reservation. Fig. 4: An example constrained optimization and (b) example puzzle pieces with two criteria (objective, reservation) to consider. Two groups of puzzle pieces, group G0 and group G1, are highlighted for discussion. IV Compatibility Criteria In this section, we discuss compatibility, which encompasses when and where data pmappings exchange data. Pmappings must have matching compatibility to satisfy data dependencies ( e.g., data must be read after it is written and before it is freed). We will show how we encode compatibility as criteria (based on backing storage and loops above backing storage) to enable grouping and, later, pruning within groups. IV-A Compatibility Criteria Pairs of pmappings must respect data dependencies to be compatible. Specifically, for every shared tensor, pmappings must agree on: (1) the shape of shared tensor tiles; (2) the memory level in which the tiles are stored, and (3) the order of production and consumption of the tiles ( i.e., the dataflow). These three attributes comprise the tensor’s compatibility , which are all attributes needed to ensure that the Einsums agree on how the tensor is exchanged. To show how to see compatibility in a LoopTree, Fig. 5 (b) shows pmappings for Einsums A and B that are separated from the full mapping in Fig. 5 (a). We focus on the blue loop nodes, “for nA ”, and red storage nodes, “GLB: A ”. We can see the same constraints from before in the separated pmapping LoopTrees: (1) the tile shape for A in GLB is the same because loops over the same rank variable with the same bounds are above the storage node for A in GLB, (2) both storage nodes specify keeping A in GLB, and (3) the dataflows of the A tile production (in Einsum A ) and consumption (in Einsum B ) match, which means the orders of loops above storage node for A match (there is only one loop in this example, but this rule generalizes to more loops). Compatibility considers only the outermost memory level in which shared tensor tiles are exchanged between Einsums (the highest storage nodes for shared tensors in the LoopTree). We term the memory level backing memory and the storage node backing storage ( e.g., in Fig. 5 , the backing memory for Tensor A is GLB). Importantly, backing memory is a design choice that naturally ecompasses the fused design space. A pmapping can specify a backing memory to be DRAM (making it unfused), GLB (making it fused), or any other memory level. This lets us support a comprehensive fused space including fusion at every memory level (rather than treating fusion as a special case that must be considered). Fig. 5: (a) A mapping for two Einsums onto an accelerator with DRAM and GLB memory levels and (b) pmappings separated from the full mapping. A pmapping may contain storage and loop nodes that are not relevant to compatibility. For example, the unhighlighted storage nodes “GLB: WA” and “GLB: I” and loop nodes determine the dataflow and tile shape of tensors only used in Einsum A . Choices for these loops do not affect compatibility, as compatibility only considers respecting data dependencies between Einsum A and B due to the shared tensor A . IV-B Compatibility for Grouping and Skipping Joins After generating the compatibility criteria for all pmappings, we group pmappings with the same compatibility to enable two mapping optimizations: skipping joining incompatible pmappings and optimality-preserving pmapping pruning. We reduce the time spent checking for pmapping compatibility by only joining pmappings from compatible groups. For example, instead of trying to join every pmapping for Einsum A with every pmapping for Einsum B , we check the compatibility between groups for Einsum A and groups for Einsum B . Then for any compatible group of A and group of B , any pmapping in the group of A is always compatible with any pmapping in the group of B . Grouping based on compatibility ensures that pruning is optimality-preserving because any two pmappings in the group are interchangeable. Specifically, just as we can trade one puzzle piece for another in the same group in Fig. 4 , we can also trade any pmapping in a mapping with another pmapping from the same group. So, if pmapping p_{1} is Pareto-better than another pmapping p_{2} in the same group, it is optimality-preserving to prune p_{2} because any mapping that contains p_{2} could be improved by replacing p_{2} with p_{1} . V Reservation Criteria Valid mappings must reserve system resources ( e.g., buffer capacity, number of processing elements) within available limits. Reservation limits represent a constraint in the mapping problem, but also a pruning opportunity. All other attributes being equal, a pmapping that reserves more resources is a worse pmapping and a pruning candidate. In this section, we discuss (1) calculating resource reservations from a full mapping, (2) tracking the minimum amount of reservation information in a partial mapping to still be able to compute the final reservations, and (3) pruning partial mappings using reservation information. V-A Calculating Reservations of Full Mappings To illustrate how we calculate a mapping’s reservations, we will calculate GLB usage for the mapping in Fig. 6 (a). We first convert the LoopTree to ReservationTree ; storage nodes immediately above splits are replaced with reservation nodes in branches where the reservation is live ( e.g., “ GLB:A ” in Fig. 6 (a)). Other storage nodes are replaced with reservation nodes at the same spot ( e.g., “ GLB:WA ” in Fig. 6 (a)). Fig. 6: (a) ReservationTree for the mapping in Fig. 5 (a) replaces storage nodes (cylinders) with reservation nodes (placards), which show tensor tile lifetimes across branches explicitly. (b) Illustration of GLB usage. Color and label correspond to reservation nodes. Timesteps are marked with the Einsum being processed. The dashed line shows the maximum GLB usage. Fig. 6 (b) shows the resources reserved by the ReservationTree. Memory usage is not uniform during the processing because the sizes and lifetimes are different for different tensor tiles, but the maximum memory usage (dotted line) must be within the GLB capacity for the mapping to be valid. All reservations within a branch are live at the same time, so we can calculate GLB usage for a branch as the sum of reservations in the branch ( e.g., Fig. 6 (a) has GLB reservations for A and I , and Fig. 6 (b) shows A and I stacked in the same timestep). Different branches are active at different times, so we take a maximum of the GLB usage across branches ( e.g., in Fig. 6 (b), compare GLB usage for Einsum A and B ). This pattern generalizes: To calculate the total reservations of a ReservationTree, recursively sum reservations within a branch, and max reservations across branches. V-B Reservation Lifetimes and Consolidating Reservations The challenge in our method is that a pmapping alone does not tell us the lifetime of all reservations in the final mapping. Fig. 7 (a) shows the same ReservationTree as in Fig. 6 , but now as a pmapping, and there are two places where a branch may be joined in the future: BranchC and BranchD . A branch may be added under any loop or under the outermost DRAM storage node. In this example, we know the lifetime of tensor I tile in GLB is only within the timesteps when we process Einsum A . However, we do not yet know the lifetime of WA . If another Einsum branches off at BranchC , then WA will be live while processing that Einsum. But if that Einsum branches off at BranchD , then WA will only be live for Einsums A and B but not the newly joined Einsum. These unknown lifetimes affect GLB usage, which we address by tracking each reservation. If \hat{C} is GLB usage within BranchC , \hat{D} is GLB usage within branch D , and X is the memory usage of tensor X , then total memory usage is: \text{{Usage}}=\max(\hat{D},WA+\max(A+I,A+B+WB,\hat{C})) (3) Note that although we do not yet know what \hat{C} and \hat{D} are, tracking the reservation of each tensor separately will allow us to compute the usage at the end. Fig. 7: (a) The ReservationTree from Fig. 6 plus branches where future pmappings may be joined. (b) The ReservationTree after summing same-lifetime reservations. (c) The ReservationTree after maxing reservations across branches. This method requires us to track many reservations, but we can reduce this number by leveraging two observations: (1) there are only a few unique lifetimes (determined by branches) and (2) many lifetimes can be consolidated. First, notice that some lifetimes include neither BranchC nor BranchD , others include BranchC only, and others include all branches. When we compare pmappings, we can only compare reservations that have the same lifetime, and two reservations have the same lifetime if they are above the same branches. This is true regardless of the contents of the branches, so it works even if we later add unknown pmappings to branches. So, any reservation between BranchC and BranchD splits could be compared to our WA reservation because they would have identical lifetimes. We can use the relatively few unique lifetimes to reduce the number of reservations to track. Fig. 7 (b) shows that instead of tracking A , I , B , and WB separately, we can track the per-branch total: \text{{Sum same lifetimes:}}\ \hat{A}=A+I,\ \hat{B}=A+B+WB (4) Then, we only have to track fewer values: \text{{Usage}}=\max(\hat{D},WA+\max(\hat{A},\hat{B},\hat{C})) (5) Moreover, branches that cannot have future pmappings joined to them ( i.e., branches on the left) can have their reservations consolidated into one value. Fig. 7 (c) shows that the branches for Einsums A and B can be consolidated: \text{{Max across branches:}}\ \widehat{AB}=\max(\hat{A},\hat{B}) (6) Then, we reduce the number of values to track even more: \text{{Usage}}=\max(\hat{D},WA+\max(\widehat{AB},\hat{C})) (7) A crucial benefit of consolidation it means the number of reservations to track does not depend on the number of Einsums. If the next split occurs \leq N loops down, then we only need to track up to 2N+1 reservations. 3 3 3 The factor 2 comes from the fact that two lifetimes must be tracked for every potential split: reservations with a lifetime that end before future Einsums and reservations with a lifetime that continues to future Einsums. The constant 1 is for reservations below the bottommost split, which never live through future Einsums. The split point is limited by the number of loops above the current split in each pmapping, which is limited by the number of shared ranks between the most recent and next Einsum. This number is generally small ( e.g., 4 for transformers). V-C Pruning Pmappings using Reservations To prune using reservations, we need to consider both the size of each reservation and the time period for which each reservation is alive. First, note that reservations can be compared for two pmappings which have the same expression for resource usage ( e.g., the same expression as Eq. 7 just with different values for WA and \widehat{AB} ). Equivalently, two pmappings can be compared if they have the same ReservationTree form after consolidation ( e.g., the tree in Fig. 7 (c). Note that a ReservationTree after consolidation reduces to a subtree that contains the same information as the compatibility criteria). Therefore, any two pmappings with the same compatibility criteria can have their reservations compared. To compare the reservation of two pmappings and ensure pruning preserves optimality, we consider all reservations and check for Pareto dominance ( i.e., a pmapping has worse reservations if and only if its reservation is larger across all lifetimes for all resources). VI Fast and Fusiest Mapper The Fast and Fusiest Mapper ( FFM ) implements the ideas in the previous sections to quickly find optimal mappings. Fig. 8 shows FFM, which has two main steps. First, FFM explores the space of pmappings for each Einsum. Next, starting with the first Einsum, it repeatedly groups, prunes, and joins pmappings until all Einsums are joined. Fig. 8: Overview of the Fast and Fusiest Mapper (FFM). VI-A Exploration of Single-Einsum Pmappings We generate all Pareto-optimal pmappings for every Einsum, exploring dataflow, tile shape, storage node placement, and spatial allocation. To explore all fusion options, the pmapping exploration considers all backing storage choices. 4 4 4 While we show one processing order for the Einsums, there may be more than one data-dependency-satisfying processing order of Einsums. FFM can explore these orders by joining in all data-dependency-respecting orders of Einsums. Pmappings are the same for any order and are only computed once. While an exhaustive exploration of all pmappings would be slow [ 24 ] , we extend ZigZag’s [ 21 ] Loop Relevancy Principle to quickly find all Pareto-optimal pmappings orders-of-magnitude more quickly than an exhaustive exploration. To evaluate pmappings, we use a model built from LoopTree [ 9 ] and energy estimation from Accelergy [ 28 , 2 ] . VI-B Group, Prune, and Join Pmappings We explain this section with an example, then extend it to the full algorithm. Assume we have the pmappings for Einsum A and we’d like to join them with the pmappings for Einsum B . We would perform the following steps: • Group the pmappings for Einsum A based on compatibility criteria. Do the same for Einsum B . • Prune dominated pmappings in each group by eliminating pmappings not on the Pareto frontier. • Join compatible pmappings for each group combination. For every valid combination of groups, we generate every combination of pmappings. After performing these steps, we will have pmappings that map both Einsums A and B . We repeat the process, adding pmappings for one Einsum at a time until we have processed all Einsums. We use several optimizations to speed up this process. First, a given pmapping for one Einsum will likely only be compatible with a fraction of pmappings for another Einsum, so we skip incompatible joins by pairing groups of pmappings first based on their compatibility, then joining pmappings only between compatible groups (described in Section IV ). Next, each Einsum adds more reservations to track, so after each join step we consolidate reservations (described in Section V ) to keep pruning effectively. VII Results In this section, we compare FFM to prior mappers and show FFM is orders-of-magnitude ( >1000\times ) faster than mappers that use prior black-box approaches. We also test our mapper on various length workloads, showing that the runtime of our mapper scales approximately linearly with the number of Einsums. Next, we show an ablation study of different FFM optimizations affecting runtime. Finally, we show that the mapspace explored by FFM can improve the throughput of accelerators over the mapspaces of prior works. VII-A Open-Source Version is Faster than Shown The results in this version of the paper were generated using a naïve pmapping generator, while the open-source AccelForge ( https://accelergy-project.github.io/accelforge/ ) version uses the Turbo-Charged pmapper, while also using more-optimized joining code. The experiment in Section VII-E ran \sim 0.75 CPU hours with the new version (versus 30 CPU hours shown in this paper). VII-B Accelerator Architecture We evaluate using an architecture based on TPUv4i [ 15 ] , which has a 128 MiB global buffer and four cores. Each core has a 4 MiB local buffer and a 128 \times 128 PE-array that supports 8-bit multiply-accumulate (MAC) operations, operating with a weight-stationary dataflow. The architecture operates at 1.05 GHz, and connects to DRAM with 614 GB/s bandwidth. Hardware Model: The hardware model is based on the validated LoopTree [ 9 ] model and component energies are modeled with HWComponents [ 2 , 28 ] . We validate that our model results exactly match those estimated by LoopTree. VII-C Baselines We compare our mapper to three baselines implemented based on prior mappers 5 5 5 Each paper’s implementation supports a different mapspace, so we create mappers for this mapspace based on their approach. . Simulated annealing , based on SET [ 4 ] , explores storage node placements, shared loops for each Einsum, and intra-Einsum by randomly changing choices and accepting the new one probabilistically. Cooling rate and initial temperature are taken from the SET implementation [ 27 ] . We run 96 parallel threads and report the best mapping found across all threads. The genetic algorithm , based on TileFlow [ 31 ] , picks storage node placements, shared loops for each Einsum, and intra-Einsum mapping choices. Each population has 104 randomly-initialized mappings (10k total across 96 threads) 6 6 6 We evaluated larger population sizes, but those converged more slowly. . We set a crossover rate of 0.7 and a mutation rate of 0.2 , which are the best-converging options found for eight matrix multiplications. Random search , based on Timeloop [ 24 ] , randomly samples a pmapping for each Einsum. We generously let baselines use our compatibility criteria to skip invalid mappings: random will only pick compatible combinations, and when genetic algorithm or simulated annealing transform one pmapping, other pmapping(s) are also transformed into compatible equivalents. We do not charge them runtime for these optimizations. VII-D Methodology For FFM and all baselines, we report the energy-delay-product (EDP) of the mappings found and the runtime of each mapper. Runtime reported for FFM is the wall-clock time, which includes the exploration of single-Einsum pmappings and the process of joining and pruning pmappings. Each baseline would take CPU-years to run directly, so we generously estimate its runtime (a lower bound of its actual runtime). To estimate baseline runtime, we run the baselines, but replace their mapping evaluation calls with queries to the cached results from FFM’s pmapping explorations. We then construct full mappings from the cached pmappings. We model baseline runtime by multiplying the number of queried pmappings by the amount of time it takes to evaluate a pmapping (approx. 1 CPU-millisecond per pmapping). This time is an underestimate because we ignore the time taken by the baselines to join pmappings and to select new pmappings ( e.g., for genetic algorithm , we do not include the time required to perform crossover and mutation). We test on a server with two Intel i9-13900HX 48-core CPUs and 384GB of RAM. FFM requires much less RAM ( e.g., around 35 GB for the GPT-3 workload), but we did use all available RAM to parallelize the baselines. All mappers are written in Python and parallelized. VII-E Baseline Comparison on Transformers We compare to the baselines on the GPT-3 6.7B Transformer model [ 3 ] with batch size 4 and 4096 tokens. The batch size and token count represent a common usage scenario in which shared tensors do not fit in on-chip memory without tiling them, making it nontrivial to find a good fused mapping 7 7 7 If the shared tensors can fit on-chip, it is trivial to fuse by keeping full shared tensors on-chip without tiling. . FFM finished after 30 CPU hours. We terminate baselines after 1000\times the time taken by FFM . Fig. 9 compares how fast the baselines converge to the optimal EDP relative to FFM . The y-axis shows the percent difference from optimal EDP. We can see that by the time FFM completes, the baselines are still far from optimal, with simulated annealing being the closest to optimal at 40\% away from the optimal EDP and genetic algorithm being the furthest at around 400% away. Genetic algorithm behaves like random search for the first 120 CPU hours ( 4\times the total runtime of FFM ). This slow start is caused by the difficulty of finding valid mappings for the initial population by choosing randomly. This task is difficult for a multi-Einsum workload: The proportion of valid mappings shrinks with each Einsum added because any pmapping can make the full mapping invalid. Fig. 9: Convergence speeds of baselines relative to FFM . FFM finds the optimal mapping before baselines are within 10\% optimal EDP. Baselines are 2\% away from optimal EDP even at 1000\times FFM ’s runtime. FFM ran in \approx 30 CPU hours. After populations are initialized, genetic algorithm quickly improves EDP, but still slower and worse EDP than FFM . Although there appears to be a sharp drop in the genetic algorithm curve, because the x-axis has a log scale, that section actually still takes several times the runtime of FFM . Finally, simulated annealing and genetic algorithm plateau at 2% from optimal at 1000 \times FFM runtime. VII-F Runtime with Number of Einsums To compare the speed of our mapper against the baselines as a function of the number of Einsums, we run the mappers on chains of matrix multiplications (the output of one matrix multiplication is the input to the next and so on), and vary the number of matrix multiplications. Each matrix multiplication has M= 8,192; and we create a variety of tensor shapes by using the following pattern for (N;K) : (16,384; 16,384) \rightarrow (4,096; 16,384) \rightarrow (4,096; 4,096) \rightarrow (16,384; 4,096) \rightarrow repeat. The single-Einsum exploration generates \approx 200,000 pmappings for each Einsum. We set the timeout for the baselines to 1000\times the time taken by FFM . Fig. 10 shows the time taken by FFM to find an optimal mapping and the baselines to find a mapping within 1\% of optimal. FFM quickly finds optimal mappings for all numbers of Einsums, while the runtime of the baselines rapidly increases with more Einsums. Genetic algorithm is faster than FFM for two Einsums because we let it stop early after finding a mapping within 1\% of optimal. In practice, with no prior knowledge of an optimal mapping, this would not be possible. FFM ’s per-Einsum runtime is approximately constant as the number of Einsums increases. This means that its runtime scales approximately linearly with the number of Einsums, despite the exponential mapspace size. While linear time is not guaranteed (the number of Pareto points may increase with more Einsums), pmapping generation time always dominated in our experiments (which included up to 64 Einsums), so FFM is linear-time in practice. Fig. 10: Time for FFM to find optimal mappings and baselines to find mappings within 1\% of optimal. FFM quickly finds optimal mappings for all numbers of Einsums, while baselines slow significantly with more Einsums. VII-G Ablation and Runtime Growth We evaluate how the optimizations described in Section VI affect FFM ’s runtime as it processes a chain of matrix multiplications. We test the following configurations of FFM : • Full FFM includes all optimizations. • Skipping Incompatible Joins avoids joining pmappings that are incompatible, which significantly improves runtime. We test a baseline that joins every current pmapping with every next-Einsum pmapping. • Consolidating Reservations increases pruning effectiveness (more pmappings are pruned in a group). We test a baseline that does not consolidate reservations and only compares and prunes pmappings whose reservations have the same lifetimes. Fig 11 shows the runtime for each step in its processing. The figure breaks down the initial pmapping generation with and joining pmappings for each Einsum. FFM runtime is dominated by the time taken to generate pmappings, as shown in the graph, because the time to join any given Einsum is much lower than the time to explore pmappings for that Einsum. This difference in runtime is because the initial single-Einsum pmapping exploration generates \approx 200k pmappings per Einsum, about 97\% of which are immediately pruned (only around 3% form the Pareto frontier). Following this, pruning at each step keeps the number of pmappings to join small. This is a significant reason why FFM ’s runtime grows approximately linearly with the number of Einsums. No Skipping Incompatible Joins leads to an \approx 100\times longer runtime from joining pmappings. This time is dominated by joining incompatible pairs of pmappings, which are then immediately pruned. The runtime, although longer, does not scale with the number of Einsums. No Consolidating Reservations leads to exponentially increasing runtime for joining pmappings as the number of Einsums increases. This is because each Einsum introduces a new shared tensor and its associated lifetime (described in Section V ). Each lifetime adds a new metric to track, which reduces pruning effectiveness and significantly increases the number of Pareto-optimal pmappings. Fig. 11: Runtime of FFM with and without optimizations. FFM runtime is dominated by the initial pmapping search, whose runtime is linear with the number of Einsums. Skipping incompatible joins reduces the time for joining einsums, and consolidating reservations prevents the number of pmappings and runtime from growing exponentially. The runtime of joining pmappings varies from one Einsum to the next because the number of Pareto-optimal pmappings varies. Overall, the number of EDP-optimal mappings increases as more Einsums are added, but their EDPs become more similar ( e.g., many mappings are within 1% EDP of each other). This did not significantly affect runtime, which was still dominated by initial pmapping exploration. VIII Related Works Many prior works propose mappers for single-Einsum workloads [ 24 , 19 , 21 , 16 , 13 , 14 ] . Multi-Einsum mappers have also been proposed for particular workloads and/or dataflows (commonly only convolutional neural networks) [ 20 , 26 , 5 , 1 ] . Most recently, mappers that support a wider range of workloads and a larger mapspace ( e.g., more dataflow choices) have been proposed [ 4 , 31 ] . However, these mappers explore their large mapspaces with black-box optimization methods, which we have shown to converge unfeasibly slowly. Optimal mappings generated by FFM can be translated into loop nests, which can guide compiler tool chains [ 11 , 6 , 18 ] . IX Conclusion Driven in part by the rise of deep neural networks and big data, tensor algebra programs are critical workloads to accelerate, and even small differences in energy or latency can become great when these programs are deployed at scale. It has become critical to use fusion to optimize these programs. However, it is a challenge to find optimal fused mappings due to the exponential mapspace size. The Fast and Fusiest Mapper partitions this exploration by introducing the notion of partial mappings and defines attributes ( e.g., compatibility, resource consumption, costs) that capture how they contribute to full mappings. This lets the Fast and Fusiest Mapper quickly find optimal fused mappings in a comprehensive mapspace.