Non-Clairvoyant Scheduling for Processing-in-Memory
TL;DR
This work develops a non-clairvoyant scheduling algorithm that does not know task work in advance, yet loses only a small additive term relative to the clairvoyant lower bound, and proves a performance upper bound under uniform random data placement.
Abstract
Processing-in-memory (PIM) is a promising architectural approach to mitigate the high cost of off-chip memory access by enabling (i) low-latency, on-memory-module data access and (ii) aggregate memory bandwidth that scales with the number of modules. To fully exploit the potential of PIM systems, we formulate and study the PIM Scheduling problem, which captures the trade-offs between computation, data movement, and load balancing across a host CPU and multiple PIM modules. We establish fundamental lower bounds on the execution time of any schedule. We then design a non-preemptive clairvoyant algorithm that achieves a constant-factor approximation to the optimal schedule. More importantly, we develop a non-clairvoyant scheduling algorithm that does not know task work in advance, yet loses only a small additive term relative to the clairvoyant lower bound. Besides scheduling based on fixed data placement, we also prove a performance upper bound under uniform random data placement. We evaluate our scheduling algorithms on both an analytical PIM simulator and a real-world 2048-module UPMEM-PIM machine. Both algorithms outperform baselines across various workload settings and hardware regimes, with up to 9.8× speedup in simulation and up to 1.8× speedup on real PIM hardware.