TW202006565A - Apparatus and method for searching linked lists - Google Patents

Abstract

An apparatus for searching linked lists includes: a memory, a linked-list search engine and a processing unit. The memory stores a linked list. The linked-list search engine searches the content of the linked list until a success or a fail, and accordingly generates a search result. The processing unit writes the content of the linked list in the memory, drives the linked list search engine to start a search operation to the linked list and obtains the search result from the linked-list search engine.

Description

Link tandem search device and method

The invention relates to a computer device, in particular to a link tandem search device and method.

Linked tandem is a data structure that contains multiple nodes, which are aggregated into a tandem. This is a linear collection of data units, and its order is not the actual placement order in the memory. Instead, each unit will point to its next unit. Generally, each node contains data and a reference position (that is, link) that points to the next node in the sequence. Such a structure allows for efficient insertion or removal of elements at any position in the sequence. Traditionally, chained search is performed by the central processing unit, which is usually the core of the computer system. Reducing the use of the central processing unit to search the data in the link list can improve the overall performance of the system. Therefore, the present invention proposes a link serial search device and method, which uses dedicated hardware to replace the central processing unit to search the data in the link serial to improve the overall performance of the computer system.

In view of this, how to mitigate or eliminate the above-mentioned deficiencies in related fields is really a problem to be solved.

This specification provides an embodiment of a link tandem search device, which includes: a memory, a link tandem search engine, and a processing unit. The memory storage chain is serial. The link search engine searches the contents of the link list until the search succeeds or fails, and generates a search result. The processing unit writes the contents of the link string to the memory, drives the link string search engine to start the link string search operation, and obtains the search results from the link string search engine.

This specification also provides an embodiment of a link tandem search method, which is executed by a link tandem search engine and includes: obtaining the memory address of the start node of the link tandem set by the processing unit from a configuration register, and Search value; repeatedly execute a loop to sequentially acquire and process multiple nodes in the link sequence from the starting node until the search is successful or the search fails; when the search is successful, the search results and the search are successful Information, so that the processing unit obtains the search results and the information of the search success; and when the search fails, the information of the search failure is stored, so that the processing unit obtains the information of the search failure.

One of the advantages of the above embodiments is that, through the cooperation between the processing unit and the chained search engine, the chained search operation can be processed in parallel with other tasks, improving the overall performance of the electronic device.

Other advantages of the present invention will be explained in more detail with the following description and drawings.

The following description is a preferred implementation of the invention, and its purpose is to describe the basic spirit of the invention, but it is not intended to limit the invention. The actual content of the invention must refer to the scope of the following claims.

It must be understood that the words "comprising", "including", etc. used in this specification are used to indicate the existence of specific technical features, values, method steps, work processes, components and/or components, but do not exclude the addition of More technical features, values, method steps, job processing, components, components, or any combination of the above.

The terms such as "first", "second", and "third" are used in the claims to modify the elements in the claims, not to indicate that there is a priority order, pre-relationship, or an element Prior to another component, or the time sequence when performing method steps, is only used to distinguish components with the same name.

Refer to Figure 1. The link serial search device may include a processing unit 110, a memory 130, and a link serial search engine 150. Linked serial search devices can be implemented in NAND flash memory devices, or other electronic devices, to provide more efficient logical physical position conversion and other functions. The processing unit 110 can be implemented in various ways, for example, using general-purpose hardware, such as a single processor, a multiprocessor with parallel processing capabilities, a graphics processor, a lightweight general-purpose processor or other tools A processor with computing power, and when executing instructions, macrocode or microcode, it provides the function of logical entity position conversion. The memory 130 may be a dynamic random access memory (DRAM), a static random access memory (SRAM), or other types of volatile memory (volatile memory). It should be noted that the actions or operations of the processing unit 110 described below are completed when executing specific firmware, and will not be repeated for brevity. The processing unit 110 is coupled to the memory 130 and writes the contents of the link series 131 to the memory 130. Since the search of the link string 131 takes a period of time, the link string search device of the embodiment uses the link string search engine 150 to complete the search operation, so as not to consume the computing power of the processing unit 110. The link serial search engine 150 is dedicated hardware, coupled to the memory 130, and is used to search the contents of the link serial 131 until the search succeeds or fails, and generates search results. The search results can be stored in a pre-allocated area in the memory 130 or a dedicated register (not shown in FIG. 1). In addition, in order for the link serial search engine 150 to search data in various link serials 131, the link serial search device may provide a configuration register 170 for storing each link in the link serial 131 The data structure of each node, the memory address of the first node to be searched, the search direction, and the value to be searched. The configuration register 170 can be integrated into the link tandem search engine 150, and the present invention is not limited thereby. The processing unit 110 is coupled to the configuration register 170, and can notify the link serial search engine 150 how to search the content of the link serial 131 by setting the configuration register 170. After the processing unit 110 writes the content of the link string 131, the link string search engine 150 is driven to start the search operation of the link string 131, and the search result is obtained from the link string search engine 150.

Refer to Figure 2. This method is executed by the chained search engine 150. The link tandem search engine 150 obtains the memory address of the first node (also called the starting node) to be searched and the value to be searched from the configuration register 170 (step S210). Next, the link series search engine 150 repeatedly executes a loop (steps S230, S250, and S270) to sequentially acquire and process the nodes in the link series 131 from the starting node until the search is successful (step S230 "Yes" path) or search failure ("Yes" path in step S250). After acquiring the first or next node from the memory 130 each round (step S210 or S270), it is determined whether the acquired node contains the value to be searched by the processing unit 110 (step S230). If the search is successful ("Yes" path in step S230), the link tandem search engine 150 stores the search results and information on the search success, so that the processing unit 110 can obtain the search results and the information on the search success (step S240), search The result may include information such as the memory address of the searched node, the corresponding result, and the number of searches. If the search fails ("No" path in step S230), it is determined whether this node is the last node (step S250). If the last node has been reached ("Yes" path in step S250), the chained search engine 150 stores the information about the search failure, so that the processing unit 110 can obtain the information about the search failure (step S260). If the last node has not been reached (the "No" path in step S250), the link tandem search engine 150 reads the content of the next node from the memory 130 according to the next node address of this node (step S270). The content of each node in the chain and the search details with different hardware circuits will be described as follows.

It should be noted that those with ordinary knowledge in the technical field can modify Fig. 2 to make the search of the link list start from the last node (also called the starting node) until the search is successful or the search fails until.

In some embodiments, when the link serial search engine 150 searches the link serial 131, the processing unit 110 may process other tasks in parallel and access the memory 130 or the dedicated register after a period of time to try to obtain the search result. When there is no result in the memory 130, the processing unit 110 may first transfer to other tasks and check again after a period of time. In other embodiments, after the search of the link serial search engine 150 is completed, a signal (such as an interrupt signal) may be sent to the processing unit 110, so that the processing unit 110 may start to obtain search results. In still other embodiments, after the search of the link serial search engine 150 is completed, the processing unit 110 may be notified of the search result information through a status register (not shown in FIG. 1). The processing unit 110 may periodically access the status register, and obtain the search result when the status register is set. Through the cooperation between the processing unit 110 and the link serial search engine 150, the search operation of the link serial 131 can be processed in parallel with other tasks, improving the overall performance of the electronic device. That is, while the link serial search engine 150 searches the content of the link serial 131, the processing unit 110 executes tasks in parallel.

Since the NAND flash memory device is not a random access device, in order to improve the efficiency of writing, the master device (not shown in FIG. 1) can provide at least one length of continuous data, such as 128K bytes of data, so that the flash memory The device can write data into several storage subunits in an efficient parallel operation mode. After successfully writing the user data in a logical location, the flash memory device updates the correspondence between the logical location and the written physical location in the temporary storage mapping table temporarily stored in the memory 130. In addition, after successfully writing user data of a predetermined number of logical locations, the non-volatile flash memory unit (not shown in FIG. 1) is updated according to the contents of the temporary temporary physical storage comparison table. Table (storage mapping table, also known as H2F Host-to-Flash table). Refer to Figure 4. The physical storage comparison table 410 sequentially stores physical location information corresponding to each logical location. The space required for the physical storage comparison table 410 varies from 64M to 1G bytes. The logical position can be represented by a logical block address (Logical Block Address LBA), and each LBA corresponds to a fixed-size physical storage space, such as 512 bytes. For example, the physical storage comparison table 410 sequentially stores physical location information from LBA0 to LBA65535. Data from several consecutive logical locations (such as LBA0 to LBA7) can form a host page. The physical location information 430 can be represented by four bytes: the first two bytes 430-0 record the physical block number (physical block number); the last two bytes 430-1 record the unit number (unit number). For example, the physical location information 430 corresponding to the logical location LBA2 may point to a physical area 451 in the physical block 450. Byte 430-0 records the number of the physical block 450, and byte 430-1 records the unit number of the physical area 451.

Since NAND flash memory devices often receive a certain sequence of main page read requests from the main device, the link tandem search device can be used to speed up the logical physical location conversion of these main pages. Refer to Figure 3. The link series 131 may include 10 nodes 300 to 390, and each node may store long word data, that is, 16-byte data. For each node, bytes 0 to 3 store the memory address pointing to the previous node (also known as the previous node address), and bytes 4 to 7 store the memory address pointing to the next node (and Known as the next node address), the 8th to 11th bytes store the main page number, and the 12th to 15th bytes store the corresponding physical location information. The address of the previous node can store a false value (NULL value, such as 0xFFFFFFFF) to indicate that this node is the first node in the chain, and the address of the next node can store a false value to indicate that this node is the chain The last node of the column. For example, nodes 300 and 390 are the first and last nodes of the chain. The starting address of node 300 is 0x00000000, the starting address of node 310 is 0x00000010, and so on. The next node address of node 300 points to the memory address 0x00000010 (that is, the starting address of node 310), and the next node address of node 310 points to the memory address 0x00000020 (that is, the starting address of node 320), So on and so forth. The previous node address of node 390 points to the memory address 0x00000080 (that is, the starting address of node 380), and the previous node address of node 380 points to the memory address 0x00000070 (that is, the starting address of node 370), So on and so forth. The main page label stored by node 300 is 0x00000033 and the corresponding physical location information is variable PA0, the main page label stored by node 310 is 0x00000044 and the corresponding physical location information is variable PA1, and so on, the values of variables PA0 to PA9 are processed by Fill in unit 110. Although the embodiments of the present invention arrange the nodes 200 and 290 of the link series 131 according to the sequential order of the addresses of the memory 130 to facilitate reading, but after several insertions and deletions, the order of the nodes 300 and 390 is usually Does not match the address order of the memory 130.

5 to 7 are block diagrams of a link tandem search engine according to an embodiment of the present invention, for implementing the link tandem search method described in FIG. 2.

Refer to Figure 5. The link tandem search engine 500 may include a configuration register 170, a reading circuit 520, a FIFO buffer 530, a comparator 540, writing circuits 550 and 560, and a result register ( result register) 590. The processing unit 110 can set a configuration register 170 to store the starting address of the first node, the data structure information of each node (for example, the offset of the previous node address, the address of the next node) Offset, comparison data offset and corresponding result offset, etc.), search value and search direction. When the processing unit 110 enables the link serial search engine 500, the reading circuit 520 can read the address of the first node under the previous node, the comparison data and the link node 131 according to the content of the configuration register 170 Corresponding results, and output the comparison data and corresponding results to the FIFO buffer 530. In addition, the reading circuit 520 may output the start address of the first node to the FIFO buffer 530. The comparator 540 compares the search value of the configuration register 170 with the comparison data of the FIFO buffer 530. When the two are different, the enable signal EN1 is output to the reading circuit 520 to drive the reading circuit 520 to read from the link serial 131 Take the content of the next node. The reading circuit 520 can determine whether any nodes have not yet been processed, for example, whether the address of the next or previous node is not a false value. If so, the reading circuit 520 can read the above-mentioned content of the next or previous node from the link serial 131 according to the content of the configuration register 170 and the address of the next or previous node, and Part output to FIFO buffer 530. If not, the reading circuit 520 outputs the enable signal EN3 to the writing circuit 560, and the writing circuit 560 is driven to store the information about the search failure to the result register 590. When the comparator 540 determines that the search value of the configuration register 170 is the same as the comparison data of the FIFO buffer 530, it outputs an enable signal EN2 to the write circuit 550, and drives the write circuit 550 to store the corresponding result of the FIFO buffer 530 and the current search node The starting address of, and the successful search information to the result register 590. For example, the 0th to 3rd bytes of the result register 590 store the corresponding results of the search, the 4th to 7th bytes store the starting address of the current search node, and the 8th byte stores the information about the success or failure of the search . When the search is successful, the 8th byte can be set to 1; otherwise, it is set to 0.

In order to allow the processing unit 110 to optimize the order of the nodes in the link string 131, in some embodiments, the link string search engine 500 may include a counter 580, coupled to the comparator 540 and the write circuit 550, each time The initial search job starts at 0. Each time the search value of the configuration register 170 and the comparison data of the FIFO buffer 530 are compared, the comparator 540 increments the counter 580 by one. When the comparator 540 determines that the search value of the configuration register 170 and the comparison data of the FIFO buffer 530 are the same, the drive write circuit 550 stores the value of the counter 580 to the result register 590. For example, the 9th byte of the result register 590 stores the value of the counter.

The comparison data of each node may include compound data, for example, two or more different types of data. In some embodiments, the processing unit 110 may set a configuration register 170 to use 4 bytes to store a mask. The comparator 540 can perform a logical AND operation on the comparison data of the FIFO buffer 530 and the mask of the configuration register 170 to generate the comparison data after masking, and then determine whether the search value of the configuration register 170 and the comparison data after masking the same. If it is, the comparator 540 drives the writing circuit 550 to store the corresponding result of the FIFO buffer 530 and the starting address of the current search node, and the information of the successful search to the result register 590. For example, as shown in FIG. 3, the first two bytes of the main page number are the numbers of the T1 table, and the last two bytes are the numbers of the T7 table. When the search value of the configuration register 170 is the number of the T1 table, the processing unit 110 can store the mask 0xFFFF00000 to the configuration register 170, so that the comparator 540 can ignore the last two bytes of the main page number (that is, the number of the T7 table) . When the search value of the configuration register 170 is the number of the T7 table, the processing unit 110 can store the mask 0x0000FFFF to the configuration register 170, so that the comparator 540 can ignore the first two bytes of the main page number (that is, the number of the T1 table) .

The comparison data of each node may contain bits that do not need to be compared, for example, the most significant bit (Most Significant Bit). In some embodiments, the processing unit 110 may set a configuration register 170 to use 1 byte to store the information of the ignored bits. For example, 0x1F represents that the 31st bit of the comparison data can be ignored. The comparator 540 can generate a mask based on the information of the ignored bits, perform a logical AND operation on the comparison data of the FIFO buffer 530 and the mask, and then determine whether the search value of the configuration register 170 and the comparison data after the mask are the same. If it is, the comparator 540 drives the writing circuit 550 to store the corresponding result of the FIFO buffer 530 and the starting address of the current search node, and the information of the successful search to the result register 590. For example, when the ignore bit is the 31st bit, the mask is 0x7FFFFFFF.

Refer to the link series 131 of FIG. 3. Suppose that the 0th to 3rd bytes of the configuration register 170 store the starting address of the first node as 0x00000000, the 4th to 7th bytes store the search value 0x00000077, and the 8th byte store the search direction as forward search, The 9th to 12th bytes respectively store the offset of the previous node address of each node as 0x00, the offset of the next bit node as 0x04, the offset of the data as 0x08 and the offset of the corresponding result It is 0x0C, and the offset is in bytes. After the processing unit 110 enables the chain search engine 500, the comparator 540 finds the search value 0x00000077 at the node 340, and drives the write circuit 550 to store the corresponding result of the FIFO buffer 530 [PA4], the starting address of the node 340 0x40, and the successful search information to the result register 590. In addition, the comparator 540 may further trigger the write circuit 550 to store the counter value (that is, 5) to the result register 590.

Refer to Figure 6. Since the firmware may have more than two commonly used configuration settings, the link tandem search engine 600 may further include shortcut registers 610_1 and 610_2 to allow the processing unit 110 to store two sets of configuration settings in the shortcut registers 610_1 and 610_2, respectively, in which Each set of configuration settings may include the memory address, search value, and data structure information of each starting node of the link series 131. Each set of configuration settings may further include information about masking or ignoring bits as described above. The link tandem search engine 600 further includes a multiplexer 630 whose input is coupled to the outputs of the shortcut registers 610_1 and 610_2, and whose output is coupled to the input of the configuration register 170. The processing unit 110 may output the selection signal SE to the multiplexer 630 to couple one of the shortcut registers 610_1 and 610_2 to the configuration register 170 so that the configuration register 170 can store the configuration settings in the coupled shortcut register. Although the embodiment of FIG. 6 includes only two shortcut registers, those skilled in the art can modify the link tandem search engine 600 to include more shortcut registers, and the present invention is not limited thereby. The structure, function and operation details of other elements in FIG. 6 can refer to the description of FIG. 5, and will not be repeated for brevity.

Refer to Figure 7. In order to make parallel operations more efficient, the link tandem search engine 700 can provide multiple search capabilities, allowing the processing unit 110 to provide multiple search values at a time and then transfer to other tasks, which is advantageous for the processing unit 110 to arrange links Serial 131 searches and other tasks optimize the overall performance of the system. The processing unit 110 may allocate a fixed area in the memory 130 for storing multiple search records 710 and for the link serial search engine 700 to write the result records 790. Each search record includes a start flag and a search value. The start flag is used to notify the link list search engine 700 whether it can start searching the link list 131. Each result record 790 is associated with a search record 710, including the end flag, the result flag, the number of searches, and the memory address of the searched node. The end flag and the result flag are used to notify the processing unit 110 of the search value. Whether the search has ended and whether it has been searched. The search record 710 and the result record 790 can be integrated together for easy access.

The reading circuit 720 can check whether there is a record with a start flag of 1 (indicating that the search can be started) and an end flag of 0 (indicating that the search has not ended). Once a qualified record is found, the reading circuit 720 stores the search value of the record in the configuration register 170. For the operation of the reading circuit 520, reference may be made to the relevant description in FIG. When the reading circuit 520 finds that no node can be searched, it outputs the enable signal EN3 to the writing circuit 730, and drives the writing circuit 730 to store the search value and the information of the search failure to the FIFO buffer 750. The write circuit 730 can further store the number of nodes of the link series 131 in the FIFO buffer 750 as the number of searches. When the comparator 740 determines that the search value of the configuration register 170 and the comparison data of the FIFO buffer 530 are the same, the corresponding result of the FIFO buffer 530, the starting address of the current node, and the information of the successful search are stored in the FIFO buffer 750 . The comparator 740 may further include a counter, which is initially 0 before the search starts. Each time the search value of the configuration register 170 is compared with the comparison data of the FIFO buffer 530, the counter is incremented by one. When the comparator 740 determines that the search value of the configuration register 170 and the comparison data of the FIFO buffer 530 are the same, it further stores the value of the counter in the FIFO buffer 750 as the number of searches. When the data enters the FIFO buffer 750, the writing circuit 760 writes the content of the FIFO buffer 750 to the result record 790, and outputs an enable signal EN4 to the reading circuit 720 for reading the next search record 710.

每筆記錄可使用13個位元組儲存資料，其中，1個位元組紀錄開始旗標Start[4]（第4位元）及結束旗標Done[0] （第0位元），4個位元組紀錄搜索值Pattern[31:0]（所有位元），4個位元組紀錄結果旗標Result[31]（第31位元）及搜索次數Effort[30:0] （第0至30位元），4個位元組紀錄搜索到節點的記憶體位址Address[31:0]（所有位元）。開始旗標可視為致能鏈結串列搜索引擎700的訊號。初始時，處理單元110寫入四個搜索值0x000000AA、0x00000044、0x00000052及0x00000055，並將前二個搜索值的開始旗標設為1。In the following, with the link chain 131 of FIG. 3, a few examples are given to illustrate the operation of the link chain search engine 700. Search record 710 and result record 790 can be integrated into a table, the initial as shown in Table 1: Table 1

Each record can use 13 bytes to store data, including 1 byte record start flag Start[4] (4th bit) and end flag Done[0] (0th bit), 4 Byte record search value Pattern[31:0] (all bytes), 4-byte record result flag Result[31] (31st byte) and search frequency Effort[30:0] (0th To 30 bytes), 4 bytes record to find the memory address of the node Address[31:0] (all bytes). The start flag may be regarded as a signal enabling the search engine 700 to be linked. Initially, the processing unit 110 writes four search values 0x000000AA, 0x00000044, 0x00000052, and 0x00000055, and sets the start flag of the first two search values to 1.

寫入電路760在第一筆紀錄中將結束旗標Done[0]設為1，將結果旗標Result[31]設為1，將搜索次數Effort[30:0]設為8，將搜索到節點的記憶體位址Address[31:0]設為0x00000070。Next, the link list search engine 700 searches the node 370 of the link list 131 for the value 0x000000AA, and the update result is shown in Table 2: Table 2

The writing circuit 760 sets the end flag Done[0] to 1 in the first record, sets the result flag Result[31] to 1, sets the number of search Effort[30:0] to 8, and searches for The memory address Address[31:0] of the node is set to 0x00000070.

Next, the processing unit 110 adds the two search values 0x00000066 and 0x00000067, and sets all the remaining start flags to 1, and the update results are shown in Table 3: Table 3

Next, the link list search engine 700 searches the node 310 of the link list 131 for the value 0x00000044, but the value 0x00000052 is not found. Then, the link list search engine 700 searches the node 320 of the link list 131 for the value 0x00000055. The above results are updated as shown in Table 4: Table 4

Those of ordinary skill in the art can combine the link serial search engines 500 to 700 of FIGS. 5 to 7 into a link serial search engine, and each element except the register shares a mode signal. The processing unit 110 can configure the link tandem search engine to be one of those shown in FIGS. 5 to 7 through the mode signal.

Although the elements described above are included in FIGS. 1, 5-7, it does not exclude the use of more other additional elements without violating the spirit of the invention, and a better technical effect has been achieved. In addition, although the flowchart in FIG. 2 is executed in a specified order, without violating the spirit of the invention, a person skilled in the art can modify the order between these steps on the premise of achieving the same effect. Therefore, the present invention does not It is not limited to use only the order described above. In addition, those skilled in the art can also integrate several steps into one step, or in addition to these steps, perform more steps sequentially or in parallel, and the present invention is not limited thereby.

Although the present invention is described using the above embodiments, it should be noted that these descriptions are not intended to limit the present invention. On the contrary, this invention covers obvious modifications and similar settings for those skilled in the art. Therefore, the scope of the claims of the application must be interpreted in the broadest way to include all obvious modifications and similar settings.

110‧‧‧Processing unit

130‧‧‧Memory

131‧‧‧Chain

150‧‧‧Linked Search Engine

170‧‧‧Configuration register

S210~S270‧‧‧Method steps

300~390‧‧‧node

410‧‧‧ physical storage comparison table

430‧‧‧Physical location information

430-0‧‧‧Entity block number

430-1‧‧‧ The starting unit number of the main page

450‧‧‧ physical block

451‧‧‧Main page

500, 600, 700 ‧‧‧ link search engine

520, 720‧‧‧ reading circuit

530, 750‧‧‧ FIFO buffer

540、740‧‧‧Comparator

550, 560, 730, 760‧‧‧ writing circuit

590‧‧‧Result register

610_1, 610_2 ‧‧‧ shortcut register

630‧‧‧Multiplexer

710‧‧‧ search record

790‧‧‧Result record

EN1~EN4‧Enable signal

SE‧‧‧Select signal

FIG. 1 is a block diagram of a link serial search device according to an embodiment of the invention.

FIG. 2 is a flowchart of a method of link tandem search according to an embodiment of the present invention.

FIG. 3 is a schematic diagram of a chain of links according to an embodiment of the invention.

FIG. 4 is a schematic diagram of physical storage comparison according to an embodiment of the invention.

5 to 7 are block diagrams of a chained search engine according to an embodiment of the present invention.

110‧‧‧Processing unit

130‧‧‧Memory

131‧‧‧Chain

150‧‧‧Linked Search Engine

170‧‧‧Configuration register

Claims (20)

A link tandem search device includes: a memory storing a link tandem; a link tandem search engine, coupled to the memory, for searching the contents of the link tandem until the search is successful or Until the search fails, and a search result is generated; and a processing unit, coupled to the memory and the link serial search engine, is used to write the contents of the link serial to the memory to drive the link The tandem search engine starts the search operation of the link tandem, and obtains the search result from the link tandem search engine. The link serial search device according to claim 1, comprising: a configuration register coupled to the processing unit and the link serial search engine; wherein, the link serial includes a plurality of nodes, each of which The node contains the next or previous node address, a comparison data and a corresponding result, wherein the processing unit sets the configuration register to store the memory address of a starting node of the link series, a search value and each A data structure information of the node, wherein the link serial search engine searches the link serial according to the content of the configuration register. The link serial search device according to claim 2, wherein the data structure information of each of the nodes includes the offset of the next or previous node address, the offset of the comparison data, and the corresponding result Offset. The link serial search device according to claim 1, wherein the link serial includes a plurality of nodes, and each of the nodes includes the next or previous node address, a comparison data, and a corresponding result, the comparison data Contains a main page number of a physical storage comparison table, and the corresponding result includes a physical location of the physical storage comparison table. The link tandem search device according to claim 1, wherein the processing unit executes a task in parallel while the link tandem search engine searches the link tandem content. The link tandem search device according to claim 1, wherein the link tandem includes a plurality of nodes, and the link tandem search engine includes: a first write circuit; a second write circuit; A configuration register, wherein the processing unit sets the configuration register to store the memory address, a search value, and the data structure information of each node of the starting node of the link series; a first reading circuit, Coupled to the configuration register and the first writing circuit, for sequentially reading the node in the link series according to the content of the configuration register, and when no node in the link series can be read, Driving the first writing circuit to store information about the search failure, so that the processing unit obtains the information about the search failure; and a comparator, coupled to the configuration register, the reading circuit, and the second writing circuit, for When it is determined that the search value of the configuration register is the same as a comparison data of one of the nodes, the second write circuit is driven to store a starting address and a corresponding result of the searched node, and The successful search information enables the processing unit to obtain the starting address and the corresponding result of the searched node, and the successful search information. The link tandem search device according to claim 6, wherein, when the comparator determines that the search value of the configuration register is different from the comparison data of one of the nodes, the first reading circuit is driven Read the next or previous node in the link list. The link tandem search device according to claim 6, wherein the link tandem search engine includes: a counter, coupled to the comparator and the second writing circuit, initially at the beginning of each search operation is 0, wherein each time the search value of the configuration register and the comparison data of one of the nodes are compared, the comparator increments the counter by 1, and when the search value of the configuration register is judged and the node When one of the comparison data is the same, the comparator drives the second writing circuit to store the value of the counter, so that the processing unit obtains the value of the counter. The link serial search device according to claim 6, wherein the processing unit sets the configuration register to store a mask, and the comparator compares the comparison data of each node with the mask Logic and operation to generate a post-mask comparison data, when it is determined that the post-mask comparison data is the same as the search value, the second write circuit is driven to store the starting address and the correspondence of the searched node Results, and information about the success of the search. The link serial search device according to claim 6, wherein the processing unit sets the configuration register to store information of ignored bits, wherein the comparator generates a mask based on the information of ignored bits The comparison data of each node and the mask perform a logical AND operation to generate a post-mask comparison data. When it is determined that the post-mask comparison data is the same as the search value, the second writing circuit is driven to The starting address and the corresponding result of the searched node are stored, as well as information on the successful search. The link tandem search device according to claim 6, wherein the first writing circuit stores the starting address and the corresponding result of the searched node, and information on the successful search to a result register. The link tandem search device according to claim 6, wherein the link tandem search engine includes: a first shortcut register to store a first set of configuration settings; a second shortcut register to store a second set Configuration settings; and a multiplexer coupled to the first shortcut register, the second shortcut register and the configuration register, wherein the processor outputs a selection signal to the multiplexer to use the first shortcut register and One of the second shortcut registers is coupled to the configuration register so that the configuration register stores the set of configuration settings in the coupled shortcut register. The link serial search device according to claim 6, wherein the memory stores multiple search records, and the link serial search engine includes: a second reading circuit coupled to the configuration register for Read the search value indicating that the search can be started but not yet ended in the search record, and store the indicated search value in the configuration register. The link tandem search device according to claim 13, wherein the processing unit provides the search value in the search record. The link tandem search device according to claim 13, wherein the first writing circuit stores the starting address and the corresponding result of the searched node, and the information of the successful search to the corresponding memory It is a record of the results indicating the search value. A link tandem search method, executed by a link tandem search engine, includes: obtaining the memory address of a starting node of a link tandem set by a processing unit from a configuration register, and a search value; Repeatedly execute a loop to sequentially acquire and process multiple nodes in the link sequence from the starting node until the search is successful or the search fails; when the search is successful, store a search result and the search is successful Information, so that the processing unit obtains the search result and the information of the successful search; and when the search fails, the information of the failed search is stored, so that the processing unit obtains the information of the failed search. The link tandem search method according to claim 16, wherein the processing unit executes a task in parallel while the link tandem search engine searches the link tandem content. The method for searching a chain link according to claim 16, wherein the chain link includes a plurality of nodes, and each of the nodes includes the address of the next or previous node, a comparison data, and a corresponding result. The link tandem search method according to claim 18, wherein the comparison data includes a main page number of an entity storage comparison table, and the corresponding result includes an entity location of the entity storage comparison table. The link serial search method according to claim 16, wherein the link serial includes a plurality of nodes, the configuration register stores data structure information of each node, and each of the link serials The content of the node is obtained based on the data structure information.

Images