Near-optimal universal scheduling for moldable tasks: the Fair algorithm

Abstract The problem of scheduling moldable tasks on multiprocessor systems with the goal of minimizing the makespan has received significant attention, especially in contexts where tasks have dependence constraints (task graphs) or arrive dynamically (online scheduling). However, the combined setting—online scheduling of moldable task graphs—remains less explored. Prior studies have addressed this problem by designing algorithms specifically tailored to particular speedup models, such as Amdahl, Communication, or Roofline. Although these specialized algorithms achieve constant competitive ratios under their respective models, their applicability is limited in practice: Each requires tasks to adhere to a predefined speedup model. In this paper, we introduce a novel, universal online algorithm capable of handling arbitrary monotonic moldable tasks without assumptions about their speedup behavior. Remarkably, when applied to the specific speedup models previously studied, our algorithm achieves competitive ratios comparable to—or better than—those obtained by the specialized algorithms. For the General and Power Communication models, we further show that the optimal simultaneous time-and-area factor is 2, matching the Amdahl case.