Communication-Conscious Mapping of Regular Nested Loop Programs onto Massively Parallel Processor Arrays

S. Siegel, R. Merker, F. Hannig, and J. Teich (Germany)


Processor Array, Interconnection, Data Path, Hardware Mapping, Integer Linear Programming.


Methods for an efficient mapping of algorithms to parallel architectures are of utmost importance because many state of-the-art embedded digital systems deploy parallelism to increase their computational power. This paper deals with the mapping of loop programs onto processor arrays imple mented in an FPGA or available as (reconfigurable) coarse grained processor architectures. Most existing work is closely related to approaches from the DSP domain and is not able to exploit the full par allelism of a given algorithm and the computational poten tial of a typical 2-dimensional array. In contrast, we present a mapping methodology which incorporates many impor tant parameters of the target architecture in one approach. These are: number of processing elements, resources of the data path and memory within a processing element, and in terconnection within the processor array. Based on these parameters, we formulate an optimization problem whose solution specifies an efficient mapping of an algorithm to the target architecture. We can optimize for speed of the algorithm and/or hardware cost caused by the communica tion and computation resources of the architecture.

Important Links:

Go Back