Coauthors: Mostafa El Daoudi and Denis Trystram

We are interested in this work in scheduling precedence task graphs which have the special structure of two dimensional grids. They correspond to the parallel execution of a large class of applications in Linear Algebra through manipulations of operations on matrices. The general problem of scheduling any graph with explicit large communication delays is known to be hard and there is no efficient approximation algorithm for solving the problem. We consider the delay model under the 1-port assumption where the communications between the machines are sequential. As the structure of the graph is restricted to regular 2D-grids, we exhibit a lower nound and a ploynomial time algorithm that reaches this bound for any number of machines.