Efficient Task Scheduling Algorithms for Decentralized Large Language Model Serving

Abstract

Large language models (LLMs) have gained enormous popularity for processing and generating text. They are a subset of generative artificial intelligence (GenAI) that require higher availability of graphical processing unit (GPU) resources for inference services. However, making GPU resources available in a centralized infrastructure is quite challenging. Therefore, recent works have focused on decentralized physical infrastructure networks (DePIN) to utilize idle GPU resources, enabling scalable LLM inference services across the decentralized network. These inference services may experience inherent latency (i.e., measured in time per output token (TPOT)) due to communication overhead or time between GPU resources responsible for generating consecutive tokens. The task scheduling algorithm is crucial in decentralized LLM inference services to minimize TPOT and maximize GPU resource utilization, particularly when GPU resources are constrained by computational capacity. This paper introduces two task scheduling algorithms, the improved greedy heuristic shortest path algorithm (IGHSPA) and the dynamic programming-based task scheduling algorithm (DPTSA), for decentralized LLM serving to achieve these objectives. Each task involves assigning a layer to a GPU resource, which IGHSPA and DPTSA accomplish using greedy heuristic and dynamic programming. Both algorithms are extensively simulated and compared with one of the recent algorithms, namely the greedy heuristic shortest path algorithm (GHSPA), in terms of TPOT and execution time (ET). Our simulation results demonstrate that DPTSA improves TPOT up to 47.50% and 35.50% and ET up to 99.95% and 35.00%, compared to GHSPA and IGHSPA.