Match resolution circuit for an associative memory

[0002] The subject matter of the present application is related to and claims priority, under 35 U.S.C. § 119(e), from U.S. provisional patent application serial No. 60/148,403, entitled “Match Resolution Circuit for Content Addressable Memory” by Alex E. Henderson and Walter E. Croft, which application was filed on Aug. 11, 1999 and is incorporated herein by reference.

[0003] A. Technical Field

[0004] The present invention relates generally to associative memories, and in particular to content addressable memories. More particularly, the present invention relates to an associative memory having a match resolution circuit for determining a best match from among multiple matches.

[0005] B. Background of the Invention

[0006] An associative memory, such as a content addressable memory (CAM), is a device that permits the contents of the memory to be searched and matched instead of having to specify a memory location address in order to retrieve data from the memory. A CAM may be used to accelerate any application requiring fast searching of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. A CAM provides a performance advantage over conventional memory devices with conventional memory search algorithms, such as binary or tree-based searches, by comparing the desired information against the entire list of entries simultaneously, giving an order-of-magnitude reduction in search time. For example, a binary search through a database of 1000 entries may take ten separate search steps whereas a CAM device with 1000 entries may be searched in a single operation resulting in a search which takes ten times less time. One example of an application in which CAM devices are often used is to store a routing table for high speed switching systems which need to rapidly search the routing table to look for a matching destination address so that a data packet may be routed to the appropriate destination address.

[0007] A CAM device is organized somewhat differently from typical SRAM or DRAM devices. Information stored in a CAM may be accessed by comparing the data stored in the memory with data placed in a special register known as a search input or compare register as opposed to RAM devices in which information is accessed by specifying a particular memory address. If there is a match in particular memory locations with every corresponding bit in the register, a Match Flag is asserted to let the user know that the data in the register was found in the CAM device. Thus, with a CAM device, the user supplies a piece of data she would like to match to the CAM and gets back the address of any matching pieces of data in the CAM. There are two common types of CAM memory, binary CAM and ternary CAM. Binary cam requires an exact match of all bits in the search input and comparand for a match. Ternary CAM uses a mask to allow some bits to be treated as “don't care” bits and ignored in the determination of a match.

[0008] Data in a Binary CAM location typically comprises 2 fields: a comparand and an associated data field. Unlike a random access memory (“RAM”), when a search is performed on a CAM, all comparands in a CAM are compared simultaneously with a search input stored in a register. As each comparand is compared with the search input, a match line for that comparand is activated if the comparand matches the search word. Prior art ternary CAM devices may also contain an additional field known as a mask. The mask may be used to filter off portions of the comparand during the search procedure. In other words, the mask allows a comparison between the search input and only certain portions of the comparand as determined by the mask.

[0009] A search on a CAM may result in several matches in response to the search input, however, only one result should be returned. Therefore, one problem in the prior art is determining which match from a plurality of matches should be returned as the best match for a particular search input. One solution in the prior art is to implement a priority resolution circuit that uses the position of the data item in the CAM array to determine which match to output. One disadvantage in using a priority resolution circuit based on the position of the data item in the CAM array is that it only offers one criteria, (i.e. position) for determining a best match. Additionally, in order to change the priority of a particular CAM data item, it is necessary to move the data items to different positions in the CAM array. This process is cumbersome and slows down the operation of the CAM. Accordingly it is desirable to provide a priority resolution system that is capable of determining a best match among a plurality of CAM matches. More specifically, it is advantageous to provide a priority resolution system that can be dynamically updated and can use criteria other than position to determine a best match among a plurality of matches.

[0010] The present invention overcomes the deficiencies and limitations of the prior art with a unique system and method for determining a best match from a plurality of matches resulting in response to a search input performed on an associative memory. The system and method for determining a best match from a plurality of matches comprises a priority field associated with each data item stored in the associative memory. The priority field corresponds to criteria that is used to order the priority of the data items. A match resolution module is coupled to receive match signals from an associative memory and the priority fields associated with the matching data entries. The match resolution structure compares the priority fields of the plurality of matching data items to determine which data item has the highest priority. The match resolution structure then indicates the data item having the highest priority as the best match of the associative memory for the particular search input.

[0011] These and other features and advantages of the present invention may be better understood by considering the following detailed description of preferred embodiments of the invention. In the course of this description, reference will be frequently made to the attached drawings.

[0012] FIG. 1 is a block diagram of one embodiment of a CAM including a priority field in accordance with the present invention.

[0013] FIG. 2 is a block diagram of one embodiment of a CAM including a match resolution circuit.

[0014] FIG. 3 is a block diagram of one embodiment of a method for determining a best match.

[0015] FIG. 4 is a block diagram illustrating one embodiment of a match resolution circuit for a CAM.

[0016] FIG. 5 is a block diagram of another embodiment of a match resolution circuit for a CAM.

[0017] FIGS. 6a-6dare block diagrams of other embodiments of a match resolution circuit for a CAM.

[0018] FIG. 7 is one embodiment of a hierarchical match resolution circuit for a CAM.

[0019] The present invention is particularly applicable to a content addressable memory (CAM) device, such as that used as a single or dual port CAM memory, an event-co-processor, and a database co-processor, and it is in this context that the invention will be described. It will be appreciated, however, that the match resolution module in accordance with the invention has greater utility and may be used with any type of associative memory that accesses data based upon the content of the stored data (rather than the location in which that data is stored) and provides multiple matches in response to a search input.

[0020] Referring now to FIG. 1, there is shown one embodiment of a CAM having a match resolution circuit in accordance with the present invention. The CAM structure comprises a CAM match structure 102 for storing CAM words or data items, an address decoder 104 for addressing the CAM when initially storing data items, and a related memory 106 which may be a random access memory (RAM) or a read-only memory (ROM). Typical CAM usage involves locating a data item in the CAM match structure 102. A data item is specified by entering a search input 108 which compares simultaneously all of the data items stored in the CAM match structure 102 with the search input 108. A typical CAM search may result in finding a plurality of data items which match the search input 108. In order to determine a “best match” for the particular search input 108, a priority field 110 associated with each data item is evaluated to determine a best match from the plurality of matches. A best match can be determined by an arithmetic or logical comparison of the priority fields 110 of all matching CAM data items. When a best match is found for a particular search input 108, the apparatus can retrieve additional information concerning the requested data item from the related memory 106. As used herein, a “best match” is used to define a single data item from a plurality of data items that match the search input 108. As one skilled in the art will readily understand, a best match does not imply that there is only one true absolute match but that in the context of the priority field 110, there is one data item which will be considered to be a best match and will be outputted by the CAM. Examples of various best matches, priority fields, and criteria are discussed in more detail below.

[0021] As discussed above, the present invention provides a priority field 110 associated with each word of the CAM. The priority field 110 allows each data item to be prioritized according to some criteria. In a preferred embodiment, a priority field 110 comprises 16 bits. One skilled in the art will realize that the number of bits comprising the priority field 110 will depend on the number of bits required to uniquely identify the priority associated with a data item. The priority field 110 may correspond to any number of criteria, including but not limited to, a weight field stored in the CAM match structure 102, length of the longest contiguous unmasked field in the CAM match structure 102, the total number of unmasked bits in the CAM match structure 102, the total number of matching bits resulting from a compare, the path length metric derived from a routing protocol such as OSPF, the order of an order dependent list such as an Access Control List for a router, a prefix length of an IP address, or position in the CAM match structure. Thus, the present invention advantageously allows the use of a variety of criteria for ordering the priority of each data item.

[0022] Additionally, because the priority field is a separate field for indicating the priority of the data item, the priority of the various data items may be changed by changing the entry in the priority field. For example, assume a CAM structure contains a first data item A, a second data item B, and a third data item C. Further assume that the first data item A has a priority field indicating that it has a priority of 1, the second data item B has a priority field indicating that it has a priority of 2, and the third data item C has a priority field indicating that it has a priority of 3. If priority is determined according to the priority field with the highest number, then the third data item C, which has a priority of 3, has the highest priority. However, if for some reason it is necessary to change the priority of the data items, the priority of a data item may be changed simply by changing the priority field. For example, assume that the priority field for the first data item A is changed from 1 to 3 and the priority field for the third data item C is changed from 3 to 1, then using the same convention that priority is determined according to the highest number, the first data item A, which now has a new priority of 3, has the highest priority. Thus, the present invention advantageously provides a simple mechanism for changing the priority of data items by changing the priority in the priority field.

[0023] The present invention also provides for hierarchical match resolution. In other words, if two or more CAM data items have the same priority according to one priority field criteria, then a second priority field criteria can be applied to these entries to determine a best match. A preferred embodiment for a hierarchical match resolution system for a CAM is described below in more detail with reference to FIG. 6.

[0024] Referring now to FIG. 2 and FIG. 3, there are shown a functional block diagram of one embodiment of a CAM including a match resolution circuit and a block diagram of one embodiment of a method for determining a best match from a plurality of matches. The CAM structure 200 comprises a CAM structure 102 coupled to receive a search input 108. The CAM structure 102 receives (302) the search input 108 and compares (304) the search input 108 to all the data item entries in the CAM structure 102 as described above. The CAM structure 102 then generates (306) a match signal (not shown) for all CAM data items in the CAM that match the search input 108. The CAM structure 102 then outputs the match signal and the priority field (not shown) to the match resolution circuit 202. The match resolution circuit 202 evaluates (308) the priority field for each matching CAM data item and determines (310) which priority field has the highest priority. The output of the match resolution circuit 202 then indicates (312) the CAM data item with the highest priority according to the priority field. The indicated item is considered the best match for the particular search input 108. Preferably, the output of the match resolution circuit 204 comprises either prioritized match signals or the address of the highest priority matching entry.

[0025] Referring now to FIG. 4, there is shown a block diagram illustrating one embodiment of a CAM match resolution circuit. A CAM match resolution circuit in accordance with the present invention comprises a first two port priority resolution circuit 402, a second two port priority resolution circuit 404, and a third two port priority resolution circuit 406. The first and second two port priority resolution circuits, 402 and 404, are each coupled to receive a match signal and a priority field associated with two CAM data items. For example, the first two port priority resolution circuit 402 is coupled to receive a first match signal 408aand a first priority field signal 408bfrom one CAM data item, and a second match signal 410aand a second priority field signal 408bfrom a second CAM data time. The first two port priority resolution circuit 402 determines which CAM data item has the higher priority according to the inputted match and priority field signals and outputs the match signal 416aand the priority field signal 416bwith the highest priority. Similarly, the second two port priority resolution circuit 404 is coupled to receive a first match signal 412aand a first priority field signal 412bfrom one CAM data item, and a second match signal 414aand a second priority field signal 414bfrom a second CAM data item. The second two port priority resolution circuit 404 determines which CAM data item has the higher priority according to the inputted match and priority field signals and outputs the match signal 418aand the priority field signal 418bwith the highest priority. The third two port priority resolution circuit 406 then compares the results from two port priority resolution circuit 402 and two port priority resolution circuit 404 and outputs the match signal 420aand the priority field signal 420bwith the highest priority. For example, if the priority field signal corresponds to an assigned priority number, then the CAM data item with the highest priority number would be outputted from two port priority resolution circuit 406. One skilled in the art will recognize that the present invention is not limited to only determining the “highest priority” but that the principles of the present invention can also be used to determine and output the data item with the “lowest” priority. Thus, a CAM match resolution circuit can be implemented as a stack of two entry match resolution circuits wherein each two entry match resolution circuit compares two input values and outputs the greater value. The present invention is not limited to the use of three two port priority resolution circuit in a two stage circuit for determining a best match, but one skilled in the art will realize that the principles of the present invention may be applied to any number of two port priority resolution circuit arranged in the necessary number of tages for comparing the priority fields of any number of data items.

[0026] Referring now to FIG. 5, there is shown a block diagram of one embodiment of one row of a match resolution circuit for a CAM. The match resolution circuit 500 comprises a priority field Most Significant Bit (MSB) component 502, a compare MSB and OR plane output component 504, a match signal 508, an AND gate 506, and a MSB OR plane 512. As indicated in FIG. 5, the match resolution circuit of the present invention incorporates each of these elements for each bit in the priority field. In other words, the bits in the priority field for a data item are evaluated serially. FIG. 5 illustrates these elements for only two bits of the priority field in the interest of simplicity. In a preferred embodiment, the match signal 508 is the high order bit of the priority field. For the first bit in the priority field, the match signal 508aand the priority field MSB are ANDed together and outputted to the MSB OR plane 512a. The result of the MSB OR plane 512ais compared with the MSB of the priority field received from the priority field MSB 502a. The result is then used as compare ok or enable signal for the next AND gate 506bfor the next comparison. This process is repeated until a determination of the best match is made. Thus, the most significant bit of all priority fields are compared to the result of the OR plane. If the priority field bit matches the result a compare OK signal is propagated to the next less significant bit. The OR function can also be implemented using pre-charge logic as shown in FIG. 6b.

[0027] Referring now to FIG. 6a, there is shown another embodiment of a match resolution circuit for a CAM in accordance with the present invention. The embodiment described in detail in FIG. 5 can be implemented using a “look ahead” logic similar to an adder circuit. The addition of a “look ahead” logic advantageously improves the speed of the match resolution circuit. In another embodiment, the MSB OR plane 512 can be implemented using wide gate structures as described in U.S. Pat. No. 5,999,435, entitled “Content Addressable Memory Device,” by Alex E. Henderson and Walter E. Croft, which patent is incorporated herein by reference in its entirety.

[0028] FIG. 6bis a precharge logic implementation of the circuit of FIG. 6a. The OR function is implemented by pre-charge transistor 600b, pulldown transistor 601b(one per cell) and inverter 602b. Transfer gate 603band transistor 604bimplement the AND function. The compare function is implemented by the pre-charge logic complex gate comprising transistors 605bthrough 609band inverter 610b. Transistors 605band 609bare controlled by a timing signal generated by a dummy row or other timing method. The timing strobe is required to prevent a false enable out from corrupting the result of the next cell. The timing circuits are designed so that the timing strobe occurs after the OR feedback line is stable.

[0029] FIG. 6cis a faster version of the circuit of FIG. 6b. The pre-charge logic OR has been divided into multiple sub-circuits comprising N rows (transistors 600c, 601cand inverter 602c). The results of the sub-circuits are combined by a second OR circuit comprising transistors 603cand 604c. This reduces the loading on the first layer OR resulting in increased speed and combines the feedback and second level OR function.

[0030] FIG. 6dis a diagram of a match resolution circuit that implements a multi-bit priority resolution to further increase speed. Multiple priority bits are decoded and used to drive multiple OR planes. The results of the OR functions are encoded to generate an enable output. The pre-charge implementations of the OR functions described in 6band 6ccan be used to implement the OR planes. For a two bit priority resolution circuit the decodes x1, 1x and 11 can be used as inputs to the OR planes.

[0031] Referring now to FIG. 7, there is shown one embodiment of hierarchical match resolution circuit for a CAM. The hierarchical match resolution circuit for CAM cascades two or more match resolution circuits, 702 and 704, such that if there are multiple “best” matches based on a first criteria (e.g. network path length), a second criteria (e.g. link speed) can be used to determine the best match. A hierarchical match resolution circuit for a CAM comprises a CAM structure 102 coupled to receive an input search 108, a first match resolution module 702, and a second match resolution module 704. As described above, the CAM structure 102 receives a search input 108 and compares the search input 108 to all the CAM data items. The CAM structure 102 then generates a match signal for each data item which matches the search input 108. The search result of the CAM may result in a plurality of data items which match the search input 108. In such instances, a first match resolution circuit 702 is coupled to receive the match signals and the first priority fields associated with each CAM data item that matched the search input 108. The first match resolution circuit 702 evaluates the first priority field of each of the matching items and determines which data item has the highest priority based on the first priority fields. The first match resolution circuit 702 may result in multiple data items having equal priority based on the first priority field (e.g. when network path length is used). The second priority fields are then evaluated to determine a best match best on the second priority field with the highest priority. The data item with the second priority field with the highest priority is then outputted as the best match. One skilled in the art will recognize that the present invention is not limited to two match resolution circuits but that any number of match resolution circuits may be implemented to determine a best match using several criteria. Additionally, for each additional criteria used for determining priority, an additional priority field is associated with each data item. Thus, if two criteria are used for determining priority in a hierarchical match resolution circuit, then preferably each data item includes a first priority field and a second priority field. Similarly, if three criteria are used for determining priority in a hierarchical match resolution circuit, then preferably each data item includes a first priority field, a second priority field, and a third priority field. Thus, the present invention advantageously allows more than one criteria to be used to determine a best match from a plurality of matches resulting from a CAM search.

[0032] From the above description, it will be apparent that the invention disclosed herein provides a novel and advantageous system and method for determining a best match from a plurality of matches determined in response to a search item. The foregoing discussion discloses and describes merely exemplary methods and embodiments of the present invention. As will be understood by those familiar with the art, the invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.