Symbolic Parallelization of Loop Programs for Massively Parallel Processor Arrays

Beitrag bei einer Tagung


Details zur Publikation

Autor(en): Teich J, Tanase AP, Hannig F
Titel Sammelwerk: Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors
Verlag: Institute of Electrical and Electronics Engineers
Verlagsort: New York, NY, USA
Jahr der Veröffentlichung: 2013
Tagungsband: Proc. 24th International Conference on Application-Specific Systems, Architectures and Processors
Seitenbereich: 1-9
ISBN: 978-1-4799-0493-8
ISSN: 1063-6862


Abstract


In this paper, we present a first solution to the unsolved problem of joint tiling and scheduling a given loop nest with uniform data dependencies symbolically. This problem arises for loop programs for which the iterations shall be optimally scheduled on a processor array of unknown size at compile-time. Still, we show that it is possible to derive parameterized latency-optimal schedules statically by proposing two new program transformations: In the first step, the iteration space is tiled symbolically into orthotopes of parametrized extensions. The resulting tiled program is subsequently scheduled symbolically. Here, we show that the maximal number of potential optimal schedules is upper bounded by 2n n! where n is the dimension of the loop nest. However, the real number of optimal schedule candidates being much less than this. 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 activated and the corresponding program configuration executed on the resulting processor array so to avoid any further run-time optimization or expensive recompilations. © 2013 IEEE.



FAU-Autoren / FAU-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)


Zitierweisen

APA:
Teich, J., Tanase, A.-P., & Hannig, F. (2013). Symbolic Parallelization of Loop Programs for Massively Parallel Processor Arrays. In Proc. 24th International Conference on Application-Specific Systems, Architectures and Processors (pp. 1-9). Washington, DC, US: New York, NY, USA: Institute of Electrical and Electronics Engineers.

MLA:
Teich, Jürgen, Alexandru-Petru Tanase, and Frank Hannig. "Symbolic Parallelization of Loop Programs for Massively Parallel Processor Arrays." Proceedings of the 24th International Conference on Application-Specific Systems, Architectures and Processors (ASAP), Washington, DC New York, NY, USA: Institute of Electrical and Electronics Engineers, 2013. 1-9.

BibTeX: 

Zuletzt aktualisiert 2018-09-08 um 23:13