Optimal scheduling for UET/UET-UCT generalized n-dimensional grid task graphs
The ii-dimensional grid is one of the most representative patterns of data now in parallel computation. Many scientific algorithms, which require nearest neighbor communication in a lattice space, are modeled by a task graph with the properties of a simple or enhanced grid. The two most frequently used scheduling models for grids are the unit execution time-zero communication delay (UET) and the unit execution time-unit communication time (UET-UCT). In this paper we introduce an enhanced model of the ii-dimensional grid by adding extra diagonal edges and allowing unequal boundaries for each dimension. For this generalized grid topology we establish the optimal makespan for both cases of UET/UET-UCT grids. Then we give a closed formula that calculates the minimum number of processors required to achieve the optimal makespan. Finally, we propose a low-complexity optimal time and processor scheduling strategy for both cases. (C) 1999 Academic Press.
grids makespan uet-uct scheduling optimal number of processors