Abstract:
A data retrieval device capable of attaining a low power consumption while utilizing high speed retrieving characteristics of a CAM, wherein a plurality of rule data with determined priority is newly arranged in an order of the size and assigned to memory blocks in accordance with the order, information on the assigned data range is stored in a register, the rule data is rearranged again in the priority order in each memory block, a range comparator compares input retrieval data with a content held in the register and a memory block to be retrieved is specified by the result, and a block controller activates only the specified block at the time of retrieving and not activating other blocks, so that a power consumption at the tem of retrieving is reduced for that amount.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to a data retrieval device operating at a high speed with a low power consumption.  
           [0003]    2. Description of the Related Art  
           [0004]    Along with a development of the Internet, there has been a demand on retrieving and comparing rule data determined in advance with packet data at a high speed for attaining high speed path retrieving and securing of security of a packet. Due to the demand, a content addressable memory (CAM) capable of retrieving data at a high speed has become an essential device (refer to, for example, the Japanese Unexamined Patent Publication No. 2001-236790).  
           [0005]    The Japanese Unexamined Patent Publication (Kokai) No. 2001-236790 discloses a content addressable memory having a plurality of physical banks storing different data in accordance with kinds of CAMs, such as a binary CAM having data of only “0” and “1” and a ternary CAM having “X (don&#39;t care)” data in addition to the binary data, and difference of bit lengths.  
           [0006]    Currently prevailing CAM is called a ternary CAM wherein one data is composed of a plurality of bit data and each bit can store three kinds, “0”, “1” and “* (don&#39;t care)”. The stored data (rule data) and retrieval data (packet data) input from the outside are compared by every bit. When a bit in the stored data is “0 (or 1)” and a corresponding bit of the retrieval data is “0 (or 1)”, the comparison result is matched, while when the retrieval data is “1 (or 0)”, the result is not matched. And the “* (don&#39;t care)” matches with both “0” and “1” of the retrieval data. This comparison is made on all bits composing the data, and the stored data and the retrieval data are considered to be matched only when all of the data was matched.  
           [0007]    Also, since there is a case where the data stored in the CAM and the retrieval data from the outside match more than one, there is a priority circuit for outputting in an ascending (descending) order of the stored address. Normally, it is configured to output only data having the smallest address among the matched data. Accordingly, when creating rule data, significant rule data is stored in an ascending order of the address. An example thereof is shown in FIG. 2.  
           [0008]    In FIG. 2, for simplification, stored rule data  100  is largely divided to three 4-bit data regions (A, B and C) and each rule data is stored at a position of a stored address  101  in accordance with the priority order of the rule data (in the figure, a priority tag  102  indicating the order is added for facilitate understanding, but it does not actually exist). Also, a mark “* (4 bits are expressed by one mark in the figure)” in the stored rule data  100  indicates that the value can be any. Furthermore, for example “2-4” indicates that the data expressing a region from “2” to “4”. In actual, for specifying such a range, vales of respective bits of the stored rule data  100  are made to be suitable values and one rule is expressed by a plurality of stored rule data  100  in some cases, but this time, it is assumed that one rule can be expressed by one stored rule data  100  for simplification.  
           [0009]    However, a content addressable memory of the related art is configured to have a comparison circuit for every stored data stored therein and compares retrieval data from the outside with all stored data at a time. Therefore, extremely high-speed retrieving becomes possible, but since all comparison circuits operate at a time, an extremely large power is necessarily consumed. Naturally, a data transmission apparatus using the device becomes capable of transferring data at a high speed, but the large power consumption has been a disadvantage. The above Japanese Unexamined Patent Publication No. 2001-236790 does not mention such comparison circuits, and it is considered that it applies a general configuration provided that it is not specifically mentioned, the same disadvantage is shared thereby.  
           [0010]    For example, the CAM shown in FIG. 2 can store the rule data effectively and retrieve the data from the outside at an extremely high speed, but the power consumption is extremely large. It is because of comparing all stored rule data with retrieval data at a time. Furthermore, it is because due to the characteristics of the priority circuit of the CAM, the more significant rule is stored at a position with the smaller (or the larger) address, and it is difficult to specify an area wherein a rule matching with retrieval data from the outside exists in advance. Therefore, it was required to perform matching comparison on all rule data, so that a large power is consumed for performing the matching comparison.  
           [0011]    The disadvantage to be solved in the present invention is the fact that a power consumption is large because of comparing the retrieval data from the outside with the all stored data, and that hinders realization of a large scale data retrieval device at a high speed.  
         SUMMARY OF THE INVENTION  
         [0012]    An object of the present invention is to provide a data retrieval device operating at a high speed with a low power consumption.  
           [0013]    To attain the above object, according to the present invention, there is provided a data retrieval device, comprising a rearrangement means for rearranging a first data group including a plurality of rule data arranged in an order of a first processing significance degree, in an order of a second processing significance degree; and an assignment means for assigning a new second data group rearranged in an order of said second processing significance degree by the rearrangement means, to a plurality of memory blocks successively in an order from smaller (larger) second processing significance degrees; wherein when storing data assigned by said assignment means to said memory blocks, data assigned to said each memory block is furthermore rearranged in an order of said first processing significance degree by said rearrangement means and stored.  
           [0014]    In the present invention, preferably, a storage data range indication register for indicating a range that includes data of at least one said memory block in an order of said second processing significance degree is provided.  
           [0015]    In this case, furthermore preferably, a comparison specifying unit for comparing said storage data range indication register with input retrieval data and specifying a memory range including a memory block storing data to be compared with the input retrieval data based on the comparison result; and a block controlling unit for activating at the time of retrieving a memory block storing said data to be compared from said plurality of memory blocks based on the specification result of said comparison specifying unit are provided.  
           [0016]    Alternately, when the storage data range indication register is provided, preferably, a block specifying register for holding a combination of one or a plurality of memory blocks among said plurality of memory blocks by relating to reference numbers; and a block controlling unit for activating said memory block in accordance with a value stored in said block specifying register are provided.  
           [0017]    In the data retrieval device of the present invention, when the first data group including a plurality of rule data wherein the first processing significance degree is determined is input, the first data group is newly rearranged in an order of the second processing significance degree by the rearrangement means. The assignment means assigns the second data group rearranged in the second processing significance degree order is successively assigned to the plurality of memory blocks from the smaller (or the larger) ones in the second processing significance degree order. The second data group is again rearranged in the first processing significance degree order in a unit of data assigned to each memory, and stored in each memory block.  
           [0018]    In the data retrieval device configured as above, which memory block should be searched is known in accordance with input retrieval data. Namely, when corresponding relationship of the second processing significance degree and the memory block is held in the storage data range indication register, a memory block to be activated by the block controlling unit can be specified by comparing the held content with the input retrieval data by the comparison specifying unit or by checking a content held by the block specifying register based on the reference number. Accordingly, it becomes possible to control to activate only one or a plurality of memory blocks including the memory block having the same content data as the retrieval data at the time of retrieving. At this time, other memory blocks are not activated.  
           [0019]    By configuring a data retrieval device having the configuration of the present invention, a large power consumption being a large disadvantage in a CAM of the related art can be suppressed. As a result, an original structure of stored data of the CAM can be freely changed and a high speed CAM with a small power consumption realizing high speed retrieving can be realized. 
       
    
    
     BRIEF DESCRIPTION OF DRAWINGS  
       [0020]    These and other objects and features of the present invention will become more clearer from the following description of the preferred embodiments given with reference to the attached drawings, in which:  
         [0021]    [0021]FIG. 1 is a block diagram of the schematic configuration of a first embodiment;  
         [0022]    [0022]FIG. 2 is a view of a general data storing method as a comparative example of a data storing method of the first embodiment;  
         [0023]    [0023]FIG. 3 is a view of a data storing method of the first embodiment;  
         [0024]    [0024]FIG. 4 is a view of the configuration of a block selection control unit and an example of data storing in the first embodiment;  
         [0025]    [0025]FIG. 5 is a view of another configuration of a block selection control unit and an example of data storing in the first embodiment;  
         [0026]    [0026]FIG. 6 is a block diagram of a data retrieval device of a second embodiment of the present invention;  
         [0027]    [0027]FIG. 7 is a table showing an example of a corresponding relationships of table numbers and blocks in the second embodiment; and  
         [0028]    [0028]FIG. 8 is a block diagram of a modified example of the data retrieval device of the second embodiment. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT  
     First Embodiment  
       [0029]    The first embodiment relates to a data retrieval device.  
         [0030]    A data retrieval device in the embodiments of the present invention is realized by a semiconductor memory integrated circuit, a module and a substrate mounted with the integrated circuit, or an electronic device, etc. housing the same in a chassis. Below, embodiments will be explained by focusing on a content addressable memory (CAM) as a key part of the data retrieval device of the present invention.  
         [0031]    [0031]FIG. 1 is a block diagram of the schematic configuration of the CAM. The CAM  10  shown in FIG. 1 comprises a CAM unit  1  composed of a plurality of memory blocks  1 - 1 ,  1 - 2 ,  1 - 3 , . . . , a block selection control unit  2  for activating any one of the memory blocks, and a retrieval control unit  3 .  
         [0032]    The block selection control unit  2  has functions of “a comparison specifying unit” and “a block controller” of the present invention. The retrieval control unit  3  is a memory peripheral circuit for performing necessary controlling for data retrieving and comprises a circuit for selecting and driving a variety of signal lines, such as bit lines, bit auxiliary lines and match lines, a data buffer circuit at the time of writing and reading, and a power source circuit, etc. while not illustrated. Also, in accordance with need, the retrieval control unit  3  includes a masking function for removing a part of bits of retrieval data (SK) from a comparison subject. Furthermore, the retrieval control unit  3  have a function of “rearrangement means” for rearranging stored rule data (first data group) input in an order of first processing significance degree to a second processing significance decree (for example, an order of a size of data values). The retrieval control unit  3  also has a function of “assignment means” for assigning a data group (a second data group) arranged by the second processing significance degree successively to the plurality of memory blocks  1 - 1 ,  1 - 2 ,  103 , . . . in an order of the second processing significance degree. Note that the “rearrangement means” and the “assignment means” may be realized by one block or respectively separated function blocks. Alternately, a function of the “assignment means” may be included in the block selection control unit  2 .  
         [0033]    A detailed explanation will be made later on, but control of storing rule data in a memory will be briefly explained here.  
         [0034]    The above “rearrangement means” rearranges the first data group to be a second data group, and the above “assignment means” determines a data range in the second data group to be stored in respective memory blocks successively by following the order of the second processing significance degree. As will be explained later on, information indicating a relation of the data range and the memory block is stored, for example, in a “storage data range indication register” in the block selection control unit  2 . After that, when writing the second data group to the actual memory blocks, the “rearrangement means” again rearranges by the first processing significance degree as the original order in unit of a data in each memory block assigned in an order of the second processing significance degree. Therefore, data stored in the respective memory block by the retrieval control unit  3  is sectionalized by ranges of the second processing significance degree when perceiving by large memory blocks, but arranged in an order of the first processing significance degree in the respective memory blocks.  
         [0035]    Below, the data arrangement and storage, and control at data retrieving will be explained in detail. The data storage structure of the related art made by following the first processing significance degree will be explained first, then the embodiments of the present invention will be explained by comparing with the same.  
         [0036]    [0036]FIG. 2 shows the data storage structure of the related art. In the present example, there are 11 storage rule data and the rule data is divided to three regions A, B and C, each composed of 4 bits.  
         [0037]    Rule data  100  having the highest priority (the data added with a priority tag  102  indicating P 1  in FIG. 2) is stored at the first address, wherein A is 11, B is 2-4 and C is 3. Rule data  100  having the second priority (the data added with a priority tag  102  indicating P 2  in FIG. 2) is stored at the second address, wherein A is 0, B is 6 and C is 3-5. Also, rule data  100  having the lowest priority (the data added with a priority tag  102  indicating P 11  in FIG. 2) is stored at the eleventh address, wherein A is 8, B is 2 and C is 10.  
         [0038]    As is understood from this example, when regarding the A, B and C as a series of data, the rule data  100  having the highest priority indicates the size of a range of 110203 to 110403, the rule data  100  having the second priority indicates a range of 000603 to 000605, and the rule data  100  having the eleventh priority indicates 080210. On the other hand, the stored rule data is compared with retrieval data from the outside, and at that time, all comparison circuits of all stored rule data are operated in the CAM of the related art.  
         [0039]    The reason why all stored rule data  100  have to be compared as such is that the stored rule data  100  is not arranged by following a certain general order (size of data, etc.) and that relationships between the retrieval data SK and the stored rule data  100  are completely unknown.  
         [0040]    Thus, in the present invention, CAM data is structured so that a certain relationship between the stored rule data  100  and the retrieval data SK can be found and an accessible portion is limited to attain a low power consumption.  
         [0041]    As general orders, a size of data is typical. FIG. 3 shows what obtained by arranging in an order of the size first and reassigned by four to each memory block (hereinafter, simply referred to as a block) by the above “rearrangement means”. When arranged in a size order, the priority order of the original rule data  100  is not maintained. However, a range of the rule data  100  stored in the respective block becomes clear. For example, a data range of the block  1  is from “000201 (rule data with a priority tag P 4 ) to “011531 (rule data with a priority tag P 7 ), a data range of the block  2  is from “011502 (rule data with a priority tag P 9 ) to “070431 (rule data with a priority tag P 10 ), and a data range of the block  3  is from “080210 (rule data with a priority tag P 11 ) to “120405 (rule data with a priority tag P 5 ).  
         [0042]    However, a problem appears on the boundary of the block  1  and the block  2 . Namely, the rule data with the priority data P 7  has an own range and expressing data from “010800” to “011531”. On the other hand, the rule data with the priority tag of P 7  may be smaller than the rule data with the priority tag of P 9  in some cases and larger than that in other cases.  
         [0043]    In such cases, largely two expressing methods are considered the rule data should be treated as which block data. Data ranges of the respective blocks at this time become as below.  
       (1) Method by Dividing  
       [0044]    In the case where the block  1  is stored with up to “011501” in the rule data with the priority tag of P 7 , the block  2  is stored with “011502” to “011531” by disassembling, the data range of the block  1  is from “000201” to “011501 (a part of the rule data with the priority tag of P 7 )”, the data range of the block  2  is from “011502 (a part of the rule data with the priority tag of P 7 )” to “070431”, and a data range of the block  3  is “080210” to “120405”.  
       (2) Method not by Dividing  
       [0045]    In the case where the block  1  stores all of the rule data with the priority tag of P 7 , “010800” to “011531”, and the block  2  stores “011502” and after that of the rule data of the priority tag of P 9 , a data range of the block  1  is from “000201” to “011531”, a data range of the block  2  is from “011502” to “070431” and a range of the block  3  is from “080210” to “120405”.  
         [0046]    It should be noted that ranges of data are overlapped between the block  1  and the block  2  at this time.  
         [0047]    [0047]FIG. 4 shows a rule data storing state in the case of the method by dividing described in the above (1). The rule data with the priority tag of P 7  expressed in the block  1  indicates a range from “010800” to “011501” (P 7 A and P 7 B in FIG. 4). Also, the rule data with the priority tag of P 7  expressed in the block  2  indicates from “011502” to “011531” (P 7 C in FIG. 4). In each block, data is arranged based on the original priority of the original rule data.  
         [0048]    How matching retrieval with the retrieval data from the outside is performed in this state will be explained. In FIG. 4, a pointer  22 A composing an embodiment of a “storage data range indication register” of the present invention is provided. First, in this example, for indicating data ranges of the memory blocks (the block  1  to block  3 ), a data top pointer TP 2  of the block  2  in the pointer  22 A is input the minimum data “011502”, a data top pointer TP 3  of the block  3  in the pointer  22 A is input the minimum data “070200” in advance.  
         [0049]    A value of retrieval data (SK) input from the outside is assumed to be “011503”. The data is input to a range comparator  21 , compared with the data top pointers TP 2  and TP 3 , and the range is judged to be a range of the block  2  of the storage rule data. Note that the range comparator  21  composes an embodiment of a “comparison specifying unit” of the present invention.  
         [0050]    From the judgment result, a block controller  23  activates only the block  2 . Then, retrieving starts on the activated memory block by using the retrieval data (SK). A retrieving range to be activated is limited, which has been impossible in the related art, and retrieving at a high speed and a low power consumption by the CAM becomes possible.  
         [0051]    Also, as a method of assigning data to respective blocks of the storage rule data regions, in the case of the above (2) wherein data ranges are overlapped, as shown in FIG. 5, in the register  22  indicating a storage data range of the block, two pointer values, that is, a top pointer value TP and an end pointer value EP are provided for every block. A combination of the respective top pointer values TP and the end pointer values EP are TP 1  (0,2,1) and EP 1  (1,15,31) for the block  1 , TP 2  (1,15,2) and EP 2  (7,4,31) for the block  2 , and TP 3  (8,2,10) and EP 3  (12,4,5) for the block  3 .  
         [0052]    In the same way as in the above (1), first, the retrieval data (SK)  201  is compared with values of the top pointer and the end pointer of each block by the range comparator. When assuming that the retrieval data is “011503”, a retrieval subject range is the block  1  and the block  2 , and the block  1  and the block  2  are controlled as regions to be activated at the time of retrieving. At this time, since the rule data with the priority tag of P 7  which should be matched is stored in the block  1 , it is matched in the block  1 .  
         [0053]    As explained above, since the range of the rule data with the priority tag of P 7  is from “010800” to “011531”, in the case where there is a smaller range or a larger range than the rule data with the priority tag of P 9 , in order to use a simple CAM priority encoder (not shown) for outputting those with small addresses, it is important to arrange those having high priority in terms of the original rule in upper blocks (block with a small address). Also, it is of course possible to design a priority encoder circuit to judge and control special priority.  
         [0054]    While not particularly described in the above explanation, a CAM is generally composed of a semiconductor integrated circuit, and the configuration installed inside the IC may be only a CAM unit  1  at least composed of a plurality of blocks, and in accordance with need, that is, as the configuration which should be included in a memory peripheral circuit in terms of easy controlling, for example, it is preferable to install a block controller  23  on the IC. In any cases, according to the present embodiment, only necessary blocks among the plurality of blocks composing the CAM unit  1  are activated, so that a power consumption of the CAM IC can be reduced.  
       Second Embodiment  
       [0055]    In the above first embodiment, information relating to a data storage place held by a pointer as a comparison specifying unit was in a range of a data size.  
         [0056]    In the second embodiment, as information relating to the data storage places, the case where other than a range of a data size can be used will be explained.  
         [0057]    [0057]FIG. 6 is a block diagram of a data retrieval device according to the second embodiment. Note that the overall configuration view of FIG. 1 is in common with that of the present embodiment.  
         [0058]    The data retrieval device comprises in a CAM  30  a CAM unit  1  including a plurality of memory blocks (blocks)  1 - 1  to  1 - 4  and block controlling unit, for example, a block controller  23  in the same way as in the first embodiment. The configuration of respective blocks in the CAM unit  1 , a method of storing data in blocks, and a method of dividing in the case where data is included over a plurality of blocks are the same as those in the first embodiment and the explanation will be omitted here.  
         [0059]    In the present embodiment, as an example of information relating to data storage places in the CAM  30 , a block specification register  31  for defining a corresponding relationship of a table number and a block number is provided. The table number and the block number correspond to a “reference number” of the present invention. Also, a conversion circuit  32  compares the table number input from the outside with the register content and converts to identification information of a block corresponding to the table number. Then, the block controller  23  activates only one or more blocks indicated by the identification information of the block.  
         [0060]    [0060]FIG. 7 is a table showing corresponding relationships of table numbers and blocks by taking an example of storing data of the block specification register  31 .  
         [0061]    In FIG. 7, in “table 1”, block number values of the blocks  1  and  2  are 1 and other than those are 0. This indicates that only the block  1  and block  2  belong to the table 1. Each block basically belong to one table, but as shown in the figure, it is possible to belong to a plurality of tables. Also, the configuration of each table and the number of blocks are not particularly limited.  
         [0062]    Outside of the CAM  30 , there is provided a table selection controller  4  for specifying a table to be selected based on input retrieval data (SK)  201 . The table selection controller  4  comprises a table pointer  40 , a table comparator  41  and a table controller  42 .  
         [0063]    The table pointer  40  stores a plurality of, four here, pointer values TA. P1 to Ta. P4, and outputs the pointer storage content to the table comparator  41  in accordance with a request by the table comparator  41 . The table comparator  41  compares input retrieval data with the read pointer storage content and specifies a table number storing the storage data in the CAM unit to be compared with the retrieval data. The table controller  42  converts the table number to a form suitable to an output bus  44  and makes the same output.  
         [0064]    The table number sent from the output bus  44  is input to the conversion circuit  32 . The conversion circuit  32  refers to a block specifying register  31  holding a defined content of the table number and a block and specifies a block to be activated from the input table number. When identification information of a block is input to the block controller  23  from the conversion circuit  32 , being controlled by the block controller  23 , one or a plurality of blocks including at least storage data to be compared with retrieve data are activated. After that, data retrieving is performed in the same way as in the first embodiment and the retrieval result is output from the CAM  30 .  
         [0065]    In the second embodiment, there is an advantage that a power consumption of the CAM itself can be reduced by specifying a data storage range outside of the CAM. Also, a method of specifying a data storage range from a different viewpoint from that of the first embodiment becomes possible.  
         [0066]    Note that the present embodiment can be combined with the first embodiment.  
         [0067]    [0067]FIG. 8 is a block diagram of the modified example.  
         [0068]    The data retrieval device comprises as a common configuration with that of the first embodiment a pointer  22  (or  22 A) as a “storage data range indication register” for holding information indicating a range of data size and a range comparator  21  as a “comparison specifying unit”. Functions of these are the same as those in the first embodiment, so that the explanation will be omitted here. In this modified example, since a data storage range of storage data to be compared with retrieval data is searched from both the table and the range (size range), the accuracy is improved and controlling efficiency can be improved by narrowing down the broad data storage range by the table, then, by specifying the data storage range by the range, etc.  
         [0069]    In the above first and second embodiments, advantages below can be obtained.  
         [0070]    The CAM can be the cell configuration, for example, on a SRAM base, so that high speed data retrieving becomes possible.  
         [0071]    In a CAM of the related art, data is stored only in a priority order (an order of the first processing significance degree) and not arranged based on a unique order (an order of the second significance degree) by which judgment from data itself is possible, relationships between the retrieval data and storage data are completely unknown. Therefore, in the CAM of the related art, all CAM cells were driven at a time to search the all ranges of the memory every time retrieval data is input.  
         [0072]    In the present embodiment, the memory is divided to a plurality of memory blocks and only one memory block in principle or two memory blocks depending on cases, which is low in probability in the normal memory block scale that one block holds several kilobytes of data, are driven. Therefore, the larger a memory capacity and the number of blocks, the larger the effect of reducing a power consumption.  
         [0073]    For example, in a rooter on the server side and for relaying, a mass of packets are processed in an extremely short time, so that a power consumption increases. An increase of a power consumption of a CAM chip causes erroneous operation due to heating and disturbs high speed performance. This has been a bottleneck of pursuing higher integration of the CAM. In the present embodiment, a power consumption of the CAM can be reduced to less than half or by one rigid or more, so that it is possible to dramatically improve the performance of such a large scale rooter, etc.  
         [0074]    Note that in the above embodiments, an embodiment of algorithm base is also possible, wherein particularly the block selection controlling means, rearrangement means and assignment means of data are executed by a program in an exclusive or existing CPU, etc. In this case, processing at a further higher speed becomes possible.  
         [0075]    Realization of the power-saving data retrieval device and a data transmission device using the same has become a significant social challenge today with a development of the Internet and the trend spreads to the allover world in the future, so that the industrial value is extremely high.  
         [0076]    The present invention can be widely applied to use as a CAM with a large scale memory capacity, a variety of data retrieval devices and data transfer devices, such as a rooter, incorporating the same.  
         [0077]    The embodiments explained above are for easier understanding of the present invention and not to limit the present invention. Accordingly, respective elements disclosed in the above embodiments includes all modifications in designs and equivalents belonging to the technical field of the present invention.