JP5778640B2 - Frame search processing apparatus and method - Google Patents

Description

  The present invention relates to a frame transfer technique, and particularly to a frame search processing technique for performing a search for determining a process according to an input frame.

  When forwarding, discarding, priority control, or the like in a router, switch, or bridge, a search process for searching for a frame that matches a preset search condition is required to determine a process according to an input frame. The search process extracts information necessary for the search from the input frame, for example, header information of the frame such as an IP address (hereinafter referred to as frame information), and outputs the result by comparing the frame information with the search condition.

  There is a frame search processing device that collates input frame information with all search conditions as one of methods for realizing frame search processing (Non-Patent Document 1). This frame search processing apparatus includes a search table (memory) that stores a plurality of search conditions, and a comparison circuit that compares the frame information with data in the search table to determine a match. In the search process, when frame information is input, access to the search table is started, the search condition is read out every clock cycle, and compared with the frame information. After the comparison with all search conditions is completed, the result is output.

  In this frame search processing device, when the bit string of the read search condition is different from the value of the previous search condition, the change of the signal line of each bit (“0” → “1” or “1”). → "0") consumes power. As a method for reducing the power consumption due to the change in the signal line of each bit, there is Patent Document 1 as a method for performing data sorting based on the Hamming distance. In Patent Document 1, the order of read data is rearranged so as to minimize the time-series Hamming distance of data read from the memory and transmitted to the data receiving side, and the read data is arranged in the read request order before the rearrangement. Rearrange again.

JP 2007-140858 A

M.Urano, T.Kawamura, S.Ohteru, H.Suto, K.Kawai, R.Kusaba, N.Miura, J.Kato, A.Miyazaki, T.Hatano, S.Yasuda, N.Tanaka, S. Shigematsu, M. Nakanishi, T. Shibata, “The 10G-EPON OLT and ONU LSIs for the coexistence of 10G-EPON and GE-PON toward the next FTTH era”, 2011 Symposium on VLSI Circuits (VLSIC), pp.132- 133, 15-17 June 2011

  However, in the conventional search processing apparatus, the order of search conditions to be compared is not limited and is arranged at random, so that power consumption due to changes in signal lines is not necessarily reduced. Further, in Patent Document 1, since the reading order cannot be grasped in advance, sorting processing is necessary not only at the time of reading but also immediately after reading. For this reason, there is a problem that the overhead required for the rearrangement of the buffers and sort processing is increased, and the delay is increased because the sort processing is required for each series of memory accesses.

  The present invention has been made to solve such problems, and an object of the present invention is to provide a frame search processing technique that can reduce power consumption required for frame search processing.

In order to achieve such an object, a frame search processing device according to the present invention collates frame information extracted from a frame to be processed in order with a plurality of search conditions stored in advance in a search table. A frame search processing device for searching for a frame that matches any of these search conditions, the search table storing a plurality of search conditions in advance, and sequentially reading the search conditions from the search table One or more comparison circuits that execute search processing for collation and output search results indicating whether or not the frame information and the search conditions match, and the search conditions stored in the search table Execute sort processing for rearranging in order that the sum of the distances between codes of the two search conditions to be read becomes smaller Comprising a chromatography preparative processor, in response to new registration notification from the outside indicating the completion of registration of the new search conditions for the search table, and a sorting control section for instructing the execution of the sorting process to the sort processing unit, the search of the conditions, the search condition read out from the lookup table when matching one of the frame information in the order, the sum of the code distance is stored in the search table in the order decreases.

  In addition, one configuration example of the frame search processing device is a search that the search table uses as a storage area surface in which the search condition can be read and written in parallel and used for matching in the comparison circuit during the search processing. An operation surface for storing conditions, and a standby surface for storing search conditions that are targets of the sorting process, and the sort processing unit includes the standby surface of the search table during the sorting process. The sort process is executed for the search conditions stored in the sort table, and upon completion of the sort process in the sort processing unit, the standby surface of the search table is set as a new operational surface, and It further includes a switching control unit that performs switching to make the operation side a new standby side.

  In addition, one configuration example of the frame search processing device includes a plurality of comparison circuits as the comparison circuit, and the search processing can be started among the comparison circuits based on the execution status of the search processing in the comparison circuit. This is a case where the frame information is distributed to any one of the comparison circuits, and the frame information is temporarily stored in an internal buffer, and the search process can be started by any of the comparison circuits. And a frame information buffer that obtains the frame information from the internal buffer and outputs the frame information to the distribution circuit when the sort processing unit is not executing the sort process.

The frame search processing method according to the present invention is adapted to any one of these search conditions by sequentially comparing the frame information extracted from the frame to be processed with a plurality of search conditions stored in advance in the search table. A frame search processing method used in a frame search processing device for searching for a frame that has been stored, wherein the search table stores a plurality of search conditions in advance, and one or more comparison circuits are connected to the search table from the search table. A comparison step for sequentially reading out the search conditions and executing a search process for collating with the frame information, and outputting a search result indicating whether or not the frame information matches the search conditions, and a sort processing unit in the search table For the stored search conditions, the sum of the distances between codes of two search conditions read out successively A sort processing step for executing a sort process for rearranging in a decreasing order, and the sort control unit executing the sort process in response to a new registration notification from the outside indicating completion of registration of a new search condition for the search table. the a sorting control step for instructing to the sort processing unit, among the search conditions, a search condition read out from the lookup table when matching one of the frame information in the order, the smaller the sum of the code distance Are stored in the search table in the following order.

  In addition, one configuration example of the frame search processing device is a search that the search table uses as a storage area surface in which the search condition can be read and written in parallel and used for matching in the comparison circuit during the search processing. An operation surface for storing conditions, and a standby surface for storing search conditions to be subjected to the sort process, and the sort processing step includes the standby surface of the search table during the sort process. The sorting process is executed for the search conditions stored in the search table, and the switching control unit sets a new operation plane as the standby plane in the search table in response to the completion of the sort process in the sort processing unit. And a switching control step for switching the operating surface to a new standby surface.

  In addition, one configuration example of the frame search processing device includes a plurality of comparison circuits as the comparison circuit, and the distribution circuit includes the search processing among the comparison circuits based on the execution status of the search processing in the comparison circuit. A distribution step of distributing the frame information to any one of the comparison circuits capable of starting the operation, and a frame information buffer temporarily stores the frame information in an internal buffer, A buffer step of acquiring the frame information from the internal buffer and outputting the frame information to the distribution circuit when the search process can be started and the sort process is not executed in the sort processing unit; It has more.

According to the present invention, in order to compare the input frame information with each search condition in the search table, when the search conditions are sequentially read from the search table, two search conditions that are read out sequentially are read. Since the sum of the inter-code distances is small, the change of each bit when data indicating these search conditions is continuously read is reduced.
Therefore, when searching for a frame that matches any of these search conditions by sequentially matching the frame information extracted from the frame to be processed with a plurality of search conditions stored in the search table, these search conditions Therefore, the power consumption required for such a frame search process can be reduced as a whole.

It is a block diagram which shows the structure of the frame search processing apparatus concerning 1st Embodiment. It is a structural example of the search table concerning 1st Embodiment. It is another example of a structure of the search table concerning 1st Embodiment. It is a flowchart which shows the frame information write-in operation | movement concerning 1st Embodiment. It is a flowchart which shows the frame information read-out operation | movement concerning 1st Embodiment. It is explanatory drawing which shows the outline | summary of the sort system concerning 1st Embodiment. It is a flowchart which shows the sort control operation | movement concerning 1st Embodiment. It is a flowchart which shows the sort processing operation | movement concerning 1st Embodiment. It is a flowchart which shows the example of the sort operation | movement concerning 1st Embodiment. It is a graph which shows the example of a relationship between total Hamming distance and power consumption. It is explanatory drawing which shows the example of reduction of the total Hamming distance concerning 1st Embodiment. It is a block diagram which shows the structure of the frame search processing apparatus concerning 2nd Embodiment. It is a flowchart which shows the frame information read-out operation | movement concerning 2nd Embodiment. It is a flowchart which shows the sort processing operation | movement concerning 2nd Embodiment. It is a flowchart which shows the search table surface switching operation | movement concerning 2nd Embodiment.

Next, embodiments of the present invention will be described with reference to the drawings.
[First Embodiment]
First, with reference to FIG. 1, a frame search processing apparatus 10 according to a first embodiment of the present invention will be described. FIG. 1 is a block diagram illustrating a configuration of a frame search processing apparatus according to the first embodiment.

  The frame search processing device 10 searches for a frame that matches any of the search conditions by sequentially comparing frame information extracted from the frame to be processed with a plurality of search conditions stored in advance in the search table. It has a function to do. Actually, the frame search processing device 10 is realized as an independent LSI or incorporated in a communication LSI.

  The frame search processing device 10 includes a search table 1, comparison circuits 21 to 2N, a distribution circuit 3, a frame information buffer 4, a sort processing unit 5, and a sort control unit 6 as main processing circuit units.

  The search table 1 includes a semiconductor memory that stores search conditions, and has a function of storing M (M is an integer of 2 or more) search conditions in advance at each memory address. At this time, the search conditions that are sequentially read from the search table 1 when collating with one frame information are stored in the search table 1 in the order in which the sum of the inter-code distances of the two search conditions that are successively read becomes smaller. Yes.

The comparison circuits 21 to 2N are composed of N comparison circuits (N is an integer equal to or greater than 1), and sequentially executes retrieval processing for reading retrieval conditions from the retrieval table 1 and collating them with frame information. It has a function of outputting a search result indicating whether or not the search condition is met.
As the frame information, for example, various types of information such as an IP address and a MAC address included in the header information and control information stored in a part of the payload portion are used among the frames to be processed.

When N is 2 or more, that is, when the comparison circuits 21 to 2N are arranged in parallel, the distribution circuit 3 uses the input frame information of the comparison circuits 21 to 2N in order to search a plurality of pieces of frame information in parallel. It has a function of distributing to any one of them.
The frame information buffer 4 has a function of performing transmission control by temporarily storing input frame information and outputting it to the distribution circuit 3.

The sort processing unit 5 has a function of executing a sort process for rearranging the search conditions stored in the search table 1 in the order in which the sum of the inter-code distances (Hamming distances), that is, the total Hamming distance becomes smaller. doing.
The sort control unit 6 has a function of instructing the sort processing unit 5 to execute sort processing in response to a new registration notification from the outside indicating completion of registration of a new search condition for the search table 1.

  The total hamming distance is the sum of the distances between the codes (hamming distances) between two search conditions that are successively read out in all the search conditions that are read out in the search processing of one frame information, that is, one frame. This is the sum of changes in the sign of the search condition (“0” → “1” or “1” → “0”) read in the information search process.

[Operation of First Embodiment]
Next, the operation of the frame search processing apparatus 10 according to the present embodiment will be described.

First, a detailed configuration of the search table 1 will be described with reference to FIG. FIG. 2 is a configuration example of a search table according to the first embodiment.
In the search table 1, M search conditions (M is an integer of 2 or more) are registered in advance for each memory address. When the search condition is distributed to each of the comparison circuits 21 to 2N, each of the comparison circuits 21 to 2N reads the search condition from the search table 1 in one clock cycle by designating the memory address. The search condition read from the search table 1 in one clock cycle is sent to all the comparison circuits 21 to 2N. Then, after the comparison is completed, each of the comparison circuits 21 to 2N erases the search condition read from the search table 1, and reads the next search condition from the search table 1 in one clock cycle.

  Thus, each of the comparison circuits 21 to 2N repeatedly reads out the search condition from the search table 1 and compares it with the frame information, and finishes comparing all the search conditions (M) in the search table 1 with the frame information. In other words, after the elapse of M clock cycles, the search result (comparison result) is output. Each of the comparison circuits 21 to 2N deletes the frame information stored for the search process after the search result is output.

  FIG. 3 is another configuration example of the search table according to the first embodiment. The search table 1 is not limited to the above-described configuration. For example, as shown in FIG. 3, there is a configuration in which the total number of search conditions (M) is divided into L (L is an integer of 1 or more) tables. In this case, the search result is output after the elapse of M / L clock cycles.

  Next, with reference to FIG. 4, an operation when writing frame information input from the outside of the frame search processing apparatus 10 to the frame information buffer 4 will be described. FIG. 4 is a flowchart showing a frame information writing operation according to the first embodiment.

  When the frame information is input, the frame information buffer 4 first acquires free information in the internal buffer (step 100) and checks whether there is a free space (step 101). If there is a free space in the internal buffer (step 101: YES), the frame information is written into the internal buffer (step 102), and the series of operations is terminated. If there is no free space in the internal buffer (step 101: NO), the input frame information is discarded (step 103), and the series of operations is terminated. The frame information buffer 4 performs the above processing every time frame information is input.

Next, with reference to FIG. 5, an operation when the frame information is read from the frame information buffer 4 and output to the distribution circuit 3 will be described. FIG. 5 is a flowchart showing the frame information reading operation according to the first embodiment.
When outputting frame information, output permission from the comparison circuits 21 to 2N indicating that the comparison circuits 21 to 2N are empty is required.

First, the frame information buffer 4 acquires the availability information from the comparison circuits 21 to 2N (step 110), and checks whether the comparison circuits 21 to 2N are available based on whether or not there is output permission (step 110). 111). This availability information is information indicating whether or not there is a comparison circuit in a state where search processing can be started among the comparison circuits 21 to 2N, that is, a comparison circuit in an empty state. As the execution status of the search process, it is obtained by ANDing the search processing information output during the execution of the search process.
When the availability information indicates that there is no availability in all the comparison circuits 21 to 2N (step 111: NO), the frame information buffer 4 ends the series of operations without outputting the frame information.

  On the other hand, when the availability information indicates that at least one comparison circuit is available (step 111: YES), the frame information buffer 4 receives the sort control unit 6 indicating whether or not the sort processing is being performed. In-process information is acquired (step 112). This in-process information is information indicating that the sort process is in progress for a period from when the sort process unit 5 is instructed to execute the sort process until the sort process unit 5 notifies the sort process completion. Output from the control unit 6.

Here, when the processing information indicates that the sorting processing is being performed (step 113: NO), the frame information buffer 4 ends the series of operations without outputting the frame information.
When the processing information indicates that the sorting processing is not in progress (step 113: YES), the frame information buffer 4 outputs the frame information to the distribution circuit 3 (step 114), and the series of operations ends.

  Since the search process is stopped during the sort process, the frame information buffer 4 stores the frame information input from the outside during the sort process. If frame information is input during the sort process, the sort process may be interrupted and the search process may be resumed.

Next, the search condition sort control method will be described in detail with reference to FIG. FIG. 6 is an explanatory diagram illustrating an overview of the sort system according to the first embodiment.
The search condition sorting system includes a sort control unit 6 and a sort processing unit 5.
The sort control unit 6 monitors the presence / absence of frame information during search processing and registration of new search conditions, and instructs the sort processing unit 5 to execute sort processing when a predetermined condition is satisfied.
The sort processing unit 5 reads the search condition 1A in response to a sort process execution instruction from the sort control unit 6, executes a predetermined sort process, and outputs the sorted search condition 1B.

  The sort processing unit 5 sorts the search conditions, and may hold the search conditions after the sort process in the intermediate file 1C until permission to write to the search table 1 is obtained. The intermediate file 1 </ b> C is stored in a memory provided inside or outside the frame search processing device 10.

Next, the sort control unit 6 will be described in detail with reference to FIG. FIG. 7 is a flowchart showing the sort control operation according to the first embodiment.
The sort control unit 6 instructs the sort processing unit 5 to execute sort processing when a predetermined condition is satisfied.

When a new search condition is registered in the search table 1, a new search condition is registered in the search table 1 from an external host device. At this time, a new registration notification indicating completion of registration of the new search condition for the search table 1 is input from the external host device to the sort control unit 6.
First, the sort control unit 6 confirms whether or not a new search condition is registered in response to a new registration notification input from the outside (step 120). If there is a new search condition registration (step 120: YES), The presence / absence of frame information during search processing and the accumulation of frame information in the frame information buffer 4 are confirmed (steps 121 and 122).

The presence / absence of frame information during search processing is obtained, for example, by performing a logical OR operation on the search processing information output from the comparison circuits 21 to 2N during execution of the search processing. Thereby, it is confirmed whether or not the search processing is executed in the comparison circuits 21 to 2N, that is, whether or not the search conditions in the search table 1 should not be sorted.
The accumulation of frame information in the frame information buffer 4 is confirmed by the frame information accumulation information output from the frame information buffer 4 when, for example, one or more pieces of frame information are accumulated in the internal buffer. As a result, it is confirmed whether or not there is a search process in the comparison circuits 21 to 2N to be preferentially executed, and the sort process for the search condition in the search table 1 should be postponed.

Here, when there is no frame information being searched (step 121: NO) and no frame information is stored in the frame information buffer 4 (step 122: NO), the sort control unit 6 instructs to execute the sort process. (Step 123), and the series of operations is completed.
On the other hand, when there is frame information being searched (step 121: YES), or when frame information is stored in the frame information buffer 4 (step 122: YES), the sort control unit 6 issues an instruction for executing the sort processing. A series of operations are terminated without taking out.

Note that the sort control method is not limited to the above, and whether or not the number of registered new search conditions has reached a predetermined number is added to the operation as a criterion, and when the predetermined number is reached, the execution of sort processing is instructed. Sometimes. In this case, since the frequency of the sorting process can be adjusted, there is an effect of suppressing an increase in power due to the frequent sorting process when the search condition is frequently registered and deleted.
Further, the sort control unit 6 acquires the total hamming distance of the search conditions stored in the current search table 1 and adds a process for determining whether or not the total hamming distance is a predetermined number or more to the above operation. When the total Hamming distance is a predetermined number or more, execution of sort processing may be instructed.
In addition, when the new search condition is registered, the sort control unit 6 acquires the total hamming distance of the search condition stored in the search table 1 before the sort process and the total hamming distance after the sort process. The search table 1 may be updated when the value is equal to or greater than a predetermined value.

Next, the sort processing unit 5 will be described in detail with reference to FIG. FIG. 8 is a flowchart showing the sort processing operation according to the first embodiment.
The sort processing unit 5 executes the sort process in response to the sort processing execution instruction from the sort control unit 6.

  First, the sort processing unit 5 reads a search condition from the search table 1 (step 130), and executes a predetermined sort process (step 131). The contents of this sorting process will be described later. The sort processing unit 5 temporarily holds the sort results sequentially obtained by this sort processing as an intermediate file (step 132).

When sorting of all the search conditions is completed (step 133: YES), the sort processing unit 5 writes and updates the sort result held in the intermediate file in the search table 1 (step 134), and performs a series of operations. finish.
If there is a write permission from the search table 1, the sort processing unit 5 may update the search condition during the sort by writing it to the search table 1 without holding it in the intermediate file. At this time, the write permission may be confirmed by reading information output from the search table 1 during reading of the search conditions from the comparison circuits 21 to 2N, or search processing is being executed from each of the comparison circuits 21 to 2N. The search-in-progress information that is output to may be confirmed by performing a logical OR.

Next, the search condition sorting operation in the sort processing unit 5 will be described with reference to FIG. FIG. 9 is a flowchart showing the sorting operation according to the first embodiment.
The sorting of search conditions that minimize the total Hamming distance is to search for the order in which the total Hamming distance is the shortest under the constraint that all search conditions are selected once and the first search condition is returned. Although it is known that it is difficult to obtain a strict optimum solution in a realistic calculation time as an optimum solution of the sorting method, there is an approximate solution method. As an approximate solution, there is a nearest neighbor method (Nearest Neighbor method, hereinafter referred to as NN method). In this embodiment, an example of a sorting operation based on the NN method is shown as a basic sorting operation.

  First, the sort processing unit 5 appropriately (arbitrarily) selects the first search condition from among the search conditions to be sorted (step 140). Next, the sort processing unit 5 calculates the hamming distance between the selected search condition and each unselected search condition (step 141), and among the unselected search conditions, the selected search condition and the most Hamming distance. A search condition with a short distance is selected (step 142). At this time, if there are a plurality of search conditions that satisfy the condition, the number with the smaller memory address stored is given priority. It should be noted that the calculation of the Hamming distance between the search conditions may all be executed before step 140.

Next, it is determined whether or not all search conditions have been selected (step 143). If selection of all search conditions has not been completed (step 143: NO), the sort processing unit 5 returns to step 141. The hamming distance is calculated again, and the search condition closest to the current hamming distance is selected from the unselected search conditions.
On the other hand, when all the search conditions are selected (step 143: YES), the sort processing unit 5 ends a series of operations.

  Note that the sort operation for reducing the total Hamming distance is not limited to the above, and there is also an operation for changing the search condition selected first in the sort operation to execute the sort a plurality of times and adopting the sort result with the smallest total Hamming distance. . Further, recently added methods (Nearest Addition Method method) and local search methods are known as approximate solution methods for the combinatorial optimization problem, and these may be applied.

  In addition, there is an operation in which a plurality of approximate solutions are used in combination. Also, if there are parts that are common to multiple search conditions, for example, if the upper or lower bits of the search condition have the same value, the parts with different values in the search condition are targeted, that is, the parts with the same value are ignored. Then, sorting may be performed by defining the Hamming distance between two search conditions.

There is also a method of calculating a hamming distance between a newly registered search condition and an already registered search condition and registering the new search condition at a location where the hamming distance is the smallest. In this case, since it is not necessary to perform the sort process for all search conditions, the sort process can be simplified and the processing time can be reduced.
In addition, when the search condition is deleted, the sorting process may not be performed. In this case, there is no need to perform the sort process when the search condition is deleted, so that the number of times the sort process is performed can be reduced.

  In addition, there is a certain correlation between the total Hamming distance and the power consumption. FIG. 10 is a graph showing a relationship example between the total Hamming distance and the power consumption. Here, the horizontal axis indicates the total Hamming distance, and the vertical axis indicates the increase in power consumption. In any frame search processing device, frame search processing is executed using search conditions sorted using the NN method. The measured power consumption increments are plotted. According to this, it can be seen that the increase in power consumption monotonously increases as the total Hamming distance increases.

  In fact, when sorting the search conditions, it takes a calculation time with a length that cannot be ignored to obtain a sort result that minimizes the total Hamming distance. This calculation time can be shortened. In order to execute the search process for the frame information without delay, the calculation time should be shortened, thereby reducing the power consumed during the sort process.

If the graph of FIG. 10 regarding the frame search processing device 10 is obtained in advance and a target power consumption reduction amount is set, the target value of the total Hamming distance necessary to realize this can be obtained.
Therefore, the sort processing unit 5 only needs to sort the search conditions so that the total Hamming distance is not the minimum but less than the target value by switching and selecting the sort processing method and its parameters. As a result, the calculation time required for sorting the search conditions can be shortened. As a result, the delay of the search process for the frame information can be reduced, and the power consumption required for sorting the search conditions can be reduced.

  Next, an example in which the total Hamming distance is reduced by executing the search condition sorting process stored in the search table 1 will be described with reference to FIG. FIG. 11 is an explanatory diagram illustrating an example of reducing the total Hamming distance according to the first embodiment.

  As described above, the frame search processing device 10 reads search conditions from different memory addresses every clock cycle. At this time, if each bit of the read search condition has a different value from the previous read search condition, switching of the signal line of each bit occurs and power is consumed. This power depends on the Hamming distance between the two search conditions. In the present embodiment, the search conditions are read cyclically in the order of memory addresses, so that the order of reading is known in advance. Further, in this embodiment, it is not always necessary to read the search condition from the first memory address, that is, there is no restriction on the comparison order between the frame information and the search condition, and the search result obtained differs depending on the order of comparison. Absent.

  In the present embodiment, by utilizing the fact that the order in which the search conditions are read out can be grasped in advance, the search conditions arranged in random order are changed in the signal line of each bit of the search conditions to be read (“0” → “1” or “ 1 ”→“ 0 ”), that is, the sort processing is executed so that the sum of the Hamming distances (total Hamming distance) is reduced.

FIG. 11 shows an example in which the search conditions are each 8 bits long, the total number of search conditions is 6, that is, M = 6, and sorting is performed by a sort operation based on the NN method.
That is, the search condition (111101010) stored in the memory address # 2 before sorting is stored in the memory address # 4 as a result of the sorting process, and the search condition (01110101) stored in the memory address # 3 before sorting is As a result of the sorting process, it is stored in the memory address # 2.

  The search condition (10111010) stored in the memory address # 4 before sorting is stored in the memory address # 5 as a result of the sorting process, and the search condition (010110101) stored in the memory address # 5 before sorting is As a result of the sorting process, the search conditions (11010101 and 10101110) stored in the memory address # 3 and stored in the memory addresses # 1 and # 6 before the sorting are not changed in the memory address stored after the sorting.

  Next, a change in the Hamming distance between two search conditions before and after sorting will be described. Before the sorting, when the search conditions are read in the order of the memory addresses, the hamming distance from the previous search condition is “6” bits, and when the search condition read cycle is completed, that is, the search processing of one frame information is performed. When the process is completed, the sum of the Hamming distances (total Hamming distance) is “36” bits.

  On the other hand, after sorting, the hamming distance is “2” bits between the memory addresses # 1 and # 2, # 2 and # 3, # 4 and # 5, and # 5 and # 6. “20” bits. Note that the order in which the search conditions are read out when the memory addresses are read out before and after the sorting changes, but the search conditions do not change, so the search results output by the comparison circuits 21 to 2N do not change.

  As described above, according to the present embodiment, by sorting the search conditions, it is possible to reduce the power consumed by the access operation to the search table 1 necessary for the frame information search process. For example, in the search of one frame information, in the frame search processing device 10 that compares each of 128 bits and 512 search conditions, the total Hamming distance is “0” bits, that is, all search conditions have the same value, When the Hamming distance is “65536” bits (128 bits × 512 search conditions), that is, when different values are read every clock cycle, the power consumption increases by about 45 mW.

[Effect of the first embodiment]
As described above, the present embodiment executes a search table 1 that stores a plurality of search conditions in advance at each memory address, and a search process that sequentially reads the search conditions from the search table 1 and collates with the frame information. , And one or more comparison circuits 21 to 2N (N is an integer of 1 or more) for outputting a search result indicating whether or not the frame information and the search conditions match, and one frame information of the search conditions The search conditions that are sequentially read from the search table 1 when collating are stored in the search table 1 in the order in which the sum of the inter-code distances of the two search conditions that are successively read is reduced.

Thus, when sequentially reading each search condition from the search table 1 in order to compare the input frame information with each search condition in the search table 1, the code interval between two search conditions that are read sequentially Since the total sum of the distances is small, changes in each bit when data indicating these search conditions are continuously read out are reduced.
Therefore, when searching for a frame that matches one of these search conditions by sequentially matching the frame information extracted from the frame to be processed with a plurality of search conditions stored in advance in the search table 1, these searches are performed. Since the power consumption required for reading the conditions is reduced, the power consumption required for such a frame search process as a whole can be reduced.

In the present embodiment, the sort processing unit 5 executes sort processing for rearranging the search conditions stored in the search table 1 in the order in which the sum of the inter-code distances becomes smaller, and the sort control unit 6 However, the sort processing unit 5 may be instructed to execute the sort process in response to a new registration notification from the outside indicating completion of registration of the new search condition for the search table 1.
Thereby, since the search conditions are sorted according to the registration of the new search conditions for the search table 1, the sum of the inter-code distances regarding the search conditions in the search table 1 can be kept small. Therefore, even after a new search condition is registered, it is possible to maintain a state where the power consumption required for the frame search process is reduced.

  Further, in the present embodiment, a plurality of comparison circuits 21 to 2N are provided, and the distribution circuit 3 starts the search process among the comparison circuits 21 to 2N based on the execution status of the search process in the comparison circuits 21 to 2N. The frame information is distributed to any one of the possible comparison circuits, the frame information buffer 4 temporarily stores the frame information in the internal buffer, and the search processing can be started in any of the comparison circuits 21 to 2N If the sort processing unit 5 does not execute the sort process, the frame information may be acquired from the internal buffer and output to the distribution circuit 3.

  Thereby, the search processing for the sequentially inputted frame information is performed in parallel in each of the comparison circuits 21 to 2N while arbitrating the conflict with the access to the search condition of the search table 1 by the sort processing in the sort processing unit 5. It is possible to increase the throughput.

  Next, differences from Patent Document 1 described above will be described. In Patent Literature 1, the order of the memory output data is sorted and transmitted to the data receiving side so that the hamming distance in the time series of the data output from the memory is minimized, and the read data is transferred in the order of the data before sorting. return. That is, since the order of reading cannot be grasped in advance, sorting processing is necessary at the time of reading, resulting in an increase in delay.

  On the other hand, in the present invention, retrieval of retrieval conditions from the retrieval table 1 follows the order of memory addresses, so that the retrieval order of retrieval conditions can be grasped in advance. Therefore, the data can be sorted so that the total hamming distance is minimized before reading from the search table 1, that is, in the order of the memory addresses read from the stage stored in the search table 1.

In Patent Document 1, output data sorting processing is executed for each memory access. In this embodiment, the sorting frequency is reduced by sort control, so that search processing delays due to frequent sorting processing. And an increase in power consumption associated with execution of sort processing can be suppressed.
In general, the frame information input to the frame search processing apparatus changes from moment to moment (unfixed), whereas the search conditions registered in the search table 1 are relatively fixed. For this reason, the sort process is not executed when reading from the memory, but the sort process is executed in advance, and the data whose total Hamming distance is reduced can be used for a certain period.

  The method for reducing the total Hamming distance of the search table 1 is not limited to the above. For example, when the search condition to be read includes a valid bit indicating whether or not this search condition is valid, the search condition in which the valid bit is invalid is the same as the search condition to be read immediately before or next valid. By setting the same value as the search condition to become, the total Hamming distance may be reduced.

  In this embodiment, an example in which search conditions are read in the order of memory addresses has been described, but the read order of search conditions is not limited to the above. For example, a table that stores memory addresses arranged in the reading order may be provided separately, and search conditions may be read in the order of memory addresses stored in the table. In this case, the total hamming distance of the retrieval condition to be read is reduced by sorting the memory addresses.

  Further, in the present embodiment, an example in which the search process is stopped during the sort process of the search table 1 is shown, but the sort control method is not limited to the above, and there is a control method for performing the sort process even during the search process. For example, if the number of search conditions in which the valid bit is valid is smaller than the maximum number of search conditions (M) that can be registered in the search table 1, that is, if the search table 1 has an empty space, first the valid conditions are copied. Then, enable the valid bit. After the reading of the search condition has been completed, the valid bit of the original search condition is then invalidated. According to the above, the same search condition is temporarily read twice, but the sort control can be performed without affecting the search result and without stopping the search process.

[Second Embodiment]
Next, a frame search processing device 10 according to the second exemplary embodiment of the present invention will be described with reference to FIG. FIG. 12 is a block diagram illustrating a configuration of a frame search processing device according to the second embodiment.

  The difference from the first embodiment is that the search table 1 stores M search conditions in advance at each memory address (M is an integer equal to or greater than 2) and executes the reading / writing of the search conditions in parallel. It is composed of L surfaces (L is an integer equal to or greater than 2), which are possible storage area surfaces, and includes a switching control unit 6 that performs switching control of these surfaces of the search table 1. For the search table 1, for example, a general semiconductor memory such as a multi-port memory having a plurality of banks may be used.

When L is 2, it is actually used for search processing, and in addition to the surface for distributing search conditions to each of the comparison circuits 21 to 2N (hereinafter referred to as operation), registration of new search conditions and sorting of search conditions This corresponds to the provision of a standby surface (hereinafter referred to as a standby surface) used for processing.
The sort processing unit 5 executes the sort process for the search conditions stored in the standby surface of the search table 1 during the sort process.

The switching control unit 7 has a function of switching the standby side to a new operational side and switching the operational side to a new standby side in the search table 1 in accordance with the completion of the sorting process in the sort processing unit 5. Have.
Other configurations according to the present embodiment are the same as those of the first embodiment, and a description thereof is omitted here.

[Operation of Second Embodiment]
Next, as an operation of the frame search processing apparatus 10 according to the present embodiment, a case where the search table 1 is configured with an operation surface and a standby surface, that is, a case where L is 2, The difference will be described in detail.

First, with reference to FIG. 13, the operation when reading frame information from the frame information buffer 4 and outputting it to the distribution circuit 3 will be described in detail. FIG. 13 is a flowchart illustrating a frame information read operation according to the second embodiment.
In outputting frame information, output permission from the comparison circuits 21 to 2N indicating that the comparison circuits 21 to 2N are free is necessary. In this case, unlike the first embodiment, since the search process can be executed using the operation side even during the sort process, it is not necessary to confirm the in-process information from the sort control unit 6.

  First, the frame information buffer 4 acquires vacancy information from the comparison circuits 21 to 2N (step 200), and confirms whether or not the comparison circuits 21 to 2N have vacancy based on whether or not output is permitted (step 200). 201). This availability information is information indicating whether or not there is a comparison circuit in a state where search processing can be started among the comparison circuits 21 to 2N, that is, a comparison circuit in an empty state. For example, from each comparison circuit 21 to 2N, As the execution status of the search process, it is obtained by ANDing the search processing information output during the execution of the search process.

When the availability information indicates that there is no availability in all the comparison circuits 21 to 2N (step 201: NO), the frame information buffer 4 ends the series of operations without outputting the frame information.
On the other hand, when the availability information indicates that at least one comparison circuit is available (step 201: YES), the frame information buffer 4 outputs the frame information to the distribution circuit 3 (step 202), End the operation.

Next, with reference to FIG. 14, the search condition sorting process will be described in detail. FIG. 14 is a flowchart illustrating the sort processing operation according to the second embodiment.
The sort processing unit 5 executes the sort process in response to the sort processing execution instruction from the sort control unit 6.

First, the sort processing unit 5 reads a search condition from the standby surface of the search table 1 (step 210), and executes a predetermined sort process (step 211). The contents of this sort processing are the same as in the first embodiment.
The sort processing unit 5 writes the sorting results sequentially obtained by this sorting processing to the standby surface (step 212), and ends the series of operations when the sorting of all the search conditions is completed.

When the predetermined condition is satisfied, the search table 1 is updated by switching the surface. Surface switching control will be described later.
In the present embodiment, the search process can be continued even during the execution of the sort process, so that an increase in delay associated with the execution of the sort process is suppressed. Note that an intermediate file may be held until permission to write to the standby surface of the search table 1 is obtained. Also, the retrieval conditions associated with the sort process are read from the operation side or the standby side.

  Next, the switching control unit 7 will be described in detail with reference to FIG. FIG. 15 is a flowchart illustrating a search table surface switching operation according to the second embodiment.

First, the switching control unit 7 checks whether or not the sorting process in the sort processing unit 5 has been completed (step 220). For the completion of the sort process, for example, the processing information from the sort control unit 6 described above may be used.
Here, when the sorting process is completed (step 220: YES), the switching control unit 7 checks whether or not there is frame information during the search process (step 221). As for the presence / absence of the frame information during the search process, for example, the logical sum of the search process information from the comparison circuits 21 to 2N described above may be used.

When there is no frame information during the search process (step 221: NO), the switching control unit 7 performs switching to set the standby side as a new operation side and the operation side as a new standby side in the search table 1. (Step 222), the series of operations is terminated.
On the other hand, when the sort process is not completed (step 220: NO), or when there is frame information being searched (step 221: YES), the switching control unit 7 does not switch the surface of the search table 1. Finally, the series of operations is completed.

  The switching control unit 7 executes the above process every time the sort processing unit 5 performs the sort process. The sort control is not limited to the above. For example, the sorting process of the standby surface search condition may be performed immediately before switching between the standby surface and the operation surface.

[Effect of the second embodiment]
As described above, in the present embodiment, the search condition used for collation in the comparison circuits 21 to 2N during the search process is stored in the search table 1 as a storage area surface on which the search condition can be read and written in parallel. And a standby surface for storing search conditions to be sorted, and the sort processing unit 5 stores the search conditions stored in the standby surface of the search table 1 during the sorting process. Sort control is performed, and the switching control unit 7 sets the standby side of the search table 1 as a new operation side and sets the operation side as a new standby in response to the completion of the sort process in the sort processing unit 5 It is intended to perform face-to-face switching.

  As a result, the sort process is executed using the standby surface, so that the search process can be executed even during the sort process, and an increase in delay time can be suppressed. Further, by suppressing the increase in delay time associated with the search condition sorting process, it is possible to minimize the overhead of the frame information buffer 4 and the like for storing the frame information input during the sort process. For this reason, it is also possible to suppress an increase in the capacity of the frame information buffer 4 provided in the previous stage of the distribution circuit 3.

  The frame search processing device 10 described in the first and second embodiments can be realized by, for example, a computer including a CPU, a storage device, and an interface, and a program that controls these hardware resources. The CPU executes the processing described in the first and second embodiments in accordance with a program stored in the storage device.

[Extended embodiment]
The present invention has been described above with reference to the embodiments, but the present invention is not limited to the above embodiments. Various changes that can be understood by those skilled in the art can be made to the configuration and details of the present invention within the scope of the present invention. In addition, each embodiment can be implemented in any combination within a consistent range.

  DESCRIPTION OF SYMBOLS 10 ... Frame search processing apparatus, 1 ... Search table, 21-2N ... Comparison circuit, 3 ... Distribution circuit, 4 ... Frame information buffer, 5 ... Sort processing part, 6 ... Sort control part, 7 ... Switching control part.

Claims (6)

A frame search processing device that searches for a frame that matches any of these search conditions by sequentially matching frame information extracted from a frame to be processed with a plurality of search conditions stored in advance in a search table. ,
The search table for storing a plurality of search conditions in advance;
One or more comparison circuits that sequentially read out the search conditions from the search table, execute a search process for matching with the frame information, and output a search result indicating whether the frame information and the search conditions are compatible ;
A sort processing unit that executes a sort process for rearranging the search conditions stored in the search table in an order in which the sum of the inter-code distances of the two search conditions that are successively read is reduced;
A sort control unit that instructs the sort processing unit to execute the sort process in response to a new registration notification from the outside indicating completion of registration of a new search condition for the search table ,
Among the search conditions, a search condition read out from the lookup table when matching one of the frame information in the order includes, characterized in that the sum of the code distance is stored in the search table in the order in which smaller Frame search processing device. The frame search processing device according to claim 1 ,
The search table includes an operation surface for storing search conditions used for matching in the comparison circuit at the time of the search process, and a sort process as a storage area surface on which the search conditions can be read and written in parallel. And a standby surface for storing search conditions that are subject to
The sort processing unit executes the sort process for the search condition stored in the standby surface of the search table during the sort process,
In response to the completion of the sort processing in the sort processing unit, a switching control unit that switches the standby surface to a new operation surface and switches the operation surface to a new standby surface in the search table is further provided. A frame search processing device characterized by comprising: In the frame search processing device according to claim 1 or 2 ,
A plurality of comparison circuits as the comparison circuit;
Based on the execution status of the search process in the comparison circuit, a distribution circuit that distributes the frame information to any one of the comparison circuits that can start the search process;
The frame information is temporarily stored in an internal buffer, the search process can be started by any of the comparison circuits, and the sort process is not executed in the sort processing unit And a frame information buffer for acquiring the frame information from the internal buffer and outputting the frame information to the distribution circuit. Used in a frame search processing apparatus that searches frame information extracted from a frame to be processed in order with a plurality of search conditions stored in advance in a search table to search for a frame that matches any of these search conditions. A frame search processing method,
A storage step in which the search table stores a plurality of search conditions in advance;
One or more comparison circuits sequentially read out the search conditions from the search table, execute a search process for collating with the frame information, and output a search result indicating whether or not the frame information matches the search conditions. A comparison step ;
Sort processing step in which the sort processing unit executes a sort process for rearranging the search conditions stored in the search table in an order in which the sum of the inter-code distances of the two search conditions that are successively read is reduced. When,
The sort control unit includes a sort control step for instructing the sort processing unit to execute the sort process in response to a new registration notification from the outside indicating completion of registration of a new search condition for the search table ,
Among the search conditions, a search condition read out from the lookup table when matching one of the frame information in the order includes, characterized in that the sum of the code distance is stored in the search table in the order in which smaller Frame search processing method. The frame search processing method according to claim 4 , wherein
The search table includes an operation surface for storing search conditions used for matching in the comparison circuit at the time of the search process, and a sort process as a storage area surface on which the search conditions can be read and written in parallel. And a standby surface for storing search conditions that are subject to
The sort processing step executes the sort processing for the search conditions stored in the standby surface of the search table during the sort processing,
In response to completion of the sort process in the sort processing unit, the switching control unit switches the standby surface to a new operation surface and switches the operation surface to a new standby surface in the search table. A frame search processing method further comprising a switching control step. In the frame search processing method according to claim 4 or 5 ,
A plurality of comparison circuits as the comparison circuit;
A distribution step in which the distribution circuit distributes the frame information to any one of the comparison circuits capable of starting the search processing based on the execution status of the search processing in the comparison circuit;
The frame information buffer temporarily stores the frame information in an internal buffer, and the search processing can be started by any of the comparison circuits, and the sort processing is performed in the sort processing unit. And a buffer step of acquiring the frame information from the internal buffer and outputting the frame information to the distribution circuit when not executed.

Images