A period-processor-time-minimal schedule for cubical mesh algorithms
Chris J. Scheiman, Peter R. Cappello · IEEE Transactions on Parallel and Distributed Systems · 1994
Using a directed acyclic graph (dag) model of algorithms, we investigate precedence-constrained multiprocessor schedules for the n/spl times/n/spl times/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 3/sup n/spl minus/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 /spl lsqb/3n/sup 2//4/spl rsqb/ 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 3/sup n/2/ steps. This lower bound is shown to be exact 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/spl times/n/2/spl times/3 mesh.>