+

WO2003052765A1 - Recherche d'espace libre dans une memoire a contenu adressable - Google Patents

Recherche d'espace libre dans une memoire a contenu adressable Download PDF

Info

Publication number
WO2003052765A1
WO2003052765A1 PCT/IL2002/001019 IL0201019W WO03052765A1 WO 2003052765 A1 WO2003052765 A1 WO 2003052765A1 IL 0201019 W IL0201019 W IL 0201019W WO 03052765 A1 WO03052765 A1 WO 03052765A1
Authority
WO
WIPO (PCT)
Prior art keywords
word
cam
sub
cells
free space
Prior art date
Application number
PCT/IL2002/001019
Other languages
English (en)
Inventor
Shaul Ben Haim
Yiftach Maayan
Yves Villaret
Original Assignee
Memcall L.L.C.
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Memcall L.L.C. filed Critical Memcall L.L.C.
Priority to AU2002360201A priority Critical patent/AU2002360201A1/en
Publication of WO2003052765A1 publication Critical patent/WO2003052765A1/fr

Links

Classifications

    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11C—STATIC STORES
    • G11C15/00—Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

Definitions

  • CAM Content Addressable Memory
  • records each word being composed of a number of sub-words.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • "Free Space" being defined as a number of consecutive invalid words equal or greater than the size of the new record.
  • 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.
  • 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.
  • the inventive method may be applied in a CAM that is designed to work in two different modes: normal and Find Free Space mode.
  • normal 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • RFA another memory
  • 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.
  • 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.
  • 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.
  • CAM Content Addressable Memories
  • CAM systems are used to execute searching operations at high speed.
  • 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.
  • 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.
  • 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.
  • 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.
  • RFA additional memory
  • 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).
  • RFA Record of Free Addresses in the CAM
  • 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.
  • RFA Record of Free Addresses in the CAM
  • 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.
  • 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.
  • the inventive method may be applied in a CAM that is designed to work in two different modes: normal and Find Free Space mode.
  • normal 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • the gain in speed of operation is particularly advantageous.
  • a CAM cell of the common type is shown.
  • the valid bit of each of the memory cells being searched is input to the comparator.
  • 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.
  • 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.
  • 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.
  • FFS Find Free Space input
  • the FFS signal is reset, and the search is executed among the words stored in the CAM having a set valid bit.
  • 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.
  • 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.
  • 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.
  • Fig 5 shows a CAM cell according to the present invention to be applied in the CAM of Fig. 4.
  • the match output signal from the comparator is combined with the valid bit and the FFS signal.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.

Landscapes

  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

L'invention porte sur un procédé accélérant la recherche de Free Space (espace libre) dans une mémoire CAM (à contenu adressable) servant à rechercher des mots de taille arbitraire. A cet effet, on inverse la fonction de bit valide associée à chacun des sous-mots de manière à ne rechercher que les données non valides. Les cellules de la CAM émettent un signal Match (de concordance) lorsque le bit invalide est fixé et que la CAM se trouve en mode Find Free Space (trouver espace libre). La même logique de système que celle utilisée pour retourner l'adresse du mot correspondant en mode normal de recherche fournit l'adresse d'un Free Space présentant un nombre total de sous-mot invalides consécutifs, égal ou plus grand que la taille du mot entré. Dans une autre exécution, les valeurs 'Don't care' (état indifférent) sont entrées dans la CAM pour chaque sous-mot du mot entré de telle manière que chaque fois qu'une valeur 'Don't care' est fixée, tous les sous-mots des enregistrements comparés à ce sous-mot entré fournissent un signal Match.
PCT/IL2002/001019 2001-12-19 2002-12-18 Recherche d'espace libre dans une memoire a contenu adressable WO2003052765A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
AU2002360201A AU2002360201A1 (en) 2001-12-19 2002-12-18 Finding free space in a content addressable memory

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US34081301P 2001-12-19 2001-12-19
US60/340,813 2001-12-19

Publications (1)

Publication Number Publication Date
WO2003052765A1 true WO2003052765A1 (fr) 2003-06-26

Family

ID=23335038

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/IL2002/001019 WO2003052765A1 (fr) 2001-12-19 2002-12-18 Recherche d'espace libre dans une memoire a contenu adressable

Country Status (2)

Country Link
AU (1) AU2002360201A1 (fr)
WO (1) WO2003052765A1 (fr)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7181567B2 (en) * 2002-06-04 2007-02-20 Lucent Technologies Inc. Hitless restart of access control module
JP2012514825A (ja) * 2009-01-22 2012-06-28 クアルコム，インコーポレイテッド 電力節約スタティックベースコンパレータ回路および方法ならびにそれらを採用する連想メモリ（ｃａｍ）回路

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5946704A (en) * 1994-02-10 1999-08-31 Kawasaki Steel Corporation Associative memory to retrieve a plurality of words
US5999434A (en) * 1992-01-10 1999-12-07 Kawasaki Steel Corporation Hierarchical encoder including timing and data detection devices for a content addressable memory
JP2000222884A (ja) * 1999-02-01 2000-08-11 Internatl Business Mach Corp <Ibm> 連想メモリのアイドルワードの検出回路および検出方法

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5999434A (en) * 1992-01-10 1999-12-07 Kawasaki Steel Corporation Hierarchical encoder including timing and data detection devices for a content addressable memory
US5946704A (en) * 1994-02-10 1999-08-31 Kawasaki Steel Corporation Associative memory to retrieve a plurality of words
JP2000222884A (ja) * 1999-02-01 2000-08-11 Internatl Business Mach Corp <Ibm> 連想メモリのアイドルワードの検出回路および検出方法
US6477615B1 (en) * 1999-02-01 2002-11-05 International Business Machines Corporation Detecting circuit and detecting method of idle word for content addressable memory

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7181567B2 (en) * 2002-06-04 2007-02-20 Lucent Technologies Inc. Hitless restart of access control module
JP2012514825A (ja) * 2009-01-22 2012-06-28 クアルコム，インコーポレイテッド 電力節約スタティックベースコンパレータ回路および方法ならびにそれらを採用する連想メモリ（ｃａｍ）回路
EP2382636B1 (fr) * 2009-01-22 2016-05-25 QUALCOMM Incorporated Comparateur statique permettant une économie d'énergie et son procédé ainsi que une mémoire adressable par le contenu utilisant ceux-ci

Also Published As

Publication number Publication date
AU2002360201A1 (en) 2003-06-30

Similar Documents

Publication Publication Date Title
US6526474B1 (en) Content addressable memory (CAM) with accesses to multiple CAM arrays used to generate result for various matching sizes
US6081440A (en) Ternary content addressable memory (CAM) having fast insertion and deletion of data values
US6665297B1 (en) Network routing table
EP1551141B1 (fr) Dispositif et procédé pour implanter effectivement une recherche d&#39;adresse IP avec une fonction de hachage dans un circuit
US6181698B1 (en) Network routing table using content addressable memory
US9280609B2 (en) Exact match lookup scheme
US7007132B2 (en) Methods and apparatus for utilizing flash burst mode to improve processor performance
US7895213B2 (en) Method and system for providing cascaded trie-based network packet search engines
US6772279B1 (en) Method and apparatus for monitoring the status of CAM comparand registers using a free list and a busy list
US11886746B1 (en) Algorithmic TCAM with storage activity-based read
US20070294472A1 (en) Integrated circuit with associated memory function
US6181592B1 (en) Content addressable memory
US7924839B2 (en) Mechanism to reduce lookup latency in a pipelined hardware implementation of a trie-based IP lookup algorithm
US7035995B2 (en) Method and apparatus for performing a high speed binary search in time critical environments
US7136960B2 (en) Hardware hashing of an input of a content addressable memory (CAM) to emulate a wider CAM
JP2002531004A (ja) 適合アドレスルックアップテーブルジェネレータのための方法および装置
US20030023581A1 (en) Method and system for performing a longest prefix match search
US6996664B2 (en) Ternary content addressable memory with enhanced priority matching
US6961337B2 (en) Interleaved processing system for processing frames within a network router
WO2003052765A1 (fr) Recherche d&#39;espace libre dans une memoire a contenu adressable
US20030163637A1 (en) Memory system for searching a longest match
US7154892B2 (en) Method and apparatus for managing LPM-based CAM look-up table, and recording medium therefor
US20080175030A1 (en) Stored don&#39;t-care based hierarchical search-line scheme
CN1996952A (zh) Tcam路由表查找方法及tcam路由表查找装置
US6665770B2 (en) Device and method for updating a pointer value by switching between pointer values

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NO NZ OM PH PL PT RO RU SC SD SE SG SK SL TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): GH GM KE LS MW MZ SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR IE IT LU MC NL PT SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
32PN Ep: public notification in the ep bulletin as address of the adressee cannot be established

Free format text: NOTING OF LOSS OF RIGHTS PURSUANT TO RULE 69(1) EPC

122 Ep: pct application non-entry in european phase
NENP Non-entry into the national phase

Ref country code: JP

WWW Wipo information: withdrawn in national office

Country of ref document: JP

点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载