JP2010049722A - Content addressable memory data error detecting device and content addressable memory data error detection method, and program - Google Patents

Abstract

An error in internal data of an associative memory (CAM) can be detected in real time during data search.
When registering data in a CAM, the same content data is registered in a storage medium. When the search key e is output from the control unit 21 during the data search, the error monitoring unit 22 sets the search key e in the internal register 23, and the CAM5 is an address where data having the same content as the search key e is registered. Is output as the search result f. The error monitoring unit 22 reads the data h from the storage medium 3 using the search result f as the read address g, and compares it with the search key e held in the register 23. If the comparison matches, it is determined that the data search has ended normally, and the search result f and the normal end notification i are output to the CPU 4. On the other hand, if the comparison does not match, it is determined that an error has occurred in the internal data of the CAM 5, and an abnormal termination notification j is output to the CPU 4.
[Selection] Figure 1

Description

  The present invention relates to an associative memory data error detection technique for detecting an internal data error in an associative memory.

  The content addressable memory (CAM) searches the internal data for data having the same pattern as the data input as a search key, and is registered in association with the physical address and the searched data as a search result. Output data.

  Such an associative memory is used, for example, to determine a transfer destination of a packet received by a packet switch device such as a router. In the packet switch device, for example, the associative memory is searched using the transmission destination address information of the packet as a search key, and the packet is transferred to the transfer destination according to the search result. Therefore, if there is an error in the search result output from the associative memory, or if there is an error in the internal data of the associative memory, the packet will be transferred to an illegal transfer destination, so error detection can be performed. Become important.

  Incidentally, an error in the search result output from the associative memory can be detected in real time by adding a parity bit to the search result, for example. However, internal data errors cannot be detected by this method. Even if a soft error such as bit inversion occurs in the internal data and internal data that is different from the internal data that should have been hit when the search key is input, there is no error in the output search results. Data errors cannot be detected.

  As a general method for detecting an internal data error in the associative memory, the internal data is periodically read from the associative memory and compared with the master data, or data with a parity bit added is registered in the associative memory. A method is known in which internal data is periodically read from an associative memory and a parity check is performed.

  In addition, a RAM in which data in which a check bit is added to data registered in the associative memory is registered is prepared, data in which the check bit is cyclically read from the RAM, error correction processing is performed, A technique is also known in which data after error correction processing is registered in an associative memory (see, for example, Patent Document 1).

JP 2005-353238 A

  According to the general method described above, it is possible to detect an error in the internal data of the associative memory. However, since the internal data error is detected by a process that is periodically performed differently from the search process, there is a problem that the internal data error cannot be detected in real time during the data search.

  Moreover, according to the technique described in Patent Document 1, the reliability of the internal data of the associative memory can be increased. However, the technique described in Patent Document 1 only writes error-corrected data to the associative memory by a process different from the search process. Cannot be detected.

(Object of invention)
Accordingly, an object of the present invention is to provide an associative memory data error detection device capable of detecting an internal data error in an associative memory in real time during data retrieval.

A first associative memory data error detection device according to the present invention includes:
A storage medium registered at an address related to a search result obtained when data having the same content as the collating unit in the data registered in the associative memory is input to the associative memory using the data as a search key;
By comparing the search key input to the associative memory at the time of data search with the data read from the address on the storage medium related to the search result of the associative memory for the search key, the internal data of the associative memory And an associative memory control circuit for detecting the error.

A first associative memory data error detection method according to the present invention includes:
A first step in which the computer registers the registration data at the registration destination address on the associative memory in accordance with a data registration instruction including registration data and a registration destination address;
The computer registers the data having the same content as the collation part in the registration data at an address on a storage medium associated with a search result obtained when the data is input to the associative memory as a search key. And the steps
The computer compares the retrieval key input to the associative memory at the time of data retrieval with the data read from the address on the storage medium associated with the retrieval result of the associative memory for the retrieval key. And a third step of detecting an error in the internal data of the memory.

The first program according to the present invention is:
Data having the same content as the collating unit in the data registered in the associative memory is provided with a storage medium registered at an address related to a search result obtained when the data is input to the associative memory as a search key. A program for causing a computer to function as an associative memory data error detection device,
The computer compares the search key input to the associative memory at the time of data search with the data read from the address on the storage medium associated with the search result of the associative memory for the search key. It functions as an associative memory control circuit that detects an error in the internal data of the memory.

  According to the present invention, it is possible to provide an associative memory data error detection device capable of detecting an internal data error of an associative memory in real time during data search.

  Next, the best mode for carrying out the present invention will be described in detail with reference to the drawings.

[First embodiment of the present invention]
Referring to FIG. 1, in the first embodiment of the present invention, a CAM data error detection device 1 is arranged between a CPU 4 on which a data search processing program operates and an associative memory (CAM) 5.

  The data search processing program operating on the CPU 4 has a function of issuing a data registration command and a data search command for the CAM 5 in order to perform data search using the CAM 5. The data registration command includes registration data and its registration destination address. The data search instruction includes a search key.

  As shown in FIG. 2A, in the CAM 5, data # 0 to # (N-1) are registered in the CAM address "0 to (N-1)", and the input search key and data area are stored. All the registered data # 0 to # (N-1) are collated instantaneously, and the address where the data matching the search key is registered is output as a search result. That is, the data registered in the data area of the CAM 5 is composed of a collation unit that is a collation target with the search key.

  The CAM data error detection device 1 includes a CAM control circuit 2 and a storage medium 3.

  The storage medium 3 is realized by NVRAM (Non Volatile RAM) or the like, and as shown in FIG. 2B, the data # 0 registered at the addresses “0 to (N−1)” of the CAM 5 is stored. Data # 0 to # (N-1) having the same contents as .about. # (N-1) are registered in storage medium addresses "0 to (N-1)", respectively.

  The CAM control circuit 2 includes a control unit 21 and an error monitoring unit 22 having a register 23.

  The control unit 21 decodes the instruction input from the CPU 4 and performs processing according to the decoding result. More specifically, when the data registration instruction a is input, the registration data b and the registration destination address c in the instruction a are output to the CAM 5 and the storage medium 3, and the registration process of the registration data b is performed. Make it. When the data search command d is input, the search key e in the command is output to the CAM 5 and the error monitoring unit 22 to cause the CAM 5 to perform search processing.

The error monitoring unit 22 has the following functions.
A function of setting the search key e output from the control unit 21 in the register 23.
A function of reading data h from the storage medium 3 using the search result (address) f output from the CAM 5 as a read address g.
The data h read from the storage medium 3 is compared with the search key e held in the register 23, and in the case of comparison match, the search result f from the CAM 5 and the normal end notification i are output to the CPU 4. And a function of outputting an abnormal termination notice j to the CPU 4 when the comparison does not match.

  The CAM control circuit 2 can be realized by a computer, and when realized by a computer, for example, as follows. A disk, a semiconductor memory, and other recording media on which a program for causing the computer to function as the CAM control circuit 2 is recorded are prepared, and the computer reads the program. The computer realizes the control unit 21 and the error monitoring unit 22 on its own computer by controlling its own operation according to the read program.

[Description of Operation of First Embodiment]
Next, the operation of the present embodiment will be described in detail. First, the operation at the time of data registration will be described with reference to the flowchart of FIG.

  At the time of data registration, the CPU 4 issues a data registration command a including registration data b and its registration destination address c (step S301).

  The control unit 21 decodes the data registration instruction a, first outputs the registration data b and the registration destination address c in the instruction a to the CAM 5, and writes the data b to the address c on the CAM 5 (step S302). . Thereafter, the registration data b and the registration destination address c are output to the storage medium 3, and the data b is registered at the address c on the storage medium 3 (step S303). Through the above processing, the same data is registered at the same address of the CAM 5 and the storage medium 3. When it is necessary to register data at a plurality of addresses of the CAM 5, the CPU 4 issues a data registration command for registering data at each address.

  Next, the operation at the time of data search will be described with reference to the flowchart of FIG.

  At the time of data search, the CPU 4 issues a data search command d including a search key e (step S401).

  The control unit 21 decodes the data search command d and outputs the search key e included in the command d to the CAM 5 and the error monitoring unit 22 (step S402). As a result, the error monitoring unit 22 sets the search key e in the register 23, and the CAM 5 starts the search process (step S402).

  Thereafter, when the CAM 5 outputs the address where the data matching the search key e is registered as the search result f (step S404), the error monitoring unit 22 inputs the search result f to the storage medium 3 as the read address g. Thus, the data h is read from the storage medium 3 and compared with the search key e held in the register 23 (steps S405 and S406).

  If the two match (YES in step S407), it is determined that the search process has ended normally, and the search result f output from the CAM 5 and the normal end notification i are sent to the CPU 4 that issued the data search instruction d. (Step S408).

  If there is no match (NO in step S407), it is determined that an error has occurred in the internal data of the CAM 5, and an abnormal termination notice j is output to the CPU 4 (step S409).

  Next, the operation when the internal data of the CAM 5 is normal will be described with reference to FIG.

  When the control unit 21 outputs “data # 1” as the search key e, the CAM 5 outputs the address “1” as the search result f. The error monitoring unit 22 holds the search key e (in this case, “data # 1”) in the internal register 23.

  When the address “1” is output as the search result f from the CAM 5, the error monitoring unit 22 reads “data # 1” from the address “1” of the storage medium 3, and the search key e held in the register 23. Compare. In this case, since “data # 1” is held in the register 23, the comparison results match and it is determined that the search processing has been completed normally.

  Next, an operation when an error has occurred in the internal data of the CAM 5 will be described with reference to FIG. In the following description, errors occur in the data “data # 1” and “data # 2” registered in the addresses “1” and “2” of the CAM 5, and “data # 1 ′” and “data # 1” respectively. Suppose that

  When the control unit 21 outputs “data # 1” as the search key e, the CAM 5 outputs “address # 2” as the search result f because “data # 1” is registered in the address “2”. This address “2” is different from the address “1” that is output when there is no error in the internal data of the CAM 5. The error monitoring unit 22 holds “data # 1” in the internal register 23 as the search key e.

  When the address “2” is output as the search result f from the CAM 5, the error monitoring unit 22 reads “data # 2” from the address “2” of the storage medium 3, and the search key e held in the register 23. Compare. In this case, since “data # 1” is held in the register 23, a comparison mismatch occurs and it is detected that an error has occurred in the internal data of the CAM 5.

[Effect of the first embodiment]
According to the present embodiment, it is possible to obtain an effect that an error in internal data of the CAM 5 can be detected in real time during data search. The reason is that a storage medium 3 having the same content as that of the CAM 5 is prepared, and at the time of data search, it corresponds to the search result output from the CAM 5 (in this embodiment, the address where the same data as the search key is registered). This is because the data registered at the address on the storage medium 3 is compared with the search key.

  In the present embodiment, the registration data b is sent to the registration destination address c on the CAM 5 and the registration destination address c on the storage medium 3 according to the data registration command a including the registration data b and the registration destination address c. Since the registration control unit 21 is provided, it is possible to obtain an effect that data can be registered in the CAM 5 and the storage medium 3 only by inputting one data registration command a.

[Second Embodiment of the Present Invention]
Next, a second embodiment of the present invention will be described. In the first embodiment, after confirming the normality of the search result output from the CAM, the search result is notified to the CPU. However, in this embodiment, the search result of the CAM is quickly displayed. In order to be able to notify the CPU, the search result output from the CAM is immediately notified to the CPU, and the normality is confirmed later.

  Referring to FIG. 7, the CAM data error detection device 1 a according to the present embodiment includes a CAM control circuit 2 a instead of the CAM control circuit 2. The CAM according to the first embodiment shown in FIG. This is different from the data error detection device 1.

  The CAM control circuit 2a of the present embodiment is that the search result duplicating unit 24 is added and that the error monitoring unit 22a is provided instead of the error monitoring unit 22 in the CAM control of the first embodiment. This is different from the circuit 2.

  The search result duplicating unit 24 outputs the search result f output from the CAM 5 to the CPU 4 and the error monitoring unit 22a.

  The error monitoring unit 22a compares the search key e held in the register 23 with the data h read from the storage medium 3, and outputs a normal end notification i to the CPU 4 if the comparison coincides. If they do not match, an abnormal termination notice j is output to the CPU 4.

  Note that the CAM control circuit 2a of the present embodiment can also be realized by a computer.

  Next, the operation of the present embodiment will be described. Since the operation at the time of data registration is the same as that of the first embodiment, only the operation at the time of data search will be described here with reference to FIG.

  When the CPU 4 issues a data search instruction d (step S801), in steps S802 to S804, the same processing as in steps S402 to S404 in FIG. 4 described above is performed, and the search result f (data matching the search key is received from the CAM 5). Registered address) is output.

  As a result, the search result duplicating unit 24 outputs the search result f to the CPU 4 and the error monitoring unit 22a (step S805). As described above, in this embodiment, the search result f output from the CAM 5 is immediately output to the CPU 4, so that the search result f of the CAM 5 can be quickly transmitted to the CPU 4.

  Thereafter, the error monitoring unit 22a inputs the search result f to the storage medium 3 as the read address g, thereby reading the data h from the storage medium 3 and comparing it with the search key e held in the register 23 (step S807). ). If they match (YES in step S808), it is determined that the search process has been completed normally, and a normal termination notification i is output to the CPU 4 (step S809). On the other hand, if they do not match (NO in step S808), it is determined that an error has occurred in the internal data of the CAM 5, and an abnormal termination notice j is output to the CPU 4.

[Effects of Second Embodiment]
According to the present embodiment, in addition to the effect obtained in the first embodiment, it is possible to obtain an effect that it is possible to quickly notify the search result of the CAM 5 to the CPU 4. The reason is that the search result f of the CAM 5 is immediately notified to the CPU 4 by using the search result duplicating unit 24, and the error detection process in the error monitoring unit 22a using the search result f is performed later.

[Other Embodiments of the Invention]
Although not described in the first and second embodiments described above, a TCAM (Ternary CAM: ternary associative memory) that can use the Don't Care bit can also be used. In this case, when comparing the search key e and the data h read from the storage medium 3 in the error monitoring units 22 and 22a, bit comparison other than the Don't Care bit may be performed.

  In the first and second embodiments described above, the CAM 5 that outputs, as a search result, an address where data matching the input search key is registered is used. As shown in FIG. Are registered with the addresses 0 to (N-1) and the data composed of the collation parts # 0 to # (N-1) and the search result parts # 0 to # (N-1) are entered. In such a case, it is possible to use the CAM 5a that outputs a search result part in the data whose collation part matches the search key as a search result. In this case, a storage medium 3a as shown in FIG. 9B is used instead of the storage medium 3. That is, a search obtained when data having the same content as the collation units # 0 to # (N-1) registered in the CAM 5a (collation units # 0 to # (N-1)) is input to the CAM 5a. The storage medium 3a registered at the address related to the result (search result part # 0 to # (N-1)) is used. As an address related to the search result, for example, a hash value of the search result can be used. Further, with the use of the storage medium 3a as shown in FIG. 9B, it is necessary to change the processing in step S303 in FIG. 3, step S405 in FIG. 4, and step S806 in FIG.

  That is, in step S303 of FIG. 3, a hash value for the search result part in the data instructed by the data registration command (consisting of the collation part and the search result part) is obtained, and the hash on the storage medium 3a is obtained. The contents of the collation part in the data are written to the address corresponding to the value.

  In step S405 in FIG. 4 and step S806 in FIG. 8, a hash value for the search result output from the CAM 5a is obtained, and data is read from an address corresponding to the hash value on the storage medium 3a.

  In addition, although not described in the first and second embodiments described above, when the number of miss hits per unit time (the number of times data that matches the search key could not be searched) is equal to or greater than a predetermined number of times, Data registered in the CAM 5 and master data may be compared to detect data in which an error has occurred.

  The present invention is suitable for use in a pattern switching device such as a router using an associative memory.

It is a block diagram which shows the structural example of the 1st Embodiment of this invention. 3 is a diagram illustrating an example of contents of a CAM 5 and a storage medium 3. FIG. It is a flowchart which shows the process example at the time of data registration. It is a flowchart which shows the process example at the time of a data search. It is a figure for demonstrating the operation | movement at the time of the data search when the error has not generate | occur | produced in the internal data of CAM5. It is a figure for demonstrating the operation | movement at the time of the data search in case the error has generate | occur | produced in the internal data of CAM5. It is a block diagram which shows the structural example of the 2nd Embodiment of this invention. It is a flowchart which shows the example of a process at the time of the data search in 2nd Embodiment. It is a figure which shows the example of the content of CAM5a and the storage medium 3a.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1, 1a ... CAM data error detection apparatus 2, 2a ... CAM control circuit 21 ... Control part 22, 22a ... Error monitoring part 23 ... Register 24 ... Search result duplication part 3, 3a ... Storage medium 4 ... CPU
5, 5a ... CAM

Claims (15)

A storage medium registered at an address related to a search result obtained when data having the same content as the collating unit in the data registered in the associative memory is input to the associative memory using the data as a search key;
By comparing the search key input to the associative memory at the time of data search with the data read from the address on the storage medium related to the search result of the associative memory for the search key, the internal data of the associative memory And an associative memory control circuit for detecting an error in the associative memory. The associative memory data error detection device according to claim 1,
The associative memory control circuit compares the search key and data read from the storage medium and determines that they match, and then outputs the search result of the associative memory to the issuer of the search key. An associative memory data error detection device. The associative memory data error detection device according to claim 1,
The associative memory control circuit outputs a search result of the associative memory to the issuer of the search key before comparing the search key with data read from the storage medium. Detection device. The associative memory data error detection device according to claim 1 or 2,
The associative memory control circuit includes:
A register for holding the search key input to the associative memory at the time of data search;
Data is read from the address on the storage medium related to the search result of the associative memory with respect to the search key, and the read data is compared with the search key held in the register. An associative memory data error comprising: an error monitoring unit that outputs a search result of the associative memory to a key issuer and outputs an abnormal end notification to the issuer in the case of a comparison mismatch Detection device. The associative memory data error detection device according to claim 1 or 3,
The associative memory control circuit includes:
A register for holding the search key input to the associative memory at the time of data search;
A search result duplicating unit that outputs a search result of the associative memory for the search key to an issuer of the search key;
Data is read from the address on the storage medium related to the search result of the associative memory with respect to the search key, and the read data is compared with the search key held in the register. An associative memory data error detection device comprising: an error monitoring unit that outputs a normal end notification to a key issuer and outputs an abnormal end notification to the issuer in case of a comparison mismatch. The associative memory data error detection device according to any one of claims 1 to 5,
A search result obtained when a search key is input to the associative memory is an address on the associative memory in which data in which the content of the matching unit matches the search key is registered,
An associative memory data error detection device, wherein an address associated with a search result of the associative memory is an address output as a search result from the associative memory. The associative memory data error detection device according to any one of claims 1 to 5,
The search result obtained when a search key is input to the associative memory is a predetermined portion in the data in which the content of the matching unit matches the search key,
An associative memory data error detection device, wherein an address associated with a search result of the associative memory is a hash value of the predetermined portion. The associative memory data error detection device according to claim 6,
The associative memory control circuit includes:
When a data registration command including registration data in the associative memory and a registration destination address is input, the registration data is registered in the registration destination address on the associative memory and the registration destination address on the storage medium is registered. An associative memory data error detection device comprising a control unit for writing the registration data. The associative memory data error detection device according to claim 7,
The associative memory control circuit includes:
When a data registration command including registration data to the associative memory and a registration destination address is input, the registration data is registered at the registration destination address on the associative memory and the verification unit in the registration data An associative memory data error detection apparatus comprising: a control unit that registers the registration data at an address on the storage medium obtained by executing a predetermined calculation. A first step in which the computer registers the registration data at the registration destination address on the associative memory according to a data registration instruction including registration data and a registration destination address;
The computer registers the data having the same content as the collation part in the registration data at an address on a storage medium associated with a search result obtained when the data is input to the associative memory as a search key. And the steps
The computer compares the retrieval key input to the associative memory at the time of data retrieval with the data read from the address on the storage medium associated with the retrieval result of the associative memory for the retrieval key. And a third step of detecting an error in the internal data of the memory. The content addressable memory data error detection method according to claim 10,
In the third step, the search key and data read from the storage medium are compared to determine that they match, and then the search result of the associative memory is output to the issuer of the search key. Associative memory data error detection method. The associative memory data error detection method according to claim 10,
In the third step, before associating the search key with the data read from the storage medium, the search result of the associative memory is output to the issuer of the search key. Detection method. Data having the same content as the collating unit in the data registered in the associative memory is provided with a storage medium registered at an address related to a search result obtained when the data is input to the associative memory as a search key. A program for causing a computer to function as an associative memory data error detection device,
The computer compares the search key input to the associative memory at the time of data search with the data read from the address on the storage medium associated with the search result of the associative memory for the search key. A program for functioning as an associative memory control circuit that detects errors in internal data in the memory. The program according to claim 13, wherein
The associative memory control circuit compares the search key and data read from the storage medium and determines that they match, and then outputs the search result of the associative memory to the issuer of the search key. Program. The program according to claim 13, wherein
The associative memory control circuit outputs a search result of the associative memory to a source of the search key before comparing the search key with data read from the storage medium.

Images