Comparative study of page-based and segment-based software DSM through compiler optimization

ABSTRACT

The experimental results clearly show that the performance of ADSM scheme is limited by the communication of unnecessary data, while that of the UDSM scheme is limited by the instrumentation overhead. The UDSM scheme reduces transmission of unnecessary data and automatically prevents the severe false sharing at fetch-on-write, which is the problem in the page-based scheme.

REFERENCES

• 1: Harold Abelson , Gerald Jay Sussman , Julie Sussman, Structure and interpretation of computer programs, MIT Press, Cambridge, MA, 1985
• 2: Sarita V. Adve , Alan L. Cox , Sandhya Dwarkadas , Ramakrishnan Rajamony , Willy Zwaenepoel, A Comparison of Entry Consistency and Lazy Release Consistency Implementations, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.26, February 03-07, 1996
• 3: Gagan Agrawal , Joel Saltz, Interprocedural compilation of irregular applications for distributed memory machines, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.48-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224336]
• 4: Gagan Agrawal , Joel Saltz , Raja Das, Interprocedural partial redundancy elimination and its application to distributed memory compilation, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.258-269, June 18-21, 1995, La Jolla, California, United States
• 5: 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
• 6: B. N. Bershad, M. J. Zekauskas, and W. A. Sawdon. The Midway Distributed Shared Memory System. In Prec. of the 1993 CompCon Conf., pages 528-537, Feb. 1993.
• 7: Ross A. Overbeek , James Boyle, Portable Programs for Parallel Processors, Saunders College Publishing, Philadelphia, PA, 1987
• 8: Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990 [doi>10.1145/78969.78963]
• 9: F. C. Chow, Minimizing register usage penalty at procedure calls, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.85-94, June 20-24, 1988, Atlanta, Georgia, United States
• 10: John Cocke, Global common subexpression elimination, ACM SIGPLAN Notices, v.5 n.7, p.20-24, July 1970
• 11: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 12: A. L. Cox , S. Dwarkadas , P. Keleher , H. Lu , R. Rajamony , W. Zwaenepoel, Software versus hardware shared-memory implementation: a case study, Proceedings of the 21ST annual international symposium on Computer architecture, p.106-117, April 18-21, 1994, Chicago, Illinois, United States
• 13: G. B. Dantzig and B. C. Evans. Fourier-Motzkin Elimination and Its Dual. Journal of Corabinatorial Theory, A(14):288-297, 1973.
• 14: 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
• 15: Sandhya Dwarkadas , Kourosh Gharachorloo , Leonidas Kontothanassis , Daniel J. Scales , Michael L. Scott , Robert Stets, Comparative Evaluation of Fine- and Coarse-Grain Approaches for Software Distributed Shared Memory, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.260, January 09-12, 1999
• 16: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 17: Andrew Erlichson , Neal Nuckolls , Greg Chesson , John Hennessy, SoftFLASH: analyzing the performance of clustered distributed virtual shared memory, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.210-220, October 01-04, 1996, Cambridge, Massachusetts, United States
• 18: Liviu Iftode , Cezary Dubnicki , Edward W. Felten , Kai Li, Improving Release-Consistent Shared Virtual Memory using Automatic Update, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.14, February 03-07, 1996
• 19: Tatsushi Inagaki , Junpei Niwa , Takashi Matsumoto , Kei Hiraki, Supporting Software Distributed Shared Memory with an Optimizing Compiler, Proceedings of the 1998 International Conference on Parallel Processing, p.225, August 10-14, 1998
• 20: Dongming Jiang , Hongzhang Shan , Jaswinder Pal Singh, Application restructuring and performance portability on shared virtual memory and hardware-coherent multiprocessors, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.217-229, June 18-21, 1997, Las Vegas, Nevada, United States
• 21: Pete Keleher , Alan L. Cox , Willy Zwaenepoel, Lazy release consistency for software distributed shared memory, Proceedings of the 19th annual international symposium on Computer architecture, p.13-21, May 19-21, 1992, Queensland, Australia
• 22: C. Koelbel , P. Mehrotra, Compiling Global Name-Space Parallel Loops for Distributed Execution, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.440-451, October 1991 [doi>10.1109/71.97901]
• 23: K. Li. IVY: A Shared Virtual Memory System for Parallel Computing. In Proc. of the 1988 ICPP, pages 94-101, Aug. 1988.
• 24: Takashi Matsumoto , Kei Hiraki, MBCF: a protected and virtualized high-speed user-level memory-based communication facility, Proceedings of the 12th international conference on Supercomputing, p.259-266, July 1998, Melbourne, Australia [doi>10.1145/277830.277889]
• 25: T. Matsumoto and K. Hiraki. Memory-Based Communication Facilities and Asymmetric Distributed Shared Memory. In Innovative Architecture for Future Generation High-Performance Processors and Systems, pages 30-39, Los Alamitos, CA, 1998. IEEE Computer Society.
• 26: T. Matsumoto, T. Konraarashi, S. Uzuhara, and K. Hiraki. The Asymmetric Distributed Shared Memory using Memory-Based Communication Facilities. In Prec. of the 1996th IPSJ Computer System Symposium, Nov. 1996. (in Japanese).
• 27: T. Matsumoto, T. Komaarashi, S. Uzuhara, S. Takeoka, and K. Hiraki. A General-Purpose Massively-Parallel Operating System: &SS-CORE-Implementation Methods for Network of Workstations -. In IPSJ SIG Notes, volume 96-OS-73, pages 115-120, Aug. 1996. (in Japanese).
• 28: T. Matsumoto, J. Niwa, and K. Hiraki. Compiler-Assisted Distributed Shared Memory Schemes Using Memory-Based Communichtion Facilities. In Prec. of the 1998 PDPTA, volume 2, pages 875-882, July 1998.
• 29: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 30: Junpei Niwa , Tatsushi Inagaki , Takashi Matsumoto , Kei Hiraki, Efficient Implementation of Software Release Consistency on Asymmetric Distributed Shared Memory, Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97), p.198, December 18-20, 1997
• 31: R. Samanta , A. Bilas , L. Iftode , J. Singh, Home-Based SVM Protocols for SMP Clusters: Design and Performance, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.113, January 31-February 04, 1998
• 32: Joel H. Salz , Ravi Mirchandaney , Kay Crowley, Run-Time Parallelization and Scheduling of Loops, IEEE Transactions on Computers, v.40 n.5, p.603-612, May 1991 [doi>10.1109/12.88484]
• 33: D. J. Scales and K. Gharachorloo. Performance of the Shasta Distributed Shared Memory Protocol. Research Report 97/2, DEC Western Research Laboratory, Feb. 1997.
• 34: 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
• 35: Robert Paul Wilson , Monica S. Lam, Efficient, context-sensitive pointer analysis for c programs, 1998
• 36: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States
• 37: Yuanyuan Zhou , Liviu Iftode , Kai Li, Performance evaluation of two home-based lazy release consistency protocols for shared virtual memory systems, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.75-88, October 29-November 01, 1996, Seattle, Washington, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Code generation

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Design, Languages, Measurement, Performance, Standardization, Theory