Symbolic inner loop parallelisation for massively parallel processor arrays

Tanase AP, Witterauf M, Teich J, Hannig F (2014)


Publication Status: Published

Publication Type: Conference contribution, Conference Contribution

Publication year: 2014

Publisher: Institute of Electrical and Electronics Engineers Inc.

Pages Range: 219-228

Article Number: 6961865

Conference Proceedings Title: Proceedings of the 12th ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE)

Event location: Lausanne CH

ISBN: 9781479953387

DOI: 10.1109/MEMCOD.2014.6961865

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.

Authors with CRIS profile

Related research project(s)

How to cite

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: Download