WO2003052765A1

WO2003052765A1 - Finding free space in a content addressable memory

Info

Publication number: WO2003052765A1
Application number: PCT/IL2002/001019
Authority: WO
Inventors: Shaul Ben Haim; Yiftach Maayan; Yves Villaret
Original assignee: Memcall L.L.C.
Priority date: 2001-12-19
Filing date: 2002-12-18
Publication date: 2003-06-26
Also published as: AU2002360201A1

Abstract

A method for accelerating the search for Free Space in a CAM memory used to search words of arbitrary size. The Valid Bit function associated to each sub-word is inverted, whereby only non-valid data are searched. The CAM cells output a Match signal when the invalid bit is set and the CAM is in Find Free Space mode. The same logic system that is used to return the address of a matching word in normal search mode will output the address of a Free Space with a total number of consecutive invalid subwords equal or greater than the size of the input word. In another embodiment, 'Don't care' values are input to the CAM for each sub-word of the input word such that whenever a 'Don't care' value is set, all sub-words of records compared to that input sub-word output a match signal.

Description

Finding Free Space in a Content Addressable Memory

Field of the Invention:

The data stored in a Content Addressable Memory (CAM) array is usually divided in words that we shall later refer to as records, each word being composed of a number of sub-words. For example, an Internet address given in the form of a URL word is composed of a number of sub-words, each sub- word representing one character of the URL. Each sub-word of the URL will then be stored in one memory cell of the CAM array, and a group of consecutive memory cells storing the sub-words of the URL will store a record. The size of the record is defined as the number of sub-words of that record.

In CAMs of the known type, data is often stored in the memory cells together with a mark (valid bit) that indicates whether the data stored is valid or not. The search operation is then disabled for the sections of data that are marked as invalid.

Where a record stored in the CAM array becomes obsolete, i.e. searching for it is no more required, a host processor will reset the valid bit for all memory cells storing sub-words of that record. The search operation for that record is then disabled. By reading the state of the valid bit, a host system, such as a host processor, can then recognize that this record is invalid, and a new record can be written in its place.

It is often necessary to update or change the data stored in the CAM. This may occur in CAMs that are applied in communication systems. Thus for example the data stored in the CAM may comprise a list of the most frequently encountered Internet Addresses that needs to be updated from time to time. In these and similar cases the need may arise for storing a new record without altering previously stored valid records.

In the prior art, whenever it is necessary to store a new record without altering previously stored valid records, a host system such as a microprocessor will search the CAM array in order to find a "Free Space" for the new record, "Free Space" being defined as a number of consecutive invalid words equal or greater than the size of the new record. In order to find such a Free Space, the host will have to scan, using a software program for example, the CAM array for an invalid word, then check if there are a sufficient number of invalid words at consecutive addresses. The total number of consecutive invalid words should be greater or equal to the number of words composing the record to be stored.

The prior art search operation is relatively long, since the CAM may contain a large number of invalid words, but only few free spaces of the required size. While executing this search operation, the normal operation of the system may be perturbed, because of the CAM or the host system limitations. For example, the CAM may not allow data reading while executing a search operation. In that case the normal search operation must be interrupted during the search for a free space.

It is known to speed-up this free space searching operation, by storing in the standard memory of the system a list of valid and invalid records and updating the list each time new data is written or data becomes obsolete. However this method also has the drawback of the searching for free place operation consuming a considerable time, and it further requires additional memory space.

It is therefore desirable to overcome the drawbacks of the prior art by providing a faster method for searching free addresses in a CAM that will minimize the perturbation to its normal operation while not requiring additional memory space.

Summary of the Invention

An inventive method is proposed for accelerating the search for Free Space in a Cam by circumventing the need to read the data in the CAM cells.

In accordance with a first embodiment, the inventive method may be applied in a CAM that is designed to work in two different modes: normal and Find Free Space mode. When the CAM is operated in normal mode, it functions as a CAM of the known type. Words to be searched are loaded to the CAM, and if there is a matching word in the CAM, it returns its address. When the CAM is operated in the Find Free Space mode, the Valid Bit function associated to each sub-word is inverted, so that subsequent searching operations will occur only on non-valid data. Whenever a free space of size n is searched, a word composed of n sub-words is loaded for searching to the CAM. The inventive CAM cells are designed to output a Match signal in case the invalid bit is set and the CAM is put in Find Free Space mode. Neither the data loaded in the n sub-words loaded into the CAM nor the data stored in the Cam cells has any influence on the operation in that mode. The same logic system that is used to return the address of a matching word in normal mode will now output the address of a Free Space. Having found the position of a free space, a new record can be written in its place, and the normal operation of the CAM is resumed. In accordance with another embodiment, the invention is applied in a CAM system that comprises means to set a "don't care" value for each sub-word of the searched word (input word) such that whenever a "don't care" value is set, all sub-words of records compared to that input sub-word output a "match" signal. In this embodiment the free space searching operation can be initiated by setting an FFS signal that initiates the Free Space Search mode and outputs a command to a selector whereby only sub words with a reset valid bit are searched. A search of a word of n sub-words, is then conducted, each sub-word containing a "don't care" value. A word match signal will thus be generated for every position where n consecutive CAM cells have a reset valid bit. This novel method eliminates the need for a special circuitry used in the prior art to discard, in case of Find Free Space mode, the result of the comparison between the input word and the record word data .

The method and system described here can be applied in CAMs used to search data of fixed word size as well as in CAMs used to search words of variable size. In case of variable size of the searched words,- the gain in speed of operation is particularly advantageous. Brief Description of the Drawings:

Fig. 1 is a block diagram of a system in which a processor uses a CAM for searching purposes, and another memory (RFA) for storing and updating a list of invalid addresses in the CAM.

Fig. 2 shows a CAM cell of the common type, the CAM cell comprising a memory for storing a Sub-word, a comparator and a valid bit that enables the function of the comparator.

Fig. 3 shows a CAM system in which an FFS means is used to put the CAM system in a mode in which a free space can be found according to the method of the invention.

Fig.4 shows the general structure of a CAM of the common type, including CAM cells, Size Logic and Priority Encoder.

Fig. 5 shows an embodiment for a CAM cell that may be operated according to the method of the invention.

Fig. 6 shows a CAM cell that may be operated according to the method of the invention, wherein the CAM system provides ternary input data.

Detailed Description of the Invention

The present invention relates to Content Addressable Memory systems of the known type as well as novel Content Addressable Memory systems (CAM systems) that are used to search word of various sizes. These latter CAM systems usually include an array of CAM cells, and a logic system (hardware or/and software) that controls and executes the different functions required for the purpose of searching a record of arbitrary size. Each CAM cell comprises a memory cell for storing a sub-word of data, a valid bit and a comparator. The comparator is enabled whenever a search operation is initiated for a word, and the valid bit is set. The output of the comparator is a match signal that is connected to the system that performs the logic functions needed to generate a global match signal for the whole word. Whenever a global match signal is generated, it is input to a priority circuit that outputs the address of the matching record with the highest priority. When the comparator is not enabled, a match signal is never output. Examples of that type of CAM are described in patents US 5,787,458 and US 6,246,601 and in PCT patent application PCT/IL 01/00436

Content Addressable Memories (CAM) and CAM systems are used to execute searching operations at high speed. For example, a CAM system may be used to find the presence of an Internet Address (URL) in an incoming data string. The list of searched URL's (the "records" ) is loaded into the memory of the CAM system, then the input string is passed through the CAM system in order to detect the presence of one or several URL's. Depending on the specific application, it may be needed to update the list of records frequently. Each time a new record is to be loaded into the CAM, the processor needs first to search the CAM for a free space. If this search were done by directly scanning the CAM for invalid words, this would interrupt the normal operation of the system. For example, the system may be an Internet router, and each time the records have to be updated, the router will be unable to transmit packets of data during the updating operation. Due to the fact that the records are of various sizes, the search for a Free Space of size n can be considerably long. The searching task includes the steps of a)_ searching for a CAM cell having a reset valid bit b)_ reading the state of the n consecutive CAM cells c)_ If one of the said n consecutive CAM cells has a valid bit set, then repeat steps a, b and c until n consecutive CAM cells with reset valid bits are found. The number of CAM read cycles needed to execute this search can be very large, since there may be many CAM cells with a reset valid bit, but only few locations having n consecutive CAM cells with reset valid bits.

One method to enhance performance of the CAM system would be to use an additional memory (RFA) in which a list of the positions of the CAM cells with reset valid bits is stored, and update that list each time a new record is stored or deleted from the CAM.

In Fig 1, a general block diagram for a system using this method is shown. The system utilizes a CAM to search words at high speed and an additional memory space to store the Record of Free Addresses in the CAM (RFA). In such a system the processor would be able to search for Free Space using the RFA, and a multitasking operation could enable normal operation of the CAM while search for Free Space operation is being conducted concurrently. However, such a system requires additional software and memory, and each search for a Free Space would still require a considerable amount of time, thus limiting the maximum updating rate.

The present invention proposes a CAM system in which no additional memory is needed, and the Search for Free Space operation is executed by the CAM system itself at high speed. In accordance with one advantage of the inventive system and method, the performance of the CAM system is increased. It is another advantage of the inventive system and method that additional memory is not needed. It is yet another advantage of the invention that the software required for searching a Free Space is simplified.

In accordance with a first embodiment, the inventive method may be applied in a CAM that is designed to work in two different modes: normal and Find Free Space mode. When the CAM is operated in normal mode, it functions as a CAM of the known type. Words to be searched are loaded to the CAM, and if there is a matching word in the CAM, it returns its address. When the CAM is operated in the Find Free Space mode, the Valid Bit function associated to each sub-word is inverted, so that subsequent searching operations will occur only on non-valid data. Whenever a free space of size n is searched, a word composed of n sub-words is loaded for searching to the CAM. The inventive CAM cells are designed to output a Match signal in case the invalid bit is set and the CAM is put in Find Free Space mode. Neither the data loaded in the n sub-words loaded into the CAM nor the data stored in the Cam cells has any influence on the operation in that mode. The same logic system that is used to return the address of a matching word in normal mode will now output the address of a Free Space. Having found the position of a free space, a new record can be written in its place, and the normal operation of the CAM is resumed.

In accordance with another preferred embodiment, the inventive method may be implemented in a CAM system that provides means to set a "don't care" value for each sub-word of the searched word (input word) as known. In a CAM system of this type, whenever a "don't care" value is set, all sub-words of records compared to that input sub-word output a "match" signal. In such a system, the free space searching operation can be initiated by setting the Free Space Search mode, and executing a search of a word of n sub-words, each sub-word containing a don't care value. A word match signal will thus be generated for every position where n consecutive CAM cells have a reset valid bit. This novel method eliminates the need for a special circuitry used in the prior art for discarding, in the Find Free Space mode, the result of the comparison between the input word and the record word data.

The method and system described here can be implemented in CAMs used to search data of fixed word size as well as in the case of CAMs used to search words of variable size. In case of variable size of the searched words, the gain in speed of operation is particularly advantageous.

The inventive method will be described in detail in respect of the preferred embodiments. It will be understood however that these embodiments are not meant to limit the invention and many other variations and modifications of the invention may be made within the scope of the description and the claims.

In Fig 2, a CAM cell of the common type is shown. In this CAM cell, the valid bit of each of the memory cells being searched is input to the comparator. When a search operation is executed, the comparator compares the data stored in the memory bits of the cell with the data set on the bit lines. The comparator will output a "Match" signal only if the comparison resulted in a Match, and if the valid bit is set, so that only valid records will be searched for the input word. The comparator is usually so designed that if the data on the bit lines and the data in the memory are equal, then a Match signal is issued from the comparator. In some cases the comparator comprises means to set some or all the bit lines in a special state (Don't care) such that the comparison between given bits of memory and the correspondent bit lines data will always result in match for that bit.

A first embodiment of the invention will be described with reference to Fig. 3. Fig 3 shows a CAM system in which a special Find Free Space input (FFS) is used to put the CAM in the Search for Free Space mode. In case of normal search operation the FFS signal is reset, and the search is executed among the words stored in the CAM having a set valid bit. When a search for a Free Space is activated, the FFS signal is set, and the function of the valid bit is inverted, i.e. the search operation in the CAM is executed among the words of CAM having a reset valid bit. Whenever it is needed to find a free space of size n, the processor sets the FFS signal, and initiates a search operation on a word of n sub-words. This search operation is done exactly in the same way a normal search operation for a word of n sub-words is done, according to the specific method of the CAM system. The CAM will then return at high speed the position (address) of a free space of size n.

Fig 4 shows the general architecture of a CAM system designed to search words of various size. Each CAM cell is able to compare one sub-word of the record to one sub- word of the input word. Each CAM cell is connected to a CAM circuitry (Size Logic) that implements the logic functions needed to detect the match of a full word of an input string with a continuous portion of a record. This Size Logic circuitry receives as input all the Sub-word Match signals from all CAM cells, and generates a Word Match signal when a full word of the input string matches a continuous portion of a record. Then all the Word Match signals are sent to a priority encoder which outputs the position address of one of the matching word records.

It will now be shown how the method of the invention uses the architecture of Fig. 4 with a modified CAM cell in order to provide the function of Free Space searching.

Fig 5 shows a CAM cell according to the present invention to be applied in the CAM of Fig. 4. In this embodiment the match output signal from the comparator is combined with the valid bit and the FFS signal. When the FFS signal is reset, the sub- word match signal is set to the state of the match signal output from the comparator. If the FFS signal is set, only the sub-words stored in the CAM cell that have a reset valid bit will output a sub-word match signal. Then the Size Logic circuit will execute the same function as for a normal search, and generate a word match signal for every position where n consecutive CAM cells have a reset valid bit. All the word match signals are sent to the priority encoder and the address of one free space is then output.

In fig 6, a CAM cell that is suitable for a second embodiment of the method according to the present invention is shown. This embodiment is applicable in case the CAM includes means to load special "Don't Care" data in each of the sub-words of an input Word. The output of a comparator comparing a "Don't Care" sub-word of a word to a sub-word stored in a CAM cell is always a sub-word match signal. In the CAM cell of fig 6, the comparator receives an enabling input which can be selected to be either the valid bit, or the inverted valid bit. The selection is done by means of a selector, and the command to that selector is the FFS signal. In accordance with this embodiment of the invention, if the FFS signal is set and a search operation is executed, only the sub-words stored in a CAM cell having a reset valid bit are compared to sub-words of the input word. In order to execute a searching operation for a free space of size n, an input word of n sub-words is input to the CAM, with each sub-word of that word storing "don't care" data, and with the FFS signal set. Because of the "don't care" data of the input word, the comparators in each CAM cell will output a sub-word match if enabled, i.e. if the valid bit is reset. Then the Size Logic circuit will execute the same function as for a normal search, and generate a word match signal for every position where n consecutive CAM cells have a reset valid bit. All the word match signals are sent to the priority encoder and the address of one free space is then output.

As seen from the description above, the inventive method has the advantage of enabling search for free space at high speed while only necessitating a minor modification of the CAM cells.

Claims

CLAIMS:

A method for finding free space to store a word composed of an arbitrary number of sub-words in a CAM with an array of CAM cells and a priority circuit, each of the CAM cells being able to store a sub-word of data and a valid bit, each of the CAM cells having a comparator and means to disable or enable the said comparator and each of the cells comprising a circuit that puts out a sub-word match signal in case the valid bit is reset and the CAM is in Find Free Space mode, comprising the following steps:

(a) setting a Find Free Space signal that disables all comparators of the cells having a set valid bit;

(b) feeding a word of arbitrary size into the CAM;

(c) executing a search operation such that all cells with a reset valid bit will generate a sub-word match signal;

(d) logically combining the said sub-word match signals to generate a word match signal;

(e) putting the said word match signal into a priority circuit that outputs the address of the matching record with the highest priority.

A method for finding free space to store a word composed of an arbitrary number of sub-words in a CAM with an array of CAM cells, each of the CAM cells being able to store a sub-word of data and a valid bit, each of the CAM cells having a comparator and means to disable or enable the said comparator and the said CAM having means to input a word wherein each of the sub-words of the said input word contains "Don't Care" data, comprising the following steps:

(a) setting a Find Free Space signal to operate a selector that selects only cells with reset valid bits to be compared;

(b) feeding a word of arbitrary size into the CAM wherein each sub-word of the said word stores "Don't Care" data;

(c) executing a search operation wherein only sub-words stored in cells with reset valid bits are compared to the sub-words of the input word and the comparators in each CAM cell output a sub word match due to the said "Don't care" data in the sub-words of the said input word;

(e) logically combining the said sub-word match signals to generate a word match signal;

(f) putting the said word match signal into a priority circuit that outputs the address of the matching record with the highest priority.

A CAM memory that may be operated in two modes: a normal search mode for finding cells with matching data and a Find Free Space mode for finding a sequence of consecutive cells with reset valid bits wherein in the said normal search mode only sub-words stored in cells with set valid bits are searched and in the said Find Free Space mode the Valid Bit function associated with each sub- word is inverted such that sub-words of the memory stored in cells with reset valid bits generate a sub-word match signal whereby the address of a sequence of CAM cells having a reset valid bit having a length equal or longer than that of the input string is put out. A CAM memory that may be operated in two modes: a normal search mode for finding cells with matching data and a Find Free Space mode for finding a sequence of consecutive cells with reset valid bits wherein in the said Find Free Space mode each of the sub-words of the input string is put in a "Don't Care" state and the valid bits of the CAM cells are inverted whereby the address of a sequence of words having a length equal or longer than that of the input string is put out.