Partitioning of processor arrays: A piecewise regular approach

Teich J, Thiele L (1993)


Publication Type: Journal article

Publication year: 1993

Journal

Publisher: Elsevier

Pages Range: 14(3):297-332

DOI: 10.1016/0167-9260(93)90013-3

Abstract

The paper describes the systematic design of processor arrays with a given dimension and given number of processing elements. This problem is called partitioning. A solution to the partitioning problem is described for mapping a class of algorithms with piecewise regular dependence graphs, i.e. piecewise regular algorithms, onto processor arrays. These arrays are also piecewise regular, i.e. they are composed of a number of regularly connected homogenous subarrays. Partitioning deals with the division of the dependence graph of a piecewise regular algorithm into tiles and the scheduling of corresponding operations on a processor array of fixed size and dimension. Different solutions to this problem are termed partitioning schemes. Partitioning schemes may be classified into projection, multiprojection, passive and active clustering. The hereafter presented unified approach to the solution of the partitioning problem is based on the following concepts: (1) Algorithms are represented by programs. These programs can be directly interpreted as a description of hardware. (2) The concept of stepwise refinement of programs is used to solve the partitioning problem by applying a sequence of provably correct program transformations. The transformations basically involve operations on index sets. Two program transformations are introduced: (a) The EXPAND program transformation partitions the iteration space of a given program into a direct sum of lattices. The dimension of the iteration space increases. In contrary to other approaches, also nonperfect tilings may be considered. (b) Operations are scheduled on a processor array of fixed size and dimension using the REDUCE transformation. The dimension of the iteration space and thereby the dimension of the processor array is reduced. The parameters of this program transformation enable the realization of the different partitioning schemes. (3) The whole solution is embedded in the concepts of a systematic design of processor arrays. © 1993.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Teich, J., & Thiele, L. (1993). Partitioning of processor arrays: A piecewise regular approach. Integration-The Vlsi Journal, 14(3):297-332. https://dx.doi.org/10.1016/0167-9260(93)90013-3

MLA:

Teich, Jürgen, and Lothar Thiele. "Partitioning of processor arrays: A piecewise regular approach." Integration-The Vlsi Journal (1993): 14(3):297-332.

BibTeX: Download