Minimizing the schedule length for a parallel 3D-grid precedence graph

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