Multiple-writer entry consistency
Abstract
In this paper, we present the design, implementation and evaluation of a new distributed shared memory (DSM) coherence model called multiple-writer entry consistency (MEC). MEC combines the efficient communication mechanisms of Lazy Release Consistency (LRC) with the flexible data management of the Shared Regions [17, 11] and Entry Consistency (EC) models [5]. This is achieved in MEC by decoupling synchronization from coherence (in contrast to the tight coupling of synchronization and coherence present in EC)while retaining the familiar synchronization structure found in Release Consistent (RC) programs. The advantage of MEC is that it allows region-based coherence protocols (those that manage data at the granularity of user-defined shared regions) to be used along side page-based protocols within an application and within the RC framework. Our experimental evaluation on an 8 processor system shows that using MEC reduces parallel execution times by margins ranging from 5% to 46% in five of the six applications that we study. However, the parallel execution time of the LRC version of the remaining application is lower than the MEC version by 48%. We conclude that offering both page-based and region-based models for coherence within the same system is not only practical but necessary.
References
[1]
{1} S.V. Adve, A.L. Cox, S. Dwarkadas, R. Rajamony and W. Zwaenepoel, "A Comparison of Entry Consistency and Lazy Release Consistency Implementations", Proceedings of the 2nd International Symposium on High-Performance Computer Architecture, pp. 26-37, February, 1996.]]
[2]
{2} S.V. Adve and M.D. Hill, "Weak Ordering - A New Definition", Proceedings of the 17th Annual International Symposium on Computer Architecture, pp. 2-14, May 1990.]]
[3]
{3} C. Amza, A.L. Cox, K. Rajamani, and W. Zwaenepoel, "Tradeoffs between False Sharing and Aggregation in Software Distributed Shared Memory", Proceedings of the Sixth Conference on Principles and Practice of Parallel Programming, pp. 90-99, June 1997.]]
[4]
{4} E. Arjomandi, W. O'Farrell, I. Kalas, G. Koblents, F. Eigler and G. Gao, "ABC++: Concurrency by Inheritance in C++", IBM Systems Journal, Vol. 34, No. 1, pp. 120-137, 1995.]]
[5]
{5} B. Bershad, M. Zekauskas and W. Sawdon, "The Midway Distributed Shared Memory System", Proceedings of COMPCOM '93, pp. 528-537, February, 1993.]]
[6]
{6} T. Brecht, H. Sandhu "The Region Trap Library: Handling Traps on Application-Defined Regions of Memory", Proceedings of the 1999 USENIX Technical Conference, to appear.]]
[7]
{7} J. Carter, J. Bennett and W. Zwaenepoel, "Implementation and Performance of Munin", Proceedings of the 13th Symposium on Operating Systems Principles, pp. 152-164, October, 1991.]]
[8]
{8} M. Feeley and H. Levy, "Distributed Shared Memory with Versioned Objects", Proceedings of the Conference on Object-Oriented Programming Systems Languages, and Applications, October, 1992.]]
[9]
{9} K. Gharachorloo, D. Lenoski, J. Laudon, P. Gibbons, A. Gupta, J. Hennessy, "Memory Consistency and Event Ordering in Scalable Shared Memory Multiprocessors", Proceedings of the 17th Annual Symposium on Computer Architecture, pp. 15-26, May, 1990.]]
[10]
{10} A. Itzkovitz and A. Schuster, "MultiView and Millipage - Fine-Grain Sharing in Page-Based DSMs", Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI '99), February, 1999.]]
[11]
{11} K. Johnson, F. Kaashoek and D. Wallach, "CRL: High-Performance All Software Distributed Shared Memory", Proceedings of the 15th Symposium on Operating Systems Principles, pp. 213-228, December, 1995.]]
[12]
{12} P. Keleher, "The Relative Importance of Concurrent Writers and Weak Consistency Models", Proceedings of the 16th International Conference on Distributed Computing Systems, May 28, 1996.]]
[13]
{13} P. Keleher, A. Cox, S. Dwarkadas and W. Zwaenepoel, "TreadMarks: Distributed Shared Memory on Standard Workstations and Operating Systems", Proceedings of the Winter 1995 USENIX Conference, pp. 115-131, 1994.]]
[14]
{14} H. Lu, S. Dwarkadas, A.L. Cox, and W. Zwaenepoel, "Message Passing Versus Distributed Shared Memory on Networks of Workstations", Proceedings of Supercomputing '95, December, 1995.]]
[15]
{15} L.R. Monnerat and R. Bianchini, "ADSM: A Hybrid DSM Protocol that Efficiently Adapts to Sharing Patterns", Federal University of Rio de Janerio, COPPE Systems Engineering Computer Science Department, Technical Report ES-425/97, March, 1997.]]
[16]
{16} N. Neves, M. Castro, and P. Guedes, "A Checkpoint Protocol for an Entry Consistent Shared Memory System", Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing August, 1994.]]
[17]
{17} H. Sandhu, B. Gamsa and S. Zhou, "The Shared Regions Approach to Software Cache Coherence on Multiprocessors", Proceedings of the Fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 229-238, May, 1993.]]
[18]
{18} J.P. Singh, W.-D. Weber and A. Gupta, "SPLASH: Stanford Parallel Applications for Shared-Memory", Computer Architecture News, Vol. 20, No. 1, pp. 5-44, March, 1992.]]
Index Terms
- Multiple-writer entry consistency
Recommendations
Data parallel programming in an adaptive environment
IPPS '95: Proceedings of the 9th International Symposium on Parallel ProcessingFor better utilization of computing resources, it is important to consider parallel programming environments in which the number of available processors varies at runtime. In this paper, we discuss runtime support for data parallel programming in such ...
WeeFence: toward making fences free in TSO
ISCA '13: Proceedings of the 40th Annual International Symposium on Computer ArchitectureAlthough fences are designed for low-overhead concurrency coordination, they can be expensive in current machines. If fences were largely free, faster fine-grained concurrent algorithms could be devised, and compilers could guarantee Sequential ...
WeeFence: toward making fences free in TSO
ICSA '13Although fences are designed for low-overhead concurrency coordination, they can be expensive in current machines. If fences were largely free, faster fine-grained concurrent algorithms could be devised, and compilers could guarantee Sequential ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Nova Science Publishers, Inc.
United States
Publication History
Published: 01 January 2001
Author Tags
Qualifiers
- Chapter
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025