The third homomorphism theorem on trees: downward & upward lead to divide-and-conquer

ABSTRACT

Parallel programs on lists have been intensively studied. It is well known that associativity provides a good characterization for divide-and-conquer parallel programs. In particular, the third homomorphism theorem is not only useful for systematic development of parallel programs on lists, but it is also suitable for automatic parallelization. The theorem states that if two sequential programs iterate the same list leftward and rightward, respectively, and compute the same value, then there exists a divide-and-conquer parallel program that computes the same value as the sequential programs.

While there have been many studies on lists, few have been done for characterizing and developing of parallel programs on trees. Naive divide-and-conquer programs, which divide a tree at the root and compute independent subtrees in parallel, take time that is proportional to the height of the input tree and have poor scalability with respect to the number of processors when the input tree is ill-balanced.

In this paper, we develop a method for systematically constructing scalable divide-and-conquer parallel programs on trees, in which two sequential programs lead to a scalable divide-andconquer parallel program. We focus on paths instead of trees so as to utilize rich results on lists and demonstrate that associativity provides good characterization for scalable divide-and-conquer parallel programs on trees. Moreover, we generalize the third homomorphism theorem from lists to trees.We demonstrate the effectiveness of our method with various examples. Our results, being generalizations of known results for lists, are generic in the sense that they work well for all polynomial data structures.

REFERENCES

• 1: K. Abrahamson , N. Dadoun , D. G. Kirkpatrick , T. Przytycka, A simple parallel tree contraction algorithm, Journal of Algorithms, v.10 n.2, p.287-302, June 1989 [doi>10.1016/0196-6774(89)90017-5]
• 2: Roland Carl Backhouse, Patrik Jansson, Johan Jeuring, and Lambert G. L. T. Meertens. Generic programming: An introduction. In Advanced Functional Programming, pages 28--115, 1998.
• 3: R. S. Bird, An introduction to the theory of lists, Proceedings of the NATO Advanced Study Institute on Logic of programming and calculi of discrete design, p.5-42, June 1987, Marktoberdorf, Germany
• 4: Wei-Ngan Chin, Towards an automated tupling strategy, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.119-132, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154643]
• 5: Murray Cole. Parallel programming, list homomorphisms and the maximum segment sum problem. In Parallel Computing: Trends and Applications, PARCO 1993, Grenoble, France, pages 489--492. Elsevier, 1994.
• 6: Murray Cole. Parallel programming with list homomorphisms. Parallel Processing Letters, 5:191--203, 1995.
• 7: Richard Cole and Uzi Vishkin. The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time. Algorithmica, 3:329--346, 1988.
• 8: Maarten M. Fokkinga. Tupling and mutumorphisms. In Squiggolist, volume 1(4), 1989.
• 9: Ian Foster, Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 10: Alfons Geser , Sergei Gorlatch, Parallelizing functional programs by generalization, Journal of Functional Programming, v.9 n.6, p.649-673, November 1999 [doi>10.1017/S0956796899003536]
• 11: Alan Gibbons , Wojciech Rytter, Optimal parallel algorithms for dynamic expression evaluation and context-free recognition, Information and Computation, v.81 n.1, p.32-45, April 1989 [doi>10.1016/0890-5401(89)90027-8]
• 12: Jeremy Gibbons. The third homomorphism theorem. Journal of Functional Programming, 6(4):657--665, 1996.
• 13: Jeremy Gibbons , Wentong Cai , David B. Skillicorn, Efficient parallel algorithms for tree accumulations, Science of Computer Programming, v.23 n.1, p.1-18, Oct. 1994 [doi>10.1016/0167-6423(94)00013-1]
• 14: Zhenjiang Hu , Hideya Iwasaki , Masato Takechi, Formal derivation of efficient parallel programs by construction of list homomorphisms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.444-461, May 1997 [doi>10.1145/256167.256201]
• 15: Zhenjiang Hu , Hideya Iwasaki , Masato Takeichi , Akihiko Takano, Tupling calculation eliminates multiple data traversals, Proceedings of the second ACM SIGPLAN international conference on Functional programming, p.164-175, June 09-11, 1997, Amsterdam, The Netherlands
• 16: Gérard Huet, The Zipper, Journal of Functional Programming, v.7 n.5, p.549-554, September 1997 [doi>10.1017/S0956796897002864]
• 17: Kiminori Matsuzaki. Parallel Programming with Tree Skeletons. PhD thesis, Graduate School of Information Science and Technology, The University of Tokyo, 2007.
• 18: Kiminori Matsuzaki and Zhenjiang Hu. Implementation of tree skeletons on distributed-memory parallel computers. Technical Report METR 2006-65, Department of Mathematical Informatics, University of Tokyo, December 2006.
• 19: Kiminori Matsuzaki, Zhenjiang Hu, and Masato Takeichi. Parallelization with tree skeletons. In Euro-Par 2003. Parallel Processing, 9th International Euro-Par Conference, Klagenfurt, Austria, August 26-29, 2003. Proceedings, volume 2790 of Lecture Notes in Computer Science, pages 789--798. Springer, 2003.
• 20: Conor McBride. The derivative of a regular type is its type of one-hole contexts. Unpublished manuscript, 2001.
• 21: Gary L. Miller , John H. Reif, Parallel tree contraction and its application, Proceedings of the 26th Annual Symposium on Foundations of Computer Science, p.478-489, October 21-23, 1985 [doi>10.1109/SFCS.1985.43]
• 22: Akimasa Morihata and Kiminori Matsuzaki. A tree contraction algorithm on non-binary trees. Technical Report METR 2008-27, Department of Mathematical Informatics, University of Tokyo, 2008.
• 23: Kazutaka Morita , Akimasa Morihata , Kiminori Matsuzaki , Zhenjiang Hu , Masato Takeichi, Automatic inversion generates divide-and-conquer parallel programs, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 24: Simon Peyton Jones, editor. Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, 2003.
• 25: John H. Reif, Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 26: D. B. Skillicorn, Parallel implementation of tree skeletons, Journal of Parallel and Distributed Computing, v.39 n.2, p.115-125, Dec. 15, 1996 [doi>10.1006/jpdc.1996.0160]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Algorithms, Theory

Keywords:
divide-and-conquer, huet's zippers, polynomial data structures, the third homomorphism theorem