| Full text | |
| Author(s): |
Mattos, Luis
;
Cesar, Divino
;
Salamanca, Juan
;
de Carvalho, Joao P. L.
;
Pereira, Marcio
;
Araujo, Guido
;
IEEE
Total Authors: 7
|
| Document type: | Journal article |
| Source: | 2018 30TH INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD 2018); v. N/A, p. 4-pg., 2018-01-01. |
| 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 2x speed-ups by quickly selecting the appropriate algorithm. (AU) | |
| FAPESP's process: | 13/08293-7 - CCES - Center for Computational Engineering and Sciences |
| Grantee: | Munir Salomao Skaf |
| Support Opportunities: | Research Grants - Research, Innovation and Dissemination Centers - RIDC |
| FAPESP's process: | 16/15337-9 - Distributed Transactional Memories and Efficient Data Distribution Models to Speed-up Irregular Data Structure Intensive Applications |
| Grantee: | João Paulo Labegalini de Carvalho |
| Support Opportunities: | Scholarships in Brazil - Doctorate |
| FAPESP's process: | 15/04285-5 - Speculative code execution for multicore architectures |
| Grantee: | Juan Jesús Salamanca Guillén |
| Support Opportunities: | Scholarships in Brazil - Doctorate (Direct) |