TL;DR
This paper introduces STANNIC, a novel hardware accelerator designed to efficiently schedule tasks on complex, heterogeneous computing systems. By leveraging a systolic array architecture and a schedule-centric approach, STANNIC significantly outperforms previous hardware solutions and even software implementations in terms of speed, scalability, and resource efficiency, making it ideal for demanding HPC environments.
What Problem Does This Paper Address?
Modern High-Performance Computing (HPC) systems are increasingly heterogeneous, featuring a mix of CPUs, GPUs, FPGAs, and other specialized processors. Efficiently scheduling tasks onto these diverse resources is a critical challenge. Traditional software-based schedulers struggle with the inherent stochasticity (unpredictability) of job arrivals and processing times, leading to high overhead, poor adaptability, and suboptimal resource utilization. This problem is exacerbated in shared HPC clusters where job characteristics are often unknown in advance or change dynamically. Existing hardware acceleration approaches, while promising, have limitations in terms of scalability and efficiency. This paper aims to address these challenges by proposing STANNIC, a more efficient and scalable hardware scheduler.
Methods
The core of the paper lies in the development of STANNIC, a hardware accelerator built upon the Stochastic Online Scheduling Algorithm (SOSA). STANNIC represents a significant architectural shift from its predecessor, HERCULES.
- Schedule-Centric Abstraction: Unlike HERCULES's task-centric approach, STANNIC adopts a schedule-centric abstraction. This focuses on the persistent elements of the scheduling process (virtual schedules) rather than transient job data, leading to more efficient memory management and reduced routing congestion.
- Systolic Array Architecture: STANNIC utilizes a one-dimensional systolic array. Each Processing Element (PE) in the array tracks a single job within a machine's virtual schedule and its associated cost attributes. This allows for parallel processing and efficient data movement.
- Optimized Cost Calculation: STANNIC leverages the ordered nature of the systolic array to precalculate and memorize summation terms for cost calculation. This eliminates the iterative summation latency found in previous approaches, enabling single-cycle lookups.
- Decentralized to Centralized Design: STANNIC consolidates the decentralized memory management and virtual schedule management components of HERCULES into a centralized Systolic Memory Management Unit (SMMU) per machine. This reduces inter-component communication and routing congestion.
- Quantization: The SOS algorithm is implemented using INT8 precision, balancing performance gains with minimal accuracy loss in scheduling decisions.
Datasets
Not discussed in the paper. The paper focuses on synthetic workload generation for evaluation.
Key Insights and Ideas
- Schedule-Centricity is Key for Scalability: Shifting from a task-centric to a schedule-centric view, combined with a systolic array, dramatically improves scalability and reduces routing congestion.
- Systolic Arrays Enable Efficient Parallelism: The systolic architecture allows for parallel cost calculation and virtual schedule maintenance, significantly reducing iteration latency.
- Pre-calculation and Memoization are Crucial: By pre-calculating summation terms for cost calculations, STANNIC avoids iterative computations, leading to substantial speedups.
- Consolidation Reduces Overhead: Unifying memory management and virtual schedule management into a centralized SMMU per machine streamlines operations and reduces hardware complexity.
- INT8 Precision is a Sweet Spot: Using INT8 precision for the SOS algorithm provides a significant performance boost with negligible impact on scheduling accuracy.
Key Results
- Iteration Latency Reduction: STANNIC achieves an average of 7.5x reduction in iteration latency compared to HERCULES (62 cycles vs. 466 cycles).
- Resource Efficiency: STANNIC uses less than half the hardware resources (LUTs and FFs) compared to HERCULES for equivalent configurations (2.24x reduction in LUTs, 2.1x reduction in FFs).
- Scalability Improvement: STANNIC can scale to schedule for systems that are 14 times larger than HERCULES (140 machines vs. 10 machines).
- Speedup over Software: STANNIC achieves a speedup of up to 1968x over a C/C++ baseline software implementation.
- Power Efficiency: Both HERCULES and STANNIC are power-efficient, consuming approximately 20.5W, with STANNIC maintaining this efficiency at larger scales.
- Robustness: SOSA (and thus STANNIC) demonstrates effectiveness and adaptability across various workloads, including memory-skewed, compute-skewed, and homogeneous scenarios, while maintaining good fairness and load balancing.
Limitations and Future Work
- Heuristic Boundaries: The paper notes that Vitis HLS encountered routing difficulties for certain mid-range configurations due to heuristic boundaries, leading to performance loss in those specific cases.
- Full Virtual Schedules: The paper mentions that full virtual schedules (where all PEs are occupied) cannot accept new jobs without losing data from the tail PE.
- Future Work: The paper implies that further exploration of different systolic array configurations and optimizations for specific hardware platforms could yield additional improvements. The authors also suggest that the demonstrated efficiency of STANNIC makes it a strong candidate for future research in areas like deep learning and scientific workloads with high variability.
Summary updated