Optimal parallel execution of complete binary trees and grids into most popular interconnection networks

AbstractWe consider an extension of the well-known PRAM model for parallel distributed-memory computers using local communications. We present scheduling algorithms for the execution of complete binary trees on hypercube, de Bruijn, linear and grid interconnection networks on this model. We also show that a two-dimensional grid precedence graph can be executed in optimal time on all these networks