Scheduling policies to support distributed 3D multimedia applications

We consider the problem of scheduling the rendering component of 3D multimedia applications on a cluster of workstations connected via a local area network. Our goal is to meet a periodic real-time constraint. In abstract terms, the problem we address is how best to schedule tasks with unpredictable service times on distinct processing nodes so as to meet a real-time deadline, given that all communication among nodes entails some (possibly large) overhead. We consider two distinct classes of schemes, static, in which task reallocations are scheduled to occur at specific times, and dynamic, in which reallocations are triggered by some processor going idle. For both classes we further examine both global reassignments, in which all nodes are rescheduled at a rescheduling moment, and local reassignments, in which only a subset of the nodes engage in rescheduling at any one time. We show that global dynamic policies work best over a range of parameterizations appropriate to such systems. We introduce a new policy, Dynamic with Shadowing, that places a small number of tasks in the schedules of multiple workstations to reduce the amount of communication required to complete the schedule. This policy is shown to dominate the other alternatives considered over most of the parameter space.