JP3766166B2 - Associative memory device - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an associative memory device capable of high-speed operation while minimizing the interface with the outside.
[0002]
[Prior art]
Conventionally, this type of associative memory device has been developed and used industrially for port switching of packet data of LAN (Local Area Network) devices. However, since the conventional one was developed in a situation where the demand for high-speed data communication is not so strict as it is nowadays, the focus was mainly on facilitating the design of the peripheral circuit. . Therefore, only one input / output port smaller than the search data width is provided. This conventional example is specifically shown below.
[0003]
FIG. 9 shows a block diagram of a conventional apparatus. The conventional associative memory device includes a 16-bit input / output port 51, a 64-bit search data register 52 for inputting search data input from this port, and which bits of the search data register 52 are cared for during a search operation. A hit register (HHA) for storing a mask register 53 for specifying (to be searched), a memory area 50 to be searched, and a memory address 50a in the memory area 50 indicating which memory word 50a is matched by the search operation The address register (HHA register) 54 is provided, and when the search data register 52 is input with a certain number of bits from the input / output port 51, in this case 48 bits, that is, when data is input three times ((1) in the figure) Associative memory control including a search control circuit 55 that automatically starts a search operation (when data from (3) to (3) are input) Consists of the road 56, address port 57 to access these registers, etc. are prepared.
[0004]
In this example, the memory word 50a constituting the memory area 50 is composed of 64 bits, of which 48 bits indicate the MAC address to be searched, and the remaining 16 bits store auxiliary data such as a port number. . The port number Pk indicates a port to which a device (terminal) having the MAC address belongs.
A destination MAC address existing at the head of each communication packet data is input to this associative memory device, and a search operation is performed. The address of the memory word hit by this search operation (hit address (HHA)) is stored in the hit address register 54. Further, the port number Pk stored in the attached data of the memory word 50a hit is read, and the output port of the packet data is determined by the port number.
[0005]
Access to ordinary registers such as the search data register 52, the hit address register 54, and the mask register 53 can be performed at a high speed of about 30 to 40 ns. However, the access and search operations to the memory area 50 are designed with a high density as the target memory area 50, making high-speed access difficult, and the access speed becomes about 80 ns, slowing down the search processing speed. It is a cause.
[0006]
  Here, a general search operation procedure is shown below.
    A) Input of search data (48 bits)
    B) Search operation
    C) Reading the hit address (HHA)
    D) Hit memoryAttachedReading data
  Here, the operation C) is not necessary if only the output port number of the packet data is known. In many cases, however, the 16 bits alone often does not have a sufficient attached data width, and an external RAM is used outside. In many cases, in this case, an external RAM corresponding to the address (HHA) of the hit memory is defined, and data is read from the external RAM at the address (HHA).
[0007]
FIG. 10 shows an outline of the timing of operations A) to D). In this timing diagram, one long square represents one cycle of 40 ns, and in this example, the search data processing cycle from T0 to T8 is 8 cycles. Further, the fact that T0 and T1 continue from the bottom to the right of T8 represents that the next search data processing cycle continues.
Here, first, data of 16 bits is input to the search data register 52 at timings T0, T1, and T2. However, at the timing of T2, the search control circuit 55 executes the search operation simultaneously with the input of this data. This search operation is an access to the memory area 50 and requires 80 ns. Thereafter, the read operation from the hit address register 54 is started at the timing of T4, and read from the input / output port 51 at the timing of T5 after 40 ns.
[0008]
  Next, hit word 50aAttachedReading of the data Pk is started at the timing of T5. This reading of data is an access to the memory area 50 and requires 80 ns. At the timing of T7, hit wordAttachedData, that is, the port number Pk is output from the input / output port 51.
  Further, the input / output port 51 is also used as a search data write port, and the search data cannot be written at the timing T7 for processing the next search data. Therefore, one dummy cycle is required until the next cycle. That is, a series of search data processing cycles takes 8 cycles (320 ns).
[0009]
[Problems to be solved by the invention]
On the other hand, in recent high-speed data communication, there is a demand for speeding up this series of search data processing cycles to be closer to 200 ns and further to be shorter than 200 ns. However, as can be seen in this conventional example, the conventional associative memory device having only one input / output port smaller than the search data width has a sufficient performance for this requirement in order to facilitate the design of the peripheral circuit. It can no longer be provided.
[0010]
SUMMARY OF THE INVENTION An object of the present invention is to provide an associative memory device that solves the above-described problems of the prior art and that has high performance and high performance without impairing the design of peripheral circuits of the conventional associative memory.
[0011]
[Means for Solving the Problems]
  To achieve the above object, the present invention provides a data input port to which W-bit data is input,
  An N (W <N) -bit first buffer in which W-bit data input via the data input port is stored, and M(W <M)A second buffer of bits;
  Input control means for storing the W-bit data in the first or second buffer;
  Detecting means for detecting that the W-bit data is input k times (k × W ≦ N) or r times (r × W ≦ M) to the second buffer; Switching to switch the buffer storing W-bit data input via the data input port from the first or second buffer to the second or first buffer according to a detection signal from the detection means Means and
  Search control means for performing a search operation to the memory area of the associative memory using the data of the first or second buffer;
The search operation cycle time Ts and the cycle time Tw for writing the W-bit data to the first or second buffer satisfy Tw <Ts.While the search operation to the memory area of the associative memory is being performed using the data of the first or second buffer, the W or W for the next search operation is performed in the second or first buffer. An associative memory device characterized by inputting bit data is provided.
The present invention also provides a data input port to which W-bit data is input;
An N (W <N) bit first buffer and an M (W <M) bit second buffer in which W bit data input via the data input port is stored;
Input control means for storing the W-bit data in the first or second buffer;
Detecting means for detecting that the W-bit data is input k times (k × W ≦ N) or r times (r × W ≦ M) to the second buffer; Switching to switch the buffer storing W-bit data input via the data input port from the first or second buffer to the second or first buffer according to a detection signal from the detection means Means and
Search control means for performing a search operation to the memory area of the associative memory using the data of the first or second buffer;
An output port that outputs an address of a hit word in the memory area of the associative memory obtained by the search operation and at least a part of the contents thereof;
The cycle time Ts of the search operation and the cycle time Tw of writing the W-bit data to the first or second buffer satisfy Tw <Ts, and the data of the first or second buffer And after the search operation to the memory area of the associative memory is completed, the W bit data for the next search operation is input to the second or first buffer. Providing equipment.
[0012]
  Here, the read cycle time Tr of data from the memory area of the associative memory is thewritingLonger than cycle time Tw (Tw <Tr), from this memory areaData at the same time as the search operation is completedReadingStart reading andA holding means DH for temporarily holding the read data, and a data read cycle from the holding means DHtimeTh is the abovereadingIt is preferably shorter than the cycle time Tr (Th <Tr).
  Also, a search operation to the memory area of the associative memoryFinishSometimes it is preferable to have an automatic holding control means for automatically holding at least a part of the memory word hit by the search in the holding means DH.
  further,First and second hit address registers respectively storing addresses of memory words in which data matching data in the first or second buffer obtained by a search operation to the memory area of the associative memory is stored A word memory of an address stored in the second or first hit address register after performing a search operation to the memory area of the associative memory using the data of the first or second buffer Update at least part of the attached data stored inIs preferred.
[0013]
DETAILED DESCRIPTION OF THE INVENTION
A content addressable memory device according to the present invention will be described in detail below based on a preferred embodiment shown in the accompanying drawings.
[0014]
  FIG. 1 shows a block diagram of an embodiment of an associative memory device of the present invention.
  The associative memory device shown in FIG. 1 has a memory area 10 consisting of a plurality of 64-bit memory words 10a to be searched, and 16-bit search data, and the hit address (HHA) of the memory word 10a matched by the search. )andAttachedInput / output port 11 to which data (port number Pk) is output, search data registers A12a and B12b that hold search data input from input / output port 11, and bits other than the search target bits in the search data Mask register 13 for masking, hit address register (HHA register) 14 for storing the hit address (HHA) of the memory word 10a having data that matches (hit) the search data, and input / output to the search data registers A12a and B12b The search data register control and search control circuit 15 that controls the search operation and the associative memory control circuit 16 that includes the control circuit 15 and controls the entire associative memory device are controlled alternately. And search data registers A12a, B12b, And Tsu DOO address register 14 and control circuit 15 and the address port 17 for accessing the like 16, hit in the search data memory word 10aAttachedAnd a data holding circuit 18 for temporarily holding contents including data.
[0015]
This associative memory device has a 16-bit input / output port 11 as in the conventional example shown in FIG. 9, and MAC address data (48 bits) is input from this input / output port 11 three times. Done. In the illustrated example, the appearance (particularly pin count) is not different from the conventional one shown in FIG. 9, and the number of control pins required by the peripheral device for controlling this associative memory device is exactly the same. If these two devices are mounted on the same board, the mounting area required for the mounting is completely the same as the conventional one.
[0016]
However, the content of this associative memory device is greatly different from the conventional example of FIG. 9 in that two search data registers A12a and B12b are provided. An operation method of the search data register A 12a and the search data register B 12b in the illustrated example apparatus will be described below.
[0017]
First, 32 bits of the MAC address data (48 bits) are stored 16 bits at a time in the areas (1) and (2) of the search data register A12a. This storage is writing to the register and is performed at high speed (1 cycle: write cycle time Tw = 40 ns (see FIG. 2)).
Next, the remaining 16 bits are written into the area (3) of the search data register A12a. At the same time, the search operation to the memory area 10 is performed with the 48-bit MAC address data stored in the search data register A12a. Be started.
[0018]
At this time, like the conventional one, the mask register 13 determines which bit of the search data register A 12a is the search target bit. In this case, 48 bits from the areas (1) to (3) of the search data register A12a are target bits, and 16 bits from the area (4) are non-target. For example, the search data register A12a of the mask register 13 Masking is performed by defining “0” in 48 bits corresponding to the areas (1) to (3) and defining “1” in 16 bits corresponding to the area (4).
[0019]
By the way, the search operation to the memory area 10 is difficult to perform at high speed, and it necessarily takes two cycles (search operation cycle time Ts = 80 ns (see FIG. 2)). The first half of these two cycles is the writing of data to the area (3) of the search data register A12a. During this time, the input / output port 11 is occupied by the write data. The output port 11 is in an idle state.
Originally, the 16-bit input / output port 11 is adopted in consideration of the design of the peripheral control circuit and cost reduction, so 3 cycles are required for data input of the MAC address (48 bits). From the standpoint of maximizing performance under this limitation, the idle state of the input / output port 11 is extremely uneconomical.
[0020]
Therefore, by providing another search data register B12b, it is possible to write the first 16 bits of the next MAC address data (48 bits) in the area (1) of the register B12b.
In this way, when MAC address data is continuously retrieved by the associative memory device of the present invention, the MAC address data is not 48 bits (16 bits × 3 cycles), but 32 bits (16 bits × 2 cycles). 1), one data input cycle can be made unnecessary.
[0021]
A schematic diagram of an example of this timing chart is shown in FIG.
In the figure, the data (2) and (3) are input to the search data register A12a at the timings of T0 and T1, and the search operation is started (at the timing of T1). It is assumed that the first 16 bits of the current MAC address data are input to the area (1) (see FIG. 1) of the same register A12a in the MAC address data search data processing cycle.
[0022]
At the same time as the search operation of the MAC address data this time is started from T1 in the figure, at the next cycle T2, the first 16 bits of the next MAC address data are the area (1) of the search data register B12b (FIG. 1). Reference).
Similarly, the search process for the next MAC address data is started from the timing of T6, but the remaining 32 bits of data are sequentially written as areas (2) and (3) in two cycles from T6 (T0), and T8 ( At the timing of T2), the first 16 bits of the next MAC address data are further written in the area (1) in FIG. 1 of the search data register A12a.
[0023]
The search data register control and search control circuit 15 shown in FIG. 1 controls the search data register A 12a and the search data register B 12b alternately.
The search data register control and search control circuit 15 has at least one data write switching register (not shown), and controls switching between the search data register A12a and the search data register B12b. That is, in this example, the number of times of writing from the input / output port 11 to one of the search data registers A12a and B12b is counted, and when it reaches 3, the write destination is changed to the other of the search data registers A12a and B12b. Is.
[0024]
That is, both search data registers A12a and B12b are toggled by this switching register. Of course, this toggle control has an initial value, and when this associative memory device is reset, writing of 16 bits to the first search data register is defined in the search data register A12a, for example.
In addition, by having the initial value of the toggle in this way, two registers that define switching of data writing from the search data register A12a to the search data register B12b and vice versa are searched. It is also possible to control the switching timing separately.
[0025]
Further, in the description so far, each search operation has been started simultaneously with the completion of the writing of data to the search data register A12a or the search data register B12b. However, the timing of this search operation is determined by another search operation timing definition register. It can also be provided. In this case as well, one search data register A12a or one search data register B12b can be provided or separately.
By providing this definition register, for example, in the above-described example, the search data register is set to be interchanged when 48 bits, that is, 16-bit data is input three times. However, the search operation timing definition register is set twice, for example. If the search data is input to the area (2) shown in FIG. 1 of each search data register A12a or B12b, the search operation can be started, and the search destination of the search data is searched. The switching of the data registers A12a and B12b and the search start timing can be controlled separately.
[0026]
Providing the two search data registers A12a and B12b in this way seems simple at first glance, but can be achieved only by carefully considering the characteristics of the associative memory device of the present invention and how to use it. The reason for this is that the design of the register itself is never complicated and can be realized without changing the external specifications at all. However, it can be seen that it is not provided as a conventional associative memory device configuration.
[0027]
In this example, in order to simplify the explanation, the search operation (Ts) is set to about twice the normal register access (Tw). Therefore, only one cycle speed is increased. The search operation for register access is considerably slow. By providing two search data registers in this way, it is possible to completely prepare for the next search data, and to the high-speed communication of the associative memory device having this new configuration. The contribution of can be said to be extremely large.
[0028]
Further, another speed-up technique shown in this embodiment will be described below. This also has a structure of this type of device, that is, both a large-capacity memory designed for the first purpose of higher integration than speed and a register group that can be accessed at high speed. Focusing on the fact that access is essential, it was devised after careful consideration.
[0029]
  In FIG. 2 or FIG. 10 of the conventional example, the hit address (HHA) is read from the hit address (HHA) register 14 after the search operation. Of course, this is an access to the register and can be read at a high speed (one cycle), but the hit memory word 10a indicated by the next hit addressAttachedData read requires access to the memory area 10 designed with high density, and requires two cycles (data read cycle time Tr = 80 ns from the memory area) (see FIGS. 2 and 10).
[0030]
  However, following the reading of the hit address (HHA)AttachedIf it is decided to read data as a procedure, this is an access to a different area internally as shown in the block diagram of FIG. 1, and the contents of the HHA register 14 are read to the input port 11. However, it is possible to simultaneously read the contents of the memory area 10 to the data holding circuit 18 newly provided inside.
  That is, reading of the hit word in the memory area 10 is started simultaneously with the data reading of the HHA register 14 at the timing T3 in FIG. 2 and this data is temporarily stored in the data holding circuit 18. Reading of the data holding circuit 18 is started at the timing of T4. At this time, the correct hit word data is not yet output, but is output as a correct value by the time of T5 (1 cycle: from the data holding circuit) Data read cycle time Th = 40 ns (see FIG. 2)).
[0031]
By doing so, it becomes possible to treat the data of the hit memory word 10a, which conventionally takes two cycles, as if it can be read in one cycle.
Of course, in this case, the trigger of this operation is the reading of the HHA register 14, and this operation is not always performed when the HHA register 14 is read, and this operation may prevent the next operation. Therefore, when reading of a series of hit addresses (HHA) and reading of the memory contents are continued, an address different from the normal access to the HHA register 14 is defined to be input from the address port 17.
[0032]
As shown in FIG. 2, a series of search processing cycles is 6 cycles, that is, 6 × 40 ns = 240 ns, which is 25% faster than the conventional 320 ns. Moreover, this high speed can be obtained without changing the external interface at all and without sacrificing the design ease and cost of the conventional peripheral circuit.
In these examples, it is assumed that the access to the register is 40 ns for one cycle for the sake of simplicity. However, it is actually possible to make the access faster, and as described above, the search data is completed in the previous search cycle. Actually, it is possible to further shorten the time by about 1 to 2 cycles, and the industrial value of these techniques is extremely high.
[0033]
Further, in order to support this technical value, the description of the high-speed version in the conventional example will be briefly described below.
In the conventional one, the number of external interfaces has been reduced, and the input / output ports have been made 16 bits mainly for the purpose of facilitating the design of the peripheral control device and cost reduction. However, improvement is desired due to a demand for speeding up the search data processing cycle, and it has been proposed to increase the speed of the input / output port to 32 bits.
[0034]
That is, in FIG. 10, it is proposed to reduce the number of cycles required three times to input 48-bit MAC address data to two. As a result of this improvement, the series of search data processing cycles has been changed from 320 ns (40 ns × 8) to 280 ns (40 ns × 7). This has led to increased equipment costs.
However, in the first embodiment of the present invention, the increase in the number of external interface pins is suppressed to “0”, that is, 240 ns (40 ns × 6) is realized, clearly showing the superiority of the present invention. It has become a thing.
[0035]
Furthermore, the present inventor proposes another speedup here. This is because it has been found that if the external interface is changed as in the second conventional example, further performance can be obtained.
FIG. 3 shows a block diagram of a second embodiment of the content addressable memory device of the present invention.
[0036]
1 is different from the associative memory device shown in FIG. 1 in that the output from the data holding circuit 18 and the HHA register 14 can be output from the output port 37 via the selector 38. It is a point.
The output port 37 has 16 bits as an example, and a select signal 39 for selecting the output is provided.
In other words, the number of external interfaces is almost the same as that of the conventional input / output port 11 expanded from 16 bits to 32 bits, but the performance is greatly improved.
[0037]
  FIG. 4 shows a timing chart of a series of search data processing cycles in the associative memory device shown in FIG.
  By simply providing a 16-bit output port 37, it becomes extremely easy to input search data. That is, as shown in FIG. 2, when reading the hit address (HHA) from T3 to T4, or from the hit word from T4 to T5AttachedBy using this output port 37 when reading data, the input / output port 11 is not occupied, and a part of the MAC address data for the next search is stored in the search data register A12a or the search data register B12b. Is possible.
[0038]
At the timings T2 and T3 in the timing chart shown in FIG. 4, 32 bits (16 bits × 2) of the MAC address data to be searched next are input to the search data register B12b. That is, the next search is started at the timing of T4 (T0) when the remaining 16 bits of the MAC address data are input to the search data register B12b.
Similarly, in this timing chart, assuming that 32 bits (16 bits × 2) of the MAC address data of the current search have already been input, the last 16 bits at the timing of T0 are the search data register A12a. In the following description, it is assumed that the search operation starts at the same time as the input to.
[0039]
The search operation starts from the timing T0, and the hit address is read from the HHA register 14 at T2. At this time, the contents of the hit memory word 10a are also read at the same time as in the first embodiment and output to the output port 37 at the timing of T4.
Further, in the conventional example or the first embodiment of the present invention, it is necessary to insert a dummy cycle before the next search data processing cycle starts after T4. This was to prevent the read data of the hit word content and the data for the next search from colliding at the same input / output port 11, but the output of the hit word and the output to be read as in the second embodiment. Since the port 37 is different from the input / output port 11 to which the next search data is written, a dummy cycle becomes unnecessary.
[0040]
As a result, in this embodiment, the series of search data processing cycle is 160 ns (40 ns × 4) of 4 cycles, which is 1/2 of 320 ns of the conventional example shown in FIG. Two times faster.
In addition, compared with 7 cycles 280 ns of a series of search data processing cycles of the conventional high-speed version having a 32-bit input / output port, it is improved 1.75 times, which is different from the first embodiment of the present invention. Compared to 6 cycles, it is 1.5 times faster.
In addition, this sufficiently satisfies the user's 200 ns demanding use in high-speed data communication.
In other words, as an improvement of the conventional device, while having almost the same external interface as that having a 32-bit input / output port, it is remarkably superior in its performance. It was possible for the first time by taking into account the unique characteristics of the device, and creativity, and its industrial value could be a high-performance, low-cost associative memory device that is extremely important for future high-speed data communications. .
[0041]
By the way, in the above-described embodiment, in order to acquire the attached data such as the port number corresponding to the MAC address existing at the head of the packet data, as a series of operations, after the search operation, the memory word 10a of the hit address is stored. An example in the case of reading attached data such as a stored port number is shown.
In the following embodiment, an example of rewriting the attached data stored in the memory word 10a of the hit address after the search operation as a series of operations in order to constantly update the attached data to the latest information. explain.
[0042]
For example, in a switching device that acquires attached data such as a port number corresponding to a MAC address existing at the beginning of packet data using the content addressable memory device of the present invention, each port is connected to a personal computer (hereinafter referred to as a personal computer). And PC) are connected and used.
[0043]
Here, when the port for connecting a PC is changed from port 1 to port 3, the port number stored in the attached data of the word memory 10a storing the data of the MAC address corresponding to this PC is changed from port 1 to port. If it is not updated to 3, the packet data transferred to this PC will be transferred to the port 1 connected before, not to the port 3 actually connected. In order to prevent this, it is necessary to constantly update the port number to which each PC is connected to the latest information.
[0044]
The number of words in the word memory 10a is generally smaller than the total number of PCs on the network, and each memory word 10a selectively stores only specific PC information. In order to improve the use efficiency of the associative memory device, for example, time stamp information for managing the use time is stored as attached data, and this time stamp information is constantly updated so that only frequently used PC information is stored. It is registered in the word memory 10a. Therefore, it is necessary to constantly update the time stamp information of each word memory 10a to the latest information.
[0045]
As described above, under the general use condition of the associative memory device, after the search operation, the attached data is read (read) from the memory word 10a at the hit address or updated to the memory word 10a at the hit address. The series of operations is continuously repeated by writing the attached data (writing) as a series of operations.
[0046]
Here, FIG. 5 shows a conceptual diagram of an example of each processing cycle of write, read, and search in the content addressable memory device of the present invention. As shown in the figure, the writing of attached data to the memory word 10a of the hit address is performed by first latching an address from the outside in the L & D (Latch & Decode) phase, decoding it, and When the external request at that time is data write, this external address points to the hit memory word and confirms that it is a data write, and then hit in the EXEC (Execution) phase. This is done by writing the attached data to the memory word 10a specified by the address. As the write data at this time, externally input data latched in the aforementioned L & D phase is used.
[0047]
In addition, the read of the attached data indicates the memory word in which the address given from the outside is hit in the L & D phase, and if the request at that time is the data read, the memory specified by the hit address in the EXEC phase Attached data such as port number and time stamp information is read from the word 10a, and in the WAIT (wait) phase, the attached data read from the word memory 10a is latched in the data holding circuit 18, and in the OUTPUT (output) phase, This is done by outputting the attached data latched in the data holding circuit 18 from the output port 37.
[0048]
In the L & D phase, the address input from the address port 17 is latched in the L & D phase, and this is decoded to interpret that the address indicates the search. In the EXEC phase, a part of the decoded address is specified. The search data in the search data register A12a or B12b and the MAC address data of each memory word 10a are compared, the hit address is latched in the HHA register 14 in the WAIT phase, and is latched in the HHA register 14 in the OUTPUT phase. The hit address is output from the output port 37.
[0049]
FIG. 6 shows an example in which such a series of continuous operations are performed in a pipeline manner. This series of operations means that after the search A is performed using the search data of the search data register A12a, the attached data is read or written to the word memory 10a of the hit address output by the search A, in this embodiment. A read (R / WA) is performed, and then a search B is performed using the search data in the search data register B12b, and then the attached data is written to the memory word 10a of the hit address output by the search B (R / WA). WB) is repeated alternately.
[0050]
As shown in the timing chart of FIG. 6, in the (1) th request operation search A from the outside, a hit address (HHA) is output from the memory area 10 after the EXEC phase. On the other hand, when an external request for reading the data attached to the memory word 10a of the hit address (HHA) obtained from this search operation is input at the timing of the second external request operation in FIG. The EXEC phase of the execution of the read operation is executed immediately after the EXEC phase of the (1) -th search operation, and since the WAIT phase has not passed, the read with the correct HHA address cannot be executed.
[0051]
Therefore, this external read request operation is input at the (3) th timing in FIG. By doing so, the result of the first search operation is executed at the timing after WAIT, and the read EXEC phase is executed, so that the read is performed using the correct hit address (HHA) latched in the HHA register 14. The action is executed. The same applies to the writing (R / WB) of the attached data to the memory word 10a of the hit address of the (4) th search B and (6) th search B of the request operation from the outside. However, in order to correctly execute the request operation from the outside in this way, the (2) th and (5) th idle states in FIG. 6 are required.
[0052]
Therefore, in terms of usage efficiency, after the search A, the attached data is read (R / WA) immediately, and after the search B, the attached data is immediately written (R / WB). Similarly, it goes without saying that it is preferable to repeatedly perform retrieval and reading / writing of attached data. However, for the above reason, the idle period during which nothing is performed between the search A and the read of the attached data (R / WA) and between the search B and the write of the attached data (R / WB). This causes a problem that the use efficiency cannot be improved.
[0053]
The associative memory device shown in FIG. 7 solves this problem.
The content addressable memory device of the illustrated example is a third embodiment of the content addressable memory device of the present invention. The content addressable memory device shown in the figure is different from the content addressable memory device shown in FIG. 3 with two HHA registers. A14a and B14b are provided. These HHA registers A14a and B14b store hit addresses of the memory word 10a in which MAC address data matching the search data of the search data registers A12a and B12b is stored.
[0054]
That is, when each memory word 10a is searched using the search data of the search data register A12a, the address of the memory word 10a in which the data of the MAC address matching the search data is stored in the HHA register A14a as a hit address. Is done. When each memory word 10a is searched using the search data in the search data register B12b, the address of the memory word 10a in which the data of the MAC address that matches the search data is stored in the HHA register B14b as a hit address. Stored.
[0055]
Although not shown, it is a hit flag, that is, whether or not there is a word memory 10a in which data of a MAC address that matches the search data in the search data register A12a or B12b exists after the search operation (hit). Hit flag register for holding information, and multi-hit flag, that is, a multi-hit flag register for holding information indicating whether or not there are a plurality of word memories 10a (multi-hit) storing MAC address data matching the search data In order to confirm whether or not a hit has occurred, it is also possible to provide two as necessary.
[0056]
Next, FIG. 8 shows a timing chart of a series of search data processing cycles in the associative memory device of FIG. Here, after the search A is performed using the search data register A12a, the attached data is written (R / WB) to the word memory 10a of the hit address output by the search B performed before the search A. Next, after the search B is performed using the search data register B12b, the attached data is read into the memory word 10a of the hit address output by the search A performed before the search B (R / WA). ) Shall be repeated alternately.
[0057]
As shown in the timing chart of FIG. 8, in the first search A, after the EXEC phase, the hit address (HHA) is output from the memory area 10 and latched in the HHA register A 14a in the WAIT phase. In the (2) th append data write (R / WB) following the search A, although not shown, the hit address latched in the HHA register B14b by the search B performed immediately before the search A is executed. Used in the phase, new attached data is written to the word memory 10a of the hit address of the search B performed immediately before the first search A.
[0058]
In addition, the (3) th search B is performed following the (2) th append data write (R / WB), and after the EXEC phase, a hit address (HHA) is output from the memory area 10 and WAIT In the phase, it is latched in the HHA register B14b. In the read (R / WA) of the (4) th attached data following the (3) th search B, the HHA register A14a is obtained by the (1) th search A performed immediately before the (3) th search B. Is used in the EXEC phase, and the attached data is read from the word memory 10a of the hit address of the search A.
[0059]
As described above, the associative memory device of FIG. 7 is provided with two HHA registers A14a and B14b. After the search A, the write of attached data to the word memory 10a of the hit address of the search B performed immediately before the search A is performed. (R / WB) is performed, and similarly, after the search B, the attached data is read (R / WA) from the word memory 10a of the hit address obtained from the search A performed immediately before the search B. it can. As a result, a series of search operations can be performed without inserting an idle period between the search and the read / write of the attached data, and the use efficiency of the associative memory device can be improved. it can. In the embodiment of FIG. 8, the series of operations is completed from (1) to (4). On the other hand, in FIG. 6, this takes from (1) to (6).
[0060]
【The invention's effect】
As described above in detail, the present invention suppresses an increase in the number of external interfaces (number of pins) for ease of design of the conventional peripheral control circuit and cost reduction, and the communication data processing procedure and this type In consideration of the characteristics of the associative memory device, the following four points of ingenuity were drastically improved, and the processing speed of the series of search data could be dramatically improved.
1) Two search data registers are provided, and during a search operation that requires a relatively long cycle, a part of the next search data is input to the other search data register, and this is controlled alternately. Shorten the search data processing cycle.
2) Data is read from the memory area simultaneously with other register (HHA register) access, temporarily held in the internal holding circuit, and apparently read out from this internal holding circuit in the next short cycle We are trying to improve the speed.
3) Also, instead of simply expanding the input / output ports as in the speed-improved version of the conventional device, the elements that are the bottleneck for speeding up are analyzed and a 16-bit output port is provided. While suppressing the increase in the number of external interfaces, the speed is doubled compared to the conventional one.
4) Further, two HHA registers are provided, and when one is used for searching, the attached data is written in the word memory of the hit address of the search performed immediately before this search, which is latched on the other. By alternately controlling this, it is possible to prevent useless idle cycles.
Due to the above inventive idea, the associative memory device of the present invention has a very good cost performance, and its industrial value is great.
[Brief description of the drawings]
FIG. 1 is a block diagram of an embodiment of an associative memory device according to the present invention.
2 is a schematic timing chart of an example of a search data processing cycle of the associative memory device shown in FIG. 1; FIG.
FIG. 3 is a block diagram of another embodiment of an associative memory device according to the present invention;
4 is a schematic timing chart of an example of a search data processing cycle of the associative memory device shown in FIG. 3;
FIG. 5 is a conceptual diagram illustrating an example of processing cycles of write, read, and search in the content addressable memory device of the present invention.
6 is a schematic timing chart of another example of the search data processing cycle of the associative memory device shown in FIG. 3; FIG.
FIG. 7 is a block diagram of still another embodiment of an associative memory device according to the present invention.
8 is a schematic timing chart of an example of a search data processing cycle of the associative memory device shown in FIG. 7;
FIG. 9 is a block diagram of a conventional content addressable memory device.
10 is a timing chart of the search operation of the associative memory device shown in FIG. 9. FIG.
[Explanation of symbols]
10 Memory area
10a memory word
11 I / O ports
12a, 12b Search data register (A, B)
13 Mask register
14, 14a, 14b Hit address (HHA) register
15, 35 Search data register control and search control circuit
16, 36 associative memory control circuit
17 Address port
18 Data holding circuit
37 output port
38 selector
39 Select signal

Claims (5)

A data input port to which W-bit data is input;
An N (W <N) -bit first buffer and an M (W <M) -bit second buffer in which W-bit data input via the data input port is stored;
Input control means for storing the W-bit data in the first or second buffer;
Detecting means for detecting that the W-bit data is input k times (k × W ≦ N) or r times (r × W ≦ M) to the second buffer; Switching to switch the buffer storing W-bit data input via the data input port from the first or second buffer to the second or first buffer according to a detection signal from the detection means Means and
Search control means for performing a search operation to the memory area of the associative memory using the data of the first or second buffer;
The cycle time Ts of the search operation and the cycle time Tw of writing the W-bit data to the first or second buffer satisfy Tw <Ts, and the data of the first or second buffer The W-bit data for the next search operation is input to the second or first buffer while the search operation to the memory area of the associative memory is being performed. Associative memory device.   A data input port to which W-bit data is input;
  An N (W <N) bit first buffer and an M (W <M) bit second buffer in which W bit data input via the data input port is stored;
  Input control means for storing the W-bit data in the first or second buffer;
  Detecting means for detecting that the W-bit data is input k times (k × W ≦ N) or r times (r × W ≦ M) to the second buffer; Switching to switch the buffer storing W-bit data input via the data input port from the first or second buffer to the second or first buffer according to a detection signal from the detection means Means and
  Search control means for performing a search operation to the memory area of the associative memory using the data of the first or second buffer;
  An output port that outputs an address of a hit word in the memory area of the associative memory obtained by the search operation and at least a part of the contents thereof;
  The cycle time Ts of the search operation and the cycle time Tw of writing the W-bit data to the first or second buffer satisfy Tw <Ts, and the data of the first or second buffer And after the search operation to the memory area of the associative memory is completed, the W bit data for the next search operation is input to the second or first buffer. apparatus. Read cycle time Tr of the data from the memory area of the associative memory, the longer than the write cycle time Tw (Tw <Tr), starts the Shi read out from the memory area and end at the same time data of said search operation , has a holding means DH for temporarily holding the read out data, the read cycle time Th of the data from the holding means DH is characterized short (Th <Tr) than the read cycle time Tr claims Item 4. The associative memory device according to Item 2. 4. The automatic holding control means for automatically holding at least a part of the memory word hit by the search in the holding means DH at the end of the search operation to the memory area of the associative memory. Associative memory device. First and second hit address registers respectively storing addresses of memory words in which data matching data in the first or second buffer obtained by a search operation to the memory area of the associative memory is stored A word of an address stored in the second or first hit address register after performing a search operation to the memory area of the associative memory using the data of the first or second buffer The content addressable memory device according to claim 1, 2, 3, or 4 , wherein at least part of the attached data stored in the memory is updated to the latest information .

Images