US 4,736,287 A · Set association memory system

Abstract

A memory system for use in a computer which in the preferred embodiment provides two megabytes of capacity per board (up to four boards) is disclosed. An ALU generates an address signal which selects a number of set locations in the main memory. Simultaneously, a portion of the address field is fed to a set association logic circuit for parallel processing. The set association circuit contains tag storage memories and comparators which store tag values. These values are compared with address fields, and if a match occurs, one of the comparators selects a 128-bit word from the main memory. A hash function is also used to provide for dispersal of storage locations to reduce the number of collisions of frequently used addresses. Because of hardware implementation of hashing and least recently used (LRU) algorithm, a constant predetermined cycle time is realized since all accessing functions occur substantially in parallel. Several sets of data are accessed simultaneously while a set association process is performed which selects one of the accessed sets, wherein access time is reduced because of the parallel accessing.

Claims20

Dependent claims

In a digital computer system which includes processing means, an address bus, and a data bus, a memory system comprising:

a plurality of random-access memories (RAMs) for storing data, said RAMs coupled to said data bus and said address bus;
set association means coupled to said data bus and said address bus, said set association means coupled to receive an address signal from said address bus and providing a first field of digital signals for a set association determination, said first field also being coupled to said RAMs to access sets of digital signals stored in said RAMs;
said processing means coupled to said data bus and said address bus for providing said address signals to said set association means;
said set association means further providing a second field of digital signals for said set association determination;
said set association means for providing a select signal to said RAMs for selecting one of said sets of stored signals from those accessed by said first field such that accessing of sets of locations in said RAMs by said first field and said set association determination of one of said sets by said first and second fields occurs substantially simultaneously;
whereby simultaneous accessing of said RAMs with said set association provides more rapid cycle times for said memory system.

3 more elements

In a digital computer system which includes processing means, an address bus and a data bus, a memory system comprising:

a plurality of random-access memories (RAMs) for storing digital signals, said RAMs coupled to said data bus for receiving said digital signals and coupled to said address bus for receiving an address signal;
a plurality of tag storage memories for storing information relating to locations of said stored digital signals in said RAMs, said tag storage memories coupled to said data bus for receiving said information and coupled to said address bus for receiving first address signals, wherein each tag storage memory provides second address signals;
a plurality of comparator means, each of which is associated with one of said tag storage memories, for comparing said first address signals and said second address signals and for providing an output signal based on said comparison, said first address signals being received from said address bus, said second address signals being received from its respective tag storage memory, said output signals from said comparator means being coupled to said RAMs for selecting one of a set of digital signals stored in said RAMs;
first address signals from said address bus being coupled to said RAMs for selecting sets of stored digital signals;
whereby said tag storage memories and comparator means provide set association for identifying a set of said digital signals from said sets of stored digital signals stored within said RAMs.

2 more elements

In a digital computer system which includes processing means, an address bus, and a data bus, a memory comprising:

a plurality of random-access memories (RAMs) for storing digital signals used by said processing means, said RAMs coupled to said address bus and said data bus for receiving said digital signals;
a plurality of tag storage memories for storing information relating to locations of said stored digital signals in said RAMs, said tag storage memories coupled to said address bus and said data bus for receiving said information;
a plurality of comparator means, each of which is associated with one of said tag storage memories for comparing a first field and a second field of digital signals and for providing an output signal based on said comparison, said first field of said signals being received from said address bus, said second field of said signals being received from its respective tag storage memory, said output signals from said comparator means being coupled to said RAMs for selecting a set of digital signals stored in said RAMs;
circuit means for determining least recently used (LRU) values such that from said LRU values for each address applied to said tag storage memories it can be determined which set of locations within said RAMs was accessed the least, said circuit means making said determination of said LRU values simultaneously while said RAMs are being accessed;
whereby said tag storage memories enable the identification of least used memory locations within certain address ranges.

2 more elements

Dependencies are inferred from the claim text.

Set association memory system

Life of this patent

Set association memory system

Life of this patent

Abstract

Claims20