Mosaic: Exploiting Instruction-Level Parallelism on Deep Learning Accelerators with iTex Tessellation

Jianxing Xu, Yuanbo Wen, Zikang Liu, Ruibai Xu, Tingfeng Ruan, Jun Bi and 9 others

A modern chip running a neural network has several different kinds of compute unit — scalar, vector, and the big tensor engine — that can all work at once, but today's deep-learning compilers map the whole computation onto one kind of instruction, so the other units sit idle; this paper (Institute of Computing Technology, CAS) proposes Mosaic, which instead tiles a tensor computation like a mosaic out of different-shaped pieces, each covered by a different instruction, so scalar, vector, and tensor units run in parallel — and because it keeps units busy that a single-unit mapping would leave idle, it can even push past the tensor engine's own theoretical peak, reaching up to 106 percent of it.

The argument in one glance

Problem

A chip has several kinds of compute unit, but the compiler feeds only one

The chips that run neural networks — CPUs, GPUs, dedicated deep-learning accelerators — are not made of one uniform sea of arithmetic. They contain several different kinds of computing unit: scalar units that do one operation at a time, vector units that do the same operation across a row of values, and tensor units (like a GPU tensor core) that do a whole small matrix multiply in one instruction. These units can all run at the same time. But a deep-learning compiler, whose job is to turn a tensor computation like a matrix multiply into hardware instructions, typically maps the entire computation onto one kind of instruction — usually the biggest, the tensor unit — so the scalar and vector units sit idle while the tensor unit works. The hardware offers parallel compute resources of different kinds, and the software uses essentially one of them at a time, leaving performance on the table that only comes from running the different units together.
What people did

Tile the computation top-down and map each tile to one instruction

The standard approach is a top-down, tiling-based compiler: recursively split the big tensor computation into smaller tiles until each tile fits a hardware instruction, then map those tiles to that instruction. It is systematic and effective for filling one unit.
Why it fell short

Top-down tiling gives a homogeneous, single-unit mapping

Because the tiling splits the computation into uniform pieces that all match the same target instruction, the result is a homogeneous mapping: the whole task runs on one class of unit. This never harnesses the different units simultaneously, so it cannot exploit the instruction-level parallelism available from running scalar, vector, and tensor instructions at once. The peak throughput a single unit can reach becomes the ceiling, even though the chip as a whole can do more if its units work together — and reaching that combined throughput needs a mapping that deliberately mixes instructions, which top-down uniform tiling does not produce.
This paper's idea

Tessellate the computation with a mix of instructions, bottom-up

Mosaic is a bottom-up, tessellation-based compiler: instead of splitting the task into uniform tiles for one instruction, it tessellates the tensor computation like a mosaic out of differently-shaped pieces, each covered by a different instruction, forming a heterogeneous instruction-to-task mapping that spreads the work across scalar, vector, and tensor units at once. Enabling this is the iTex abstraction, which formalizes what each instruction computes as affine functions, so the compiler can reason about how to cover the task with varying instructions. A heuristic generates tessellation plans, and an iTex scheduler orders the instructions to reduce hardware conflicts and maximize the parallelism — even exceeding a single unit's peak throughput.

Why this problem is worth solving

The waste here is structural: the hardware’s parallelism is real, and the compiler simply does not reach for it.

A modern processor for deep learning contains several distinct kinds of arithmetic unit that can operate concurrently. Scalar units perform a single operation on single values; vector units apply one operation across a lane of many values at once; and tensor units perform a dense matrix operation — a small matrix multiply-accumulate — in a single instruction, which is why they dominate deep-learning throughput. Crucially, these units are separate pieces of hardware, so a scalar, a vector, and a tensor instruction can be in flight simultaneously. That simultaneous use of different units is a form of instruction-level parallelism: extra work accomplished per cycle not by making one unit faster but by keeping several busy at once. If a computation can be split so that some of it runs on the tensor unit while other parts run on the vector and scalar units in parallel, the effective throughput can surpass what the tensor unit alone could deliver. Exploiting this requires a mapping that assigns different parts of the computation to different instructions, which is exactly what conventional single-target mappings fail to produce.

The reason conventional compilers miss it is the direction they reason from.

Deep-learning compilers traditionally map a tensor computation to hardware by top-down tiling: they take the whole computation and recursively divide it into smaller and smaller tiles until each tile matches the shape of a single chosen hardware instruction, then emit that instruction for every tile. This is clean and it fills one unit well, but by construction it produces a homogeneous mapping — every tile targets the same instruction, so the whole task runs on one class of unit. Tessellation reverses the direction. Rather than dividing down toward one instruction, it builds the covering up from the instructions themselves, fitting differently-shaped pieces — each corresponding to a different instruction, whether scalar, vector, or tensor — together to cover the computation like tiles in a mosaic. The covering is heterogeneous by design, so different regions of the same computation are assigned to different units. The shift from top-down uniform tiling to bottom-up mixed tessellation is what makes it possible to use the chip’s several units together instead of one at a time.

What people did before, and where it broke

Top-down tiling-based deep-learning compilers. Recursively split a tensor computation into uniform tiles matched to a single hardware instruction and emit that instruction throughout. Where it broke. The mapping is homogeneous, running the whole task on one class of unit, so it cannot use scalar, vector, and tensor units simultaneously and forfeits the cross-unit instruction-level parallelism.
Hand-tuned vendor libraries. Rely on expert-optimized kernels from the hardware vendor for common operations. Where it broke. These are highly optimized but still generally drive one dominant unit per kernel; the paper reports Mosaic beating them, indicating the simultaneous-units opportunity is left unexploited even by hand-tuned code.
Target the tensor unit alone for peak throughput. Since the tensor unit has the highest peak, map everything to it and treat its peak as the goal. Where it broke. The tensor unit’s peak is a ceiling only if it works alone; leaving the vector and scalar units idle caps throughput below what the whole chip could produce with them running in parallel.
Schedule instructions without a formal model of what each covers. Try to interleave different instructions ad hoc to fill idle units. Where it broke. Without a precise abstraction of what region of the computation each instruction computes, it is hard to generate a valid heterogeneous covering or to schedule it to avoid the hardware conflicts that arise when mixed instructions contend for resources.
The gap. No compiler both produced a heterogeneous instruction-to-task mapping — covering a tensor computation with a mix of scalar, vector, and tensor instructions — and formalized instruction semantics well enough to generate and schedule such coverings efficiently. That combination is what Mosaic introduces to actually harness the chip’s parallel units together.

How Mosaic works

From a tensor task to a scheduled heterogeneous tessellation

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Cover the computation with a mosaic of different instructions, not uniform tiles. The root of the missed parallelism is that top-down tiling divides a computation down toward a single instruction shape, guaranteeing a homogeneous, one-unit mapping. Mosaic inverts the direction: it builds the covering bottom-up from the instructions, fitting differently-shaped pieces — each a scalar, vector, or tensor instruction — together to tile the whole task, like the tiles of a mosaic. Because the pieces come from different instruction types, the covering is heterogeneous by construction, assigning different regions of the same computation to different units so they run in parallel. Deliberately spreading a neural-network computation across the several kinds of unit a chip provides, rather than funneling it all through the one dominant unit, is the same use-everything instinct the tandem-processor work covered elsewhere on this site is built on, engaging the units that a tensor-only mapping would leave idle so the whole computation moves faster than the marquee unit alone allows.

Formalize what each instruction computes so coverings can be generated and reasoned about. A heterogeneous tessellation is only possible if the compiler knows precisely what region of a tensor computation each instruction covers and how those regions fit together — otherwise mixing instructions is guesswork. Mosaic’s enabling abstraction, iTex, supplies this by modeling the relationship between an instruction’s operation and its semantics with formalized affine functions, giving a uniform, mathematical description of every instruction’s footprint over the computation. On top of that abstraction, a heuristic generates candidate tessellation plans efficiently instead of exhaustively searching. Building a formal, affine abstraction of hardware operations so a compiler can map a tensor computation onto them systematically is the same principled-abstraction approach the tensor-computation IR work covered elsewhere on this site relies on, giving the compiler a precise language for how a computation lands on hardware rather than leaving the mapping to ad hoc rules.

Schedule the mixed instructions so the units actually overlap. Producing a heterogeneous covering is not enough; if the mixed instructions collide over shared hardware resources, the units stall instead of overlapping and the parallelism evaporates. Mosaic’s iTex scheduling technique orders the instructions of a tessellation to reduce these structural hazards, arranging the scalar, vector, and tensor instructions so they run concurrently rather than contending, which is what turns a heterogeneous mapping into actual instruction-level parallelism — and lets the combined throughput exceed any single unit’s peak. Carefully scheduling a computation so that diverse hardware resources stay busy together, rather than serializing on contention, is the same orchestration discipline the schedule-language work covered elsewhere on this site is built on, treating how operations are ordered and overlapped as a first-class lever for wringing performance out of the hardware.

Following a matrix multiply through Mosaic

Tessellating a layer's matrix multiply across units

A conceptual walk, based on the paper's abstract, of how Mosaic covers one tensor computation with mixed instructions and runs the units in parallel. Internal details of the iTex formalization and heuristic come from the paper body, which was not available for this draft.

Step 1 of 5

Describe each instruction with iTex

For the target chip, Mosaic models each instruction — the tensor matrix-multiply, the vector operation, the scalar operation — as affine functions capturing exactly what part of a tensor computation it performs. This gives a uniform description the compiler can compose.

The affine formalization is what lets differently-shaped instruction footprints be fit together validly.

Why it works

A heterogeneous covering uses units a uniform tiling leaves idle. Top-down tiling maps everything to one instruction, so only one unit works → but tessellating the task with mixed instructions assigns regions to scalar, vector, and tensor units → so previously idle units contribute and the combined throughput rises above a single unit’s.
An affine abstraction makes mixing instructions systematic. Composing different instruction footprints is intractable without knowing exactly what each computes → but iTex formalizes each instruction’s semantics as affine functions → so the compiler can generate valid heterogeneous coverings rather than guessing at how instructions fit together.
A heuristic keeps the huge plan space tractable. There are enormous numbers of ways to tessellate a computation with mixed instructions → but a heuristic efficiently generates and selects promising tessellation plans → so Mosaic finds good multi-unit mappings without exhaustive search.
Scheduling turns a mapping into real overlap. A heterogeneous mapping stalls if its instructions contend for the same resource → but the iTex scheduler orders them to reduce structural hazards → so the units execute concurrently and the exploitable instruction-level parallelism is actually realized.
Combining units breaks the single-unit ceiling. The tensor unit’s peak bounds throughput only when it runs alone → but adding vector and scalar work in parallel stacks their throughput on top → so Mosaic can reach up to 106 percent of the tensor core’s theoretical peak, beating even hand-tuned vendor libraries.

What it costs (trade-offs and scope)

This is a draft written without the paper’s main text. The full paper was behind a publisher access wall for this draft (the ACM PDF was not retrievable, and there is no preprint), so this account is built from the paper’s abstract. The reported numbers — the 1.08-to-1.28-times and 1.34-times speedups and the 106 percent of tensor-core peak — are the abstract’s own; the internal iTex affine formalization, the tessellation heuristic, and the scheduling algorithm are not reproduced here and should be read from the paper.
The gains are real but modest on average. Average speedups of 1.08 to 1.28 times over highly optimized vendor libraries, and 1.34 times over the best baselines on LLM operators, are meaningful given how tuned those baselines are, but they are incremental rather than transformative; the headline 106 percent of tensor-core peak is an upper-end result, not the typical case.
The benefit depends on there being idle units and suitable work. Tessellation helps when a computation leaves scalar or vector units underused alongside the tensor unit and can be partitioned to fill them; computations that already saturate the tensor unit, or that do not decompose into pieces suited to the other units, have less to gain from the heterogeneous mapping.
It adds compiler complexity and a scheduling burden. Generating tessellation plans and scheduling mixed instructions to avoid structural hazards is more complex than uniform tiling; the heuristic keeps it tractable, but the approach is heavier than a single-target mapping and its effectiveness depends on the heuristic and scheduler choosing well.
Evaluation spans several platforms and operators, but is still bounded. The results cover multiple hardware platforms, vendor-library comparisons, and real operators extracted from large language models; this is a solid demonstration, but the magnitude of benefit will vary with the specific chip’s unit mix, the operator, and how well the iTex model captures the target’s instructions.

The evaluation

Mapping a tensor computation to a multi-unit chip

Property	Top-down tiling	Vendor library
Instruction-to-task mapping
Units used simultaneously
How the mapping is built		Expert-written kernels
Throughput ceiling		Near single unit's peak
Reported speedup	Baseline	Highly optimized baseline

A comparison based on the paper's abstract; the paper's main body, including the iTex formalization, the tessellation heuristic, and the scheduling algorithm, was not available for this draft. The speedups and the 106-percent-of-peak figure are the abstract's reported results across multiple hardware platforms and real LLM operators.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This is an honest draft assembled from the paper’s abstract; the full text was not accessible, so the internal design — how iTex formalizes instruction semantics with affine functions, how the heuristic generates tessellation plans, and how the iTex scheduler reduces structural hazards — is not reproduced, and no numbers beyond the abstract’s own have been introduced. What is solid is the core idea: modern deep-learning chips have scalar, vector, and tensor units that can run in parallel, but top-down tiling compilers produce a homogeneous mapping that uses one unit at a time; Mosaic instead tessellates a tensor computation bottom-up with a mix of instructions, forming a heterogeneous mapping that spreads work across units, enabled by the iTex abstraction and an iTex scheduler that reduces hazards. The reported results are average speedups of 1.08 to 1.28 times over highly optimized vendor libraries, 1.34 times over the best baselines on real LLM operators, and up to 106 percent of the GPU tensor core’s theoretical peak. Read that within its scope: the average gains are incremental, the benefit depends on there being idle units and decomposable work, the approach adds compiler and scheduling complexity, and the effectiveness rests on how well iTex models a given chip. Within those bounds, Mosaic is a clean idea — cover the computation with a mosaic of instructions so the whole chip works at once — and the fact that it can exceed a single unit’s peak is a striking validation.

Background

Why squeezing every unit matters for deep learning

It helps to see why a few percent of extra throughput is worth a new compiler. Deep-learning models, and large language models most of all, are enormously expensive to run: their operators execute trillions of arithmetic operations, and at the scale these models are deployed, the cost is measured in data-center-fulls of accelerators and correspondingly vast amounts of energy and money. In that regime, the throughput a chip actually sustains, versus what it could in principle deliver, translates almost directly into how much hardware and power a workload needs, so even modest improvements in utilization compound into large savings. This is why so much effort goes into keeping the expensive units of an accelerator busy — an idle tensor core or an underfed vector unit is wasted capacity that someone is paying for. That world, where extracting the last increments of achievable throughput from deep-learning accelerators is a first-order concern, is the same one the attention-dataflow optimization work covered elsewhere on this site operates in, restructuring how a model’s heaviest operators move data so the compute units stay fed. Mosaic attacks the same waste from the mapping side: if the chip has several kinds of unit, use them all at once, rather than leaving most of the silicon idle while one unit carries the load.

If you remember only three things

1. Chips that run neural networks contain several kinds of compute unit — scalar, vector, and tensor (like a GPU tensor core) — that can execute in parallel, but conventional top-down tiling-based deep-learning compilers produce a homogeneous mapping that translates the whole tensor computation into one kind of instruction, running it on one class of unit and leaving the others idle, which caps throughput at a single unit's peak and forfeits cross-unit instruction-level parallelism.
2. Mosaic is a bottom-up tessellation-based compiler that covers a tensor computation like a mosaic out of differently-shaped pieces, each corresponding to a different instruction, forming a heterogeneous instruction-to-task mapping that spreads the work across scalar, vector, and tensor units simultaneously; it is enabled by the iTex abstraction, which formalizes each instruction's operation and semantics as affine functions, a heuristic that efficiently generates tessellation plans, and an iTex scheduling technique that orders instructions to reduce structural hazards and maximize the exploitable parallelism.
3. Across multiple hardware platforms Mosaic reports average speedups of 1.08 to 1.28 times over highly optimized vendor libraries and 1.34 times over the best baselines on real operators from large language models, and it reaches up to 106 percent of the GPU tensor core's theoretical peak throughput — surpassing a single unit's ceiling by using the others in parallel. This explainer is a draft from the abstract without the paper body, so the iTex formalization, the tessellation heuristic, and the scheduler should be confirmed against the paper.

Check yourself

Check your understanding

1. Why do conventional deep-learning compilers underuse a chip's compute units?
2. What does Mosaic do differently, and what does "tessellation" mean here?
3. What is the iTex abstraction and why is it needed?
4. What did Mosaic achieve, and how should the results be read?

Sources

The paper is “Mosaic: Exploiting Instruction-Level Parallelism on Deep Learning Accelerators with iTex Tessellation” by Jianxing Xu, Yuanbo Wen, Zikang Liu, Ruibai Xu, Tingfeng Ruan, Jun Bi, Rui Zhang, Di Huang, Xinkai Song, Yifan Hao, Xing Hu, and Zidong Du (Institute of Computing Technology, Chinese Academy of Sciences, and collaborators), published at ASPLOS 2025 (Volume 2), DOI 10.1145/3676641.3716262.

This explainer is a draft. The full paper text was not accessible at the time of writing (the ACM Digital Library PDF returned a bot-verification challenge, there is no arXiv version, and no openly accessible author copy was found), so it is written from the paper’s abstract. The abstract supplies the problem framing (deep learning’s high computational cost, and that commodity hardware such as CPUs and GPUs offers scalar, vector, and tensor units that can execute in parallel, while existing top-down tiling-based deep-learning compilers generate a homogeneous mapping from the tensor computation to hardware arithmetic instructions and so fail to use different computing units simultaneously), the core technique (Mosaic, a bottom-up tessellation-based compiler that directly tessellates the tensor computation with varying instructions to form a heterogeneous instruction-to-task mapping exploiting instruction-level parallelism across units; the iTex abstraction that models the relationship between instruction operations and their semantics with formalized affine functions; a heuristic approach to efficiently generate tessellation plans; and an iTex scheduling technique that orchestrates instruction execution to reduce structural hazards and maximize exploitable parallelism), and the reported results (average speedups ranging from 1.08 to 1.28 times across multiple hardware platforms compared to highly optimized vendor libraries, an average speedup of 1.34 times over the best existing baselines on real-world operators extracted from large language models, and reaching up to 106 percent of the GPU tensor core theoretical peak throughput). The paper’s detailed iTex formalization, tessellation heuristic, and scheduling algorithm are not reproduced here and should be read from the paper; no numbers beyond the abstract’s have been introduced.