Partitioning of processor arrays: A piecewise regular approach

Beitrag in einer Fachzeitschrift

Details zur Publikation

Autor(en): Teich J, Thiele L
Zeitschrift: Integration-The Vlsi Journal
Verlag: Elsevier
Jahr der Veröffentlichung: 1993
Seitenbereich: 14(3):297-332
ISSN: 0167-9260


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.

FAU-Autoren / FAU-Herausgeber

Teich, Jürgen Prof. Dr.-Ing.
Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)

Autor(en) der externen Einrichtung(en)
Eidgenössische Technische Hochschule Zürich (ETHZ) / Swiss Federal Institute of Technology in Zurich


Teich, J., & Thiele, L. (1993). Partitioning of processor arrays: A piecewise regular approach. Integration-The Vlsi Journal, 14(3):297-332.

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


Zuletzt aktualisiert 2018-18-07 um 22:23