An efficient caching support for critical sections in large-scale shared-memory multiprocessors
Pages 34 - 47
Abstract
Directory-based and software-assisted schemes are the two main approaches to solving the cache coherence problem in large scale shared-memory multiprocessors. Until now, the emphasis in software-assisted schemes has been on ascertaining consistency within parallel constructs such as DoAll or DoAcross loops. In this paper, we propose a timestamped-based approach which also allows caching within critical sections. This scheme combines the best features of software-assisted and directory-based cache coherence protocols. It is based on a compile time analysis of interactions among critical sections and execution time local detection of cache incoherence by comparing the times when a variable was last written and last updated in the cache. A quantitative evaluation based on synthetic traces shows that this scheme results in hit ratios almost as high as in directory-based solutions while significantly reducing the network traffic.
References
[1]
AGARWAL, A., SIMONI, R., HENNESSY, J., AND HOROWITZ, M. An evaluation of directory schemes for cache coherence. In Proceedings of the 15th Annual International Symposium on Computer Architecture (June 1988), pp. 280- 289.
[2]
AMDAHL, G. M. Validity' of the single processor approach to achieve large scale computing capabilities. In AFIPS Conference Proceedings National Computer Conference (1967), pp. 483- 485.
[3]
ARCHIBALD, J., AND BAER, J.-L. An economical solution to the cache coherence problem. In Proceedings of the 12th Annual International Symposium on Computer Architecture (June 1985), pp. 355-362.
[4]
ARCHIBALD, J. K. The Cache Coherence Problem in Shared-Memory Mulliprocessors. PhD thesis, University of Washington, November 1986.
[5]
B BN. Butterfly Parallel Processor Overview, version 1 ed.
[6]
BITAR, P., AND DESPAIN, A. M. Multiprocessot cache synchronization : Issues, innovations, evolution. In Proceedings of the 13th Annual International Symposium on Computer Archileclure (June 1986), pp. 424-433.
[7]
CENSIER, L. M., AND FEAUTRIER, P. A new solution to coherence problems in multicache systems. IEEE Transactions on Computers C-27, 12 (December 1978), 1112-1118.
[8]
CHEONG, H., AND VEIDENBAUM, A. A version control approach to cache coherence. In Proceedings of the 1989 International Conference on Supercomputing (June 1989), pp. 322-330.
[9]
CHEONG, H., AND VEIDENBAUM, A. V. A cache coherence scheme with fast selective invalidation. In Proceedings of the 15th Annual International Symposium on Computer Architecture (June 1988), pp. 299-307.
[10]
CYTRON, R., KARLOVSKY, S., AND MCAULIFFE, K. P. Automatic management of programmable caches (extended abstract). In Proceedings of the 1988 International Conference on Parallel Processing, Vol. H Software (August 1988), pp. 229-238.
[11]
Dusols, M., AND BRIGGS, F. Effects of cache coherency in multiprocessors. IEEE Transactions on Computers C-31, 11 (November 1982), 1083-1099.
[12]
EGGERS, S. J. Simulation Analysis of Data Sharing in Shared Memory Multiprocessors. PhD thesis, University of California, Berkeley, February 1989.
[13]
GAJSKI, D., KucK, D., LAWRIE, D., AND SAMEH, A. Cedar - a large scale multiprocessor. Computer Architecture News 11, 1 (March 1983), 7-11.
[14]
GOODMAN, J. R. Using cache memory to reduce processor-memory traffic. In Proceedings of the l Oth Annual International Symposium on Computer Architecture (June 1983), pp. 124-131.
[15]
GOODMAN, J. R., VERNON, M. K., AND WOEST, P. J. Efficient synchronization primitives for large-scale cache-coherent multipro- ~essors. In Proceedings of the 3rd International Conference on Architectural Support for Programming Languages and Operating Systems (April 1989), pp. 64-75.
[16]
GOTTLmB, A., GrUSHMAN, R., KrtUSKnL, C. P., MCAULrFFE, K. P., RUDOLPH, L., AND SNIrt, M. The NYU Ultracomputer- Designing a MIMD, Shared-Memory Parallel Machine. In Proceedings of the 9th Annual International Symposium on Computer Architecture (April 1982), pp. 27-42.
[17]
KATZ, R. H., E66Erts, S. J., WOOD, D. A., PERKINSK, C. L., AND SHELDON, R. G. Implementing a cache consistency protocol. In Proceedings of the 12th Annual International Symposium on Computer Architecture (June 1985), pp. 276-283.
[18]
LEE, J., AND RAMACHANDttAN, V. Synchronization with multiprocessor caches. Tech. Rep. GIT-ICS-89/47, School of Information and Computer Science, Georgia institute of Technology, Nov. 1989.
[19]
LEE, R. L. The effectiveness of caches and data prefetch buffers in large-scale shared memory multiprocessors. Tech. Rep. CSRD Report. No. 670, Center for Supercomputing Research and Development, University of Illinois, May 1987.
[20]
MCAULIFFE, K. P. Analysis of Cache Memories in Highly Parallel Systems. PhD thesis, New York University, May 1986.
[21]
MIN, S. L., AND BAER, J.-L. A timestampbased cache coherence scheme. In Proceedings of the 1989 International Conference on Parallel Processing, Vol. I Architecture (August 1989), pp. 23-32.
[22]
PFISTER, G. F., BRANTLEY, W. C., GEORGE, D. A., HARVEY, S. L., KLEINFELDER, W. J., MCAULIFFE, K. P., MELTON, E. A., NORTON, V. A., AND WEISS, J. The IBM Research Parallel Processor Prototype (RP3): introduction and Architecture. In Proceedings of the 1985 International Conference on Parallel Processing (August 1985), IEEE, pp. 764-771.
[23]
RUDOLPH, L., AND SEGALL, Z. Dynamic decentralized cache consistency schemes for MIMD parallel processors. In Proceedings of the l~th Annual International Symposium on Computer Architecture (June 1985), pp. 340-347.
[24]
SMITH, A. J. CPU cache consistency with software support and using "one time identifiers". In Proceedings of the Pacific Computer Communications Symposium (October 1985), pp. 22-24.
[25]
SMITH, A. J. Line (block) size choice for CPU caches. IEEE Transactions on Computers 6".36, 9 (September 1987), 1063-1075.
[26]
TANG, C. K. Cache design in the tightly coupled multiprocessor system. In AFIPS Conference Proceedings National Computer Conference (1976), pp. 749-753.
[27]
TnaeKErt, C. P., AND STEWART, L. C. Firefly : a multiprocessor workstation. In Proceedings Second International Conference on Architectural support for Programming Languages and Operating Systems (October, 1987), pp. 164- 172.
[28]
VF.IDENBAUM, A. V. A compiler-assisted cache coherence solution for multiprocessors. In Proceedings of the 1986 In~ernational Conference on Parallel Proessing (August 1986), pp. 1029- 1036.
[29]
WEBER, W., AND GUPTA, A. Analysis of cache invalidation patterns in multiprocessors. In Proceedings of the 3rd International Conference on Architectural Support for Programming Languages and Operating Systems (April 1989), pp. 243-256.
[30]
WULF, W. A., AND BELL, C. G. C.mmp- A multi-mini processor. In Proc. Fall Joint Computer Conference (Montvale, New Jersey, December 1972), pp. 765-777.
[31]
YEN, W. C., YEN, D. W. L., AND FU, K.-S. Data coherence problem in a multicache system. IEEE Transactions on Compulers C-3~, 1 (January 1985), 56-65.
Index Terms
- An efficient caching support for critical sections in large-scale shared-memory multiprocessors
Recommendations
An efficient caching support for critical sections in large-scale shared-memory multiprocessors
ICS '90: Proceedings of the 4th international conference on SupercomputingDirectory-based and software-assisted schemes are the two main approaches to solving the cache coherence problem in large scale shared-memory multiprocessors. Until now, the emphasis in software-assisted schemes has been on ascertaining consistency ...
Minimizing the Directory Size for Large-Scale Shared-Memory Multiprocessors
Directory-based cache coherence schemes are commonly used in large-scale shared-memory multiprocessors, but most of them rely on heuristics to avoid large hardware requirements. We proposed using physical address mapping on directories to significantly ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sept. 1990
489 pages
Copyright © 1990 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 June 1990
Published in SIGARCH Volume 18, Issue 3b
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations4Total Citations
- 379Total Downloads
- Downloads (Last 12 months)31
- Downloads (Last 6 weeks)3
Reflects downloads up to 17 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in