SYSTEMATIC DERIVATION OF TREE CONTRACTION ALGORITHMS
Abstract
While tree contraction algorithms play an important role in efficient tree computation in parallel, it is difficult to develop such algorithms due to the strict conditions imposed on contracting operators. In this paper, we propose a systematic method of deriving efficient tree contraction algorithms from recursive functions on trees. We identify a general recursive form that can be parallelized into efficient tree contraction algorithms, and present a derivation strategy for transforming general recursive functions to the parallelizable form. We illustrate our approach by deriving a novel parallel algorithm for the maximum connected-set sum problem on arbitrary trees, the tree-version of the well-known maximum segment sum problem.
This work was partly supported by a PRESTO project of Japan Science and Technology Agency.
References
-
M. Cole , Algorithms skeletons: a structured approach to the management of parallel computation ,Research Monographs in Parallel and Distributed Computing ( Pitman , London , 1989 ) . Google Scholar -
F. Rabhi and S. Gorlatch , Patterns and Skeletons for Parallel and Distributed Computing ( Springer-Verlag New York Inc. , 2002 ) . Google Scholar - M. Cole, Parallel programming, list homomorphisms and the maximum segment sum problems, Report CSR-25-93, Department of Computing Science, The University of Edinburgh (1993) . Google Scholar
S. Gorlatch , Proc. Annual European Conference on Parallel Processing (Euro-Par '96),LNCS 1124 (Springer-Verlag, 1996) pp. 401–408. Crossref, Google Scholar- ACM Trans. on Programming Languages and Systems 19(3), 444 (1997). Crossref, ISI, Google Scholar
- , Software for Parallel Computation,
NATO ASI Series F 106, eds.J. S. Kowalik and L. Grandinetti (Springer-Verlag, 1993) pp. 120–133. Crossref, Google Scholar - Parallel Process. Lett. 10(1), 87 (2000). Link, Google Scholar
- J. Algorithms 10(2), 287 (1989). Crossref, ISI, Google Scholar
G. L. Miller and J. H. Reif , Proc. 26th Annual Symposium on Foundations of Computer Science (IEEE Computer Society Press, 1985) pp. 478–489. Google Scholar- SIAM J. Comput. 20(6), 1128 (1991). Crossref, ISI, Google Scholar
- J. H. Reif and S. R. Tate, Dynamic parallel tree contraction, in Proc. the Symposium on Parallel Algorithms and Architecture (1994) 114–121 . Google Scholar
- Sci. Comput. Program. 23(1), 1 (1994). Crossref, ISI, Google Scholar
-
D. B. Skillicorn , Foundations of Parallel Programming ( Cambridge University Press , 1994 ) . Crossref, Google Scholar - J. Parallel Distr. Com. 39(2), 115 (1996). Crossref, ISI, Google Scholar
- Inform. Process. Lett. 60(5), 231 (1996). Crossref, ISI, Google Scholar
- J. Univers. Comput. Sci. 3(1), 42 (1997). Google Scholar
- H. Deldari, J. R. Davy, and P. M. Dew, Parallel CSG, skeletons and performance modelling, in Proc. the Second Annual CSI Computer Conference (CSICC'96) (1996) 115–122 . Google Scholar
K. Matsuzaki , Z. Hu and M. Takeichi , Proc. Annual European Conference on Parallel Processing (Euro-Par 2003),LNCS 2790 (Springer-Verlag, 2003) pp. 789–798. Crossref, Google Scholar- Z. Hu, M. Takeichi and H. Iwasaki, Towards polytypic parallel programming, Technical Report METR 98-09, University of Tokyo (1998) . Google Scholar
J. Bentley , Programming Pearls (Addison-Wesley, 1986) pp. 69–80. Google ScholarZ. Hu , H. Iwasaki and M. Takeichi , Proc. 21st International Symposium on Mathematical Foundation of Computer Science,LNCS 1113 (Springer-Verlag, 1996) pp. 407–418. Google ScholarZ. Hu , H. Iwasaki and M. Takeichi , Proc. Annual European Conference on Parallel Processing (Euro-Par '96),LNCS 1123 (Springer-Verlag, 1996) pp. 553–562. Crossref, Google Scholar- W. N. Chin, A. Takano, and Z. Hu, Parallelization via context preservation, in Proc. IEEE Computer Society International Conference on Computer Languages (ICCL'98) (1998) 153–162 . Google Scholar


