TWI844174B - Method and apparatus for searching for logical address ranges of host commands - Google Patents

Abstract

The invention is related to a method, a computer program product and an apparatus for searching logical address ranges of host commands. The method includes: inputting a first logical address range including a first start logical address to a first end logical address; inputting a second logical address range including a second start logical address to a second end logical address; outputting, by a first comparator, logic 0 to a NOR gate when detecting that the first end logical address is not less than the second start logical address; outputting, by a second comparator, logic 0 to the NOR gate when detecting that the second end logical address is not less than the first start logical address; and outputting, by the NOR gate, logic 1 to a match register to inform the processing unit that all or a portion of data of the first logical address range is temporarily stored in a random access memory (RAM), and outputting, by the NOR gate, logic 1 to output circuitry, thereby enabling the output circuitry to output a memory address in the RAM that stores the second logical address range to a resulting address register, when receiving logic 0 from both the first and the second comparators. With the arrangement of dedicated search engine, the processing unit could hand over the search tasks for logical address ranges requiring excessive comparisons to the search engine, and provide its computing resources to other tasks, thereby improving the overall performance of storage device.

Description

Logical address interval search method and device for host commands

The present invention relates to a storage device, and more particularly to a method and device for searching a logical address range of a host command.

Flash memory is usually divided into NOR flash memory and NAND flash memory. NOR flash memory is a random access device. The host side can provide any address to access the NOR flash memory on the address pins and obtain the data stored at the address from the data pins of the NOR flash memory in a timely manner. In contrast, NAND flash memory is not randomly accessed, but sequentially accessed. NAND flash memory cannot access any random address like NOR flash memory. Instead, the host side needs to write the value of the sequence of bytes into the NAND flash memory to define the type of request command (such as read, write, discard, erase, etc.) and the address used in this command. The address can point to a page (the smallest data block for write operations in flash memory) or a block (the smallest data block for erase operations in flash memory).

However, before actually updating the data stored in the flash memory module, the data to be written sequentially may be temporarily stored in the random access memory in the flash memory controller for a period of time. The temporarily stored data may be read by a subsequent host read command. If the temporarily stored data can be read directly from the random access memory and replied to the host, rather than performing the actual read operation from the flash memory module through the flash memory interface, the execution time of the host read command will be shortened. Alternatively, the temporarily stored data may be overwritten by a subsequent host data update command (e.g., a write command, an erase command, a discard command, etc.). If the hit data temporarily stored in the random access memory can be directly updated, the execution time of the host data update command will be shortened. The present invention proposes a method and device for searching the logical address interval of a host command, which is used to determine whether the address interval of a subsequent host command hits the logical address interval of the temporarily stored data, thereby shortening the execution time of the host command.

In view of this, how to alleviate or eliminate the deficiencies in the above-mentioned related areas is indeed a problem to be solved.

The present invention relates to an address interval search method for a host command, comprising: inputting a first logical address interval, including a first starting logical address to a first ending logical address; inputting a second logical address interval, including a second starting logical address to a second ending logical address; when a first comparator detects that the first ending logical address is not less than the second starting logical address, outputting a logical "0" to a NOR gate; when a second comparator detects that the second ending logical address is not less than the first starting logical address, outputting a logical "0" to a NOR gate; when a second comparator detects that the second ending logical address is not less than the first starting logical address, When the first comparator receives the logical address, the NOR gate outputs a logical "0" to the NOR gate; and when the NOR gate receives the logical "0" from both the first comparator and the second comparator, the NOR gate outputs a logical "1" to the matching register to notify the processing unit that all or part of the data in the first logical address interval is temporarily stored in the random access memory, and outputs a logical "1" to the output circuit to allow the output circuit to output the memory address of the second logical address interval stored in the random access memory to the result address register.

The data to be written in the second logical address range is temporarily stored in the random access memory and has not yet been written to the flash memory module.

The present specification also relates to an address interval search device for host commands, comprising: a second start register; a second end register; a first comparator; a second comparator; an NOR gate; and an output circuit. The second start register stores a second start logical address, and the second end register stores a second end logical address. The first comparator comprises a first input terminal, a second input terminal and a first output terminal, the first input terminal is coupled to the first end register, the second input terminal is coupled to the second start register, and the first output terminal is configured to output a logical "0" to the NOR gate when the first end logical address stored in the first end register is not less than the second start logical address. The second comparator includes a third input terminal, a fourth input terminal and a second output terminal, the third input terminal is coupled to the second end register, the fourth input terminal is coupled to the first start register, and the second output terminal is set to output a logic "0" to the NOR gate when the second end logic address is not less than the first start logic address stored in the first start register. The NOR gate includes a fifth input terminal, a sixth input terminal and a third output terminal, the fifth input terminal is coupled to the first output terminal, the sixth input terminal is coupled to the second output terminal, and the third output terminal is set to output a logic "1" to the matching register when both the fifth input terminal and the sixth input terminal receive a logic "0", and output a logic "1" to the output circuit. The output circuit is configured to output the memory address of the second logical address interval stored in the random access memory to the result address register when a logical "1" is received from the NOR gate, wherein the second logical address interval includes the second start logical address to the second end logical address.

One of the advantages of the above embodiment is that, through the configuration of the above-mentioned dedicated search engine, the processing unit can hand over the search task of the logical address interval that requires a large number of comparisons to the search engine, and provide its computing resources for other tasks, thereby improving the overall performance of the storage device.

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

10: Electronic devices

110: Host side

130: Flash memory controller

131: Host interface

132: Bus

134: Processing unit

135,135#0~135#7:Search engine

136: Random Access Memory

138: Direct Memory Access Controller

139: Flash memory interface

150: Flash memory module

151: Interface

153#0~153#15: NAND flash memory unit

CH#0~CH#3: Channel

CE#0~CE#3: Enable signal

310: Sequential write queue

330: Data Cache

410#0~410#7: Register group

511,523: Start register

512,524: End register

515: Matching register

516: Result address register

521: Start register

525: Project address register

526: Status register

551,553: Comparator

555: or non-gate

580:Memory access controller

591:D Flip-flop

593: Output circuit

S610~S660: Method steps

S710~S760: Method steps

Figure 1 is a system architecture diagram of an electronic device according to an embodiment of the present invention.

Figure 2 is a schematic diagram of a flash memory module according to an embodiment of the present invention.

FIG3 is a schematic diagram showing the association between an example item of a sequential write queue and an example space of a data cache according to an embodiment of the present invention.

Figure 4 is a schematic diagram of multiple search engines and corresponding register groups according to an embodiment of the present invention.

Figure 5 is a block diagram of a search engine and peripheral components according to an embodiment of the present invention.

Figure 6 is a flow chart of the execution method of the host reading command with the search engine according to the embodiment of the present invention.

Figure 7 is a flow chart of the execution method of the host write command with the search engine according to the embodiment of the present invention.

FIG8 is a schematic diagram showing the association between example items of a sequential write queue and example space of a data cache after executing an example host write command according to an embodiment of the present invention.

The following description is a preferred implementation method for completing 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 subsequent claims.

It must be understood that the words "include", "comprising" and the like used in this specification are used to indicate the existence of specific technical features, values, method steps, operation processes, elements and/or components, but do not exclude the addition of more technical features, values, method steps, operation processes, elements, components, or any combination thereof.

The words "first", "second", "third" etc. used in the claims are used to modify the elements in the claims, and are not used to indicate a priority order, a precedence relationship, or that one element precedes another element, or a temporal sequence in performing method steps. They are only used to distinguish elements with the same name.

It must be understood that when an element is described as being "connected" or "coupled" to another element, it can be directly connected or coupled to other elements, and there may be intermediate elements. Conversely, when an element is described as being "directly connected" or "directly coupled" to another element, there are no intermediate elements. Other words used to describe the relationship between elements can also be interpreted in a similar way, such as "between" versus "directly between", or "adjacent" versus "directly adjacent", etc.

Referring to FIG. 1 , the electronic device 10 includes a host side 110, a flash memory controller 130, and a flash memory module 150, and the flash memory controller 130 and the flash memory module 150 may be collectively referred to as a device side. The electronic device 10 may be implemented in electronic products such as personal computers, laptop computers, tablet computers, mobile phones, digital cameras, digital video cameras, smart TVs, smart refrigerators, and automotive electronic systems. The host interface 137 of the host end 110 and the flash memory controller 130 can communicate with each other using a communication protocol such as Universal Serial Bus (USB), advanced technology attachment (ATA), serial advanced technology attachment (SATA), peripheral component interconnect express (PCI-E), Universal Flash Storage (UFS), and embedded Multi-Media Card (eMMC). The flash interface 139 of the flash memory controller 130 and the flash memory module 150 can communicate with each other using a double data rate (DDR) communication protocol, such as Open NAND Flash Interface ONFI, double data rate switch (DDR Toggle), or other communication protocols. The flash memory controller 130 includes a processing unit 134, which can be implemented in a variety of ways, such as using general hardware (e.g., a single processor, a multi-processor with parallel processing capabilities, a graphics processor, or other processors with computing capabilities), and provides the functions described later when executing software and/or firmware instructions. The processing unit 134 receives host commands such as read commands, write commands, discard commands, and erase commands through the host interface 131, generates host data-update commands according to the type of host commands and the parameters carried therein, and schedules and executes these commands. The flash memory controller 130 further includes a random access memory (RAM) 136, which can be implemented as a dynamic random access memory (DRAM), a static random access memory (SRAM), or a combination of the two, and is used to configure space as a data buffer to store user data (also referred to as host data) read from the host end 110 and to be written to the flash memory module 150, as well as user data read from the flash memory module 150 and to be output to the host end 110. The random access memory 136 can also store data required during the execution process, such as variables, data tables, host-to-flash H2F Table, flash-to-host F2H Table, sequential update queue, etc. The flash memory interface 139 includes a NAND flash controller (NAND Flash Controller NFC), which provides the functions required when accessing the flash memory module 150, such as a command sequencer, a low density parity check (LDPC), etc.

The flash memory controller 130 may be configured with a bus architecture 132 for coupling components to transmit data, addresses, control signals, etc. These components include a host interface 131, a processing unit 134, a RAM 136, a direct memory access (DMA) controller 138, a flash memory interface 139, etc. The DMA controller 138 may transfer data between components through the bus architecture 132 according to instructions from the processing unit 134, for example, moving data from a specific data buffer in the host interface 131 or the flash memory interface 139 to a specific address in the RAM 136, and moving data from a specific address in the RAM 136 to a specific data buffer in the host interface 131 or the flash memory interface 139, etc.

The flash memory module 150 provides a large amount of storage space, usually hundreds of Gigabytes (GB) or even several Terabytes (TB), for storing a large amount of user data, such as high-resolution pictures, videos, etc. The flash memory module 150 includes a control circuit and a memory array, and the memory cells in the memory array can be configured as single-level cells (SLCs), multiple-level cells (MLCs), triple-level cells (TLCs), quad-level cells (QLCs), or any combination thereof. The processing unit 134 writes user data to the specified address (destination address) in the flash memory module 150 through the flash memory interface 139, and reads user data from the specified address (source address) in the flash memory module 150. The flash memory interface 139 uses several electronic signals to coordinate the data and command transmission between the flash memory controller 130 and the flash memory module 150, including data lines (Data Line), clock signals (Clock Signal) and control signals (Control Signal). The data line can be used to transmit commands, addresses, read and write data; the control signal line can be used to transmit chip enable (Chip Enable, CE), address extraction enable (Address Latch Enable, ALE), command extraction enable (Command Latch Enable, CLE), write enable (Write Enable, WE) and other control signals.

Referring to FIG. 2 , the interface 151 in the flash memory module 150 may include four I/O channels (hereinafter referred to as channels) CH#0 to CH#3, each of which is connected to four NAND flash memory cells. For example, channel CH#0 is connected to NAND flash memory cells 153#0, 153#4, 153#8, and 153#12. Each NAND flash memory cell may be packaged as an independent die. The flash memory interface 139 can enable NAND flash memory cells 153#0 to 153#3, 153#4 to 153#7, 153#8 to 153#11, or 153#12 to 153#15 by sending one of the enable signals CE#0 to CE#3 through the interface 151, and then read user data from the enabled NAND flash memory cells or write user data to the enabled NAND flash memory cells in parallel.

The processing unit 134 can load and execute the code of the Firmware Translation Layer (FTL) from the RAM 136, execute various host commands sent by the host end 110, and execute background operations for improving the overall performance of the storage device. The background operations can be programs such as garbage collection (GC), wear leveling (WL), read reclaim, and read refresh. Every time the FTL drives the host interface 131 to obtain a sequential update command from the host end 110, the multiple logical addresses carried by the sequential update command are pushed into the sequential update queue, and the data to be written by the sequential update command is temporarily stored in the data buffer of the RAM 136. Then, each time the FTL receives a host command (e.g., a read command, a write command, an erase command, a discard command, etc.) from the host terminal 110 through the host interface 131, it searches the entry in the sequential update queue to determine whether the sequential update queue has recorded the logical address of the host command, or all or part of the address in the logical address range of the host command. If so, it means that the data hitting the logical address or the logical address range is temporarily stored in the RAM 136, but the data has not yet been written to the flash memory module 150. The FTL can operate the temporarily stored data in the RAM 136 to speed up the execution of the host command.

In some embodiments, the sequential update queue is configured to store a logical address in each entry. The logical address may be a logical block address number (LBA Number), each LBA number pointing to a 512-byte data. Alternatively, the logical address may be a host page number (Host Page Number), each host page number pointing to a 4K-byte data. For example, if the sequential update command instructs the flash controller 130 to write data from LBA#0x1000 to LBA#0x13FF, the FTL pushes 1024 entries in the sequential update queue, each including logical addresses "0x1000" to "0x13FF". However, the above implementation will allocate a large amount of space in RAM 136 to the sequential update queue. In addition, each time the FTL receives a host command from the host end 110 through the host interface 131, it also takes a lot of time to search a large number of items in the sequential update queue and compare them one by one to determine whether at least one logical position carried in the host command already exists in the sequential update queue.

In order to reduce the space consumption of RAM 136, the embodiment of the present invention proposes a streamlined data structure for representing each item in the sequential write queue, wherein each item stores a logical address interval, including a start address and an end address. Refer to the configuration diagram of the memory space shown in FIG3. RAM 136 configures space for the sequential update queue 310 and the data buffer 330. The sequential update queue 310 is used to store the start address and the end address corresponding to the sequential update command sent by the host end 110 according to the time sequence of the sequential update command arriving at the flash memory controller 130. The sequential update command may include a host write command with a logical address length greater than 1, a host erase command, a host discard command, etc. The sequential update queue 310 can store hundreds or thousands of logical address intervals of sequential update commands. The basic operating principle of the sequential update queue 310 is to add a logical address interval of a sequential update command from the end position (which can be called enqueue), and to remove a logical address interval of a sequential update command from the start position (which can be called dequeue). In other words, the first logical address interval added to the queue will also be the first to be removed and processed, in accordance with the First-In First-Out (FIFO) principle. For example, each item in the sequential update queue 310 can store a 4-byte starting logical address and a 4-byte ending logical address, representing multiple consecutive logical addresses. The address "0x41000" of RAM 136 stores the start logic address "0x1000" and the end logic address "0x13FF" of the 0th sequential update command, and the address "0x41008" of RAM 136 stores the start logic address "0x8C0" and the end logic address "0x8DF" of the 1st sequential update command, and so on. The starting logical address "0x1000" and the ending logical address "0x13FF" represent 1024 consecutive logical addresses, the starting logical address "0x8C0" and the ending logical address "0x8DF" represent 32 consecutive logical addresses, and so on. The sequential update queue 310 can be designed as a cyclic queue (Cyclical Queue).

The data buffer 330 is used to store the data to be written by the sequential update command. For example, the space Buf#0 in the data buffer 330 stores the data to be written by the 0th host write command, and its logical address range is "0x1000" to "0x13FF"; the space Buf#1 stores the data to be written by the 1st host write command, and its logical address range is "0x8C0" to "0x8DF", and so on. RAM 136 can further store a host command basic data table (not shown in FIG. 3 ), including multiple entries, each of which records a command number, a command type, continuity, a start memory address of a logical address interval stored in a sequential update queue 310, a start memory address of data to be written stored in a data buffer 330, etc. Command types can include read “R”, write “W”, erase “E”, discard “D”, etc. Continuity can include sequential “Sqt”, random “Rnd”, etc. The FTL can know which memory space in the data cache 330 the to-be-written data corresponding to each logical address interval in the sequential update queue 310 is actually stored in through the host command basic data table.

Referring to FIG. 4 , eight dedicated search engines 135#0 to 135#7 and corresponding register sets 410#0 to 410#7 can be set in the flash memory controller 130, so that when the processing unit 134 executes the firmware to process the host command, the specified registers in the register sets 410#0 to 410#7 can be set to drive the search engines 135#0 to 135#7 to execute the search tasks in eight address intervals in parallel. After the processing unit 134 drives the search engines 135#0 to 135#7 to start working, the execution of the host command can be interrupted first and jump to execute different host commands, or background operations, without waiting for the execution results of the eight search tasks. For ease of explanation, if the search engine 135 is mentioned in the entire disclosure, it means any one of the search engines 135#0 to 135#7. If the register set 410 is mentioned, it means any one of the register sets 410#0 to 410#7 or a corresponding one. The search engine 135 can obtain the search logic address interval in the corresponding register set 410, and compare the items written sequentially in the queue 310 one by one until all or part of the search logic address interval is found to appear in any item, or until all items are compared and the search logic address interval is not found. Whenever the search engine 135 finds that all or part of the search logic address interval appears in any item, it sets the specified register in the corresponding register set 410 to notify the processing unit 134 of the successful search and the searched items. When the search engine 135 has compared all items and has not found the search logic address range, the designated register in the corresponding register group 410 is set to notify the processing unit 134 of the search failure. The processing unit 134 can read the search results from the designated registers in the register group 410 #0 to 410 #7 after a period of time, and continue to execute the host command according to the search results. Since the processing unit 134 does not need to execute these eight search tasks and can provide its computing resources for other tasks, the overall performance of the storage device is improved. Although the disclosure describes eight dedicated search engines and corresponding register sets, those skilled in the art may set more or fewer dedicated search engines and corresponding register sets in the flash controller 130 according to different system requirements, and the present invention should not be limited thereto.

Refer to the block diagram of the search engine 135 and peripheral components shown in FIG5 . The processing unit 134 can store the example items of the sequential write queue 310 shown in FIG3 to the RAM 136, and respectively set the values startA and endA of the start register 511 and the end register 512 to define a logical address interval for a search. In order to accelerate the execution of the received host command, the processing unit 134 can drive the search engine 135 by setting the start register 521. The processing unit 134 can also start the timer to count for a period of time, interrupt the execution of the host command first, and start the processing of other tasks. The start register 511 and the end register 512 can be integrated into the processing unit 134 or the search engine 135.

Initially, the match register 515 and the result address register 516 store NULL values. After the processing unit 134 sets the enable register 521 to logic "1", the enable register 521 outputs logic "1" to the memory access controller 580 and the D flip-flop 591 to enable the memory access controller 580 and the D flip-flop 591. In addition, the enable register 521 outputs logic "1" to the status register 526, indicating that the search engine 135 is now in a busy state. At each clock signal transition, the memory access controller 580 reads 8 bytes of data from the start address of the sequential write queue 310 (e.g., the memory address "0x41000" of the RAM 136), and stores the value of the first 4 bytes in the start register 523 as the start logical address startB, and stores the value of the second 4 bytes in the end register 524 as the end logical address endB. The memory access controller 580 also stores the start read address in the RAM 136 in the entry address register 525. The comparator 551 determines whether the value endA of the end register 512 is less than the value startB of the start register 523. If so, it outputs a logical "1" to the NOR gate 555, indicating that the logical address range to be searched by the processing unit 134 and the logical address range in the current read item do not overlap (that is, there is no hit); otherwise, it outputs a logical "0" to the NOR gate 555. The comparator 553 determines whether the value endB of the end register 524 is less than the value startA of the start register 511. If so, it outputs a logical "1" to the NOR gate 555, indicating that the logical address range to be searched by the processing unit 134 and the logical address range in the current read item do not overlap (that is, there is no hit); otherwise, it outputs a logical "0" to the NOR gate 555. When the NOR gate 555 receives a logical "1" from the comparator 551 or the comparator 553, it outputs a logical "0" to the D flip-flop 591, the output circuit 593 and the memory access controller 580, so as to allow the D flip-flop 591 to output a logical "0" to the matching register 515 (representing no hit), prevent the output circuit 593 from outputting the result, and allow the memory access controller 580 to continue reading the logical address interval of the next item from the sequential write queue 310. When the NOR gate 555 receives a logical "0" from both the comparator 551 and the comparator 553, it outputs a logical "1" to the D flip-flop 591, the output circuit 593 and the memory access controller 580, so as to allow the D flip-flop 591 to output a logical "1" to the match register 515 (representing a hit), so that the output circuit 593 stores the value of the item address register 525 in the result address register 516 as the searched result (that is, the starting memory address of the hit item in the RAM 136), and disables the memory access controller 580. When the memory access controller 580 searches for the last item in the sequential write queue 310 or is disabled, it outputs a logical "0" to the status register 526, indicating that the search engine 135 is now in an idle state. The matching register 515 and the result address register 516 can be integrated into the processing unit 134 or the search engine 135.

When the timer counts to this period of time, the processing unit 134 can check the status register 526 to determine whether the search engine 135 is now busy (indicating that the search is in progress) or idle (indicating that the search is completed). If the search engine 135 is busy, the processing unit 134 resets the timer to count a period of time. If the search engine 135 is idle, the processing unit 134 reads the value in the matching register 515. If the value in the matching register 515 is a logical "0", it means that no items overlapping the logical address interval startA to endA are found in the sequential write queue 310. If the value in the match register 515 is a logical "1", it means that the sequential write queue 310 contains items overlapping the logical address range startA to endA, and the processing unit 134 reads the memory address stored in the result address register 516. Then, the processing unit 134 reads the 8 bytes starting from this memory address of the RAM 136 to obtain the hit logical address range.

The above-mentioned dedicated search engine 135, together with the streamlined data structure of the items in the sequential write queue 310, can be applied to the execution process of the host read command. Referring to the flowchart of the execution method of the host read command shown in FIG6, this method is executed by the processing unit 134 when loading and executing the FTL, and is used to repeatedly receive the host read command from the host end 110, and use the sequential write queue 310 and the search engine 135 to accelerate the execution of the host read command. The detailed description is as follows:

Step S610: Obtain the logical address interval carried in the host read command.

Step S622: Set the start logical address startA and the end logical address endA of the logical address interval to the start register 511 and the end register 512 respectively.

Step S624: Set the startup register 521 to drive the search engine 135 to start searching the contents of the sequential write queue 310 to determine whether all or part of the logical address range of the host read command can be found in the sequential write queue 310.

Step S626: Start the timer to count a period of time. During this period of time, FTL can jump to execute other host commands or background operations without waiting for the search results of the search engine 135.

Step S632: Read the value of status register 526 to determine whether search engine 135 has completed the search. If the value of status register 526 is logical "0" (indicating that search engine 135 is currently in an idle state), the process continues with step S634. If the value of status register 526 is logical "1" (indicating that search engine 135 is currently in a busy state), the process continues with step S626.

Step S634: Read the value of the matching register 515 to determine whether the search engine 135 has searched for the data corresponding to the above logical address interval temporarily stored in the RAM 136. If the value of the matching register 515 is logical "1" (indicating that the temporarily stored data has been searched), the process continues to process step S636. If the value of the matching register 515 is logical "0" (indicating that the temporarily stored data has not been searched), the process continues to process step S650.

Step S636: Determine whether data needs to be read from the flash memory module 150. If yes, the process continues to process step S642. Otherwise, the process continues to process S660. The FTL can read the memory address stored in the result address register 516, and read the 4-bit starting logical address startB and the 4-bit ending logical address endB starting from this memory address of the RAM 136. The FTL determines whether the logical address interval startA to endA is completely contained in the logical address interval startB to endB. If yes, it means that the data in the logical address interval startA to endA is completely temporarily stored in RAM 136, and there is no need to read the data from the flash memory module 150. Otherwise, it means that part of the data in the logical address interval startA to endA is not temporarily stored in RAM 136, and it needs to be read from the flash memory module 150.

Step S642: Drive the flash memory interface 139 to read the required data from the flash memory module 150 (that is, the data of the logical address interval startC to endC that does not overlap between the logical address interval startA to endA and the logical address interval startB to endB).

Step S644: Merge the data temporarily stored in RAM 136 and the data read from flash memory module 150, and drive host interface 131 to reply the merged data to host end 110.

Step S650: Drive the flash memory interface 139 to read the required data (i.e., the data in the logical address range from startA to endA) from the flash memory module 150, and drive the host interface 131 to reply the read data to the host end 110.

Step S660: Read the temporarily stored data (i.e. the data in the logical address range from startA to endA) from RAM 136, and drive the host interface 131 to reply the read data to the host end 110.

For example, the FTL receives a host read command requesting to read data from logical address "0x800" to "0xFFF" (step S610), sets the values of the start register 511 and the end register 512, so that startA="0x800", endA="0xFFF" (step S622), and then sets the start register 521 to logical "1" to drive the search engine 135 to start searching the contents of the sequential write queue 310 to determine whether the logical address range of this host read command can be found in the sequential write queue 310 (step S624). After the FTL drives the search engine 135 (step S624) and starts the timer (step S626) by starting the register 521, the execution of the host read command can be interrupted and other tasks can be processed. After the timer counts this period of time, the FTL knows that the item hit by the logical address range startA="0x800" to endA="0xFFF" requested to search is stored in the memory address "0x41008" in the RAM 136 by reading the values in the status register 526, the match register 515 and the result address register 516. Next, the FTL determines that the logical address interval startA="0x800" to endA="0xFFF" partially overlaps with the logical address interval startB="0x8C0" to endB="0x8DF" of the first sequential update command (the "yes" path in step S636). The FTL searches the host-flash memory comparison table to find the physical addresses of the logical address intervals "0x800" to "0x8BF" and "0x8E0" to "0xFFF", and drives the flash memory interface 139 to read data from these physical addresses of the flash memory module (step S642). The FTL also reads the data to be written in the logical address range "0x8C0" to "0x8DF" from the space Buf#1 of the data buffer 330 according to the content of the host command basic data table, merges the temporarily stored and read data, and drives the host interface 131 to reply the merged data to the host end 110 (step S644).

The above-mentioned dedicated search engine 135, combined with the streamlined data structure of the items in the sequential write queue 310, can be applied to the execution process of the host write command. Referring to the flowchart of the host write command execution method shown in FIG. 7, this method is executed by the processing unit 134 when loading and executing the FTL, and is used to repeatedly receive the host write command from the host end 110, and use the sequential write queue 310 and the search engine 135 to accelerate the execution of the host write command. The detailed description is as follows:

Step S710: Obtain the logical address interval carried in the host write command.

The technical details of steps S722, S724, S726, S732, and S734 can be referred to the description of steps S622, S624, S626, S632, and S634 in Figure 6, respectively, and will not be elaborated for the sake of brevity.

Step S736: Determine whether a new item is added to the sequential write queue 310. If so, the process continues to process step S742. Otherwise, the process continues to process S760. The FTL can read the memory address stored in the result address register 516, and read the 4-bit starting logical address startB and the 4-bit ending logical address endB starting from this memory address of the RAM 136. The FTL determines whether the logical address interval startA to endA is completely contained in the logical address interval startB to endB. If yes, it means that the data in the logical address interval startA to endA is completely temporarily stored in RAM 136, and no new items need to be added to the sequential write queue 310. Otherwise, it means that part of the data in the logical address interval startA to endA has not been temporarily stored in RAM 136, and this part of the data in the logical address interval needs to be temporarily stored in the unallocated space of the data buffer 330, and a new item is added to the sequential write queue 310 to reflect the newly temporarily stored data to be written.

Step S742: Update the searched data temporarily stored in RAM 136 (that is, the data of the logical address interval startC to endC overlapping the logical address interval startA to endA and the logical address interval startB to endB).

Step S744: Store the remaining data to be written into the newly allocated space of the data buffer 330 (i.e., the data in the logical address range startD to endD that does not overlap between the logical address range startA to endA and the logical address range startB to endB), and add corresponding items to the sequential write queue 310.

Step S750: Store the data to be written in the logical address range from startA to endA into the newly allocated space of the data buffer 330, and add corresponding items to the sequential write queue 310.

Step S760: Update the searched data temporarily stored in RAM 136 (i.e. the data in the logical address range from startA to endA).

For example, the FTL receives a host write command requesting to write data from logical address "0x7800" to "0x83FF" (step S710), sets the values of the start register 511 and the end register 512, so that startA="0x7800", startB="0x83FF" (step S722), and then sets the start register 521 to logical "1" to drive the search engine 135 to start searching the contents of the sequential write queue 310 to determine whether the logical address range of this host write command can be found in the sequential write queue 310 (step S724). After the FTL drives the search engine 135 (step S724) and starts the timer (step S726) by starting the register 521, the execution of the host write command can be interrupted and the processing of other tasks can be started. After the timer counts this period of time, the FTL knows that the item hit by the logical address range startA="0x7800" to endA="0x83FF" requested to search is stored in the memory address "0x41010" in the RAM 136 by reading the values in the status register 526, the match register 515 and the result address register 516. Next, the FTL determines that the logical address interval startA="0x7800" to endA="0x83FF" partially overlaps with the logical address interval startB="0x8000" to endB="0x9FFF" of the second sequential update command (the "yes" path in step S736). The FTL updates the temporary data of the logical address interval "0x8000" to "0x83FF" in the space Buf#2 of the data buffer 330 as the data to be written by this host write command (step S742). FTL also stores the data to be written in the logical address range "0x7800" to "0x7FFF" to the newly allocated space Buff#4, and adds the 4th item to the sequential write queue 310 (step S744). The result after execution can be referred to the configuration diagram of the memory space shown in Figure 8.

All or part of the steps in the method described in the present invention can be implemented by computer instructions, such as the firmware translation layer (FTL) in the storage device, the driver of the specific hardware, etc. In addition, it can also be implemented in other types of programs. A person with ordinary knowledge in the relevant technical field can write the method of the embodiment of the present invention into computer instructions, and for the sake of brevity, it will not be described again. The computer instructions implemented according to the method of the embodiment of the present invention can be stored in a suitable computer-readable medium, such as a DVD, CD-ROM, USB disk, hard disk, or placed in a network server that can be accessed through a network (for example, the Internet, or other appropriate carriers).

Although Figures 1, 2, 4, and 5 contain the elements described above, it is not excluded that more additional elements may be used to achieve better technical effects without violating the spirit of the invention. In addition, although the flowcharts of Figures 6 to 7 are executed in a specified sequence, a person skilled in the art may modify the sequence of these steps without violating the spirit of the invention, so the present invention is not limited to the sequence described above. In addition, a person skilled in the art may also integrate several steps into one step, or perform more steps sequentially or in parallel in addition to these steps, and the present invention is not limited thereto.

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, the present invention covers modifications and similar arrangements that are obvious to those skilled in the art. Therefore, the scope of the claims should be interpreted in the broadest way to include all obvious modifications and similar arrangements.

310: Sequential write queue

511,523: Start register

512,524: End register

515: Matching register

516: Result address register

521: Start register

525: Project address register

526: Status register

551,553: Comparator

555: or non-gate

580:Memory access controller

591:D Flip-flop

593: Output circuit

Claims (12)

A host command logic address interval search device comprises: a second start register storing a second start logic address; a second end register storing a second end logic address; a first comparator comprising a first input terminal, a second input terminal and a first output terminal, wherein the first input terminal is coupled to the first end register, the second input terminal is coupled to the second start register, and the first output terminal is configured to store the second end register when the first end register stores the second start logic address. When the first end logic address of the second end register is not less than the second start logic address, the logic "0" is output to the NOR gate; the second comparator includes a third input terminal, a fourth input terminal and a second output terminal, wherein the third input terminal is coupled to the second end register, the fourth input terminal is coupled to the first start register, and the second output terminal is set to when the second end logic address is not less than the first start logic address stored in the first start register, Output logic "0" to the NOR gate; the NOR gate includes a fifth input terminal, a sixth input terminal and a third output terminal, wherein the fifth input terminal is coupled to the first output terminal, the sixth input terminal is coupled to the second output terminal, and the third output terminal is set to output logic "1" to the matching register when the fifth input terminal and the sixth input terminal both receive logic "0", and output logic "1" to the output circuit, representing that the first switch The interval from the starting logical address to the first ending logical address overlaps the interval from the second starting logical address to the second ending logical address; and the output circuit is configured to output the memory address of the second logical address interval stored in the random access memory to the result address register when a logical "1" is received from the NOR gate, wherein the second logical address interval includes the second starting logical address to the second ending logical address. The logical address interval search device of the host command as described in claim 1 comprises: a D flip-flop, comprising a seventh input terminal and a fourth output terminal, wherein the seventh input terminal is coupled to the third output terminal, the fourth output terminal is coupled to the matching register, and the fourth output terminal is configured to output a logical "0" to the matching register when the seventh input terminal receives a logical "0", and output a logical "1" to the matching register when the seventh input terminal receives a logical "1". A logical address interval search device for host commands as described in claim 2, wherein, when the matching register stores a logical "0", it indicates that the data in the first logical address interval from the first start logical address to the first end logical address is not temporarily stored in the random access memory; and wherein, when the matching register stores a logical "1", it indicates that all or part of the data in the first logical address interval is temporarily stored in the random access memory. The logical address interval search device for host commands as described in claim 2 includes: an activation register, which is set to allow the processing unit to set to activate the logical address interval search device for the host commands, and when set, outputs an enable signal to the D flip-flop to start outputting a signal to the matching register. The logical address interval search device for host commands as described in claim 4 comprises: a status register coupled to the activation register and the NOR gate, configured to store a logical "1" to represent that the logical address interval search device for host commands is in a busy state when the activation register is set; and to store a logical "0" to represent that the logical address interval search device for host commands is in an idle state when the NOR gate outputs a logical "1". A logical address interval search device for a host command as described in claim 1, wherein the processing unit stores the first start logical address to the first start register and stores the first end logical address to the first end register when executing the host command; wherein the first logical address interval includes the first start logical address to the first end logical address. The logical address interval search device of the host command as described in claim 4 comprises: the first start register; and the first end register. The logical address interval search device of the host command as described in claim 1 comprises: the matching register; and the result address register. A method for searching a logical address interval of a host command comprises: inputting a first logical address interval, including a first starting logical address to a first ending logical address; inputting a second logical address interval, including a second starting logical address to a second ending logical address, wherein the data to be written in the second logical address interval is temporarily stored in a random access memory and has not yet been written to a flash memory module; when a first comparator detects that the first ending logical address is not less than the second starting logical address, the first comparator outputs a logical "0" to a NOR gate; when a second comparator detects that the second ending logical address is not less than the first starting logical address, the first comparator outputs a logical "0" to a NOR gate; when a second comparator detects that the second ending logical address is not less than the first starting logical address, the first comparator outputs a logical "0" to a NOR gate; When the first comparator receives a logical address, the second comparator outputs a logical "0" to the NOR gate; when the NOR gate receives a logical "0" from both the first comparator and the second comparator, it outputs a logical "1" to the matching register, indicating that the first logical address interval overlaps the second logical address interval, so as to notify the processing unit that all or part of the data in the first logical address interval is temporarily stored in the random access memory; and outputs a logical "1" to the output circuit, so as to allow the output circuit to output the memory address of the second logical address interval stored in the random access memory to the result address register. A method for searching a logical address interval of a host command as described in claim 9, wherein when the matching register stores a logical "0", it indicates that the data in the first logical address interval is not temporarily stored in the random access memory; and wherein, when the matching register stores a logical "1", it indicates that all or part of the data in the first logical address interval is temporarily stored in the random access memory. A logical address interval search method for host commands as described in claim 9, wherein the data to be written in the second logical address interval is temporarily stored in a data cache in the random access memory. A logical address interval search method for host commands as described in claim 9, wherein the second logical address interval is stored in an item of a sequential write queue in the random access memory.

Images