Symbolic Parallelization of Loop Programs for Massively Parallel Processor Arrays

Teich J, Tanase AP, Hannig F (2013)

Publication Type: Conference contribution

Publication year: 2013

Journal

International Conference on Application-Specific Systems, Architectures and Processors, Proceedings Institute of Electrical and Electronics Engineers

Publisher: Institute of Electrical and Electronics Engineers

Edited Volumes: Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors

City/Town: New York, NY, USA

Pages Range: 1-9

Conference Proceedings Title: Proc. 24th International Conference on Application-Specific Systems, Architectures and Processors

Event location: Washington, DC US

ISBN: 978-1-4799-0493-8

DOI: 10.1109/ASAP.2013.6567543

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.

Authors with CRIS profile

Jürgen Teich Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design) Alexandru-Petru Tanase Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design) Frank Hannig Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)

Related research project(s)

Dedizierte massiv parallele Systeme (PARO) Jan. 3, 2000 - Jan. 3, 2003

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