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 near est 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 u sed scheduling models for grids are the unit execution time-zero communicat ion delay (UET) and the unit execution time-unit communication time (UET-UC T). In this paper we introduce an enhanced model of the ii-dimensional grid by adding extra diagonal edges and allowing unequal boundaries for each di mension. For this generalized grid topology we establish the optimal makesp an 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.