Technical Reports
HPL-2010-81R1
Click here for full text:
A Technique for the Effective and Automatic Reuse of Classical Compiler Optimizations on Multithreaded Code
Joisha, Pramod G.; Schreiber, Robert S.; Banerjee, Prithviraj; Boehm, Hans-J.; Chakrabarti, Dhruva R.
HP Laboratories
HPL-2010-81R1
Keyword(s): compilers, parallel-program optimization, multithreading, data-flow analysis
Abstract: A large body of data-flow analyses exists for analyzing and optimizing sequential code. Unfortunately, much of it cannot be directly applied on parallel code, for reasons of correctness. This paper presents a technique to automatically, aggressively, yet safely apply sequentially-sound data-flow transformations, without change, on shared-memory programs. The technique is founded on the notion of program references being "siloed" on certain control-flow paths. Intuitively, siloed references are free of interference from other threads within the confines of such paths. Data-flow transformations can, in general, be unblocked on siloed references.
The solution has been implemented in a widely used compiler. Results on benchmarks from SPLASH-2 show that performance improvements of up to 41% are possible, with an average improvement of 6% across all the tested programs over all thread counts.
17 Pages
Additional Publication Information: Originally internally and externally posted on July 22, 2010. An abridged version will be published in the 38th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 2011).
External Posting Date: December 6, 2010 [Fulltext]. Approved for External Publication
Internal Posting Date: December 6, 2010 [Fulltext]