JP3623082B2 - Associative memory module - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention uses a partial bit string of input data as a search key, and matches the search key from a data table consisting of a plurality of data groups stored in advance in data storage means built in the associative memory module. This function has a function to search a data group including items to be read and to read out the contents or storage position, and when the search key coincides with a plurality of data groups at the same time, the search key bit string is the longest. The present invention relates to an associative memory module for extracting a data group.
[0002]
[Prior art]
In order to perform IP routing processing using an IP routing processing device (router) having a plurality of input / output ports, a 32-bit “partner IP address” is detected from the header information of a packet arriving at an input port, and this It is necessary to send the arrived packet to an output port that matches the detected partner IP address, that is, to determine an output port to which the arrived packet is to be sent. In this case, the above-mentioned "partner IP address" is used as a search key, and an item in the routing table existing in the router is searched, and by selecting an output port registered in the item that matches the search key, Determine the output port to which the arriving packet should be sent.
[0003]
As a process for determining the output port, the best match method is adopted. In this best match processing, first, IP addresses in the routing table are matched one-to-one for each IP address, and some bits of the “partner IP address” are matched using separately prepared netmask information. After performing mask processing to be excluded from the target, the masked data is compared with data to be searched using the masked data as a search key, and when a plurality of candidates are matched, the mask length (bit width of the mask) is the longest. This is a process of adopting data (data with the shortest bit width excluded from the matching target) as the highest priority candidate.
[0004]
If the bit with “1” on the mask data is to be compared, for example, the data of the mask data is “11111111 11111111 11111111 00000000” and the data is 32 bits wide (data for comparison is 24 bits) When the search key matches the 32-bit width data (data whose comparison reference is 16 bits) whose mask data is “11111111 11111111 00000000 00000000”, the former data whose comparison target is 24 bits is selected. .
[0005]
Although this best match process is the main part of the routing process, conventionally, the best match process is executed by software using a CPU, so that an improvement in the throughput of the router itself is prevented. There is.
[0006]
[Problems to be solved by the invention]
On the other hand, associative memory (CAM) is conventionally known as hardware for comparing contents at high speed. This conventional associative memory performs a mask process uniformly on input data and only searches the contents, and performs a mask process individually for each IP address stored for performing the best match process. Not something to do.
By the way, the mask data used for the best match process is generally the same for a plurality of IP addresses because of communication rules. Therefore, the best match process is executed using a plurality of conventional associative memories. Can be considered.
[0007]
That is, first, the search target data having the “partner IP address” having the same mask data is stored in the same associative memory. In this case, the same mask data is set in the mask data storage register of each associative memory. When the search process is actually performed, first, input data (search data) is simultaneously given to each associative memory, and the mask process and the search for each associative memory are executed simultaneously. Next, each search result is sent to a separately provided priority encoder, and the search result having the mask data with the longest bit width among the plurality of search results output from the associative memory is finally adopted. In this way, the best match process can be realized.
[0008]
However, when the best match process is executed using a plurality of conventional associative memories as described above, the number of data to be searched to be stored cannot be assumed in advance, so when configuring a circuit that executes the best match process In addition, the capacity of the associative memory to be prepared for each mask data cannot be predicted.
[0009]
That is, the number of data to be searched having the same mask data (partner IP data to be searched) is expected to vary from mask data to mask data. Therefore, an associative memory having the same capacity is prepared for each mask data. As a result, there is a problem that the capacity may be excessive or insufficient, and the capacity of the prepared associative memory may not be used effectively.
[0010]
An object of the present invention is to provide an associative memory module having high speed by performing the best match processing by hardware and flexibility capable of effectively using the capacity of the prepared associative memory. It is.
[0011]
[Means for Solving the Problems]
The present invention performs mask processing on input data with mask data given from the outside, takes out the bit string masked by the mask processing as a search key, and retrieves the search from a plurality of search target data stored in advance. A plurality of associative memories that search for searched data that matches the key, and a priority encoder that selects one search result from a plurality of search results output from each of the plurality of associative memories according to a preset priority order A priority order setting means capable of arbitrarily setting the priority order of data selection in the priority encoder from the outside, and simultaneously providing the input data to each of the plurality of associative memories, Simultaneously let each of the associative memories perform a search simultaneously The priority encoder selects one search result from the plurality of search results obtained by the simultaneous execution according to the set priority order, and the priority order setting means includes: When there are N associative memories in the associative memory module, N or less types of groups in which selection priority order by the priority encoder is determined are provided, and each of the plurality of associative memories is included in the group. It has a group registration register indicating which group it belongs to, and only by changing the value of the group registration register, a predetermined associative memory among the plurality of associative memories This is an associative memory module having means for registering in a desired group.
[0012]
BEST MODE FOR CARRYING OUT THE INVENTION
FIG. 1A is a circuit diagram showing an associative memory module 100 according to an embodiment of the present invention.
[0013]
The associative memory module 100 includes four associative memories (CAM) 100a, 100b, 100c, and 100d, and a group registration register 115.
[0014]
Each of the associative memories 100a, 100b, 100c, and 100d includes a circuit that uniformly performs mask processing on the input data 117, and includes mask registers Ra, Rb, Rc, and Rd that store mask data. . Here, associative memories 100a, 100b, 100c, and 100d have a capacity of n words when 32 bits are taken as one word. Each of the mask registers Ra, Rb, Rc, and Rd has a capacity of 32 bits.
[0015]
The searched data and the mask data are in one-to-one correspondence, and the searched data having the same mask data are grouped into one group, and the searched data is stored in different associative memories for each group. Is done. The mask data is set in a mask register built in the corresponding content addressable memory.
[0016]
It is assumed that the values shown in FIG. 1B are stored in the mask registers Ra, Rb, Rc, and Rd provided in the associative memories 100a, 100b, 100c, and 100d, respectively. If the mask data stored in the mask registers Ra to Rd are the same, they are grouped into one group. Therefore, in the state shown in FIG. 1 (2), the four mask registers are “Ra”. , “Rb, Rc” and “Rd”. In FIG. 1A, mask registers belonging to the same group are displayed with the same pattern.
[0017]
The associative memory module 100 can store search target data having a maximum of four types of mask data, and the associative memories 100a to 100d include a hit flag indicating that search target data that matches as a result of search exists. The search target data that coincides as a result of the search is output. When there is matching data to be searched, the hit flag is “1”, and when there is no matching data to be searched, the hit flag is “0”. All signals output from the associative memories 100 a to 100 d are input to the priority encoder 106.
[0018]
When the plurality of hit flags become “1”, the priority encoder 106 selects one hit flag from among the plurality of hit flags that have become “1” according to the priority order that determines which is finally output. A hit flag is selected, and data to be searched corresponding to the selected hit flag is selected. The priority order is determined by the value of the group registration register 115.
[0019]
The group registration register 115 indicates which group each of the four associative memories 100a, 100b, 100c, and 100d belongs to, and includes four registers C0, C1, C2, and C3. C1, C2, and C3 are each composed of 4 bits, and the 4 bits correspond to the associative memories 100a, 100b, 100c, and 100d from the left in FIG.
[0020]
For example, in the embodiment shown in FIG. 1, since the register C0 is “0110”, the two associative memories 100b and 100c belong to the group C0, and the register C1 is “1000”. Since 100a belongs to the group C1 and the register C2 is “0000”, there is no associative memory belonging to the group C2, and since the register C3 is “0001”, the associative memory 100d belongs to the group C3.
[0021]
The associative memories belonging to the same group have the same mask data, that is, the same mask data is set in the mask registers of the associative memories belonging to the same group. In this case, it is assumed that the groups have the highest priority in the order of the registers C0, C1, C2, and C3, and the search target data having mask data with a long bit width is stored in the corresponding associative memory in that order. In the above embodiment, as shown in FIG. 1B, the associative memories 100b and 100c have the highest priority, the associative memory 100a has the second highest priority, and the associative memory 100d has the highest priority last.
[0022]
Here, it is assumed that the priorities of the associative memories belonging to the same group are higher as they are located on the left side in the group registration register 115 shown in FIG. Therefore, in the above embodiment, the priority of the associative memory 100b is higher than the priority of the associative memory 100c.
[0023]
The priority encoder 106 can uniquely determine the priority for the input data according to the above rules.
[0024]
That is, the associative memory module 100 performs mask processing on input data with mask data given from the outside, takes out the bit string masked by the mask processing as a search key, and stores it in the associative memories 100a to 100d in advance. A plurality of associative memories 100a to 100d are provided for searching for a search target data that matches the search key from a plurality of search target data. From the plurality of search results output from each of the plurality of associative memories 100a to 100d, The associative memory module is provided with a priority encoder 106 for selecting one search result in accordance with a preset priority order, and has priority order setting means and simultaneous search execution means. The priority order setting means can arbitrarily set the priority order of data selection in the priority encoder 106 from the outside, and the simultaneous search execution means stores the input data in a plurality of associative memories 100a to 100d. It is a means for giving each one simultaneously and causing each of the plurality of associative memories 100a to 100d to execute a search simultaneously.
[0025]
Next, the operation of the above embodiment will be described.
[0026]
In the embodiment shown in FIG. 1, input data 117 is simultaneously added to the four associative memories 100a, 100b, 100c, and 100d, and the input data is searched. As a result of this search, the search target data that matches the search key is associative. It is assumed that the memories 100a, 100b, and 100c exist. That is, if the hit flags 107, 109, 111, and 113 become “1”, “1”, “1”, and “0”, respectively, among the above four associative memories 100a, 100b, 100c, and 100d It can be seen from the setting contents of the group registration register 115 that the associative memory 100b has the highest priority. That is, the priority is higher in the order of the registers C0, C1, C2, and C3, and the higher the priority is in the group registration register 115 shown in FIG. The degree will be the highest.
[0027]
Therefore, as a final result, the priority encoder 106 outputs the value 110 of the associative memory 100b as the output data 119, and further sets a hit flag 118 that informs that the matching data exists as a whole of the associative memory module 100 as “ 1 ”to inform the outside. According to the embodiment, the best match process can be realized.
[0028]
Further, according to the above embodiment, the four associative memories 100a, 100b, 100c, and 100d can be grouped in any way according to the setting of the group registration register 115. For example, when there are three types of masks and the number of data to be searched is n or less, it can be handled by three associative memories, for example, associative memories 100a, 100b, and 100c. That is, new search target data is added, and mask data corresponding only to a predetermined group of mask data (for example, the associative memory 100a) is the number of search target data that can be stored in one associative memory. Is exceeded, the mask data corresponding to n + 1 or more searched data is stored in the associative memory 100d (that is, the same as the mask data written in the associative memory 100a in the mask register Rd of the associative memory 100d). Further, the value of the corresponding group registration register 115 may be rewritten so that the associative memory 100d belongs to the group to which the associative memory 100a belongs.
[0029]
In this way, when the number of data to be searched stored in one associative memory belonging to a predetermined group increases, mask data corresponding to the data to be searched is associated with another associative memory from the one associative memory. What is necessary is just to rewrite the value of the corresponding group registration register | resistor 115 so that it may store in a memory and said another content addressable memory may belong to the said predetermined group. By doing so, it is possible to newly create a storage area for n new searched data without changing any registered data to be searched.
[0030]
In the embodiment shown in FIG. 1, the number of registers constituting the group registration register 115 is the same as the total number of groups (= the number of associative memories), and the bit width of each register is the same as the number of associative memories. Therefore, the total number of bits of the group registration register 115 is the square of the number of associative memories. For example, in the embodiment shown in FIG. 1, the total number of bits of the group registration register 115 is 4 × 4 = 16 bits. This is the measure taken to simplify the logic of the priority encoder. By the way, since it is only necessary to express to which group each associative memory belongs, the number of the group may be encoded and expressed by a binary number. For example, in the embodiment shown in FIG. 1, there are four groups, and if each group number is set to “00”, “01”, “10”, “11”, the group number is 2 It can be expressed in bits. In this way, the priority order of data to be searched in the priority encoder can be controlled by 4 × 2 = 8 bits.
[0031]
Further, the priority order of the priority encoder may be controlled by assigning a unique order to each associative memory without grouping. In this case, the number of bits representing the total number of associative memories in binary may be provided corresponding to each associative memory, and the total number of bits in the register is the same as in the above case of encoding the group number. This makes the priority encoder logic generally easier than in the above case of encoding group numbers. However, if a unique order is assigned to each associative memory, the priority order of the other associative memories is set to the highest priority when it is desired to raise the priority of the newly added associative memories over the already used associative memories. It may be necessary to shift the position back and forth one by one, which may cause the corresponding register value to be rewritten. On the other hand, if the group registration register 115 is used as in the associative memory module 100, when adding a new associative memory to the same existing group, it is necessary to change the value of another register that has already been set. There is no.
[0032]
FIG. 2 is a circuit diagram showing an associative memory module group 200 according to another embodiment of the present invention, and shows a circuit configuration for performing a large-scale best match process.
[0033]
The associative memory module group 200 includes associative memory modules 200a, 200b, and 200c, a priority encoder 211, and a group registration register 215.
[0034]
The associative memory modules 200a, 200b, and 200c are associative memory modules similar to the associative memory module 100, respectively.
[0035]
The functions of the priority encoder 211 and the group registration register 215 are the same as the functions of the priority encoder 106 and the group registration register 115 shown in FIG.
[0036]
That is, the associative memory module group 200 performs mask processing on input data using mask data separately provided from the outside, takes out a bit string masked by the mask processing as a search key, and stores a plurality of pre-stored objects. One search according to a preset priority order from a plurality of associative memories that search for searched data that matches the search key from the search data, and a plurality of search results output from each of the plurality of associative memories. A first priority encoder for selecting a result, first priority order setting means capable of arbitrarily setting the priority order of data selection in the first priority encoder from the outside, and the input data as the above Given to each of the plurality of associative memories at the same time, A plurality of associative memory modules having simultaneous search execution means for executing a search, and a plurality of search results output from each of the plurality of associative memory modules, one search result according to a preset priority order A second priority encoder to be selected; and second priority order setting means capable of arbitrarily setting the priority order of data selection in the second priority encoder from the outside. This is a group of associative memory modules configured hierarchically.
[0037]
In the associative memory module group 200, input data (search key) 217 is simultaneously sent to each of the associative memory modules 200a, 200b, and 200c, and search processing is performed in parallel to obtain an entire search result 212. As shown in FIG. 2, when the associative memory modules 200a, 200b, and 200c are hierarchically configured (that is, when a plurality of associative memory modules 100 are hierarchically configured), compared to the case where only one associative memory module is used. Thus, it is possible to easily increase the scale without sacrificing the search time. That is, since the associative memory modules 200a, 200b, and 200c in the associative memory module group 200 perform the search process at the same time, the process is the same as the process of only one associative memory module, and the processing time of the priority encoder 211 only. It only takes extra.
[0038]
According to the associative memory module group 200, hardware that performs a larger-scale mast matching process can be easily realized by using the associative memory modules in a hierarchical manner.
[0039]
In addition, when the amount of data to be searched is large, the search result 212 is regarded as an address, and the final address 214 is obtained by adding the address to the address terminal of the semiconductor memory 213 provided separately outside. Good.
[0040]
In this way, it is possible to reduce the capacity of the associative memory itself mounted in the associative memory modules 200a, 200b, and 200c. That is, if information (information specifying an output port, information such as various parameters necessary for device setting) included in the searched data is stored in the associative memories 100a to 100d, the associative memory is correspondingly increased. Although the number of data to be searched that can be stored (entry) in 100a to 100d is reduced, information included in the data to be searched (information specifying the output port, various parameters necessary for setting the device, etc.) Information) is not stored in the associative memories 100a to 100d, but is stored in the semiconductor memory 213 provided outside the associative memory module group 200, and the final result 214 is output from the semiconductor memory 213. One search target data stored in the associative memory itself mounted on 200a, 200b, 200c It is possible to reduce the capacity.
[0041]
That is, a plurality of data to be searched are stored, an output signal of the associative memory module group 200 is regarded as an address, and the data to be searched corresponding to the address among the plurality of stored data to be searched is used as a final result. An external memory for output may be provided.
[0042]
Further, since the group registration register 215 is used in the associative memory module group 200, when adding a new associative memory to the same existing group, it is necessary to change the value of another register that has already been set. Absent.
[0043]
Further, each of the above-described embodiments is suitable for a purpose of performing the best match process used in the routing process for the Internet protocol (IP) at a high speed.
[0044]
【The invention's effect】
According to the present invention, when a plurality of conventional associative memories that can only mask input data uniformly are used, hardware that performs best match processing at high speed can be configured. There is an effect that it is possible to prevent an excess or deficiency of the associative memory capacity generated for each mask data.
[Brief description of the drawings]
FIG. 1 is a circuit diagram showing an associative memory module 100 according to an embodiment of the present invention.
FIG. 2 is a circuit diagram showing an associative memory module group 200 according to another embodiment of the present invention, showing a circuit configuration for performing a large-scale best match process;
[Explanation of symbols]
100 ... associative memory module,
100a, 100b, 100c, 100d ... associative memory,
Ra, Rb, Rc, Rd ... mask registers,
106: Priority encoder,
115 ... Group registration register,
117 ... input data,
118 ... Output data,
200 ... associative memory module group,
200a, 200b, 200c ... associative memory module,
211 ... Priority encoder,
215 ... Group registration register,
213: Semiconductor memory,
217 ... input data,
214 ... Output data.

Claims (3)

The input data is masked with mask data given from the outside, the bit string masked by the mask processing is extracted as a search key, and matches the search key from a plurality of pre-stored data to be searched. An associative memory comprising: a plurality of associative memories for retrieving data to be searched; and a priority encoder for selecting one search result from a plurality of search results output from each of the plurality of associative memories according to a preset priority order. In the memory module,
Priority order setting means capable of arbitrarily setting the priority order of data selection in the priority encoder from the outside;
Simultaneous search execution means for simultaneously applying the input data to each of the plurality of associative memories and causing each of the plurality of associative memories to execute a search simultaneously;
And the priority encoder selects one search result from the plurality of search results obtained by the simultaneous execution according to the set priority order , and the priority order setting means includes the associative memory module If there are N associative memories, N or less types of groups in which the priority order of selection by the priority encoder is determined are provided, and each of the plurality of associative memories belongs to any of the groups A group registration register indicating whether or not a predetermined associative memory of the plurality of associative memories is changed to a desired one of the N or less groups by changing the value of the group registration register. An associative memory module having means for registering in a group. The input data is masked with mask data given from the outside, the bit string masked by the mask processing is extracted as a search key, and matches the search key from a plurality of pre-stored data to be searched. A plurality of associative memories for retrieving data to be searched; a first priority encoder for selecting one search result from a plurality of search results output by each of the plurality of associative memories according to a preset priority order; In the associative memory module, the first priority order setting means capable of arbitrarily setting the priority order of data selection in the first priority encoder from the outside, and the input data to each of the plurality of associative memories Given simultaneously, search in each of the multiple associative memories at the same time A plurality of associative memory modules and a simultaneous retrieval execution means that;
A second priority encoder that selects one search result from a plurality of search results output from each of the plurality of associative memory modules according to a preset priority order;
Second priority order setting means capable of arbitrarily setting the priority order of data selection in the second priority encoder from the outside;
A group of associative memory modules, wherein the plurality of associative memory modules are hierarchically configured. In claim 2 ,
The plurality of data to be searched are stored, the output signal of the associative memory module group is regarded as an address, and the data to be searched corresponding to the address is output as a final result among the plurality of stored data to be searched An associative memory module group, comprising: an external memory that performs processing.

Images