MINIMIZING THE SCHEDULE LENGTH FOR A PARALLEL 3D-GRID PRECEDENCE GRAPH

We consider in this paper an extension of the complexity analysis of p arallel algorithms on MIMD computers which takes into account the over head, defined as the tradeoff between the communications and the idle time. We propose a series of parallel algorithms for scheduling a 3-di mensional grid precedence graph of size n with O(n) processors. First, we compute a lower bound of the overhead and we present two simple al gorithms, easy to implement, with an overhead of O(n(9/4)) and O(n(2)) respectively. Then by exploiting the underlying ideas of these schedu les, we derive a better algorithm with an overhead O(n(5/3)). Finally, we extend this analysis by considering the case of communications pro portional to the amount of exchanged data.