A period-processor-time-minimal systolic array for cubical mesh algorithms
Chris J. Scheiman, Peter R. Cappello · 2002
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/sup 2//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.>