Optimal schedules for d-D grid graphs with communication delays

摘要

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 processor is adequate for dealing with the whole width of the task graph(i.e. the number of processor in 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 gird in the optimal time. Furthermore, We compute the minimum number of processor required to execute a d-D grid opti- Mally.