Title
DOACROSS Parallelization Based on Component Annotation and Loop-Carried Probability
Date Issued
20 February 2019
Access level
metadata only access
Resource Type
conference paper
Author(s)
University of Campinas
Publisher(s)
Institute of Electrical and Electronics Engineers Inc.
Abstract
Although modern compilers implement many loop parallelization techniques, their application is typically restricted to loops that have no loop-carried dependences (DOALL) or that contain well-known structured dependence patterns (e.g. reduction). These restrictions preclude the parallelization of many computational intensive DOACROSS loops. In such loops, either the compiler finds at least one loop-carried dependence or it cannot prove, at compile-time, that the loop is free of such dependences, even though they might never show-up at runtime. In any case, most compilers end-up not parallelizing DOACROSS loops. This paper brings three contributions to address this problem. First, it integrates three algorithms (TLS, DOAX, and BDX) into a simple openMP clause that enables the programmer to select the best algorithm for a given loop. Second, it proposes an annotation approach to separate the sequential components of a loop, thus exposing other components to parallelization. Finally, it shows that loop-carried probability is an effective metric to decide when to use TLS or other non-speculative techniques (e.g. DOAX or BDX) to parallelize DOACROSS loops. Experimental results reveal that, for certain loops, slow-downs can be transformed in 2×speed-ups by quickly selecting the appropriate algorithm.
Start page
29
End page
32
Language
English
OCDE Knowledge area
Ingeniería eléctrica, Ingeniería electrónica
Hardware, Arquitectura de computadoras
Scopus EID
2-s2.0-85063124261
ISBN of the container
9781538677698
Conference
Proceedings - 2018 30th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2018
Sponsor(s)
This work is supported by CCES CEPID/FAPESP under grants 2013/08293-7, 2015/04285-5, and 2016/15337-9.
Sources of information:
Directorio de Producción Científica
Scopus