OPTIMAL SCHEDULES FOR D-D GRID GRAPHS WITH COMMUNICATION DELAYS

We consider a task graph model taking into account the communication a mong tasks of a parallel system. First, we assume that the available n umber of processors is adequate for dealing with the whole width of th e task graph (i.e. the number of processors is unbounded), and we prop ose a scheduling strategy, called Line-Schedule, which executes the ta sks of a d-dimensional grid graph (d-D grid in short) in the optimal t ime. We continue by proving that Line-Schedule is the only strategy ab le to execute a d-D grid in the optimal time. Furthermore, we compute the minimum number of processors required to execute a d-D grid optima lly. (C) 1998 Elsevier Science B.V. All rights reserved.