Provably Efficient Online Batch Scheduling for Deep Learning Inference

Graphics processing units (GPUs) are widely used to enhance deep learning inference throughput through batch processing, where multiple inference requests are processed simultaneously. When inference requests arrive randomly, waiting for more requests to form a batch can improve throughput but increases latency. Therefore, designing efficient batch scheduling strategies is crucial to strike a good balance. Current batch scheduling strategies are primarily heuristic and non-preemptive, meaning the next batch is scheduled only after the current one completes. In this paper, we first demonstrate that no non-preemptive online batch scheduling algorithm can achieve a constant competitive ratio that does not depend on system configuration parameters. We further propose a preemption restart based online batch scheduling algorithm, and theoretically prove that it achieves a constant competitive ratio. Finally, we demonstrate the effectiveness of our proposed algorithm through extensive simulations.