A New Algorithm for Online Scheduling of Rigid Task Graphs with Near-Optimal Competitive Ratio

This paper addresses the challenges of online scheduling within high-performance computing (HPC) systems, focusing on rigid parallel tasks with precedence constraints organized as a directed acyclic graph (DAG). We introduce an online algorithm, called CATBATCH, which efficiently schedules tasks to minimize the overall completion time, or the makespan. We show that CATBATCH achieves a competitive ratio of log(n) + 3, with n being the number of tasks. Although CATBATCH only discovers tasks on the fly when they are ready, it almost matches the best offline algorithm, which has an approximation ratio of log(n + 1) + 2. We further show that CATBATCH achieves a competitive ratio of log (M/m) + 6, where M and m are the lengths of the longest and shortest tasks, respectively. Consequently, CATBATCH achieves a constant competitive ratio when the number of tasks or the task lengths are bounded. Finally, our analysis indicates the algorithm's near-optimal performance in worst-case scenarios for both metrics, showing that no online algorithm can have a competitive ratio lower than Θ(log(n)) or Θ(log (M/m)) in this context.