On scheduling dags to maximize area

A new quality metric, called area, is introduced for schedules that execute dags, i.e., computations having intertask dependencies. Motivated by the temporal unpredictability encountered when computing over the Internet, the goal under the new metric is to maximize the average number of tasks that are eligible for execution at each step of a computation. Area-maximization is a weakening of IC-optimality, which strives to maximize the number of eligible tasks at every step of the computation. In contrast to IC-optimal schedules, area-maximizing schedules exist for every dag. For dags that admit IC-optimal schedules, all area-maximizing schedules are IC-optimal, and vice versa. The basic properties of this metric are derived in this paper, and tools for efficiently crafting area-maximizing schedules for large classes of computationally significant dags are developed. Several of these results emerge from a close connection between area-maximizing scheduling and the MAX Linear-Arrangement Problem for Dags.