Symbolic loop parallelization for balancing I/O and memory accesses on processor arrays

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

Publication Status: Published

Publication Type: Conference contribution, Conference Contribution

Publication year: 2015

Publisher: Institute of Electrical and Electronics Engineers Inc.

Pages Range: 188-197

Article Number: 7340486

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

Event location: Austin US

ISBN: 9781509002375

DOI: 10.1109/MEMCOD.2015.7340486

Abstract

Loop parallelization techniques for massively parallel processor arrays using one-level tiling are often either I/O- or memory-bounded, exceeding the target architecture's capabilities. Furthermore, if the number of available processing elements is only known at runtime - as in adaptive systems - static approaches fail. To solve these problems, we present a hybrid compile/runtime technique to symbolically parallelize loop nests with uniform dependences on multiple levels. At compile time, two novel transformations are performed: (a) symbolic hierarchical tiling followed by (b) symbolic multi-level scheduling. By tuning the size of the tiles on multiple levels, a trade-off between the necessary I/O-bandwidth and memory is possible, which facilitates obeying resource constraints. The resulting schedules are symbolic with respect to the number of tiles; thus, the number of processing elements to map onto does not need to be known at compile time. At runtime, when the number is known, a simple prolog chooses a feasible schedule with respect to I/O and memory constraints that is latency-optimal for the chosen tile size. In this way, our approach dynamically chooses latency-optimal and feasible schedules while avoiding expensive re-compilations.

Authors with CRIS profile

Alexandru-Petru Tanase Sonderforschungsbereich/Transregio 89 Invasives Rechnen Michael Witterauf Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design) Frank Hannig Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design) Jürgen Teich 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:

Tanase, A.-P., Witterauf, M., Hannig, F., & Teich, J. (2015). Symbolic loop parallelization for balancing I/O and memory accesses on processor arrays. In Proceedings of the 13th ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE) (pp. 188-197). Austin, US: Institute of Electrical and Electronics Engineers Inc..

MLA:

Tanase, Alexandru-Petru, et al. "Symbolic loop parallelization for balancing I/O and memory accesses on processor arrays." Proceedings of the ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2015, Austin Institute of Electrical and Electronics Engineers Inc., 2015. 188-197.

BibTeX: Download