Conference contribution
(Conference Contribution)


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


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

Event details
Event: ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2015
Event location: Austin
Start date of the event: 21/09/2015
End date of the event: 23/09/2015

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.



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
Share link
Last updated on 2017-12-11 at 02:25
PDF downloaded successfully