Dynamic on-line task scheduling on parallel processors

The problem of scheduling on-line a stream of multi-tasked jobs on a set of parallel processors is considered. The goal is to minimize the average soj ourn time experienced by each individual job in the system. The arriving jo bs are comprised of parallel applications, each consisting of multiple inde pendent tasks that are instantaneously assigned to processor queues upon it s arrival to the system. The processors independently and concurrently serv ice the tasks in their local queues which are first-come-first-served (FCFS ). A job can depart from the system only when ail its tasks have been execu ted and reassembled into the original single-job structure; until then, com pleted tasks are placed in a reassembly queue. All tasks have i.i.d. memory less exponential service times and any task can be processed by any process or. Migration of tasks between queues after their initial allocation-is not allowed. This model captures the main features of multiprocessor computer systems executing parallel programs. The key scheduling issue is as follows. When some queue backlogs are small, an incoming job should spread its tasks to those lightly loaded queues in order to take advantage of the parallel processing gain and lower its proce ssing delay. On the other hand, when all queues are fairly congested, the j ob should schedule all its tasks sequentially in a single queue to avoid ex cessive reassembly delay (due to backlog fluctuations) and lower its task s ynchronization delay. In this paper, the trade-off between these two object ives is quantified and it is shown that the optimal schedule's structure is based on backlog thresholds. Moreover, an off-line mechanism for determini ng these thresholds is provided, and further characteristics of the optimal scheduling policy under special cases is discussed. Finally, asymptotics a nd approximations for systems comprised of a large number of processors are considered. (C) 2001 Elsevier Science B.V. All rights reserved.