On mapping algorithms onto processor arrays
A. Yavuz Oruç, Weicheng Shen · 1987
Two design procedures for parallel computers have been developed, which map computations onto processor arrays. The first is a procedure that programs a processor array for computing a given expression. It consists of the following steps: (1) determining the type of expressions that can be evaluated by a given processor array; (2) setting the processors in the processor array to carry out a computation within its computation space. This mapping procedure has been demonstrated for mesh-connected processing networks. The second procedure is a contraction mapping procedure that derives a target processor array from a directed acyclic graph representation of a program. This procedure consists of the following steps: (1) representing the given problem by a homogenous program graph; (2) partitioning the vertices of the graph into subsets such that all the vertices in the same subset will be executed by one processor; (3) characterizing the algebraic relations of delays between computations by a fundamental loop matrix; (4) establishing a linear function of delays as a performance metric and solving the delays that minimize the linear cost function by linear programming; (5) constructing a contracted graph from that program graph. The contracted graph delineates the target processor array that computes the given problem. This contraction mapping procedure is applied to a variety of problems, including algebraic computations and character string processing.