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

Conference contribution
(Conference Contribution)


Publication Details

Author(s): Tanase AP, Witterauf M, Hannig F, Teich J
Publisher: Institute of Electrical and Electronics Engineers Inc.
Publication year: 2015
Conference Proceedings Title: Proceedings of the 13th ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE)
Pages range: 188-197
ISBN: 9781509002375


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.



FAU Authors / FAU Editors

Hannig, Frank Dr.-Ing.
Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)
Tanase, Alexandru-Petru Dr.-Ing.
Sonderforschungsbereich/Transregio 89 Invasives Rechnen
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)


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: 

Last updated on 2018-19-04 at 03:25