Logical inference techniques for loop parallelization
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Logical inference techniques for loop parallelization. / Oancea, Cosmin Eugen; Rauchwerger, Lawrence.
Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation. Association for Computing Machinery, 2012. p. 509-520.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Logical inference techniques for loop parallelization
AU - Oancea, Cosmin Eugen
AU - Rauchwerger, Lawrence
N1 - Conference code: 33
PY - 2012
Y1 - 2012
N2 - This paper presents a fully automatic approach to loop parallelization that integrates the use of static and run-time analysis and thus overcomes many known difficulties such as nonlinear and indirect array indexing and complex control flow. Our hybrid analysis framework validates the parallelizationtransformation by verifying the independence of the loop'smemory references.To this end it represents array references using the USR (uniform set representation) language and expresses the independence condition as an equation, S={}, where S is a set expression representing array indexes. Using a language instead of an array-abstraction representation for S results in a smaller number of conservative approximations but exhibits a potentially-high runtime cost.To alleviate this cost we introduce a language translation F from the USR set-expression language to an equally rich language of predicates ( F(S) => S = {} ). Loop parallelization is then validated using a novel logic inference algorithm that factorizes the obtained complex predicates F(S) into a sequence of sufficient-independence conditions that are evaluated first statically and, when needed, dynamically, in increasing order of their estimated complexities.We evaluate our automated solution on 26 benchmarks from PERFECT-CLUB and SPEC suites and show that our approach is effective in parallelizing large, complex loops and obtains much better full program speedups than the Intel and IBM Fortran compilers.
AB - This paper presents a fully automatic approach to loop parallelization that integrates the use of static and run-time analysis and thus overcomes many known difficulties such as nonlinear and indirect array indexing and complex control flow. Our hybrid analysis framework validates the parallelizationtransformation by verifying the independence of the loop'smemory references.To this end it represents array references using the USR (uniform set representation) language and expresses the independence condition as an equation, S={}, where S is a set expression representing array indexes. Using a language instead of an array-abstraction representation for S results in a smaller number of conservative approximations but exhibits a potentially-high runtime cost.To alleviate this cost we introduce a language translation F from the USR set-expression language to an equally rich language of predicates ( F(S) => S = {} ). Loop parallelization is then validated using a novel logic inference algorithm that factorizes the obtained complex predicates F(S) into a sequence of sufficient-independence conditions that are evaluated first statically and, when needed, dynamically, in increasing order of their estimated complexities.We evaluate our automated solution on 26 benchmarks from PERFECT-CLUB and SPEC suites and show that our approach is effective in parallelizing large, complex loops and obtains much better full program speedups than the Intel and IBM Fortran compilers.
U2 - 10.1145/2254064.2254124
DO - 10.1145/2254064.2254124
M3 - Article in proceedings
SN - 978-1-4503-1205-9
SP - 509
EP - 520
BT - Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation
PB - Association for Computing Machinery
Y2 - 11 June 2012 through 16 June 2012
ER -
ID: 44883047