The design of a lockup-free cache for high-performance multiprocessors

ABSTRACT

High-performance multiprocessors must incorporate a high-bandwidth, short-latency memory aggregate to support maximal processor utilization. Cache memories are often used to meet this requirement. The performance of cache-based, shared-memory multiprocessors can suffer greatly from moderate cache miss rates because of the usually high ratio between memory-access and cache-access times. In this paper we propose a lockup-free cache design in which the handling of one or several cache misses is overlapped with processor activity. In multiprocessors, lockup-free caches aggravate the memory coherence problem. Three different cache architectures relying on different compiler interventions are introduced. A performance model demonstrates the usefulness of lockup-free caches for high-performance processors. The merits and disadvantages of the three schemes are discussed and compiler techniques, to take advantage of the proposed designs, are illustrated at the end of the paper.

REFERENCES

• 1: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 2: L. M. Censier and P. Feautrier, "A New Solution to Coherence Problems in Multicache Systems," IEEE Transactions on Computers, Vol. C-27~ 1~o.12, December 1978.
• 3: David Kroft, Lockup-free instruction fetch/prefetch cache organization, Proceedings of the 8th annual symposium on Computer Architecture, p.81-87, May 12-14, 1981, Minneapolis, Minnesota, United States
• 4: P.M. Kogge, "The Architecture of Pipelined Computers," McGraw-Hill Book Company, 1981.
• 5: M. Dubois , C. Scheurich , F. Briggs, Memory access buffering in multiprocessors, Proceedings of the 13th annual international symposium on Computer architecture, p.434-442, June 02-05, 1986, Tokyo, Japan
• 6: M. Dubois, "Effect of Invalidations on the Hit Ratio of Cache-Based Multiprocessors," Proceedings of the 1987 International Conference on Parallel Processing, Aug. 1987.
• 7: 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]
• 8: C. Scheurich and M. Dubois~ "Concurrent Miss Resolution in Multiprocessor Caches~" Proceedings of the 1988 International Conference on Parallel Processing~ Aug. 1988.
• 9: J.H. Patel, "Analysis of Multiprocessor with Private Cache Memories," IEEE Transactions on Computers, Vol. C-31, No. 4, April 1982.
• 10: Charles E. Gimarc , Veljko M. Milutinovic, A survey of RISC processors and computers of the mide-1980s, Computer, v.20 n.9, p.59-69, Sept. 1987 [doi>10.1109/MC.1987.1663695]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

General Terms:
Algorithms, Design, Performance