More Web Proxy on the site http://driver.im/

article

Free access

Hiding communication latency and coherence overhead in software DSMs

Authors:

L. I. Kontothanassis,

C. L. AmorimAuthors Info & Claims

ACM SIGOPS Operating Systems Review, Volume 30, Issue 5

Pages 198 - 209

https://doi.org/10.1145/248208.237185

Published: 01 September 1996 Publication History

Abstract

In this paper we propose the use of a PCI-based programmable protocol controller for hiding communication and coherence overheads in software DSMs. Our protocol controller provides three different types of overhead tolerance: a) moving basic communication and coherence tasks away from computation processors; b) prefetching of diffs; and c) generating and applying diffs with hardware assistance. We evaluate the isolated and combined impact of these features on the performance of TreadMarks. We also compare performance against two versions of the Shrimp-based AURC protocol. Using detailed execution-driven simulations of a 16-node network of workstations, we show that the greatest performance benefits provided by our protocol controller come from our hardware-supported diffs. Reducing the burden of communication and coherence transactions on the computation processor is also beneficial but to a smaller extent. Prefetching is not always profitable. Our results show that our protocol controller can improve running time performance by up to 50% for TreadMarks, which means that it can double the TreadMarks speedups. The overlapping implementation of TreadMarks performs as well or better than AURC for 5 of our 6 applications. We conclude that the simple hardware support we propose allows for the implementation of high-performance software DSMs at low cost. Based on this conclusion, we are building the NCP₂ parallel system at COPPE/UFRJ.

References

[1]

A. Agarwal, R. Bianchini, D. Chaiken, K.L. Johnson, D. Kranz, J. Kubiatowicz, B.-H. Lim, K. Mackenzie, and D. Yeung. The MIT Alewife Machine: Architecture and Performance. In Proceedings of the ~2nd Annual Internat~onaI Symposium on Computer Architecture, June 1995.]]

Digital Library

[2]

R. Bianchini and B.-H. Lira. Evaluating the Performance of Multithreading and Prefetching in Shared-Memory Multiprocessors. To appear in Journal of Parallel and Distributed Computing, spectal issue on Multithreading for MuItiprocessors, October 1996.]]

Digital Library

[3]

R. Bianchini, R. Pinto, and C. L. Amorim. Page Fault Behavior and Prefetching in Software DSMs. Technical Report ES-401/96, COPPE Systems Engineering, Federal University of Rio de Janeiro, July 1996.]]

[4]

M. Blumrich, K. Li, R. Alpert, C. Dubnicki, E. Felten, and J. Sandberg. Virtual Memory Mapped Network Interface for the SHRIMP Multicomputer. In Proceedings of the 21st An~zual International $ympoai~m on Computer Architecture, pages 142-153, April 1994.]]

Digital Library

[5]

D. Callahan, K. Kennedy, and A. Porterfield. Software Prefetching. Proceedzngs of the dth International Confer- ~nce on ArchztecturaI Support for Programming Languages and Operating Systems, pages 40-52, April 1991.]]

Digital Library

[6]

J. B. Carter, J. K. Bennett, and W. Zwaenepoel. Implementation and Performance of Munin. In Proceedings of the 13th Symposium on Operating Systems Principles, October 1991.]]

Digital Library

[7]

D. Culler etaI. Parallel Programming in Split-C. in Proceedings of Supercomputing '93, pages 262-273, November 1993.]]

Digital Library

[8]

F. Dahlgren and P. Stenstrom. Effectiveness of Hardware- Based Stride and Sequential Prefetching in Shared-Memory Multiprocessors. In Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, January 1995.]]

Digital Library

[9]

F. Dahlgren and P. Stenstrom. Reducing the Write Traffic for a Hybrid Cache Protocol. In Proceedings of the 199,1 International Conference on Parallel Processing, August 1994.]]

Digital Library

[10]

S. Dwarkadas, A. Cox, and W. Zwaenepoel. An Integrated Compile-Time/Run-Time Software Distributed Shared Memory System. In Proceedings of the 7th International Conference on Architectural Support for Programming Languages and Operating Systems, Oct 1996.]]

Digital Library

[11]

S. Dwarkadas, P. Keleher, A. Cox, and W. Zwaenepoel. Evaluation of Release Consistent Software Distributed Shared Memory on Emerging Network Technology. In Proceedings of the 20~d Annual International Symposium on Computer Architecture, May 1993.]]

Digital Library

[12]

L. Iftode, C. Dubnicki, E. Felten, and K. Li. Improving Release-Consistent Shared Virtual Memory using Automatic Update. In Proceedings of the ~nd IEEE Symposium on High- Performance Computer Architecture, February 1996.]]

Digital Library

[13]

P. Keleher. Coherence as an Abstract Type. Technical Report CS-TR-3544, Department of Computer Science, University of Maryland, Oct 1995.]]

Digital Library

[14]

P. Keleher, A. L. Cox, and W. Zwaenepoel. Lazy Release Consistency for Software Distributed Shared Memory. in Proceedings of the 19th Annual International Symposium on Computer Architecture, pages 13-21, May 1992.]]

Digital Library

[15]

P. Keleher, S. Dwarkadas, A. Cox, and W. Zwaenepoel. TreadMarks: Distributed Shared Memory on Standard Workstations and Operating Systems. in Proceedings of the USENIX Winter '9~ Technical Conference, pages 17-21, Jan 1994.]]

Digital Library

[16]

Kendall Square Research. KSRi Principles of Operation, 1992.]]

[17]

L. I. Kontothanassis and M. L. Scott. Distributed Shared Memory for New Generation Networks. In Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, February 1996.]]

[18]

J. Kuskin et aI. The Stanford FLASH Multiprocessor. In Proceedings of the 21st Annual International Symposium on Computer Architecture, Chicago, iL, April 1994.]]

Digital Library

[19]

D. Lenoski, J. Laudon, T. Joe, D. Nakakira, L. Stevens, A. Gupta, and J. Hennessy. The DASH Prototype: Logic Overhead and Performance. IEEE Transactions on Parallel and Distributed Systems, 4(1):41-61, Jan 1993.]]

Digital Library

[20]

T. Mowry and A. Gupta. Tolerating Latency Through Software-Controlled Prefetching in Shared-Memory Multiprocessors. Journal of Parallel and Distributed Computing, 12(2):87-106, June 1991.]]

Digital Library

[21]

S. K. Reinhardt, J. R. Larus, and D. A. Wood. Tempest and Typhoon: User-Level Shared Memory. In Proceedings of the 21st Annual International Symposium on Computer Archztecture, Chicago, IL, April 1994.]]

Digital Library

[22]

S. K. Reinhardt, R. W. Pfile, and D. A. Wood. Decoupled Hardware Support for Distributed Shared Memory. In Proceedings of the ~3rd Annual International Symposium on Computer Architecture, Philadelphia, PA, May 1996.]]

Digital Library

[23]

I. Schoinas, B. Falsafi, A. Lebeck, S. Reinhardt, J. Larus, and D. Wood. Fine-grain Access Control for Distributed Shared Memory. Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 297-307, October 1994.]]

Digital Library

[24]

J. E. Veenstra and R. J. Fowler. MINT: A Front End for Efficient Simulation of Shared-Memory Multiprocessors. In Proceedings of the 2nd International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, 1994.]]

Digital Library

[25]

S. C. Woo, M. Ohara, g. Torrie, J. P. Singh, and A. Gupta. The SPLASH-2 Programs: Characterization and Methodological Considerations. In Proceedings of the 22rid Annual International Symposium on Computer Architecture, pages 24-36, May 1995.]]

Digital Library

Cited By

Cai JStrazdins P(2012)An Accurate Prefetch Technique for Dynamic Paging Behaviour for Software Distributed Shared MemoryProceedings of the 2012 41st International Conference on Parallel Processing10.1109/ICPP.2012.16(209-218)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1109/ICPP.2012.16
Yan SZhou XGao YChen HWu GLuo SSaha B(2011)Optimizing a shared virtual memory system for a heterogeneous CPU-accelerator platformACM SIGOPS Operating Systems Review10.1145/1945023.194503545:1(92-100)Online publication date: 18-Feb-2011
https://dl.acm.org/doi/10.1145/1945023.1945035
Cai JStrazdins PRendell A(2010)Region-Based Prefetch Techniques for Software Distributed Shared Memory SystemsProceedings of the 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing10.1109/CCGRID.2010.16(113-122)Online publication date: 17-May-2010
https://dl.acm.org/doi/10.1109/CCGRID.2010.16
Show More Cited By

Index Terms

Hiding communication latency and coherence overhead in software DSMs

Recommendations

Hiding communication latency and coherence overhead in software DSMs
ASPLOS VII: Proceedings of the seventh international conference on Architectural support for programming languages and operating systems

In this paper we propose the use of a PCI-based programmable protocol controller for hiding communication and coherence overheads in software DSMs. Our protocol controller provides three different types of overhead tolerance: a) moving basic ...
Hiding communication latency and coherence overhead in software DSMs

In this paper we propose the use of a PCI-based programmable protocol controller for hiding communication and coherence overheads in software DSMs. Our protocol controller provides three different types of overhead tolerance: a) moving basic ...
Reducing coherence overhead of barrier synchronization in software DSMs
SC '98: Proceedings of the 1998 ACM/IEEE conference on Supercomputing

Software Distributed Shared Memory (SDSM)systems usually have the large coherence granularity that is imposed by the underlying virtual memory page size. To alleviate the coherence overheads such as the net worktraffic to preserve the coherence, or page ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review

ACM SIGOPS Operating Systems Review Volume 30, Issue 5

Dec. 1996

273 pages

ISSN:0163-5980

DOI:10.1145/248208

Chairmen:
Bill Dally
Massachusetts Institute of Technology
,
Susan Eggers
Univ. of Washington, Seattle

Issue’s Table of Contents

ASPLOS VII: Proceedings of the seventh international conference on Architectural support for programming languages and operating systems
October 1996
290 pages
ISBN:0897917677
DOI:10.1145/237090
Chairmen:
Bill Dally
Massachusetts Institute of Technology
,
Susan Eggets
Univ. of Washington, Seattle

Copyright © 1996 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1996

Published in SIGOPS Volume 30, Issue 5

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
730
Total Downloads

Downloads (Last 12 months)206
Downloads (Last 6 weeks)56

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cai JStrazdins P(2012)An Accurate Prefetch Technique for Dynamic Paging Behaviour for Software Distributed Shared MemoryProceedings of the 2012 41st International Conference on Parallel Processing10.1109/ICPP.2012.16(209-218)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1109/ICPP.2012.16
Yan SZhou XGao YChen HWu GLuo SSaha B(2011)Optimizing a shared virtual memory system for a heterogeneous CPU-accelerator platformACM SIGOPS Operating Systems Review10.1145/1945023.194503545:1(92-100)Online publication date: 18-Feb-2011
https://dl.acm.org/doi/10.1145/1945023.1945035
Cai JStrazdins PRendell A(2010)Region-Based Prefetch Techniques for Software Distributed Shared Memory SystemsProceedings of the 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing10.1109/CCGRID.2010.16(113-122)Online publication date: 17-May-2010
https://dl.acm.org/doi/10.1109/CCGRID.2010.16
Zhang ZHu YMidkiff SHorner-Miller B(2006)CycleMeterProceedings of the 2006 ACM/IEEE conference on Supercomputing10.1145/1188455.1188584(124-es)Online publication date: 11-Nov-2006
https://dl.acm.org/doi/10.1145/1188455.1188584
Zhang ZHu YMidkiff S(2006)CycleMeter: Detecting Fraudulent Peers in Internet Cycle SharingACM/IEEE SC 2006 Conference (SC'06)10.1109/SC.2006.20(32-32)Online publication date: Nov-2006
https://doi.org/10.1109/SC.2006.20
Petit SSahuquillo JPont AKaeli D(2006)Addressing a workload characterization study to the design of consistency protocolsThe Journal of Supercomputing10.1007/s11227-006-7866-438:1(49-72)Online publication date: 1-Oct-2006
https://dl.acm.org/doi/10.1007/s11227-006-7866-4
Park SMaeng S(2006)Log-based rollback recovery without checkpoints of shared memory in software DSMThe Journal of Supercomputing10.1007/s11227-006-1667-735:2(141-154)Online publication date: 1-Feb-2006
https://dl.acm.org/doi/10.1007/s11227-006-1667-7
Hu WShi WTang Z(2006)JIAJIA: A software DSM system based on a new cache coherence protocolHigh-Performance Computing and Networking10.1007/BFb0100607(461-472)Online publication date: 17-Nov-2006
https://doi.org/10.1007/BFb0100607
Petit SSahuquillo JPont A(2005)A Comparison Study of the HLRC-DU Protocol versus a HLRC Hardware Assisted ProtocolProceedings of the 13th Euromicro Conference on Parallel, Distributed and Network-Based Processing10.1109/EMPDP.2005.2(197-204)Online publication date: 9-Feb-2005
https://dl.acm.org/doi/10.1109/EMPDP.2005.2
Nanri TSato HShimasaki M(2005)Cost estimation of coherence protocols of software managed cache on distributed shared memory systemHigh Performance Computing10.1007/BFb0024228(335-342)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0024228
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Issue’s Table of Contents