Abstract
Constant propagation (CP) is a powerful, practically relevant optimization of sequential programs. However, systematic adaptions to the parallel setting are still missing. In fact, because of the computational complexity paraphrased by the catch-phrase “state explosion problem”, the successful transfer of sequential techniques is currently restricted to bitvector-based optimizations, which because of their structural simplicity can be enhanced to parallel programs at almost no costs on the implementation and computation side. CP, however, is beyond this class. Here, we show how to enhance the framework underlying the transfer of bitvector problems obtaining the basis for developing a powerful algorithm for parallel constant propagation (PCP). This algorithm can be implemented as easily and as efficiently as its sequential counterpart for simple constants computed by state-of-the-art sequential optimizers.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
P. Cousot and R. Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Conf. Rec. 4th Symp. Principles of Prog. Lang. (POPL’77), pages 238–252. ACM, NY, 1977.
M. S. Hecht. Flow Analysis of Computer Programs. Elsevier, North-Holland, 1977.
J. B. Kam and J. D. Ullman. Monotone data flow analysis frameworks. Acta Informatica, 7:309–317, 1977.
G. A. Kildall. A unified approach to global program optimization. In Conf. Rec. 1st Symp. Principles of Prog. Lang. (POPL’73), pages 194–206. ACM, NY, 1973.
J. Knoop. Constant propagation in explicitly parallel programs. Technical report, Fak. f. Math. u. Inf., Univ. Passau, Germany, 1998.
J. Knoop. Eliminating partially dead code in explicitly parallel programs. TCS, 196(1–2):365–393, 1998. (Special issue devoted to Euro-Par’96).
J. Knoop, O. Rüthing, and B. Steffen. Partial dead code elimination. In Proc. ACM SIGPLAN Conf. on Prog. Lang. Design and Impl. (PLDI’94), volume 29, 6 of ACM SIGPLAN Not., pages 147–158, 1994.
J. Knoop, B. Steffen, and J. Vollmer. Code motion for parallel programs. In Proc. of the Poster Session of the 6th Int. Conf. on Compiler Construction (CC’96), pages 81–88. TR LiTH-IDA-R-96-12, 1996.
J. Knoop, B. Steffen, and J. Vollmer. Parallelism for free: Efficient and optimal bitvector analyses for parallel programs. ACM Trans. Prog. Lang. Syst., 18(3):268–299, 1996.
S. P. Midkiff and D. A. Padua. Issues in the optimization of parallel programs. In Proc. Int. Conf. on Parallel Processing, Volume II, pages 105–113, 1990.
E. Morel and C. Renvoise. Global optimization by suppression of partial redundancies. Comm. ACM, 22(2):96–103, 1979.
J. H. Reif and R. Lewis. Symbolic evaluation and the global value graph. In Conf. Rec. 4th Symp. Principles of Prog. Lang. (POPL’77), pages 104–118. ACM, NY, 1977.
B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Global value numbers and redundant computations. In Conf. Rec. 15th Symp. Principles of Prog. Lang. (POPL’88), pages 2–27. ACM, NY, 1988.
M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In S. S. Muchnick and N. D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 7, pages 189–233. Prentice Hall, Englewood Cliffs, NJ, 1981.
M. Wolfe. High performance compilers for parallel computing. Addison-Wesley, NY, 1996.
H. Zima and B. Chapman. Supercompilers for parallel and vector computers. Addison-Wesley, NY, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Knoop, J. (1998). Parallel constant propagation. In: Pritchard, D., Reeve, J. (eds) Euro-Par’98 Parallel Processing. Euro-Par 1998. Lecture Notes in Computer Science, vol 1470. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0057887
Download citation
DOI: https://doi.org/10.1007/BFb0057887
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64952-6
Online ISBN: 978-3-540-49920-6
eBook Packages: Springer Book Archive