A period-processor-time-minimal systolic array for cubical mesh algorithms

The paper, using a directed acyclic graph (dag) model of algorithms, investigates precedence constrained multiprocessor schedules for the n×n×n directed mesh. Any such schedule requires at least 3n-2 multiprocessor steps. Time-minimal 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 period-processor-time-minimal. The period of any processor-time-minimal schedule for the cubical mesh is at least 4n/3 steps. This lower bound is shown to be exact by constructing such a schedule, which can be realized on a toroidally-connected systolic array