Performance evaluation of the Orca shared-object system

ABSTRACT

Orca is a portable, object-based distributed shared memory (DSM) system. This article studies and evaluates the design choices made in the Orca system and compares Orca with other DSMs. The article gives a quantitative analysis of Orca's coherence protocol (based on write-updates with function shipping), the totally ordered group communication protocol, the strategy for object placement, and the all-software, user-space architecture. Performance measurements for 10 parallel applications illustrate the trade-offs made in the design of Orca and show that essentially the right design decisions have been made. A write-update protocol with function shipping is effective for Orca, especially since it is used in combination with techniques that avoid replicating objects that have a low read/write ratio. The overhead of totally ordered group communication on application performance is low. The Orca system is able to make near-optimal decisions for object placement and replication. In addition, the article compares the performance of Orca with that of a page-based DSM (TreadMarks) and another object-based DSM (CRL). It also analyzes the communication overhead of the DSMs for several applications. All performance measurements are done on a 32-node Pentium Pro cluster with Myrinet and Fast Ethernet networks. The results show that Orca programs send fewer messages and less data than the TreadMarks and CRL programs and obtain better speedups.

REFERENCES

• 1: Cristiana Amza , Alan L. Cox , Willy Zwaenepoel , Sandhya Dwarkadas, Software DSM Protocols that Adapt between Single Writer and Multiple Writer, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.261, February 01-05, 1997
• 2: BAL, H. AND TANENBAUM, A. 1988. Distributed programming with shared data. In Proceedings of the IEEE CS 1988 International Conference on Computer Languages. 82-91.
• 3: BAL, H., BHOEDJANG, R., HOFMAN, R., JACOBS, C., LANGENDOEN, K., RIJHL, T., AND KAASHOEK, M. 1997a. Portability in the Orca shared object system. Tech. Rep., Vrije Universiteit.
• 4: Henri Bal , Raoul Bhoedjang , Rutger Hofman , Ceriel Jacobs , Koen Langendoen , Tim Rühl , Kees Verstoep, Performance of a high-level parallel language on a high-speed network, Journal of Parallel and Distributed Computing, v.40 n.1, p.49-64, Jan. 10, 1997 [doi>10.1006/jpdc.1996.1265 ]
• 5: 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 ]
• 6: Saniya Ben Hassen , Henri Bal, Integrating task and data parallelism using shared objects, Proceedings of the 10th international conference on Supercomputing, p.317-324, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237628]
• 7: J. K. Bennett , J. B. Carter , W. Zwaenepoel, Munin: distributed shared memory based on type-specific memory coherence, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.168-176, March 14-16, 1990, Seattle, Washington, United States
• 8: BERSHAD, B., ZEKAUSHAS, M., AND SAWDON, W. 1993. The Midway distributed shared memory system. In Proceedings of COMPCON. 528-537.
• 9: Matthias A. Blumrich , Cezary Dubnicki , Edward W. Felten , Kai Li , Malena R. Mesarina, Virtual-Memory-Mapped Network Interfaces, IEEE Micro, v.15 n.1, p.21-28, February 1995 [doi>10.1109/40.342014 ]
• 10: Nanette J. Boden , Danny Cohen , Robert E. Felderman , Alan E. Kulawik , Charles L. Seitz , Jakov N. Seizovic , Wen-King Su, Myrinet: A Gigabit-per-Second Local Area Network, IEEE Micro, v.15 n.1, p.29-36, February 1995 [doi>10.1109/40.342015 ]
• 11: CARREIRA, J., SILVA, J., LANGENDOEN, K., AND BAL, H. 1997. Implementing tuple space with threads. In Proceedings of the International Conference on Parallel and Distributed Systems (Euro-PDS'97). 259-264.
• 12: CASTRO, M., GUEDES, P., SEQUEIRA, M., AND COSTA, M. 1996. Efficient and flexible object sharing. In Proceedings of the 1996 International Conference on Parallel Processing. Vol. 1. 128-137.
• 13: David Chaiken , Craig Fields , Kiyoshi Kurihara , Anant Agarwal, Directory-Based Cache Coherence in Large-Scale Multiprocessors, Computer, v.23 n.6, p.49-58, June 1990 [doi>10.1109/2.55500 ]
• 14: Satish Chandra , James R. Larus, Optimizing communication in HPF programs on fine-grain distributed shared memory, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.100-111, June 18-21, 1997, Las Vegas, Nevada, United States
• 15: Cox, A., DWARKADAS, S., KELEHER, P., AND ZWAENEPOEL, W. 1994. TreadMarks: Distributed shared memory on standard workstations and operating systems. In Proceedings of the Winter 94 Usenix Conference. USENIX Assoc., Berkeley, Calif., 115-131.
• 16: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 17: Sandhya Dwarkadas , Alan L. Cox , Willy Zwaenepoel, An integrated compile-time/run-time software distributed shared memory system, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.186-197, October 01-04, 1996, Cambridge, Massachusetts, United States
• 18: B. Fleisch , G. Popek, Mirage: a coherent distributed shared memory design, Proceedings of the twelfth ACM symposium on Operating systems principles, p.211-223, November 1989
• 19: David S. Greenberg , James K. Park , Eric J. Schwabe, The cost of complex communication on simple networks, Journal of Parallel and Distributed Computing, v.35 n.2, p.133-141, June 15, 1996 [doi>10.1006/jpdc.1996.0076 ]
• 20: 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 ]
• 21: Andrew S. Grimshaw , Jon B. Weissman , W. Timothy Strayer, Portable run-time support for dynamic object-oriented parallel processing, ACM Transactions on Computer Systems (TOCS), v.14 n.2, p.139-170, May 1996 [doi>10.1145/227695.227696]
• 22: Matthew Haines , Koen Langendoen, Platform-Independent Runtime Optimizations Using OpenThreads, Proceedings of the 11th International Symposium on Parallel Processing, p.460, April 01-05, 1997
• 23: K. L. Johnson , M. F. Kaashoek , D. A. Wallach, CRL: high-performance all-software distributed shared memory, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.213-226, December 03-06, 1995, Copper Mountain, Colorado, United States
• 24: KAASHOEK, M. 1992. Group communication in distributed computer systems. Ph.D. thesis, Vrije Universiteit, Amsterdam.
• 25: Peter J. Keleher , Chau-Wen Tseng, Enhancing Software DSM for Compiler-Parallelized Applications, Proceedings of the 11th International Symposium on Parallel Processing, p.490-499, April 01-05, 1997
• 26: Leonidas Kontothanassis , Galen Hunt , Robert Stets , Nikolaos Hardavellas , Michał Cierniak , Srinivasan Parthasarathy , Wagner Meira, Jr. , Sandhya Dwarkadas , Michael Scott, VM-based shared memory on low-latency, remote-memory-access networks, Proceedings of the 24th annual international symposium on Computer architecture, p.157-169, June 01-04, 1997, Denver, Colorado, United States
• 27: K. Langendoen , J. Romein , R. Bhoedjang , H. Bal, Integrating polling, interrupts, and thread management, Proceedings of the 6th Symposium on the Frontiers of Massively Parallel Computation, p.13, March 27-31, 1996
• 28: LEE, J. 1993. Concord: Re-thinking the division of labor in a distributed shared memory system. Tech. Rep. TR-93-12-05, Univ. of Washington, Seattle, Wash.
• 29: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Wolf-Dietrich Weber , Anoop Gupta , John Hennessy , Mark Horowitz , Monica S. Lam, The Stanford Dash Multiprocessor, Computer, v.25 n.3, p.63-79, March 1992 [doi>10.1109/2.121510 ]
• 30: Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989 [doi>10.1145/75104.75105]
• 31: Honghui Lu , Alan L. Cox , Sandhya Dwarkadas , Ramakrishnan Rajamony , Willy Zwaenepoel, Compiler and software distributed shared memory support for irregular applications, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.48-56, June 18-21, 1997, Las Vegas, Nevada, United States
• 32: Honghui Lu , Sandhya Dwarkadas , Alan L. Cox , Willy Zwaenepoel, Message passing versus distributed shared memory on networks of workstations, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.37-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224285]
• 33: Honghui Lu , Sandhya Dwarkadas , Alan L. Cox , Willy Zwaenepoel, Quantifying the performance differences between PVM and TreadMarks, Journal of Parallel and Distributed Computing, v.43 n.2, p.65-78, June 15, 1997 [doi>10.1006/jpdc.1997.1332 ]
• 34: Lucco, S. 1987. A heuristic Linda kernel for hypercube multiprocessors. In Proceedings of the Conference on Hypercube Multiprocessors. 32-38.
• 35: MINNICH, R. AND FARBER, D. 1990. Reducing host load, network load, and latency in a distributed shared memory. In Proceedings of the l Oth International Conference on Distributed Computing Systems. 468-475.
• 36: Rishiyur S. Nikhil, Cid: A Parallel, "Shared-Memory" C for Distributed-Memory Machines, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.376-390, August 08-10, 1994
• 37: Scott Pakin , Mario Lauria , Andrew Chien, High performance messaging on workstations: Illinois fast messages (FM) for Myrinet, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.55-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224360]
• 38: Larry Peterson , N. Hutchinson , Sean O'Malley , Herman Rao, The x-kernel: A Platform for Accessing Internet Resources, Computer, v.23 n.5, p.23-33, May 1990 [doi>10.1109/2.53352 ]
• 39: Mukund Raghavachari , Anne Rogers, Ace: linguistic mechanisms for customizable protocols, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.80-89, June 18-21, 1997, Las Vegas, Nevada, United States
• 40: T. Ruhl , H. E. Bal, Optimizing atomic functions using compile-time information, Proceedings of the conference on Programming Models for Massively Parallel Computers, p.68, October 09-12, 1995
• 41: RUHL, T., BAL, H., BHOEDJANG, R., LANGENDOEN, K., AND BENSON, G. 1996. Experience with a portability layer for implementing parallel programming systems. In Proceedings of the 1996 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA '96). 1477-1488.
• 42: Daniel J. Scales , Kourosh Gharachorloo , Chandramohan A. Thekkath, Shasta: a low overhead, software-only approach for supporting fine-grain shared memory, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.174-185, October 01-04, 1996, Cambridge, Massachusetts, United States
• 43: SCALES, D. AND LAM, M. 1994. The design and evaluation of a shared object system for distributed memory machines. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation. USENIX Assoc., Berkeley, Calif., 101-114.
• 44: Ioannis Schoinas , Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , James R. Larus , David A. Wood, Fine-grain access control for distributed shared memory, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.297-306, October 05-07, 1994, San Jose, California, United States
• 45: Jaswinder Pal Singh , Wolf-Dietrich Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory, ACM SIGARCH Computer Architecture News, v.20 n.1, p.5-44, March 1992 [doi>10.1145/130823.130824]
• 46: E. A. West , A. S. Grimshaw, Braid: integrating task and data parallelism, Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation (Frontiers'95), p.211, February 06-09, 1995
• 47: Gregory V. Wilson , Henri E. Bal, Using the Cowichan Problems to Assess the Usability of Orca, IEEE Parallel & Distributed Technology: Systems & Technology, v.4 n.3, p.36-44, September 1996 [doi>10.1109/88.532138 ]
• 48: Gregory V. Wilson , Paul Lu , Bjane Stroustrup, Parallel Programming Using C++, MIT Press, Cambridge, MA, 1996

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming; Distributed programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Design, Languages, Performance

Keywords:
distributed shared memory, parallel processing, portability