Optimal schedules for d-D grid graphs with communication delays

✍ Scribed by E. Bampis; C. Delorme; J.-C. König

• Book ID: 104304649
• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 125 KB
• Volume: 24
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(98)00047-7

✦ Synopsis

We consider a task graph model taking into account the communication among tasks of a parallel system. First, we assume that the available number of processors is adequate for dealing with the whole width of the task graph (i.e. the number of processors is unbounded), and we propose a scheduling strategy, called Line-Schedule, which executes the tasks of a d-dimensional grid graph (d-D grid in short) in the optimal time. We continue by proving that Line-Schedule is the only strategy able 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 optimally.