Browse Prior Art Database

LINKED LIST OF MULTIPLE IDENTICAL CONTENT ADDRESSABLE MEMORY TAG FIELDS

IP.com Disclosure Number: IPCOM000006157D
Original Publication Date: 1991-Apr-01
Included in the Prior Art Database: 2001-Dec-10
Document File: 3 page(s) / 137K

Publishing Venue

Motorola

Related People

William D. Atwell, Jr.: AUTHOR [+3]

Abstract

WHAT ARE THE PROBLEMS SOLVED BY THIS STRUCTURE? There is a general problem of CAM design con- cerning how to handle multiple identical CAM tag fields. The solutions have generally been either to disallow multiple identical tags or to provide some hardware means to resolve which one of the multiple matches to recognize. AI1 of such hardware means known to the authors are effective at the time of the associative operation that results in a multiple match condition. The standard state of the art solution is the use of some kind of priority encoder to resolve one of the multiple matching entries. These priority encoder circuits are problematical in that their performance degrades rapidly as the depth (number of entries) of the CAM is increased due to the use of gate-pass chains and look-ahead logic. That is, for a given desired performance level, there is a practical limit on the size of the CAM that uses any of these priority encoder circuits. This performance penalty grows linearly with CAM depth whereas the penalty associated with a simple encoder grows as log2 (CAM depth). A benefit of the structure being discussed is that it provides for the use of simple match encoders while accommodating multiple identical CAM tag fields.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 3

0 M

MOlYlROLA INC. Technical Developments Volume 12 April 1991

LINKED LIST OF MULTIPLE IDENTICAL CONTENT ADDRESSABLE MEMORY TAG FIELDS

by William D. Atwell, Jr., Grady L. Giles and Jesse R. Wilson

WHAT ARE THE PROBLEMS

SOLVED BY THIS STRUCTURE?

  There is a general problem of CAM design con- cerning how to handle multiple identical CAM tag fields. The solutions have generally been either to disallow multiple identical tags or to provide some hardware means to resolve which one of the multiple matches to recognize. AI1 of such hardware means known to the authors are effective at the time of the associative operation that results in a multiple match condition. The standard state of the art solution is the use of some kind of priority encoder to resolve one of the multiple matching entries. These priority encoder circuits are problematical in that their performance degrades rapidly as the depth (number of entries) of the CAM is increased due to the use of gate-pass chains and look-ahead logic. That is, for a given desired performance level, there is a practical limit on the size of the CAM that uses any of these priority encoder circuits. This performance penalty grows linearly with CAM depth whereas the penalty associated with a simple encoder grows as log2 (CAM depth). A benefit of the structure being discussed is that it provides for the use of simple match encoders while accommodating multiple identical CAM tag fields.

DESCRIPTION OF THE STRUCTURE,

INCLUDING ITS OPERATION, PURPOSE, AND ENVIRONMENT.

  Figure 1 shows a simple block diagram of a CAM that incorporates this structure. In this figure, the decoder, tag array, V bit (valid) and the simple encoder will all be recognized as common parts of a generic state-of-the-art CAM. Additions being proposed to this structure are the L bit and Link fields of the array, a link sequencer and associated logic, refer to flow diagrams of Figures 2 and 3.

  The proposed structure presents a method and apparatus for constructing content addressable linked lists of identical tag characteristics for subsequent orderly retrieval. A linked list is constructed automatically as entries are loaded into the CAM without regard or knowledge of any of the previously loaded CAM entries of identical tag characteristic. The load operation is as follows. Entries are always loaded with the L bit set and with the Link field initialized to a predetermined initial value, refer to Figure 2. The L bit = 1 indicates that the entry is the last member of a linked list even if it might be the only member of the list. The Link field is the ordinal number of the entry within the linked list. If during the load of one entry, another entry indicates a hit at load time, that other entry's L bit is immediately reset signifying that it is no longer the end of the list. (The Link field is masked for purposes of a load time compare.) The entry indicating hit at load time also reads out its Link field value to be input into...