JP4343377B2 - Associative memory - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an associative memory that realizes the functions of a plurality of associative memories having different configurations with one device.
[0002]
[Prior art]
In recent years, with the development of the Internet, for example, high speed and high functionality have been required for relay apparatuses that construct networks such as switching hubs and routers. In order to respond to such a request, in these devices, for example, content addressable memory (CAM) has been frequently used for processing such as address filtering and packet classification (classification). .
[0003]
CAM is often used in each of layers 2, 3, and 4 of an OSI (Open Systems Interconnection) model of a network. In this case, the length of the search key data varies from 32 to 256 bits or more, and as a CAM function, a conventional binary CAM configuration having only “0” and “1” data is sufficient. Some of them require a function of a ternary CAM configuration having “X (Don't care)” data.
[0004]
Accordingly, as shown in FIG. 12A, devices having different configurations suitable for the functions required in layers 2 to 4, respectively, in the example shown, a 64-bit binary CAM, a 64-bit ternary CAM, A 256-bit ternary CAM is used, or a binary CAM function is substituted for a ternary CAM function, as shown in FIG. This is implemented using three ternary CAMs of bits.
[0005]
In the example of FIG. 12 (a), each process can be pipelined because CAMs adapted to the respective functions are used. However, in the figure, the network function blocks that control each CAM are few or one-chip LSIs. If configured, an increase in signal pins to the CAM becomes a problem. In recent years, a large-capacity CAM has been mainstream, and a CAM with a small memory capacity has not been manufactured. Therefore, there has been a problem that a large-capacity CAM has to be mounted as shown in FIG. .
[0006]
Further, in the example of FIG. 7B, in order to satisfy all with a multi-bit CAM, for example, when a 64-bit table is realized with a 128-bit CAM, as shown in FIG. Data is divided and registered on the MSB (most significant bit) side and LSB (least significant bit) side, the LSB side is masked to search the MSB side, and conversely, the MSB side is masked to search the LSB side. External processing is required to obtain Therefore, there is a problem that the external circuit becomes complicated.
[0007]
[Problems to be solved by the invention]
An object of the present invention is to provide an associative memory which is free from cost and easy to control in a system which uses a plurality of associative memories having different configurations and solves the problems based on the prior art.
[0008]
[Means for Solving the Problems]
To achieve the above object, the present invention provides an associative memory array that is divided into a plurality of physical banks and each of the physical banks can be set to a different configuration.
Set the configuration of each physical bank, set the configuration of each logical bank corresponding to this, assign the correspondence between each logical bank and each physical bank, and control each physical bank Logical / physical signal conversion circuit
A priority circuit that searches the physical bank corresponding to the logical bank and sequentially outputs search results output from the physical banks in accordance with preset priorities. Realize functions of multiple associative memories with different configurations on a single device An associative memory characterized by the above is provided.
Here, it is preferable that the logical / physical signal conversion circuit includes a register which is provided corresponding to each of the physical banks and which is set from the outside and defines the configuration of the corresponding physical bank.
The logical / physical signal conversion circuit preferably includes a logical / physical conversion table in which one or a plurality of allocations of the physical banks to the respective logical banks are set by a signal input from the outside.
Further, the logical / physical signal conversion circuit receives an input of a signal designating one of the logical banks and a signal instructing start of a search, and receives one or a plurality of signals associated with the one logical bank. It is preferable to output a signal instructing the start of the search only to the physical bank.
The priority circuit preferably outputs a search result output from the physical bank by adding a bit indicating the corresponding physical bank.
[0009]
DETAILED DESCRIPTION OF THE INVENTION
The content addressable memory of the present invention will be described below in detail with reference to the preferred embodiments shown in the accompanying drawings.
[0010]
FIG. 1 is a schematic configuration diagram of an embodiment of an associative memory according to the present invention.
The content addressable memory (hereinafter referred to as CAM) 10 of the present invention can realize the functions of a plurality of CAMs having different configurations having different types of binary CAM / ternary CAM and different bit lengths in one device. As shown in the figure, the content addressable memory array 12, the logical / physical signal conversion circuit 14, the priority circuit 16, and the decoder 18 are provided.
[0011]
First, the associative memory array 12 is composed of a plurality of physical banks divided into blocks. In the illustrated example, the associative memory array 12 is divided into eight blocks of physical banks 0 to 7. The configuration of each physical bank can be set as a binary CAM or a tertiary CAM according to the signal CONFIG input from the logical / physical signal conversion circuit 14, and a plurality of types prepared in advance. The bit length can be set to an arbitrary bit length.
[0012]
Subsequently, the logical / physical signal conversion circuit 14 sets the configuration of each physical bank of the associative memory array 12 according to the required configuration of the CAM, and sets the configuration of each logical bank correspondingly. By assigning a correspondence relationship between each logical bank and each physical bank of the associative memory array 12, the physical bank of the associative memory array 12 corresponding to each logical bank is correctly accessed. Each physical bank of the associative memory array 12 is controlled.
[0013]
Here, the signal IN <63: 0>, the signal LBANK <2: 0>, the signal SEARCH, the signal GENFUL, the signal PURGE_HIT, and the signal TABLE_WR are input to the logical / physical signal conversion circuit 14. The logic / physical signal conversion circuit 14 outputs a signal SRCH, a signal GNFL, a signal PRG_HIT, and a signal CONFIG <2: 0> to each physical bank of the associative memory array 12.
[0014]
In the associative memory array 12, in addition to each signal input from the logical / physical signal conversion circuit 14, the upper 3 bits of the signal RD, the signal RD generated by the signal WRITE, the signal WR, and the ADDRESS <14: 0> A signal ADDRESS <11: 0> and a signal DATIN <63: 0> generated from the ADDRESS <14:12> by the decoding circuit 18 are input, and the associative memory array 12 sends a signal HHA < 11: 0>, signal HEA <11: 0>, signal HIT, and signal FULL are output. The associative memory array 12 also outputs a signal DATOUT <63: 0>.
[0015]
Finally, the priority circuit 16 adds the upper 3 bits of the address to the signal HHA <11: 0> and the signal HEA <11: 0> input from the associative memory array 12 in accordance with a preset priority order. HHA <14: 0> and signal HEA <14: 0> are sequentially output. In this embodiment, it is assumed that the priority of the physical bank 0 of the associative memory array 12 is the highest, the priority is subsequently lowered, and the priority of the physical bank 7 is the lowest. The priority circuit 16 also outputs a signal HIT and a signal FULL.
[0016]
In the present invention, a physical bank is each block when the associative memory array 12 is physically divided into a plurality of blocks. On the other hand, a logical bank is a logically allocated memory space of a physical bank, and a plurality of physical banks can be connected as needed and used as one memory space. With this logical bank concept, the memory space of the logical bank can be used without being conscious of the memory space of each physical bank.
[0017]
For example, as shown in FIG. 2, the physical bank 0 is set to an A-bit binary CAM, and similarly, the physical bank 1 is a B-bit binary CAM, the physical bank 2 is a C-bit binary CAM, Bank 3 is an A-bit ternary CAM, physical bank 4 is a B-bit ternary CAM, physical bank 5 is a C-bit ternary CAM, physical bank 6 is an A-bit binary CAM, and physical bank 7 is B-bit long Set as the ternary CAM.
[0018]
Then, as shown in FIG. 3, an A-bit binary CAM obtained by concatenating physical banks 0 and 6 is assigned to logical bank 0. Similarly, B of physical banks 1 to 3 is assigned to logical banks 1 to 3, respectively. A bit length binary CAM, a C bit length binary CAM, and an A bit length ternary CAM are allocated. Further, a B-bit ternary CAM obtained by connecting the physical banks 4 and 7 is allocated to the logical bank 4, and a C-bit ternary CAM of the physical bank 5 is allocated to the logical bank 5.
[0019]
In the CAM 10 of the present invention, as shown in FIG. 2, depending on the required associative memory configuration, that is, the type of CAM used as a binary CAM or a ternary CAM, and the required bit length, The configuration of each physical bank of the associative memory array 12 is determined, and according to the required number of words, a plurality of physical banks are connected to form each logical bank as shown in FIG. A plurality of different CAM functions can be realized by one device.
[0020]
Hereinafter, the operation of the CAM 10 of the present invention will be described in detail with reference to the embodiments shown in FIGS.
[0021]
First, FIG. 4 is a conceptual diagram of an embodiment showing the correspondence between each logical bank and each physical bank in the CAM 10 of FIG. In the case of the present embodiment, as shown in the figure, the physical banks 0, 2, 6 are set as 64-bit binary CAM, and similarly, the physical banks 1, 3, 4 are 128-bit ternary CAM, The physical banks 5 and 7 are set as a 256-bit ternary CAM. Details of each physical bank will be described later.
[0022]
Here, the configuration of each physical bank is set by the signal CONFIG <2: 0> output from the logical / physical signal conversion circuit 14 to each physical bank, as described above. This signal CONFIG <2: 0> is defined by, for example, 3 bits × 8 registers (not shown) in the logic / physical signal conversion circuit 14, and each register gives a signal TABLE_WR. It is set from outside the CAM 10.
[0023]
Further, in the illustrated example, the logical bank 0 is obtained by concatenating the physical banks 0, 2 and 6 with a 64-bit length, 12K word binary CAM, and the logical bank 1 is obtained by concatenating the physical banks 1, 3 and 4. A 128-bit long, 6K-word ternary CAM, and a 256-bit long 2K-word ternary CAM obtained by concatenating the physical banks 5 and 7 to the logical bank 2 are allocated. The correspondence relationship between each logical bank and each physical bank in FIG. 4 is shown in the table of FIG.
[0024]
The designation of the logical bank is performed by signals LBANK <2: 0>. The correspondence relationship between the logical bank and the physical bank is defined by, for example, a logical / physical conversion table in the logical / physical signal conversion circuit 14 as shown in FIG. This logical-physical conversion table corresponds to the correspondence table between each logical bank and each physical bank shown in FIG. 5, and is assigned to “Assign (assigned)” and “No Assign” (not assigned) in FIG. Corresponding to “1” and “0”, respectively.
[0025]
In this logical-physical conversion table, a value input from the signal IN <63: 0> is set in FIG. 7 so as to represent the correspondence relationship by giving the signal TABLE_WR. Based on the correspondence relationship between each logical bank and each physical bank, eight registers that define the signal CONFIG <2: 0> and the logical-physical conversion table of FIG. of By setting the contents, when a logical bank is designated by the signal LBANK <2: 0>, a physical bank corresponding to the logical bank can be controlled.
[0026]
Next, FIG. 8 is a conceptual diagram of an embodiment showing signals connected to a physical bank. This figure shows a physical bank of the content addressable memory array 12 of the CAM 10 shown in FIG. , ADDRESS <11: 0>, HHA <11: 0>, HEA <11: 0>, HIT, FULL, and DATOUT <63: 0>.
[0027]
First, CONFIG <2: 0> is a signal for setting the physical bank configuration of the associative memory array 12. In this embodiment, as shown in the table of FIG. 9, the difference in the type of CAM whether the physical bank is used as a binary CAM or a ternary CAM, and the bit length is 64, 128, 256 bits. Depending on the difference in whether or not, the functional configuration of each physical bank can be designated from among six types by a 3-bit signal.
[0028]
Next, ADDRESS <11: 0> is an input signal for designating the memory address of this physical bank.
DATIN <63: 0> is an input signal for entry data and search key data for this physical bank.
DATOUT <63: 0> is an output signal obtained by reading entry data stored in the physical bank.
[0029]
WRITE is an input signal for writing a 64-bit signal input as DATAIN <63: 0> to a memory address specified by ADDRESS <11: 0>.
READ is an input signal for reading out the entry data stored in the memory address of the physical bank specified by ADDRESS <11: 0> as DATOUT <63: 0>.
[0030]
SRCH is an input signal that instructs the physical bank to start searching.
HIT is an output signal indicating whether or not there is a hit entry, that is, entry data that matches the search key data in this physical bank as a result of the match search. In this embodiment, the HIT is at a low level when there is even one hit entry in the entry data, and is at a high level only when there is no hit entry.
[0031]
HHA <11: 0> is an output signal of the highest priority hit address. As HHA <11: 0>, as a result of matching search, when the above-mentioned HIT becomes low level and there is a hit entry, the memory address storing the hit entry with the highest priority, that is, the highest priority The hit address is output. In this embodiment, the smallest address among the hit addresses is output.
[0032]
PRG_HIT is an input signal for erasing the hit entry when the HIT becomes low level as a result of the match search and there is a hit entry in this physical bank.
GNFL is an input signal for searching for the highest priority empty address (HEA) in the physical bank. By inputting this GNFL, HEA <11: 0> is output.
[0033]
As a result of inputting the above-described GNFL to this physical bank, FULL indicates whether or not there is an empty entry in this physical bank, that is, a memory address in which valid entry data to be searched for matching is not stored. It is an output signal for representing. In the present embodiment, FULL is low level only when there is no empty entry, and is high level when at least one empty entry exists.
[0034]
Finally, HEA <11: 0> is an output signal of the above-mentioned highest priority empty address. As HEA <11: 0>, when GNFL is input and FULL becomes high level and there is an empty entry in the physical bank, the memory address at which the empty entry with the highest priority is stored, that is, This is the output signal of the highest priority empty address. In this embodiment, the smallest address among the empty addresses is output.
[0035]
The physical bank in the illustrated example is a block of an associative memory array having a ternary CAM configuration having a physical length of 64 bits, 4K words, and a memory capacity of 256K bits. For example, if this physical bank is set as a 128-bit binary CAM, two matching searches are performed using different 64-bit search key data, and the AND of the search results is taken as a final search result. Is output. As a result, it apparently operates as a 128-bit CAM.
[0036]
In this case, the number of words in the physical bank is apparently half of 2K words. Therefore, when a CAM of 128 bits length and 4K words is required, two physical banks are connected and used as one logical bank. The ternary CAM can be used as a binary CAM by appropriately setting the “X (Don't Care)” data of the ternary CAM. In the case of a 256-bit CAM, a total of four AND searches are performed.
[0037]
In the CAM 10 shown in FIG. 1, the signal CONFIG <2: 0>, the signal SRCH, the signal GNFL, the signal PRG_HIT, the signal WR, the signal RD, the signal DATIN <63: 0>, the signal ADDRESS <11: 0>, and the signal HHA <11. : 0>, signal HEA <11: 0>, signal HIT, signal FULL, and signal DATOUT <63: 0> are signals corresponding to the signals connected to the physical bank shown in FIG.
[0038]
The signal SRCH, the signal GNFL, and the signal PRG_HIT are logical products of the signal SEARCH, the signal GENFUL, and the signal PURGE_HIT that are input to the logical / physical signal conversion circuit 14 and the output from the logical physical conversion table of FIG. Thus, this signal is output only to a logical bank designated by the signal LBANK <2: 0> and a physical bank for which “1” is set in the logical-physical conversion table.
[0039]
In the CAM 10 shown in FIG. 1, first, before performing a match search, entry data is written to each physical memory of the associative memory array 12 corresponding to each logical bank. The entry data is supplied with the signal WRITE, so that the signal DATIN <63: 0 with respect to the memory address of the logical bank designated by the signal ADDRESS <14: 0>, that is, the memory address of the physical bank corresponding to this logical bank. > Is written.
[0040]
As an example, when a match search is performed on a 128-bit ternary CAM in the logical bank 1, first, the logical bank 1 is designated as a signal LBANK <2: 0> = '001 (binary number)'. By this designation, the setting of physical bank assignment of the row corresponding to the logical bank 1 of the logical-physical conversion table of FIG. 6 = '01011000' is output, and the signal SRCH, Signal GNFL and signal PRG_HIT are applied.
[0041]
For example, when the search key data is input as DATIN <63: 0> and the signal SEARCH is input to start the search, the logical / physical signal conversion circuit 14 applies to the physical banks 1, 3, and 4. Only the signal SRCH is given, and the matching search is started only in these physical banks 1, 3 and 4. Since the logical bank 1 is a 128-bit ternary CAM, as described above, two AND searches are performed using different 64-bit search key data.
[0042]
As a result, if there is a hit entry that matches the search key data with a total length of 128 bits among the entry data registered in these physical banks 1, 3 and 4, the signal HIT goes low, and the corresponding physical data Signals HHA <11: 0>, which are hit addresses in which hit entries are registered, are output from the banks 1, 3 and 4, and these signals HIT and HHA <11: 0> are input to the priority circuit 16. .
[0043]
As a result of the match search, the physical bank 1, 3, 4 that does not have a hit entry and the physical bank 0, 2, 5 to 7 that is not given the signal SRCH are high as the signal HIT. The level is output.
In the priority circuit 16, the priority is determined by the signal HIT input from each physical bank, and the highest priority signal HHA <11: 0> is added with the top 3 bits of the physical bank having the highest priority. Signal HHA <14: 0> is output. For example, if the physical bank having the highest priority is “5”, the added 3 bits are “101”. In addition, a signal HIT is also output.
[0044]
In this embodiment, as shown in the table of FIG. 10, the lower the physical bank number, the higher the priority, and for example, when there is a hit entry in the physical bank 1, regardless of the state of the physical banks 3 and 4 The priority circuit 16 outputs the signal HHA <11: 0> of the physical bank 1 and HHA <14:12> becomes “001”. The signal HIT is the logical product of the signals HIT input from the respective physical banks 0 to 7. If the hit entry exists in any of the physical banks 0 to 7, the signal HIT becomes low level.
[0045]
Similarly, when searching for an empty address, if the logical bank 1 is designated, the signal GNFL is given from the logical / physical signal conversion circuit 14 only to the corresponding physical banks 1, 3 and 4. When the search for the empty address is started by inputting the signal GENFUL, as described above, the signal GNFL is given only to the physical banks 1, 3 and 4, and the empty address of these physical banks 1, 3 and 4 is supplied. The search is started.
[0046]
As a result, the signal FULL of the physical banks 1, 3, and 4 in which the empty address exists is at a high level, and the signal HEA <11: 0> that is an empty address is output from the corresponding physical bank 1, 3, and 4. As a result of the search for the empty address, the physical bank 1, 3, 4 does not have an empty address, and the physical bank 0, 2, 5 to 7 to which the signal GNFL is not given, Is output as a low level.
[0047]
In the priority circuit 16, the priority is determined by the signal FULL input from each physical bank, and the highest priority signal HEA <11: 0> has the highest priority according to the priority shown in the table of FIG. A signal HEA <14: 0> with the bank number 3 bits added to the upper part is output. In addition, a signal FULL is also output. The signal FULL is the logical sum of the signals FULL input from the respective physical banks 0 to 7, and becomes a high level if any of the physical banks 0 to 7 has an empty address.
[0048]
As described above, the CAM 10 of the present invention divides the large-capacity associative memory array 12 into a plurality of physical bank blocks and reconfigures these physical banks as logical banks. It can be divided and used according to. Further, since the search operation is performed by dividing the large-capacity associative memory array 12, that is, the search operation is performed only on the physical bank corresponding to the logical bank, power consumption can be reduced.
[0049]
In the illustrated example, the case where the associative memory array 12 is divided into eight physical banks is described as an example. However, the present invention is not limited to this, and may be divided into two or more physical banks. In the embodiment, the settable bit lengths are three types of 64, 128, and 256 bits, but this is not limited. In addition, as shown in FIG. 11, the setting of the physical bank configuration and the setting of the correspondence relationship between the logical bank and the physical bank can be freely set without any limitation.
[0050]
Further, in the above-described embodiment, two types of CAM type and bit length, which are binary CAM or ternary CAM, are described as elements that determine the configuration of the physical bank. However, the present invention is not limited to this, and for example, other functional differences may be selected as elements that determine the configuration of the physical bank. Further, the present invention only needs to include at least one element as an element for determining the configuration of the physical bank.
[0051]
Further, in the above embodiment, specific configuration circuits of the associative memory array 12, the logical / physical signal conversion circuit 14, the priority circuit 16, and the decoder 18 are not shown, but in the present invention, these specific circuit configurations are shown. Is not limited at all, and any configuration may be used as long as the circuit realizes the above-described function. In particular, the case where the logical / physical signal conversion circuit 14 is configured using a register or a table is illustrated, but the present invention is not limited to this, and may be configured using another circuit.
[0052]
The content addressable memory of the present invention is basically as described above.
The content addressable memory of the present invention has been described in detail above. However, the present invention is not limited to the above-described embodiments, and various improvements and modifications may be made without departing from the spirit of the present invention. .
[0053]
【The invention's effect】
As described in detail above, the associative memory of the present invention divides a large-capacity associative memory array into a plurality of physical bank blocks, and each of these physical banks can be set to different configurations. The physical bank is reconfigured and used as a logical bank.
Thus, according to the associative memory of the present invention, a large-scale associative memory can be divided and used according to usage, and the functions of a plurality of associative memories having different configurations can be realized by one device. Therefore, cost can be reduced. Further, according to the associative memory of the present invention, it is not necessary to be aware of the memory space of the physical bank due to the concept of the logical bank, so that there is an advantage that the control is easy. Further, according to the associative memory of the present invention, the search operation is performed only on the physical bank corresponding to the logical bank. Therefore, the power consumption which is always a problem in the associative memory in which all the associative memory cells operate simultaneously is reduced. be able to.
[Brief description of the drawings]
FIG. 1 is a schematic configuration diagram of an embodiment of an associative memory according to the present invention.
FIG. 2 is a conceptual diagram of an embodiment showing a state in which the configuration of each physical bank is set.
FIG. 3 is a conceptual diagram of an embodiment showing a state in which a correspondence relationship between each logical bank and each physical bank is assigned.
FIG. 4 is a conceptual diagram of an embodiment showing a correspondence relationship between each logical bank and each physical bank.
FIG. 5 is a table showing an example of a correspondence relationship between each logical bank and each physical bank.
FIG. 6 is a table showing an example of a correspondence relationship between each logical bank and each physical bank.
FIG. 7 is a table of an example showing a relationship between the table of FIG. 8 and each bit of the signal IN <63: 0>.
FIG. 8 is a conceptual diagram of an embodiment showing signals connected to a physical bank.
FIG. 9 is a table showing an example of the correspondence between signals CONFIG <2: 0> and the configuration of the physical bank of the associative memory array;
FIG. 10 is a table showing an example of priorities among physical banks.
FIG. 11 is a conceptual diagram of another embodiment showing a correspondence relationship between each logical bank and each physical bank.
FIGS. 12A and 12B are schematic configuration diagrams of an example of a system using a conventional associative memory. FIGS.
FIG. 13 is a schematic configuration diagram of an example of a system using a conventional associative memory.
[Explanation of symbols]
10 Associative memory
12 Associative memory array
14 logic / physical signal conversion circuit
16 priority circuit
18 Decoder

Claims (5)

An associative memory array divided into a plurality of physical banks and configured so that each of the physical banks can be set to a different configuration;
Set the configuration of each physical bank, set the configuration of each logical bank corresponding to this, assign the correspondence between each logical bank and each physical bank, and control each physical bank Logical / physical signal conversion circuit
Perform a search against the physical bank corresponding to the logical bank, search result output from each of the physical bank, and a priority circuit that sequentially outputs according to the order that is set in advance, different configurations plurality of An associative memory characterized by realizing the function of the associative memory in one device .   2. The associative memory according to claim 1, wherein the logical / physical signal conversion circuit includes a register which is provided corresponding to each of the physical banks and which is set from the outside and defines a configuration of the corresponding physical bank. .   The logical-physical signal conversion circuit includes a logical-physical conversion table in which one or a plurality of allocations of the physical bank to each logical bank is set by a signal input from the outside. The associative memory according to 1 or 2.   The logical / physical signal conversion circuit receives an input of a signal for designating one of the logical banks and a signal for instructing the start of a search, and one or a plurality of physical banks associated with the one logical bank 4. The associative memory according to claim 1, wherein a signal for instructing the start of the search is output only.   5. The content addressable memory according to claim 1, wherein the priority circuit outputs a search result output from the physical bank by adding a bit indicating the corresponding physical bank.

Images