A period-processor-time-minimal schedule for cubical mesh algorithms

The paper, using a direct acyclic graph (dag) model of algorithms, investigates precedence constrained multiprocessor schedules for the n × n × n directed mesh. This cubical mesh is fundamental, representing the standard algorithm for square matrix product, as well as many other algorithms. Its completion requires at least 3n - 2 multiprocessor steps. Time-minimal multiprocessor schedules that use as few processors as possible are called processor-time-minimal. For the cubical mesh, such a schedule requires at least [3n²/4] processors. Among such schedules, one with the minimum period (i.e., maximum throughput) is referred to as a period-processor-time-minimal schedule. The period of any processor-time-minimal schedule for the cubical mesh is at least 3n/2 steps. This lower bound is shown to be exact by by constructing, for n a multiple of 6, a period-processor-time-minimal multiprocessor schedule that can be realized on a systolic array whose topology is a toroidally-connected n/2 × n/2 × 3 mesh