TL;DR
WaferTetris introduces "freeform mapping" for wafer-scale accelerators, moving away from rigid rectangular layouts to flexible, Tetris-like placements of processing elements (PEs). By leveraging adapted FPGA place-and-route algorithms and a novel recurrence-based performance model, it achieves up to $4.42\times$ higher throughput and nearly doubles the supported context length for large language models (LLMs) on the Cerebras WSE-3.
What Problem Does This Paper Address?
Wafer-scale engines (WSEs), like those from Cerebras, are massive chips containing hundreds of thousands of PEs on a single silicon wafer. To run an application, developers must "map" the compute graph onto this grid. Traditionally, this is done using template-based mapping, where each operation (like a matrix multiplication) is assigned to a fixed rectangular "island" of PEs.
The problem is spatial fragmentation. Just like a game of Tetris where you can't fit a square block into a jagged hole, these rigid rectangles often leave many PEs idle because the available empty space doesn't match the required dimensions. This wasted space isn't just lost compute; it's lost memory. Since each PE has its own local SRAM, fragmentation limits the total memory available to the application, often leading to "Out of Memory" (OOM) errors for large models even when the wafer has enough total capacity.
Methods
The authors present WaferTetris, a system that treats the wafer as a flexible fabric rather than a collection of boxes. Its core components include:
- Freeform Mapping: Instead of forcing operations into rectangles, WaferTetris allows them to take any shape. This enables "Tetris-like" packing that fills gaps and maximizes PE utilization.
- Recurrence-Based Throughput Model: Traditional mappers often use a "slowest-unit" proxy, assuming the bottleneck is simply the operation that takes the longest. WaferTetris recognizes that in complex graphs with branches and joins (like Transformer layers), dependencies matter more. It uses a timed-graph model to calculate the Maximum Cycle Mean (MCM), providing a much more accurate prediction of steady-state pipeline throughput.
- WSE-to-FPGA Architecture Model: To solve the massive placement and routing problem, the authors adapted mature FPGA Place-and-Route (P&R) tools (specifically VTR). They created a custom architecture model that translates WSE constraints—like the limited number of "colors" (virtual channels) available for routing—into standard FPGA congestion constraints using a novel "color-gate" bank at each PE.
Datasets
The system was evaluated on the Cerebras WSE-3 using two primary benchmark groups:
- LLM Decoding: Models included LLaMA3.1-8B, LLaMA2-13B, and Qwen2.5-7B. These were tested at various sequence lengths (1k to 80k tokens).
- Scientific Stencils: Two classic high-performance computing benchmarks: Gray-Scott (reaction-diffusion) and Elastic Wave propagation.
Key Insights and Ideas
- The "Square Peg" Insight: The authors realized that the primary bottleneck in wafer-scale computing wasn't the code itself, but the geometric constraints of the layout. By decoupling the logical task from its physical shape, they unlocked "stranded" resources.
- FPGA Algorithms are a Natural Fit: WSEs and FPGAs share a fundamental challenge: mapping a logical netlist onto a 2D grid with finite routing resources. By modeling WSE "colors" as FPGA "routing tracks," they could reuse decades of optimization research.
- Recurrence over Bottlenecks: Figure 3 illustrates a key "aha" moment: a single slow unit might not be the bottleneck if it's not on the critical recurrence path. Modeling the whole graph's timing is essential for finding the best spatial parallelism.
Key Results
- Throughput Gains: For LLM decoding, WaferTetris achieved $3.24\times$ to $4.42\times$ the system throughput of the template-based baseline (CU.POKer) on the same fabric size.
- Memory/Context Scaling: On LLaMA3.1-8B, WaferTetris supported a context length of 80k tokens, compared to only 44k for the manually optimized WaferLLM—a $1.8\times$ improvement.
- High Utilization: WaferTetris consistently achieved over 93% PE utilization, whereas traditional methods often hovered between 50% and 85% due to fragmentation.
- Efficiency: The entire mapping and compilation flow for a large model like LLaMA2-13B takes only about 37 minutes, making it practical for real-world deployment.
Limitations and Future Work
- Partition Scheduling: Currently, the user must define the "mapping units" (which operations to group together). The authors suggest a future "partition scheduler" could automate this choice to further optimize communication.
- Fault Tolerance: While the paper mentions that freeform mapping could theoretically "flow" around manufacturing defects (dead PEs) on the wafer, this was not explicitly implemented or tested in the current work.
- PE Replication: The authors explored "PE replication" (duplicating compute to shorten long communication paths) as a manual optimization in the appendix, noting that automating this within the P&R flow is a promising future direction.
Summary updated