Using generative design patterns to generate parallel code for a distributed memory environment

ABSTRACT

A design pattern is a mechanism for encapsulating the knowledge of experienced designers into a re-usable artifact. Parallel design patterns reflect commonly occurring parallel communication and synchronization structures. Our tools, CO2P3S (Correct Object-Oriented Pattern-based Parallel Programming System) and MetaCO2P3S, use generative design patterns. A programmer selects the parallel design patterns that are appropriate for an application, and then adapts the patterns for that specific application by selecting from a small set of code-configuration options. CO2P3S then generates a custom framework for the application that includes all of the structural code necessary for the application to run in parallel. The programmer is only required to write simple code that launches the application and to fill in some application-specific sequential hook routines. We use generative design patterns to take an application specification (parallel design patterns + sequential user code) and use it to generate parallel application code that achieves good performance in shared memory and distributed memory environments. Although our implementations are for Java, the approach we describe is tool and language independent. This paper describes generalizing CO2P3S to generate distributed-memory parallel solutions.

REFERENCES

• 1: J. Anvik, S. MacDonald, D. Szafron, J. Schaeffer, S. Bromling, and K. Tan. Generating parallel programs from the wavefront design pattern. In Proceedings of 7th International Workshop on High-Level Parallel Programming Models and Supportive Environments, CD-ROM 1--8, 2002.
• 2: Henri E. Bal , M. Frans Kaashoek , Andrew S. Tanenbaum, Orca: A Language for Parallel Programming of Distributed Systems, IEEE Transactions on Software Engineering, v.18 n.3, p.190-205, March 1992 [doi>10.1109/32.126768]
• 3: Kent Beck , Ralph E. Johnson, Patterns Generate Architectures, Proceedings of the 8th European Conference on Object-Oriented Programming, p.139-149, July 04-08, 1994
• 4: R. F. Boisvert, J. J. Dongarra, R. Pozo, K. A. Remington, and G. W. Stewart. Developing numerical libraries in Java. In ACM 1998 Workshop on Java for High-Performance Network Computing. ACM SIGPLAN, 1998.
• 5: J. Bosch. Design patterns as language constructs. Journal of Object-Oriented Programming, 11(2):18--32, 1998.
• 6: S. Bromling. Meta-programming with parallel design patterns. Master's thesis, Dept. of Computing Science, University of Alberta, 2001.
• 7: S. Bromling , S. MacDonald , J. Anvik , J. Schaeffer , D. Szafron , K. Tan, Pattern-Based Parallel Programming, Proceedings of the 2002 International Conference on Parallel Processing (ICPP'02), p.257, August 18-21, 2002
• 8: F. J. Budinsky , M. A. Finnie , J. M. Vlissides , P. S. Yu, Automatic code generation from design patterns, IBM Systems Journal, v.35 n.2, p.151-171, 1996
• 9: Nicholas Carriero , David Gelernter, Linda in context, Communications of the ACM, v.32 n.4, p.444-458, April 1989 [doi>10.1145/63334.63337]
• 10: X. Chen and V. H. Allan. MultiJav: a distributed shared memory system based on multiple Java virtual machines. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'98), pp. 91--98, 1998.
• 11: Murray Cole, Algorithmic skeletons: structured management of parallel computation, MIT Press, Cambridge, MA, 1991
• 12: Leonardo Dagum , Ramesh Menon, OpenMP: An Industry-Standard API for Shared-Memory Programming, IEEE Computational Science & Engineering, v.5 n.1, p.46-55, January 1998 [doi>10.1109/99.660313]
• 13: A. Eden, Y. Hirshfeld, and A. Yehudai. Towards a mathematical foundation for design patterns. Technical Report Technical Report 1999-004, Dept. of Information Technology, University of Uppsala, 1999.
• 14: Raphael Finkel , Udi Manber, DIB—a distributed implementation of backtracking, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.2, p.235-256, April 1987 [doi>10.1145/22719.24067]
• 15: G. Florijn, M. Meijers, and P. van Winsen. Tool support for object-oriented patterns. In Proceedings of the 11th European Conference on Object-Oriented Programming, volume 1241 of Lecture Notes in Computer Science, pages 472--495. Springer-Verlag, 1997.
• 16: E. Freeman and S. Hupfer, Make room for JavaSpaces, Part 1: Ease the development of distributed apps with JavaSpaces, http://www.javaworld.com/javaworld/jw-11-1999/jw-11-jiniology.html
• 17: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 18: GigaSpaces Technologies. GigaSpaces cluster white paper, http://www.gigaspaces.com/download/GSClusterWhitePaper.pdf, 2002.
• 19: Andrew S. Grimshaw, Easy-to-Use Object-Oriented Parallel Processing with Mentat, Computer, v.26 n.5, p.39-51, May 1993 [doi>10.1109/2.211896]
• 20: R. Johnson and B. Foote. Designing reusable classes. Journal of Object-Oriented Programming, 1(2):22--35, 1988.
• 21: Efficient Java RMI for parallel programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.6, p.747-775, November 2001 [doi>10.1145/506315.506317]
• 22: S. MacDonald. From patterns to frameworks to parallel programs. Ph.D. thesis, Dept. of Computing Science, University of Alberta, 2002.
• 23: S. MacDonald , J. Anvik , S. Bromling , J. Schaeffer , D. Szafron , K. Tan, From patterns to frameworks to parallel programs, Parallel Computing, v.28 n.12, p.1663-1683, December 2002 [doi>10.1016/S0167-8191(02)00190-4]
• 24: S. MacDonald, D. Szafron, and J. Schaeffer. Object-oriented pattern-based parallel programming with automatically generated frameworks. In Proceedings of the 5th USENIX Conference on Object-Oriented Technology and Systems, pp. 29--43, 1999.
• 25: S. MacDonald , D. Szafron , J. Schaeffer , J. Anvik , S. Bromling , K. Tan, Generative Design Patterns, Proceedings of the 17th IEEE international conference on Automated software engineering, p.23, September 23-27, 2002
• 26: Steve MacDonald , Duane Szafron , Jonathan Schaeffer , Steven Bromling, Generating Parallel Program Frameworks from Parallel Design Patterns, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.95-104, August 29-September 01, 2000
• 27: M. Massingill, T. Mattson, and B. Sanders. A pattern language for parallel application programs. Technical Report CISE TR 99-022, University of Florida, 1999.
• 28: ModelMaker Tools. Design patterns in ModelMaker. http://www.modelmakertools.com/mm_design_patterns.htm.
• 29: J. E. Moreira , S. P. Midkiff , M. Gupta , P. V. Artigas , M. Snir , R. D. Lawrence, Java programming for high-performance numerical computing, IBM Systems Journal, v.39 n.1, p.21-56, January 2000
• 30: Jan Newmarch, A programmer's guide to Jini technology, Springer-Verlag New York, Inc., Secaucus, NJ, 2000
• 31: M. Philippsen, B. Haumacher, and C. Nester. More efficient serialization and RMI for Java. Concurrency: Practice and Experience, 12(7):495--518, May 2000.
• 32: J. Reynders, et al. POOMA: A framework for scientific simulations of parallel architectures, Parallel Programming in C++, G. Wilson and P. Lu (editors), pp. 547--588, MIT Press, 1996.
• 33: Jonathan Schaeffer , Duane Szafron , Greg Lobe , Ian Parsons, The Enterprise Model for Developing Distributed Applications, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.3, p.85-96, August 1993 [doi>10.1109/88.242459]
• 34: Douglas C. Schmidt , Hans Rohnert , Michael Stal , Dieter Schultz, Pattern-Oriented Software Architecture: Patterns for Concurrent and Networked Objects, John Wiley & Sons, Inc., New York, NY, 2000
• 35: Hanmao Shi , Jonathan Schaeffer, Parallel sorting by regular sampling, Journal of Parallel and Distributed Computing, v.14 n.4, p.361-372, April 1992 [doi>10.1016/0743-7315(92)90075-X]
• 36: A. Singh , J. Schaeffer , M. Green, A Template-Based Approach to the Generation of Distributed Applications Using a Network of Workstations, IEEE Transactions on Parallel and Distributed Systems, v.2 n.1, p.52-67, January 1991 [doi>10.1109/71.80189]
• 37: A. Singh, J. Schaeffer, and D. Szafron. Experience with parallel programming using code templates. Concurrency: Practice & Experience, 10(2):91--120, 1998.
• 38: S. Siu, M. De Simone, D. Goswami, and A. Singh. Design patterns for parallel programming. Proceedings of the 1996 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'96), pp. 230--240, 1996.
• 39: Marc Snir , Steve W. Otto , David W. Walker , Jack Dongarra , Steven Huss-Lederman, MPI: The Complete Reference, MIT Press, Cambridge, MA, 1995
• 40: F. Sommers. Activatable Jini Services, Part 1: Implement RMI Activation, http://www.javaworld.com/javaworld/jw-09-2000/jw-0915-jinirmi.html
• 41: Sun Microsystems. Java Remote Method Invocation Specification, JDK 1.1, http://java.sun.com/products/jdk/rmi_ed, 1997.
• 42: Sun Microsystems. Jini Architectural Overview, 2001. http://wwws.sun.com/software/jini/whitepapers/architecture.pdf.
• 43: Sun Microsystems. JNI Specification, 2000. http://java.sun.com/products/jdk/1.2/docs/guide/jni/spec/jniTOC.doc.html
• 44: K. Tan, Pattern-based parallel programming in a distributed memory environment. Master's thesis, Dept. of Computing Science, University of Alberta, 2003.
• 45: TogetherSoft Corporation. TogetherSoft ControlCenter tutorials: Using design patterns. http://www.togethersoft.com/services/tutorials/index.jsp.
• 46: Bill Venners, Inside the Java Virtual Machine, McGraw-Hill Professional, 1999
• 47: M. Welsh and D. Culler. Jaguar: Enabling efficient communication and I/O in Java. Concurrency: Practice and Experience, 12(7):519--538, 2000.
• 48: Barry Wilkinson , Michael Allen, Parallel programming: techniques and applications using networked workstations and parallel computers, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
      D.1.5 Object-oriented Programming
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Patterns (e.g., client/server, pipeline, blackboard)

General Terms:
Design, Languages, Performance, Reliability

Keywords:
design patterns, frameworks, parallel programming, programming tools