TY - JOUR
T1 - Containers on the parallelization of general-purpose Java programs
AU - Wu, Peng
AU - Padua, David
N1 - Funding Information:
1This work is supported in part by Army contract DABT63-95-C-0097; Department of Energy contract B341494; the National Science Foundation and the Defense Advanced Research Projects Agency under the OPAAL initiative and Grant NSF DMS 98-7394; and, a Partnership Award from IBM. This work is not necessarily representative of the positions or policies of the Army or Government. 2Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield Ave., Urbana, Illinois 61801. E-mail: [pengwu, padua] cs.uiuc.edu.
PY - 2000/12
Y1 - 2000/12
N2 - Static parallelization of general-purpose programs is still impossible, in general, due to their common use of pointers, irregular data structures, and complex control-flows. One promising strategy is to exploit parallelism at runtime. Runtime parallelization schemes, particularly data speculations, alleviate the need to statically prove independent computations at compile-time. However, studies show that many real-world applications exhibit limited speculative parallelism to offset the overhead and penalty of speculation schemes. This paper addresses this issue by using compiler analyses to compensate for speculative parallelizations. We focus on general-purpose Java programs with extensive use of Java container classes. In our scheme, compilers serve as a guideline of where to speculate by 'lazily' detecting dependences that are mostly static, while leaving those that are more dynamic to runtime. We also propose techniques to enhance speculative parallelism in the programs. The experimental results show that, after eliminating static dependences, the four applications we study exhibit significant parallelism that can be gainfully exploited by a speculative parallelization system.
AB - Static parallelization of general-purpose programs is still impossible, in general, due to their common use of pointers, irregular data structures, and complex control-flows. One promising strategy is to exploit parallelism at runtime. Runtime parallelization schemes, particularly data speculations, alleviate the need to statically prove independent computations at compile-time. However, studies show that many real-world applications exhibit limited speculative parallelism to offset the overhead and penalty of speculation schemes. This paper addresses this issue by using compiler analyses to compensate for speculative parallelizations. We focus on general-purpose Java programs with extensive use of Java container classes. In our scheme, compilers serve as a guideline of where to speculate by 'lazily' detecting dependences that are mostly static, while leaving those that are more dynamic to runtime. We also propose techniques to enhance speculative parallelism in the programs. The experimental results show that, after eliminating static dependences, the four applications we study exhibit significant parallelism that can be gainfully exploited by a speculative parallelization system.
UR - http://www.scopus.com/inward/record.url?scp=0034505635&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0034505635&partnerID=8YFLogxK
U2 - 10.1023/A:1007564701813
DO - 10.1023/A:1007564701813
M3 - Article
AN - SCOPUS:0034505635
SN - 0885-7458
VL - 28
SP - 589
EP - 605
JO - International Journal of Parallel Programming
JF - International Journal of Parallel Programming
IS - 6
ER -