06097760

j

06097760 Cordasco, Gennaro De Chiara, Rosario Rosenberg, Arnold L. On scheduling {\sc DAGs} for volatile computing platforms: area-maximizing schedules. J. Parallel Distrib. Comput. 72, No. 10, 1347-1360 (2012). 2012 Elsevier Science (Academic Press), San Diego, CA EN scheduling for dynamically heterogeneous platforms {\sc DAG} scheduling cloud computing volunteer computing desktop grids

doi:10.1016/j.jpdc.2012.06.007

Summary: 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.