On scheduling dags for volatile computing platforms: Area-maximizing schedules

摘要

Many modern computing platforms-notably clouds and desktop grids-exhibit dynamic heterogeneity: the availability and computing power of their constituent resources can change unexpectedly and dynamically, even in the midst of a computation. We introduce a new quality metric, area, for schedules that execute computations having interdependent constituent chores (jobs, tasks, etc.) on such platforms. Area measures the average number of tasks that a schedule renders eligible for execution at each step of a computation. Even though the definition of area does not mention and properties of host platforms (such as volatility), intuition suggests that rendering tasks eligible at a faster rate will have a benign impact on the performance of volatile platforms-and we report on simulation experiments that support this intuition. We derive the basic properties of the area metric and show how to efficiently craft area-maximizing {A-M) schedules for several classes of significant computations. Simulations that compare A-M scheduling against heuristics ranging from lightweight ones (e.g., FIFO) to computationally intensive ones suggest that A-M schedules complete computations on volatile heterogeneous platforms faster than their competition, by percentages that vary with computation structure and platform behavior-but are often in the double digits.