Authors: Devang Patel, Lawrence Rauchwerger

Venue: Languages and Compilers for Parallel Computing (LCPC.) Lecture Notes in Computer Science
DOI: 10.1007/3-540-48319-5_21
Link to Publication

Abstract:
Current parallelizing compilers cannot identify a significant fraction of parallelizable loops because they have complex or statically insufficiently defined access patterns. We advocate a novel framework for the identification of parallel loops. It speculatively executes a loop as a doall and applies a fully parallel data dependence test to check for any unsatisfied data dependencies; if the test fails, then the loop is re-executed serially. We will present the principles of the design and implementation of a compiler that employs both run-time and static techniques to parallelize dynamic applications. Run-time optimizations always represent a tradeoff between a speculated potential benefit and a certain (sure) overhead that must be paid. We will introduce techniques that take advantage of classic compiler methods to reduce the cost of run-time optimization thus tilting the outcome of speculation in favor of significant performance gains. Experimental results from the PERFECT, SPEC and NCSA Benchmark suites show that these techniques yield speedups not obtainable by any other known method. 

@inproceedings{Patel-posrp-1998, 
 address = {Berlin, Heidelberg}, 
 author = {Patel, Devang 
and Rauchwerger, Lawrence}, 
 booktitle = {Languages and Compilers for Parallel Computing}, 
 editor = {Chatterjee, Siddhartha 
and Prins, Jan F. 
and Carter, Larry 
and Ferrante, Jeanne 
and Li, Zhiyuan 
and Sehr, David 
and Yew, Pen-Chung}, 
 isbn = {978-3-540-48319-9}, 
 pages = {323--337}, 
 publisher = {Springer Berlin Heidelberg}, 
 title = {Principles of Speculative Run---Time Parallelization}, 
 year = {1999} 
}