Article

Free access

Life span strategy—a compiler-based approach to cache coherence

Author:

Hoichi CheongAuthors Info & Claims

ICS '92: Proceedings of the 6th international conference on Supercomputing

Pages 139 - 148

https://doi.org/10.1145/143369.143402

Published: 01 August 1992 Publication History

Abstract

In this paper, a cache coherence strategy with a combined software and hardware approach is proposed for large-scale multiprocessor systems. The new strategy has the scalability advantages of existing software strategies and does not rely on shared hardware resources to maintain coherence. It exploits as much intra-task temporal locality as previously proposed low-cost, compiler-based strategies such as Simple Invalidation and Fast Selective Invalidation. With a small amount of additional hardware and a small set of cache management instructions, the new strategy preserves more inter-task-level temporal locality than these strategies. It is an economical alternative and has potential performance close to that of more elaborate strategies such as Version Control and Time Stamp. Also, the new strategy is easily extendable to include Doacross loops.

References

[1]

A.J. Smxth, "CPU cache consistency with software support and using 'One Time Identifiers'," Proceedings Pacific Computer Communications Symposium, pp. 153-161, October 1985.

[2]

A. Veidenbaum, "A compder-asslsted cache coherence soluuon for multlprocessors," Proceedings 1986 Internattonal Conference on Parallel Processing, pp. 1029-1036, August 1986.

[3]

K.P. McAuliffe, "Analysis of cache memories in highly parallel systems," Tech. Rep. No. 269, Ph.D. dissertation, Courant Institute of Mathematical Sciences, NYU, 1986.

Digital Library

[4]

R.L. Lee, "The effectiveness of caches and data prefetch buffers In large-scale shared memory multlprocessors," Tech. Rep. No. 670, Ph.D. &ssertation, Umverslty of Ilhnois, Urbana, IL, August 1987.

Digital Library

[5]

R. Lee, P. Yew, and D. Lawrie, "Multiprocessor cache design considerations," Proceedings of the 14th Annual International Symposium on Computer Architecture, pp. 253-262, June 1987.

Digital Library

[6]

H. Cheong and A. Veldenbaum, "A cache coherence scheme with fast selective mvahdation," Proceedings of the 15th Annual International Symposium on Computer Architecture, p. 299, June 1988.

Digital Library

[7]

H. Cheong and A. V. Veidenbaum, "Stale data detection and coherence enforcement using flow analysis," Proceedings ofthe 1988 International Conference on Parallel Processing, vol. I, pp. 138- 145, August 1988.

[8]

R. Cytron, S. Karlovsky, and K. P. McAuhffe, "Automatic management of programmable caches," Proceedings the 1988 International Conference on Parallel Processing, vol. II, pp. 229-238, August 1988.

[9]

C.K. Tang, "Cache system design in the tightly coupled multiprocessor system," Proceedings NCC, vol. 45, pp. 749-753, 1976.

[10]

L. M. Censier and P. Feautrier, "A new soluuon to coherence problems in mult~cache systems," IEEE Transations on Computers, vot. C-27, no. I2, pp. 1112-1118, December, 1978.

[11]

J. ArchlbaId and J.-L. Baer, "An economical solution to the cache coherence problem," Proceedings of the 11th Annual International Symposium on Computer Architecture, pp. 355-362, June 5-7, 1984.

Digital Library

[12]

J.R. Goodman, "Using cache memory to reduce processor-memory traffic," Proceedings of the lOth Annual International Symposium on Computer Architecture, pp. 124-131, 1983.

Digital Library

[13]

E. McCrelght, "The dragon computer system: An early overview," tech. rep., Xerox Corp., September 1984.

[14]

M.S. Papamarcos and J. H. Patel, "A Iow-overhead coherence solution for multiprocessors with private cache memories," Proceedings of the 11th Annual International Symposium on Computer Architecture, pp. 348-354, June 1984.

Digital Library

[15]

L. Rudolph and Z. Segall, "Dynamic decentralized cache schemes for MIMD parallel processors," Proceedings of the 11th Annual International Symposium on Computer Archttecture, pp. 340-347, June 1984.

Digital Library

[16]

R. H. Katz, S. J. Eggers, D. A. Wood, C. L. Perkins, and R. G. Sheldon, "Implementing a cache consistency protocol," Proceedings of the 12th Annual International Sympostum on Computer Architecture, pp. 276-283, June 1985.

Digital Library

[17]

Y.-C. Chen and A. V. Veidenbaum, "A software coherence scheme with the assistance of directories," Proceedings 1989 International Conference on Supercomputing, June 1991.

Digital Library

[18]

H. Cheong and A. Veidenbaum, "A version control approach to cache coherence," Proceedings Internauonal Conference of Supercomputing 89, pp. 322-330, June 1989.

Digital Library

[19]

S. L. Min and J.-L. Baer, "A timestamp-based cache coherence scheme," Proceedings 1989 International Conference on Parallel Processing, I, Architecture:23-32, August 1989.

[20]

J. Fang and M. Lu, "A solution of cache ping-pong problem in RISC based parallel processing systems," Proceedings 1991 International Conference On Parallel Processing, I, Architecture:238-245, August 1991.

[21]

H. Cheong, "Compiler-directed cache coherence strategies for largescale shared-memory multiprocessor systems," Tech. Rep. CSRD No. 953, Ph.D. dissertation, Umversity of Ilhnols at Urbana- Champaign, January 1990.

Digital Library

[22]

J. R. Goodman, "Coherency for multlprocessor virtual address caches," Proceedings of the Second International Conference on Architecture Support for Programming Languages and Operating Systems (ASPLOS H), pp. 72-81, 1987.

Digital Library

[23]

U. Banerjee, "Data dependence in ordinary programs," Tech. Rep. No. 76-837, M.S. thests, Umverslty of Illinois at Urbana-Champaign, November 1976.

[24]

S. L. Min and J.-L. Baer, "Design and analysis of a scalable cache coherence scheme basaed on clocks and timestamps," IEEE Transacttons on Parallel and Dtstributed Systems, vol. 3, no. 1, January 1992.

Digital Library

[25]

M. Wolfe, "Optimizing compilers for supercomputers," Tech. Rep. No. UIUCDCS-R-82-1105, Ph.D. &ssertation, University of Illinois, Urbana, IL, October 1982.

Digital Library

[26]

J.-K. Peir, K. So, and J.-H. Tang, "Inter-section locality of shared data in parallel programs," Proceedings 1991 International Conference On Parallel Processing, I, Architecture:278-286, August 1991.

Cited By

Pyka AZaykov PCasse HOzaktas HRochange CUhrig S(2015)Case study: Performance and WCET analysis for parallelised avionic applications with ODC²2015 IEEE 13th International Conference on Industrial Informatics (INDIN)10.1109/INDIN.2015.7281939(1400-1407)Online publication date: Jul-2015
https://doi.org/10.1109/INDIN.2015.7281939
Pyka ARohde MUhrig S(2014)Extended performance analysis of the time predictable on-demand coherent data cache for multi- and many-core systems2014 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS XIV)10.1109/SAMOS.2014.6893201(107-114)Online publication date: Jul-2014
https://doi.org/10.1109/SAMOS.2014.6893201
Pyka ARohde MUhrig S(2014)A real-time capable coherent data cache for multicoresConcurrency and Computation: Practice & Experience10.1002/cpe.317226:6(1342-1354)Online publication date: 25-Apr-2014
https://dl.acm.org/doi/10.1002/cpe.3172
Show More Cited By

Index Terms

Recommendations

Maintaining Cache Coherence through Compiler-Directed Data Prefetching

In this paper, we propose a compiler-directed cache coherence scheme which makes use of data prefetching to enforce cache coherence in large-scale distributed shared-memory (DSM) systems. TheCache Coherence With Data Prefetching(CCDP) scheme uses ...
Efficient Integration of Compiler-Directed Cache Coherence and Data Prefetching

Cache coherence enforcement and memory latency reduction and hiding are very important and challenging problems in the design of large-scale distributed shared-memory (DSM) multiprocessors. We propose an integrated approach to solve these problems ...
On the integration of compiler-directed cache coherence and data prefetching

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICS '92: Proceedings of the 6th international conference on Supercomputing

August 1992

495 pages

ISBN:0897914856

DOI:10.1145/143369

Chairmen:
Ken Kennedy
Rice University, Houston, TX
,
Constantine D. Polychronopoulos
Kubota Pacific Computers and CSRD

Copyright © 1992 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]

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1992

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ICS92

Sponsor:

SIGARCH

ICS92: ACM SIGARCH International Conference on Supercomputing

July 19 - 24, 1992

D. C., Washington, USA

Acceptance Rates

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
303
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)13

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pyka AZaykov PCasse HOzaktas HRochange CUhrig S(2015)Case study: Performance and WCET analysis for parallelised avionic applications with ODC²2015 IEEE 13th International Conference on Industrial Informatics (INDIN)10.1109/INDIN.2015.7281939(1400-1407)Online publication date: Jul-2015
https://doi.org/10.1109/INDIN.2015.7281939
Pyka ARohde MUhrig S(2014)Extended performance analysis of the time predictable on-demand coherent data cache for multi- and many-core systems2014 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS XIV)10.1109/SAMOS.2014.6893201(107-114)Online publication date: Jul-2014
https://doi.org/10.1109/SAMOS.2014.6893201
Pyka ARohde MUhrig S(2014)A real-time capable coherent data cache for multicoresConcurrency and Computation: Practice & Experience10.1002/cpe.317226:6(1342-1354)Online publication date: 25-Apr-2014
https://dl.acm.org/doi/10.1002/cpe.3172
Rochange CUhrig SSainrat P(2014)BibliographyTime‐Predictable Architectures10.1002/9781118790229.biblio(163-178)Online publication date: 17-Jan-2014
https://doi.org/10.1002/9781118790229.biblio
Pyka ARohde MUhrig S(2013)Performance Evaluation of the Time Analysable On-Demand Coherent CacheProceedings of the 2013 12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications10.1109/TrustCom.2013.250(1887-1892)Online publication date: 16-Jul-2013
https://dl.acm.org/doi/10.1109/TrustCom.2013.250
Choi LYew P(2005)Interprocedural array data-flow analysis for cache coherenceLanguages and Compilers for Parallel Computing10.1007/BFb0014193(81-95)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0014193
O'Boyle MFord RNisbet A(2005)Compiler reduction of invalidation traffic in virtual shared memory systemsEuro-Par'96 Parallel Processing10.1007/3-540-61626-8_58(432-440)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-61626-8_58
O'Boyle MFord RStohr E(2003)Towards general and exact distributed invalidationJournal of Parallel and Distributed Computing10.1016/j.jpdc.2003.07.00763:11(1123-1137)Online publication date: 1-Nov-2003
https://dl.acm.org/doi/10.1016/j.jpdc.2003.07.007
Choi LYew P(2000)Compiler Analysis for Cache CoherenceIEEE Transactions on Parallel and Distributed Systems10.1109/71.87977211:9(879-896)Online publication date: 1-Sep-2000
https://dl.acm.org/doi/10.1109/71.879772
Choi LYew P(2000)Hardware and Compiler-Directed Cache Coherence in Large-Scale MultiprocessorsIEEE Transactions on Parallel and Distributed Systems10.1109/71.85083411:4(375-394)Online publication date: 1-Apr-2000
https://dl.acm.org/doi/10.1109/71.850834
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

Media

Figures

Other

Tables

View Table of Contents