Minimizing Stretch and Makespan of Multiple Parallel Task Graphs via Malleable Allocations
Many scientific applications can be structured as Parallel Task Graphs (PTGs), i.e., graphs of data parallel tasks. Adding data-parallelism to a task-parallel application provides opportunities for higher performance and scalability, but poses scheduling challenges. The authors study the off-line scheduling of multiple PTGs on a single, homogeneous cluster. The objective is to optimize performance and fairness. They propose a novel algorithm that first computes perfectly fair PTG completion times assuming that each PTG is an ideal malleable job. These completion times are then relaxed so that the schedule is organized as a sequence of periods and is still close to the perfectly fair schedule.