A processor-time-minimal schedule for 3D rectilinear mesh algorithms

The paper, using a directed acyclic graph (dag) model of algorithms, investigates precedence constrained multiprocessor schedules for the n_x×n_y×n_z directed rectilinear mesh. Its completion requires at least n_x+n_y +n_z-2 multiprocessor steps. Time-minimal multiprocessor schedules that use as few processors as possible are called processor-time-minimal. Lower bounds are shown for the n_x×n_y×n_z directed mesh, and these bounds are shown to be exact by constructing a processor-time-minimal multiprocessor schedule that can be realized on a systolic array whose topology is either a two dimensional mesh or skewed cylinder. The contribution of this paper is two-fold: It generalizes the previous work on cubical mesh algorithms, and it presents a more elegant mathematical method for deriving processor-time lower bounds for such problems