Symbolic Mapping of Loop Programs onto Processor Arrays

Beitrag in einem Sammelwerk

Details zur Publikation

Autorinnen und Autoren: Teich J, Tanase AP, Hannig F
Titel Sammelwerk: Journal of Signal Processing Systems
Verlag: Springer-Verlag
Verlagsort: Berlin; Heidelberg
Jahr der Veröffentlichung: 2014
Band: 77(1-2)
Seitenbereich: 31-59
ISSN: 1939-8115


In this paper, we present a solution to the problem of joint tiling and scheduling a given loop nest with uniform data dependencies symbolically. This challenge arises when the size and number of available processors for parallel loop execution is not known at compile time. But still, in order to avoid any overhead of dynamic (run-time) recompilation, a schedule of loop iterations shall be computed and optimized statically. In this paper, it will be shown that it is possible to derive parameterized latency-optimal schedules statically by proposing a two step approach: First, the iteration space of a loop program is tiled symbolically into orthotopes of parametrized extensions. Subsequently, the resulting tiled program is also scheduled symbolically, resulting in a set of latency-optimal parameterized schedule candidates. At run time, once the size of the processor array becomes known, simple comparisons of latency-determining expressions finally steer which of these schedules will be dynamically selected and the corresponding program configuration executed on the resulting processor array so to avoid any further run-time optimization or expensive recompilation. Our theory of symbolic loop parallelization is applied to a number of loop programs from the domains of signal processing and linear algebra. Finally, as a proof of concept, we demonstrate our proposed methodology for a massively parallel processor array architecture called tightly coupled processor array (TCPA) on which applications may dynamically claim regions of processors in the context of invasive computing.

FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Hannig, Frank PD Dr.-Ing.
Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)
Tanase, Alexandru-Petru Dr.-Ing.
Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)
Teich, Jürgen Prof. Dr.-Ing.
Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)


Teich, J., Tanase, A.-P., & Hannig, F. (2014). Symbolic Mapping of Loop Programs onto Processor Arrays. In Journal of Signal Processing Systems. (pp. 31-59). Berlin; Heidelberg: Springer-Verlag.

Teich, Jürgen, Alexandru-Petru Tanase, and Frank Hannig. "Symbolic Mapping of Loop Programs onto Processor Arrays." Journal of Signal Processing Systems. Berlin; Heidelberg: Springer-Verlag, 2014. 31-59.


Zuletzt aktualisiert 2019-23-07 um 07:27

Link teilen