Conference contribution


Symbolic Parallelization of Loop Programs for Massively Parallel Processor Arrays


Publication Details
Author(s): Teich J, Tanase AP, Hannig F
Title edited volumes: Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors
Publisher: Institute of Electrical and Electronics Engineers
Publishing place: New York, NY, USA
Publication year: 2013
Conference Proceedings Title: Proc. 24th International Conference on Application-Specific Systems, Architectures and Processors
Pages range: 1-9
ISBN: 978-1-4799-0493-8
ISSN: 1063-6862

Event details
Event: 24th International Conference on Application-Specific Systems, Architectures and Processors (ASAP)
Event location: Washington, DC
Start date of the event: 05/06/2013
End date of the event: 07/06/2013

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.



How to cite
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: Download
Share link
Last updated on 2017-11-18 at 01:52
PDF downloaded successfully