Joint Batching and Scheduling for High-Throughput Multiuser Edge AI with Asynchronous Task Arrivals

Abstract

<p>Edge artificial intelligence (AI) in the sixth-generation networks will provide inference services at the network edge to enrich the capabilities of mobile devices and lengthen their battery lives. As a well-known technique in computing, batching can boost the computation throughput at an edge server by assembling multiple tasks into a batch that is fed into a pre-trained prediction model. This reduces the memory-access frequency and hence accelerates the execution of each task. In this paper, we study joint batching and (task) scheduling to maximise the throughput (i.e., the number of completed tasks) under the practical assumptions of heterogeneous task arrivals and deadlines. The design aims to optimise the number of batches, their starting time instants, and the task-batch association that determines batch sizes. The joint optimisation problem is complex due to multiple coupled variables as mentioned and numerous constraints including heterogeneous tasks arrivals and deadlines, the causality requirements on multi-task execution, and limited radio resources. Our approach of solving the formulated mixed-integer problem is to transform it into a convex problem via integer relaxation method and ℓ₀-norm approximation. This results in an efficient alternating optimization algorithm for finding a close-to-optimal solution. Specifically, it iterates between solving two sub-problems, optimal task-batch association and optimal batch starting time. The former is a linear program whose solution can be found using a derived scheme of greedy task selection while that of the latter is derived in closed form. In addition, we also design the optimal algorithm from leveraging spectrum holes, which are caused by fixed bandwidth allocation to devices and their asynchronized multi-batch task execution, to admit unscheduled tasks so as to further enhance throughput. Simulation results demonstrate that the proposed framework of joint batching and resource allocation can substantially enhance the throughput of multiuser edge-AI as opposed to a number of benchmarking schemes.</p>