Scheduling UET grids with unit communication time delays into unbounded/fixed number of processors
Panayiotis D. Tsanakas, T. Andronikos, Nectarios Koziris, G. Papakonstantinou · WIT Press eBooks · 2001
The n-dimensional grid is one of the most representative patterns of data flow in parallel computation. Many scientific algorithms, especially nested loops, which require nearest-neighbor communication in a lattice space, are modeled by a task graph or iteration space with the properties of a grid. We consider the nested loop model with unit dependencies thus having an iteration space with the form of a n-dimensional grid. The exact model is that of generalized grids with diagonal edges, allowing unequal boundaries for each dimension. We survey the optimal time scheduling techniques for UET-UCT (unit execution time - unit communication time) grid topologies, using unbounded and bounded number of processors, without allowing task duplication. UET-UCT scheduling of generalized n-dimensional grids is low complexity tractable.