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

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, New York University, New York, NY, 1986
• 4: Roland Lun Lee , Duncan H. Lawrie , Pen-Chung Yew, The effectiveness of caches and data prefetch buffers in large-scale shared memory multiprocessors, 1987
• 5: R. L. Lee , P. C. Yew , D. H. Lawrie, Multiprocessor cache design considerations, Proceedings of the 14th annual international symposium on Computer architecture, p.253-262, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30379]
• 6: H. Cheong , A. V. Vaidenbaum, A cache coherence scheme with fast selective invalidation, Proceedings of the 15th Annual International Symposium on Computer architecture, p.299-307, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 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: James Archibald , Jean Loup Baer, An economical solution to the cache coherence problem, Proceedings of the 11th annual international symposium on Computer architecture, p.355-362, January 1984
• 12: James R. Goodman, Using cache memory to reduce processor-memory traffic, Proceedings of the 10th annual international symposium on Computer architecture, p.124-131, June 13-17, 1983, Stockholm, Sweden
• 13: E. McCrelght, "The dragon computer system: An early overview," tech. rep., Xerox Corp., September 1984.
• 14: Mark S. Papamarcos , Janak H. Patel, A low-overhead coherence solution for multiprocessors with private cache memories, Proceedings of the 11th annual international symposium on Computer architecture, p.348-354, January 1984
• 15: Larry Rudolph , Zary Segall, Dynamic decentralized cache schemes for mimd parallel processors, Proceedings of the 11th annual international symposium on Computer architecture, p.340-347, January 1984
• 16: R. H. Katz , S. J. Eggers , D. A. Wood , C. L. Perkins , R. G. Sheldon, Implementing a cache consistency protocol, Proceedings of the 12th annual international symposium on Computer architecture, p.276-283, June 17-19, 1985, Boston, Massachusetts, United States
• 17: Yung-Chin Chen , Alexander V. Veidenbaum, A software coherence scheme with the assistance of directories, Proceedings of the 5th international conference on Supercomputing, p.284-294, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109095]
• 18: Hoichi Cheong , Alex Veidenbaum, A version control approach to Cache coherence, Proceedings of the 3rd international conference on Supercomputing, p.322-330, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318824]
• 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: Hoichi Cheong, Compiler-directed cache coherence strategies for large-scale shared-memory multiprocessor systems, University of Illinois at Urbana-Champaign, Champaign, IL, 1990
• 22: James R. Goodman, Coherency for multiprocessor virtual address caches, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.72-81, October 1987, Palo Alto, California, United States
• 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 , J. L. Baer, Design and Analysis of a Scalable Cache Coherence Scheme Based on Clocks and Timestamps, IEEE Transactions on Parallel and Distributed Systems, v.3 n.1, p.25-44, January 1992 [doi>10.1109/71.113080]
• 25: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982
• 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.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

General Terms:
Algorithms, Design, Performance

Keywords:
Doacross loop, compiler-based cache coherence, fast selective invalidation, inter-task-level temporal locality, life span strategy, parallel task execution, simple invalidation, time-stamp approach, version control