Abstract
Scientific computing relies heavily on stencil computations, a fundamental pattern for modeling complex physical phenomena. Traditionally, these computations require expensive, manually-tuned supercomputers. This paper presents Tetris, a system designed to democratize scientific computing by enabling high-performance stencil execution on heterogeneous Cloud environments. By employing "polymorphic tiling tetrominoes," Tetris optimizes data movement across CPU and GPU hierarchies. Experimental results demonstrate a 29.6× speedup in thermal simulations and a 4.4× improvement over state-of-the-art frameworks, all while maintaining strict FP64 precision.
Introduction
Scientific computing has long been restricted to elite researchers with access to multi-million dollar supercomputers. "Grand Challenges"—such as modeling viral spread or seismic activity—rely on Stencil computation, where grid points are updated based on their neighbors. However, supercomputers are rigid and require hardware-specific tuning that does not translate well to the elastic, heterogeneous nature of the modern Cloud.
The Cloud offers accessible CPU and GPU resources, but it is often "hardware-unfriendly" for traditional scientific code. Stencil kernels have complex dependencies that clash with modern SIMD registers in CPUs and Tensor Cores in GPUs. To bridge this gap, researchers from Microsoft Research and the Chinese Academy of Sciences introduced Tetris, a system that "gamifies" data processing to fit scientific data into Cloud hardware "slots."
Methodology: Polymorphic Tiling Tetrominoes
The core innovation of Tetris is the use of Polymorphic Tiling Tetrominoes. Similar to Tetris blocks, these are flexible data shapes designed to fit perfectly into different levels of the hardware memory hierarchy.
The system operates through three primary components:
- Concurrent Scheduler (Memory-level): Balances workloads between CPU and GPU using "Bidirectional Memory Squeezing" to maximize GPU utilization while offloading remaining tasks to the CPU.
- Locality Enhancer (Cache/SMEM-level): Implements "Tessellate Tiling" and "Checkerboard Blocking" to maximize data reuse within fast on-chip memory.
- Pattern Mapping (Register-level):
- On CPUs, "Vector Skewed Swizzling" resolves data alignment conflicts in SIMD registers.
- On GPUs, "Tensor Trapezoid Folding" adapts stencil operations into the Matrix Multiplication (MM) format required by high-speed Tensor Cores.
Key Insights: The Tensor Core Hack
A pivotal realization in Tetris is that stencil operations can be reformulated as weighted reductions. This allows the system to leverage GPU Tensor Cores—hardware optimized for AI—to accelerate scientific mathematics that was never intended for them.
Furthermore, Tetris employs Spatial-Temporal Tessellation. Instead of tiling data only in space, it tiles in time. By "piling" tetrominoes, the system can update a point multiple times while it remains in the fast cache, significantly reducing slow trips to main RAM.
Evaluation and Results
Tetris was evaluated using a suite of classic Stencil "Dwarfs" (fundamental kernels like Heat-3D and Star-2D9P) and a large-scale thermal diffusion case study.
- Performance: In thermal diffusion simulations, Tetris achieved a 29.6× speedup, reducing computation time from days to hours.
- Comparison: It outperformed state-of-the-art frameworks like AN5D and Pluto by an average of 4.4×.
- Scalability: The system showed nearly linear scaling on the Cloud as CPU cores were added, maintaining efficiency as problem dimensions increased.
- Precision: Unlike AI surrogate models which can introduce precision loss, Tetris maintains the strict FP64 (double precision) accuracy required for scientific rigor.
Conclusion
Tetris provides a blueprint for moving high-end science from specialized supercomputer centers to the accessible infrastructure of the Cloud. While challenges remain in coordination overhead for high-dimensional problems and cluster-scale expansion, the "gamification" of data movement represents a significant step toward democratizing scientific computing.
Summary updated