Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1997-12-18
2001-01-16
Cabeca, John W. (Department: 2752)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S128000, C370S230000
Reexamination Certificate
active
06175902
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of data storage, and more particularly, to method and apparatus for maintaining a time order of entries in a memory.
BACKGROUND ART
There are many circumstances in which it is desirable to age entries stored in a memory. Aging memory entries permits a memory to be kept relatively small, since older entries that have not been accessed for some time can be removed to make room for new entries. This aging is useful in a cache memory, for example, in which speed of access and searching for entries is a normal requirement. Such caches are used in many types of systems, such as computers, network switches for packet switched networks, etc. To keep a cache memory small and therefore fast and readily searchable, only the entries that are most likely to be accessed should be kept in the cache memory at any one time, and these are typically the most recent entries into the cache memory.
A conventional arrangement for aging memory entries employs time stamping of the entries in the memory. Time stamping involves encoding and associating a “time stamp” with an entry. This time stamp is decoded by the memory manager in order to determine the relative ages of the entries in the memory, and allow the memory manager to remove old entries in favor of newer entries.
The time stamping procedure and arrangements in the prior art require additional overhead and structure, and may slow down a memory due to the time it takes to perform the time stamping procedures. A similar problem in memories is that of determining the validity of entries. Again, in order to keep cache memories as small as practical, it is normally important to remove invalid entries from the cache memory in order to provide room for new, valid entries. Typically, an entry will be provided with a valid bit, which indicates the validity of that entry. A memory manager will examine these valid bits in the cache when accessing an entry in the memory to determine if the accessed entry in the memory is valid. This separately provided valid bit adds to the size of the cache and the complexity of the memory arrangement.
SUMMARY OF THE INVENTION
There is a need for a memory arrangement and a method of maintaining a time order of entries in a memory that does not employ additional bits dedicated to time stamps or validity bits.
This and other needs are met by the present invention which provides a memory arrangement for storing entries in a memory and maintaining a time order of the entries, comprising an n-way set associative memory divided into m rows and n columns. Each row contains n entry locations and each entry location stores a separate entry. The entry locations in each row are ordered from a newest to an oldest entry location. A manager stores an entry in the memory by writing the entry into the newest entry location in the row, and shifting each entry previously in a newer entry location into the next older entry location in the row.
The above-described embodiment of the invention does not require time stamps as the entries are aged (i.e., time order of the entries is maintained) by a physical reordering of the entries in the memory. The use of a single row to store multiple entries, and writing them in the row in order, and shifting that order and writing a new entry into the newest entry location, maintains the order (ages) of entries as they are written into the memory. Time stamps are not required, as the relative physical position of an entry within a row indicates the relative age of that entry with respect to the other entries in that row.
Another embodiment of the invention also satisfies the earlier stated needs and provides a network switch for a packet switched network, the switch being able to transmit multiple copies of a single frame of received data. The switch has a multicopy queue configured to queue entries, each entry containing a frame pointer that points to a location at which a frame is stored and a copy number that indicates the number of copies to be transmitted. A memory arrangement is provided for storing entries exiting the multicopy queue that have a positive copy number and maintaining a time order of these entries. The memory arrangement includes an n-way set associative memory divided into m rows and n columns, each row containing n entry locations, each entry location configured to store a separate entry, with the n entry locations in each row being ordered from a newest to an oldest entry location. The manager is configured to store entries in the memory by writing the entry into the newest entry location in the row, and shifting each entry previously in a newer entry location into the next older entry location in the row.
The network switch of the present invention employs a memory arrangement that orders the entries by physically reordering the entries in the memory. This avoids the use of time stamp structure in the cache and allows the cache to be kept smaller, a critical consideration in devices such as network switches, in which space on the chip is at a premium. The less on-chip space devoted to memory, the smaller the chip and/or the more functionality can be placed on the chip. Also, in certain embodiment of the network switch of the present invention, the validity of an entry is encoded within the entry itself. For example, the copy number is used as an encoded validity indication in certain embodiments. A null copy number means in a stored entry that the entry in the memory is not valid. The encoding of the validity avoids the need for a separate validity bit for each entry, and further reduces the complication and size of the memory arrangement.
The earlier stated needs are also met by another embodiment of the present invention which provides a method of maintaining a time order of entries in a memory, comprising the steps of logically dividing a memory into rows and columns, with each column within a row providing storage for a different entry, with the columns within a row arranged sequentially from a column that stores a newest entry to a column that stores an oldest entry. A new entry received at the memory and the row in which the entry will be stored is then determined. Each entry currently stored in a row is reordered from a newer column to the next older column in the row. If an entry originally is stored in the oldest column in the row prior to the reordering, that entry is removed from the row. The new entry is then written in the newest column in the determined row.
The foregoing and other features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 4980816 (1990-12-01), Fukuzawa et al.
patent: 5155831 (1992-10-01), Emma et al.
patent: 5226125 (1993-07-01), Balmer et al.
patent: 5256958 (1993-10-01), Eng et al.
patent: 5440546 (1995-08-01), Bianchini, Jr. et al.
patent: 5515376 (1996-05-01), Murthy et al.
patent: 5590122 (1996-12-01), Sandorfi et al.
patent: 5842224 (1998-11-01), Fenner
patent: 5953335 (1999-09-01), Erimli et al.
patent: 0 622 922 A1 (1994-11-01), None
patent: 2 624 994 (1989-06-01), None
patent: 2 107 092 (1983-04-01), None
Kenneth J. Schultz et al., “Cam-Based Single-Chip Shared Buffer ATM Switch”, Supercomm/ICC, New Orleans, May 1-5, vol. 2, Institute of Electrical and Electronics Engineers, 1994, pp. 1190-1195.
Erimli Bahadir
Runaldue Thomas J.
Advanced Micro Devices , Inc.
Bataille Pierre-Michel
Cabeca John W.
LandOfFree
Method and apparatus for maintaining a time order by... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for maintaining a time order by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for maintaining a time order by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2452170