Cache designs with partial address matching

ABSTRACT

One critical aspect in designing set-associative cache at high clock rate is deriving timely results from directory lookup. In this paper we investigate the possibility of accurately approximating the results of conventional directory search with faster matches of few partial address bits. Such fast and accurate approximations may be utilized to optimize cache access timing, particularly in a customized design environment. Through analytic and simulation studies we examine the trade-offs of various design choices. We also discuss few other applications of partial address matching to computer designs.

REFERENCES

• 1: C.J. Conti, "Concepts for Buffer Storage," IEEE Comp. Group News, 2, 8, (March 1969), pp. 9-13.
• 2: A. J. Smith, "A Comparative Study of Set Associative Memory Mapping Algorithms and Their Use for Cache and Main Memory," IEEE Trans. on Software Engineering, SE-4, 2 (March 1978).
• 3: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 4: Mark D. Hill, A Case for Direct-Mapped Caches, Computer, v.21 n.12, p.25-40, December 1988 [doi>10.1109/2.16187]
• 5: S. Prybylski , M. Horowitz , J. Hennessy, Performance tradeoffs in cache design, Proceedings of the 15th Annual International Symposium on Computer architecture, p.290-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 6: T. Wada, S. Rajan and S. A. Pryzybylski, "An Analytic Access Time Model for On-Chip Cache Memories," IEEE Journal of Sohd-State Czrcu~ts, Vol. 27, No. 8 (August 1992) pp. 1147-1156.
• 7: J. J. Losq, G. S. Rao and H. E. Sachar, "Decode History Table for Conditional Branch instructions,'' U.S. Patent No. 4,477,872 (October 16, 1984).
• 8: R. E. Kessler , R. Jooss , A. Lebeck , M. D. Hill, Inexpensive implementations of set-associativity, Proceedings of the 16th annual international symposium on Computer architecture, p.131-139, April 1989, Jerusalem, Israel
• 9: L. Liu, "Partial Address Directory for Cache Access,'' IBM Research Report, RC18803 (February 1993). Also published in IEEE Trans. on VLSI Systems, Vol. 2, No. 2 (June 1994) pp. 226-240.
• 10: J. M. Lee and A. Weinberger, "A Solution to the Synonym Problem," IBM Technical D~sclosure Bulletin, 22, 8A (January 1980), pp. 3331-3333.
• 11: "3033 Processor Complex, Theory of Operation/Diagrams Manual (Vol. 4), Processor Storage Control Function (15SCF),'' IBM, Poughkeepsie, New York (1978).
• 12: Alan Jay Smith, Characterizing the Storage Process and Its Effect on the Update of Main Memory by Write Through, Journal of the ACM (JACM), v.26 n.1, p.6-27, Jan. 1979 [doi>10.1145/322108.322110]
• 13: J. H. Chang , H. Chao , K. So, Cache design of a sub-micron CMOS system/370, Proceedings of the 14th annual international symposium on Computer architecture, p.208-213, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30374]
• 14: K. Hun, A. Hunt, L. Liu, J. Peir, D. Pruett and J. Temple, "Early Resolution of Address Translation in Cache Design," Proc. 1990 IEEE International Conf. on Computer Design (September 1990)
• 15: S. G. Tucker, "The IBM 3090 Systems: An Overview," IBM Systems Journal, 25, 6 (January 1986).
• 16: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Memory design

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

  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

General Terms:
Design