Gamify Stencil Dwarf on Cloud for Democratizing Scientific Computing

Mao Yang 杨懋, Kun Li, Zhichun Li, Yuetao Chen, Zixuan Wang, Yiwei Zhang, Liang Yuan, Haipeng Jia, Yunquan Zhang, Ting Cao, Mao YangarXiv 2023 · DOI · arXiv

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.

Overview of the Tetris system architecture across CPU and GPU memory hierarchies.

The system operates through three primary components:

  1. 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.
  2. Locality Enhancer (Cache/SMEM-level): Implements "Tessellate Tiling" and "Checkerboard Blocking" to maximize data reuse within fast on-chip memory.
  3. Pattern Mapping (Register-level):
    • On CPUs, "Vector Skewed Swizzling" resolves data alignment conflicts in SIMD registers.
  4. 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.

Mapping Star-2D9P stencil operations to Matrix Multiplication for FP64 on Tensor Cores.

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

Abstract

Stencil computation is one of the most important kernels in various scientific computing. Nowadays, most Stencil-driven scientific computing still relies heavily on supercomputers, suffering from expensive access, poor scalability, and duplicated optimizations. This paper proposes Tetris, the first system for high-performance Stencil on heterogeneous CPU+GPU, towards democratizing Stencil-driven scientific computing on Cloud. In Tetris, polymorphic tiling tetrominoes are first proposed to bridge different hardware architectures and various application contexts with a perfect spatial and temporal tessellation automatically. Tetris is contributed by three main components: (1) Underlying hardware characteristics are first captured to achieve a sophisticated Pattern Mapping by register-level tetrominoes; (2) An efficient Locality Enhancer is first presented for data reuse on spatial and temporal dimensions simultaneously by cache/SMEM-level tetrominoes; (3) A novel Concurrent Scheduler is first designed to exploit the full potential of on-cloud memory and computing power by memory-level tetrominoes. Tetris is orthogonal to (and complements) the optimizations or deployments for a wide variety of emerging and legacy scientific computing applications. Results of thermal diffusion simulation demonstrate that the performance is improved by 29.6x, reducing time cost from day to hour, while preserving the original accuracy.
BibTeX
@misc{2023gamify,
  author = {Mao Yang 杨懋 and Kun Li and Zhichun Li and Yuetao Chen and Zixuan Wang and Yiwei Zhang and Liang Yuan and Haipeng Jia and Yunquan Zhang and Ting Cao and Mao Yang},
  title = {{Gamify Stencil Dwarf on Cloud for Democratizing Scientific Computing}},
  year = {2023},
  eprint = {2303.08365},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.08365},
}
Figure