Symbolic inner loop parallelisation for massively parallel processor arrays

Beitrag bei einer Tagung
(Konferenzbeitrag)


Details zur Publikation

Autor(en): Tanase AP, Witterauf M, Teich J, Hannig F
Verlag: Institute of Electrical and Electronics Engineers Inc.
Jahr der Veröffentlichung: 2014
Tagungsband: Proceedings of the 12th ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE)
Seitenbereich: 219-228
ISBN: 9781479953387


Abstract


This paper presents a first solution to the unsolved problem of symbolically scheduling a given loop nest with uniform data dependences using inner loop parallelization, in particular, the locally parallel, globally sequential (LPGS) mapping technique. This technique is needed in the case of loop program specifications for which the iterations shall be scheduled on a processor array of unknown size at compile time while keeping the local memory consumption independent of the problem size of the mapped loop nest. We show that it is possible to derive such parameterized LPGS schedules statically by proposing a mixed compile-/runtime approach: At compile time, we first determine the set of all schedule candidates, each latency-optimal for a different scanning order of the loop nest. Then we devise an exact parameterized formula for determining the latency of the resulting symbolic schedules, thus making each schedule fully predictable. At runtime, once the size of the processor array becomes known, a simple prolog selects the overall latency-optimal schedule that is then dynamically activated and executed on the processor array. Hence, our approach avoids any further runtime optimization and expensive re-compilations while achieving the same results as computing an optimal static schedule for each possible combination of array and problem size.



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)
Witterauf, Michael
Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)


Zitierweisen

APA:
Tanase, A.-P., Witterauf, M., Teich, J., & Hannig, F. (2014). Symbolic inner loop parallelisation for massively parallel processor arrays. In Proceedings of the 12th ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE) (pp. 219-228). Lausanne, CH: Institute of Electrical and Electronics Engineers Inc..

MLA:
Tanase, Alexandru-Petru, et al. "Symbolic inner loop parallelisation for massively parallel processor arrays." Proceedings of the 12th ACM/IEEE International Conference on Methods and Models for System Design, MEMOCODE 2014, Lausanne Institute of Electrical and Electronics Engineers Inc., 2014. 219-228.

BibTeX: 

Zuletzt aktualisiert 2018-12-10 um 21:50