Methods and systems for software based prefetching for low buffer depth sequential read traffic

A system and related method, including storage circuitry and a control circuitry, which while executing a storage device driver, is to receive at least one instruction of a stream of instructions for the storage device. The control circuitry determines that a hardware buffer of the storage device is storing less than two instructions. In response to the determination that the hardware buffer of the storage device is storing less than two instructions, the control circuitry accesses data associated with an address of the memory of the storage device, wherein the address is predicted based on analysis of the stream of instructions and causes to be stored the data in a buffer of a plurality of buffers. The control circuitry executes an instruction of the stream of instructions using at least the data stored in the buffer.

TECHNICAL FIELD

The present disclosure is related to host device systems and related methods for software-based prefetching for low hardware buffer depths in a storage device, wherein the host device is executing a storage device driver. More particularly, this present disclosure is related to analyzing, by host software, received read instructions in order to predict a stream of instructions and prefetch data from memory based on the prediction in order to improve latency of streams of spatially sequential read instructions.

SUMMARY

In accordance with the present disclosure, systems and methods are provided for software-based prefetching that operates on a host device. More particularly, a host device that is communicatively coupled to a storage circuitry, such as on a solid-state drive (SSD) with a low instruction hardware buffer depth, while the host device is executing a storage device driver. In some embodiments, the storage circuitry (e.g., SSD device) may be located within the host device or be connected to a host via a suitable cable. For example, a storage host device may include storage circuitry (e.g., SSD device), control circuitry, and additional memory (e.g., RAM that is faster than SSD memory). In some embodiments, the storage circuitry may be an SSD or other suitable storage non-volatile memory drive, which contains a hardware buffer.

In one approach, the current technique is performed when the hardware buffer comprises less than two outstanding hardware instructions (e.g., exactly one hardware instruction). The software-based prefetching may be implemented at least in part on the control circuitry using software, hardware, or a combination thereof. In some embodiments, when the hardware buffer of the storage circuitry has a low buffer depth (e.g., one outstanding hardware instruction stored in hardware buffer), without software-based prefetching, the control circuitry must access data for incoming hardware instructions directly from the storage device without benefit of pipelining or pre-fetching, which may cause larger latencies. To solve this problem, prefetching may be initiated by software at the host-level (e.g., by the storage device driver) when the number of outstanding hardware instructions in the hardware buffer is low. This approach reduces latency of accessing memory by the storage device driver storing data in a buffer provisioned on a memory device that has shorter access times (e.g., RAM memory), reducing the overall latency of storage access.

In some embodiments, the software-based (e.g., driver based) prefetching can be used to improve instruction processing efficiency at low hardware buffer depth of any suitable host device having control circuitry executing a device driver, coupled to a hardware buffer. In some embodiments, the device may, for example, be any suitable host device that is executing a memory device driver.

In some embodiments, the host device is provided having a control circuitry and storage circuitry that is communicatively coupled to each other. In some embodiments, the control circuitry includes a processor, a software instruction buffer, and a storage device driver with a plurality of buffers. In some embodiments, the control circuitry (e.g., while executing the storage device driver) is configured to incrementally receive a stream of read instructions to be executed by the control circuitry. The control circuitry further determines, while executing a storage device driver, that the hardware buffer of the storage circuitry currently stores less than two hardware instructions (i.e., or exactly one hardware instruction). In some embodiments, when the control circuitry determines that the hardware buffer currently stores less than two hardware instructions (i.e., or exactly one hardware instruction), the control circuitry predicts addresses of future read instructions based on the received read instructions of the stream of instruction. The control circuitry then accesses data associated with a predicted address of the memory of the storage circuitry and stores that data in the software buffer. In some embodiments, when the control circuitry later receives the predicted software read instruction, the control circuitry fulfills by prefetching at least the data stored in the software buffer. In some embodiments, the received stream of instructions may be received from the operating system of a host, from another application executing on the host, or from a device other than the host device.

DETAILED DESCRIPTION

In accordance with the present disclosure, host device systems and methods are provided for software-based (e.g., storage device driver-based) prefetching for low hardware buffer depths in storage circuitry to improve the operational quality of the host system (e.g., improve latency when a hardware buffer has a low number of outstanding hardware instructions). In some embodiments, the hardware buffer (e.g., of the storage circuitry) may be an instruction stack or an instruction queue for the storage circuitry. In some embodiments, the hardware buffer and storage circuitry may be located outside of the host device (e.g., connected via a suitable cable). A host device may have a control circuitry that executes a storage device driver for controlling the storage device. The storage device driver may provide a plurality of buffers (e.g., using RAM of the host device). In some embodiments, control circuitry of the host device may include a processing unit (e.g., a processor), which may operate on an instruction of a stream of instructions (e.g., a sequential stream of instructions), wherein the control circuitry (e.g., when executing the storage device driver) receives the stream of instructions. In some embodiments, a spatially sequential stream of read instructions includes instructions stored at sequential memory addresses. In some embodiments, executing an instruction may be split up into stages of four timing categories, including: software sending/completing the instruction, hardware processing the instruction, software idling time while hardware processes the instruction, and software copying a prefetched buffer.

In some embodiments, for each instruction of a stream of instructions, the operations run sequentially with regard to clock cycles. In a single processor example, the hardware processing of a second instruction cannot necessarily start before the hardware processing of a first instruction is complete. By analyzing a particular number of instructions of the stream of instructions and predicting which prefetched data to access based on the identified stream of instructions, the latency of accessing data by the host device is improved upon. In some embodiments, the storage control circuitry, while executing the storage device driver, analyzes a portion or a particular number of incoming instructions in order to predict a stream of instructions associated which prefetched data stored in the plurality of buffers. A software-based prefetching for the host device driver may enable an improved latency of the host device when driving instructions or requests.

In one approach, when the hardware buffer has a low number of hardware instructions (e.g., less than two or only one hardware instruction), the instruction may be driven and there may be additional latency between each instruction request that the control circuitry receives due to inability to fully exploit pipeline of the storage device.

To solve this problem, the operation of the host device may have the software (e.g., storage device driver) predict and prefetch data associated with at least one instruction such that the storage device driver does not have to idle between the receipts of each instruction. Therefore, the storage device driver predicts a stream of instructions and prefetches data associated with the predicted stream of instructions before any additional requests are received. In this way, the latency of the host device is lowered in the situation when the number of instructions in the hardware buffer is below two hardware instructions (i.e., or exactly one instruction).

In some embodiments, a processor of the control circuitry may be a highly parallelized processor capable of handling high bandwidths of instructions quickly (e.g., by starting simultaneous processing of new instructions before completion of previous instructions).

In some embodiments the system and methods of the present disclosure may refer to a host device communicatively coupled to an SSD storage system, wherein the host device is executing a storage device driver with a plurality of buffers for a network protocol interface, such as non-volatile memory express (NVMe) buffers.

An SSD is a data storage device that uses integrated circuit assemblies as memory to store data persistently. SSDs have no moving mechanical components, and this feature distinguishes SSDs from traditional electromechanical magnetic disks, such as, hard disk drives (HDDs) or floppy disks, which contain spinning disks and movable read/write heads. Compared to electromechanical disks, SSDs are typically more resistant to physical shock, run silently, have lower access time, and less latency.

Many types of SSDs use NAND-based flash memory which retains data without power and include a type of non-volatile storage technology. Quality of Service (QOS) of an SSD may be related to the predictability of low latency and consistency of high input/output operations per second (IOPS) while servicing read/write input/output (I/O) workloads. This means that the latency or the I/O command completion time needs to be within a specified range without having unexpected outliers. Throughput or I/O rate may also need to be tightly regulated without causing sudden drops in performance level.

The subject matter of this disclosure may be better understood by reference toFIGS.1-9.

FIG.1shows an illustrative diagram of a host device system100with storage circuitry104, control circuitry106, and a storage device driver118, in accordance with some embodiments of the present disclosure. In some embodiments, host device system100may include a host device102, which includes control circuitry106and storage circuitry104. In some embodiments, control circuitry106may include a processor120, a software instruction buffer (e.g., reserved in memory124), and a storage device driver118with a plurality of buffers116(e.g., reserved in memory124). In some embodiments, the plurality of buffers116and the software instruction buffer may use memory124other than storage circuitry104(e.g., memory124may be RAM memory with lower access latency than storage circuitry104).

In some embodiments, each buffer114is configured to store data associated with an instruction of a determined stream of instructions (e.g., prefetched data from a predicted address of a stream of instructions in storage circuitry104) in order to manage instruction stream detection for software-based prefetching. In some embodiments, the software instruction buffer122is used as a temporary software buffer to store received software instructions when the control circuitry106, while executing the storage device driver118, is analyzing and predicting a stream of instructions. In some embodiments, the storage circuitry104includes a hardware buffer112, which is configured to store hardware instructions. The host device102may also include memory124, such as volatile memory, such as RAM memory (e.g., dynamic random access memory (DRAM)), which has faster access times compared to access times of storage circuitry104(e.g., SSD). It will be understood that the embodiments of the present disclosure are not limited to SSDs. For example, in some embodiments, the host device system100may include a hard disk drive (HDD) device in addition to or in place of the storage circuitry104.

In some embodiments, the host device system100may receive a stream of instructions110from a source, wherein the source is externally located from the host device102or located within the host device102(e.g., from an application). In some embodiments, control circuitry106may identify a stream of instructions110when it receives read requests for several (e.g., five or ten or any other suitable number) sequential addresses in storage circuitry104.

In some embodiments, memory124includes any one or more of a non-volatile memory, such as Phase Change Memory (PCM), a PCM and switch (PCMS), a Ferroelectric Random Access Memory (FeRAM), or a Ferroelectric Transistor Random Access Memory (FeTRAM), and a Magnetoresistive Random Access Memory (MRAM), any other suitable memory, or any combination thereof. In some embodiments, memory124includes any one of a non-volatile memory, volatile memory, or any combination thereof. In some embodiments, control circuitry106is communicatively coupled to the hardware buffer112of the storage circuitry104, in order to receive information of outstanding hardware instructions stored in the hardware buffer112. In addition, the control circuitry106is communicatively coupled to the memory124. In some embodiments, a data bus interface is used to transport instructions (e.g., instruction108) or an address or data associated with the instruction. The data bus between the memory124and control circuitry106provides a network bus for the reading or writing of data through memory124. Processor120of control circuitry106may include a hardware processor, a software processor (e.g., a processor emulated using a virtual machine), or any combination thereof. Processor120may include any suitable software, hardware, or both for controlling the storage device driver118, instruction stream prediction, and the prefetching of data associated with the predicted instruction stream. Memory124may include hardware elements for non-transitory storage of commands or instructions.

In some embodiments, memory124is a multi-plane or three-dimensional (3D) memory array. In some embodiments, memory124includes floating-gate NAND gates. The control circuitry106may receive a sequential read command which causes a read operation. The read operation may be a snap read operation, which is used to access a4K,8K, or16K of data from memory124. In some embodiments, a snap read operation is used to access any other suitable size of data from memory124. In some embodiments, the sequential read command may cause a read that accesses multiple planes of memory124. The control circuitry106may cause a multi-plane read by using an independent multi-plane read operation (IMPRO), which accesses portions of at least two different planes of the memory124. To improve the efficiency of IMPRO, the control circuitry106may be configured to perform IMPRO using the snap reads. This allows the control circuitry106to perform multi-plane snap reads to access at least two planes of the memory124.

The control circuitry106, while executing the storage device driver118, is configured to receive an instruction108of the stream of instructions110and determine how many outstanding hardware instructions are stored within the hardware buffer112. When the control circuitry106, while executing the storage device driver118, determines that there is a low hardware buffer112depth (e.g., a hardware buffer depth of exactly one hardware instruction), the control circuitry106may prefetch data associated with an address of the memory124where the address is predicted based on the stream of read instructions110. In some embodiments, control circuitry106, while executing the storage device driver118, stores the prefetched data for the stream of instructions110in a buffer114of the plurality of buffers116. When the control circuitry106receives instruction108as part of the stream of instructions110, if that instruction matches data that was prefetched based on a prediction, the instruction108is fulfilled by storage device driver118directly from buffer114without a need to further access storage circuitry104.

Storage circuitry104(for example, SSD devices) may include one or more packages of non-volatile memory dies, where each die includes storage cells. In some embodiments, the storage cells are organized into pages, and pages are organized into blocks. Each storage cell can store one or more bits of information.

It will be understood that, while host device system100depicts an embodiment in which a host device102, while executing a storage device driver118, is configured to have software-based prefetching capabilities in accordance with the present disclosure, any other suitable device can have software-based prefetching in a similar manner.

For purposes of clarity and brevity, and not by way of limitation, the present disclosure is provided in the context of software-based prefetching for low hardware buffer depth that provides the features and functionalities disclosed herein. The software-based prefetching can be configured by any suitable software, hardware, or both for implementing such features and functionalities. Software-based prefetching can be at least partially implemented in, for example, host device system100(e.g., as part of host device102, or any other suitable device on which efficiency may improve at low hardware buffer depth), while executing storage device driver118. For example, for a host device102communicatively coupled to a solid-state storage device (i.e., storage circuitry104), software-based prefetching can be implemented in control circuitry106, while executing storage device driver118. In some embodiments, software-based prefetching can be at least partially implemented as part of an operating system for a host device system in which the storage device driver118is integrated.

FIG.2shows an illustrative diagram of an operating system202handling multiple applications (e.g., first application210, second application212, and third application214), while executing a storage device driver204, in accordance with some embodiments of the present disclosure. While three applications (210,212, and214) are shown inFIG.2, any suitable number of applications can be included in some embodiments. In some embodiments, the operating system202is loaded on the control circuitry106of host device102(as seen inFIG.1). In some embodiments, the storage device driver204includes a plurality of buffers206, wherein each buffer208is configured to store a data associated with a determined stream of instructions for software-based prefetching. In some embodiments, each buffer208may store prefetched data for streams from applications210-214in memory that is faster than storage circuitry216(e.g., in memory124ofFIG.1). In some embodiments, the storage device driver204, the plurality of buffers206, buffer208, and storage circuitry216correspond to the storage device driver118, plurality of buffers116, buffer114, and storage circuitry104inFIG.1, respectively. The storage device driver204may be commutatively coupled to storage circuitry216.

In some embodiments, the storage device driver204receives streams of instructions from multiple applications, such as a first stream of read instructions from the first application210, a second stream of read instructions from the second application212, and a third stream of read instructions from the third application214. The storage device driver204may also receive streams of instructions110from the operating system202or from outside of the operating system202, which is shown in system100inFIG.1. In some embodiments, the storage device driver204may receive more than three different streams of read instructions from more than three applications.

In some embodiments, each buffer208of the plurality of buffers206may store data associated with a stream of instructions that was prefetched from storage circuitry216. In some embodiments, the control circuitry106, while executing the storage device driver204, may keep track of whether a buffer208that is storing data associated with a partial stream of instructions or data associated with a complete stream of instructions is storing valid data by configuring a valid bit bitmap. In some embodiments, each buffer208of the plurality of buffers206may correspond to a bit of the bitmap wherein the bit map contains a flag bit for each buffer208of the plurality of buffers206. The valid bit may be useful for when determining which buffer208to clear or overwrite when each buffer208of the plurality of buffers206is storing data associated with a partial stream of instructions or data associated with a complete stream of instructions.

FIG.3shows a diagram of a buffer208of the storage device driver204, in which a stream of instructions302is detected, in order to prefetch data of a predicted addresses of the stream of instructions (e.g.,306,308,310,312,314,316,318,320) when the hardware buffer has a low number of hardware instructions, in accordance with some embodiments of the present disclosure. In some embodiments, the storage device driver204and buffer208correspond to the storage device driver118and buffer114inFIG.1, respectively.

The storage device driver204contains a buffer208which stores data associated with a stream of instructions (e.g.,306,308,310,312,314,316,318, and320). As shown, the control circuitry106incrementally receives the incoming instructions302(e.g., read instruction at address1001, read instruction at address1002, read instruction at address1003, read instruction at address1004, and read instruction at address1005). In some embodiments, the control circuitry106, while executing the storage device driver204, analyzes a particular number of incoming instructions302to predict a stream of instructions. In some embodiments of the present disclosure, the number of incoming instructions and number of buffers are not limited to the number of incoming instructions302and number of buffers208shown inFIG.3, respectively. For example, the control circuitry106, while executing the storage device driver204, predicts a stream of instructions because a particular number of requests (e.g., five or ten) to read data from five addresses (e.g., addresses1001-1005) were received by the storage device driver204. In some embodiments, the control circuitry106, while executing the storage device driver204, prefetches the data associated with the predicted addresses of stream of instructions. The control circuitry106, while executing the storage device driver204, does not prefetch any data until the stream of spatially sequential read instructions (e.g., addresses1001-1005) is detected. For example, the control circuitry106may predict the addresses of the stream of instructions after sequentially receiving read instruction at address1001through read instruction at address1005(thus control circuitry106may predict that the stream will in the future have read request for addresses following address100, i.e. addresses1006,1007,108. . . etc.). Therefore, the control circuitry106, while executing the storage device driver204, prefetches the data304associated with the future instructions of the predicted addresses of stream of instructions (e.g.,308,310,312,314,316,318, and320). As shown, prefetched data from predicted addresses1006-1013is stored in buffer208before the stream of instruction302requests data from the predicted addresses. By using software-based prefetching, the data associated with the predicted addresses of the stream of instructions are more easily accessible with smaller access latencies while stored in buffer208than if stored in host memory124.

FIG.4shows illustrative diagrams400,401, and402of a storage device driver204at three different times (time t1, time t2, and time t3), in accordance with some embodiments of the present disclosure. For example, the buffer at time t1may be the same as buffer208inFIG.3. As shown at time t1, the buffer stores prefetched data from spatially sequential addresses1006-1037(e.g.,406,408,410,412,414,416, and418). In one example, when prefetched data from address1037was stored into the last entry in the buffer418, the buffer had no more space to store prefetched, and prefetching may have been temporarily paused or continue prefetching data into another available buffer. In the shown example, the prediction was correct and the stream of sequential read instructions404began to request data from addresses1006to address1037. Because that data was prefetched, storage device driver204may have served that data from the buffer. When the data from address1037was requested, the control circuitry, while executing the storage device driver204, provides the stored prefetched data from buffer entry418, and determines that the last prefetched data in the buffer was already requested by the stream of sequential read instructions404. Therefore, the buffer may be reused for further prefetching of data at the predicted sequential addresses of the stream of read instructions404(e.g., for read instruction at address1038, read instruction at address1039, read instruction at address1040, etc.). In some embodiments of the present disclosure, the number of incoming instructions is not limited to the number of incoming instructions of the stream of sequential read instructions404shown inFIG.4.

At time t2, the control circuitry marks the buffer entries as stale and available for reuse. Therefore, the buffer entries of the buffer are available for storing data associated with a newly identified stream of instructions or continuing to prefetch a currently identified stream of sequential read instructions. At time t3, the control circuitry, while executing the storage device driver resumes prefetching predicted instructions for the stream of sequential read instructions404(e.g., by prefetching data from addresses1038-1069into the previously stale buffer). In some embodiments, the buffer entries (e.g.,420,422,424,426,428,430, and432) are no longer marked as stale, by setting the corresponding valid bits of the valid bit map to indicate valid data. In another example, the buffer can be used for a newly predicted stream of instructions. For example, if another stream of instructions requested reads from addresses2500-2505, the buffer may prefetch data from address2506to2537for quicker data access when processing the instructions.

In some embodiments, the valid bit bitmap which indicates whether each buffer of the plurality of buffers may be either a valid buffer or a stale buffer. At time t2, the “*” symbols within the buffer entries of buffer204denote a corresponding valid bit for buffer208in the bitmap for the plurality of buffers. These valid bits may be useful for when determining which buffer memory to clear or overwrite when each buffer of the plurality of buffers is storing data associated with a partial stream of instructions or data associated with a complete stream of instructions. Therefore, at time t2, buffer208is marked as a stale buffer and is available to control circuitry to be reused for storing data associated with a newly identified stream of instructions.

FIG.5shows an illustrative diagram of two timelines of executing instructions (e.g.,501,502,503,504,511,512,513, and514) with prefetching disabled500and prefetching enabled510, in accordance with some embodiments of the present disclosure. To show a comparison between the two timelines500and510, there are four instructions shown in each timeline, wherein each instruction is a sequential read instruction. In addition, each timeline has an instruction which corresponds to the opposite timeline. For example, instruction501is assumed to be the exact same instruction as instruction511, just in different implementation for instruction processing.

In some embodiments, executing an instruction may be split up into stages of four timing categories, including: software sending/completing the instruction, hardware processing the instruction, software idling time while hardware processing the instruction, and software copying a prefetched buffer. However, in general, for each instruction of a stream of instructions, the operations must run sequentially with regard to clock cycles. In a single processor example, the hardware processing of a second instruction502cannot necessarily start before the hardware processing of a first instruction501is complete.

In some embodiments of the present disclosure, the timeline without prefetching500, indicates a cyclic pattern of instruction processing, with a consistent idle time of the software of the storage device waiting for the instruction processing in hardware to be complete. However, once a stream of instructions is predicted by the control circuitry, while executing a storage device driver (as seen in the prefetching timeline), the control circuitry is able to prefetch data associated with the predicted stream of instructions for the second instruction512before the second instruction is received and sent to be processed. As expected, the latency of each first instruction501and511of the two timelines have the same latency. The latency of subsequent instructions is reduced because the latency associated with accessing a buffer of the plurality of buffers is much smaller than accessing the host memory (e.g., RAM memory). By prefetching the data at the predicted sequential addresses into a buffer, the control circuitry can access the data quickly as the data is requested. Although the latency of subsequent instructions (e.g.,512,513, and514) for the prefetching timeline510is reduced, the latency of the first instruction remains the same as the control circuitry has not yet prefetched any data for the first instruction511and is to use the first instruction511to determine a predicted stream of instructions.

FIG.6shows a flowchart illustrating a process600for accessing data associated with an address of a memory of a storage device and executing an instruction of the stream of the stream of instructions using at least the data stored in a buffer, in accordance with some embodiments of the present disclosure. In some embodiments, the referenced control circuitry, storage device driver, instruction of a stream of instructions, storage device, hardware buffer, memory, and buffer may be implemented as control circuitry106, storage device driver118, instruction108of a stream of instructions110, storage device102, hardware buffer112, memory124, and buffer114, respectively. In some embodiments, the process600can be modified by, for example, having steps rearranged, changed, added, and/or removed.

At step602, the control circuitry, while executing a storage device driver, receives at least one instruction of a stream of instructions for the storage device. In some embodiments of the present disclosure, the stream of instructions may be of an external source, outside of the storage device. In some embodiments, the stream of instructions may be of an internal source within the operating system (e.g., operating system202), such as an application with a number of outgoing instructions to be executed. In some embodiments, the control circuitry, while executing the storage device driver, is capable of receiving multiple streams of instructions from sources that are located within or outside of the storage device. In some embodiments, the streams of instructions are sequential streams of instructions, wherein at least one instruction is a sequential read instruction. After the receipt of a stream of instructions the control circuitry, while executing the storage device driver, then determines that the hardware buffer of the storage circuitry (e.g., storage circuitry104) stores less than two outstanding hardware instructions, at step604.

At step604, the control circuitry, while executing the storage device driver, determines whether the hardware buffer of the storage device is currently storing less than two instructions. In some examples, when there is a low depth (e.g., exactly one hardware instruction is stored in the hardware buffer) of outstanding hardware instructions in the hardware buffer, the amount of time to access data associated with the outstanding instructions that is stored in a buffer of the plurality of buffers may be less than the latency of receiving a subsequent instruction of a stream of instructions. In an example without prefetching, the storage device driver and control circuitry have large latencies for accessing data associated with the outstanding instruction from memory. In some embodiments, this increase in latency is detrimental to the efficiency of the processing capabilities of the host device.

At step606, the control circuitry, while executing the storage device driver, determines a next step for the process600based on whether the hardware buffer is currently storing less than two hardware instructions at604. If the hardware buffer is storing two or more hardware instructions, the control circuitry will, while executing the storage device driver, continue to receive streams of instructions while executing the outstanding hardware instructions in the hardware buffer without any instruction stream prediction or software-based prefetching, at602. In some embodiments, if the hardware buffer is currently storing only one hardware instruction or is not currently holding any instructions, the control circuitry will, while executing the storage device driver, perform stream prediction by accessing data associated with an address of the memory of the storage device, at608.

At step608, the control circuitry, while executing the storage device driver, accesses data associated with an address of the memory of the storage device, wherein the address is predicted based on analysis of the received stream of instructions. In some embodiments, the control circuitry determines a predicted stream of instructions based on the outstanding hardware instruction in the hardware buffer, as well as by analyzing a particular number of the received stream of instructions. In such embodiments, the control circuitry may determine a buffer of the plurality of buffers, wherein the corresponding stream of instructions associated with the data stored in the buffer matches the predicted stream of instructions. Once the control circuitry determines a buffer, the control circuitry, while executing the storage device driver, stores the data to in the buffer at610.

At step610, the control circuitry, while executing storage device driver, causes to store the data into a buffer. In some embodiments, the buffer is a buffer of a plurality of buffers available. In some embodiments, the determined buffer may contain data associated with an incomplete stream of instructions such that any data associated with newly detected instructions of the sequential stream of instructions may be stored in the determined buffer. In such an embodiment, the determined buffer is capable to store further data associated with instructions until the stream of instructions has terminated or the buffer reaches full memory capacity. In some embodiments, the control circuitry, while executing the storage device driver, may maintain the data associated with the corresponding streams of instructions associated with each buffer of the plurality of buffers until every buffer has data associated with at least a partial stream of instructions stored for software-based prefetching. In some embodiments of the present disclosure, the control circuitry, while executing the storage device driver, is able to mark buffers as stale or reusable for storing data associated with a newly identified stream of instructions. According to the present disclosure, data associated with at least one instruction of the predicted stream of instructions stored within the determined buffer is executed by the control circuitry, while executing the storage device driver, at612.

At step612, the control circuitry, while executing the storage device driver, executes an instruction of the stream of instructions using at least the data stored in the determined buffer. In some embodiments, the control circuitry, while executing the storage device driver, will be able to execute the stream of instructions more efficiently with prefetched the data rather than wait for longer access times for the data associated with each sequential instruction stored in memory. In some embodiments, the streams of instructions are streams of sequential read instructions.

FIG.7shows a flowchart illustrating a process700for marking an identified stale buffer to be reused, in accordance with some embodiments of the present disclosure. In some embodiments, the referenced control circuitry, storage device driver, instruction of a stream of instructions, storage device, and a buffer of a plurality of buffers may be implemented as control circuitry106, storage device driver118, instruction108of a stream of instructions110, storage device102, and buffer114of plurality of buffers116, respectively. In some embodiments, the process700can be modified by, for example, having steps rearranged, changed, added, and/or removed.

At step702, the control circuitry, while executing the storage device driver, configures a plurality of buffers, wherein each buffer of the plurality of buffers may be assigned data associated with instructions of a corresponding stream of instruction of a plurality of streams of instructions received by the driver of the storage device. In some embodiments, the plurality of buffers is configured to be wrapped in the storage device driver. Each buffer is to be configured such that if the control circuitry, while executing the storage device driver detects an additional instruction within a received instruction that matches a stream of instruction of a buffer, data associated with the additional instruction may be appended to the end of the buffer. In addition, in some embodiments, each buffer of the plurality of buffers may store data associated with an or an address pointing to data associated with an instruction. In some embodiments, each buffer of the plurality of buffers may correspond to a bit map wherein there the bit map contains a flag bit for each buffer of the plurality of buffers. In some embodiments, the corresponding bitmap is used to keep track of whether a buffer that is storing data associated with a partial stream of instructions or data associated with a complete stream of instructions is still valid. The valid bit may be useful for when determining which buffer memory to clear or overwrite when each buffer of the plurality of buffers is storing data associated with a partial or data associated with a complete stream of instructions. In some embodiments, a valid bitmap uses a single bit for each corresponding data structure (e.g., each buffer) wherein, in some implementations a valid bit value of 1 means that they buffer should not be cleared, and that a valid bit value of 0 indicates that the stream of instructions of that buffer may no longer be needed to be detected.

At step704, the control circuitry, while executing the storage device driver, identifies the stream of instructions by detecting a particular number of sequential read instructions. In some embodiments, the control circuitry, while executing the storage device driver, determines a predicted stream of instructions by analyzing a particular number of the received stream of instructions. In such embodiments, the control circuitry, while executing the storage device driver, may determine a buffer of the plurality of buffers, wherein the corresponding stream of instructions associated with the stored data of the buffer matches predicted stream of instructions based on the particular number of analyzed instructions of the received stream of instructions. The control circuitry, while executing the storage device driver, may then determine the buffer to be stale among the plurality of buffers, as seen in step706.

At step706, the control circuitry, while executing the storage device driver, identifies a stale buffer among the plurality of buffers. After identifying the buffer and completing software-based prefetching for the given predicted stream of instructions, the control circuitry may, while executing the storage device driver, determine that a source of streams of instructions, such as an application that is no longer running and therefore at least one buffer of the plurality of buffers stored data associated with a stream of instructions for the source. Once the control circuitry identifies a stale buffer, the control circuitry, while executing the storage device driver, then marks the identified stale buffer, at step708.

At step708, the control circuitry, while executing the storage device driver, marks the identified buffer to be reused. In some embodiments of the present disclosure, the control circuitry, while executing the storage device driver, marks the identified buffer as stale, for example, by toggling the corresponding valid bit of the valid bitmap to indicate that the data within the identified buffer is no longer valid for use. According to the present disclosure, the marked buffer may be reused by data associated with a newly identified stream of instructions by the control circuitry.

FIG.8shows a flowchart illustrating a process800for determining a buffer of the plurality of buffers to be reused when each buffer of the plurality of buffers already assigned to data associated with a determined stream of instructions, in accordance with some embodiments of the present disclosure. In some embodiments, the referenced control circuitry, storage device driver, instruction of a stream of instructions, storage device, and a buffer of a plurality of buffers may be implemented as control circuitry106, storage device driver118, instruction108of a stream of instructions110, storage device102, and buffer114of plurality of buffers116, respectively. In some embodiments, the process800can be modified by, for example, having steps rearranged, changed, added, and/or removed.

At step802, the control circuitry, while executing the storage device driver, identifies a new stream. In some embodiments, a new stream of instructions may be detected by the control circuitry, while executing the storage device driver, that does not match any of the streams of instructions associated with the stored data of the plurality of buffers. Therefore, data associated with the newly identified stream of instructions is to be stored in a buffer in order to aid in latency reduction for subsequent streams of instructions. In some embodiments, the control circuitry, while executing the storage device driver, is then to determine if all buffers are already assigned to valid data associated with streams of instructions, at804.

At step804, the control circuitry, while executing the storage device driver, determines whether all buffers of the plurality of buffers are already assigned to data associated with corresponding streams of instructions. In some embodiments, the control circuitry can, while executing the storage device driver, determine whether each valid bit of the valid bitmap associated with the plurality of buffers is set to valid. The control circuitry, while executing the storage device driver, is then to determine the next step of process800based on whether all buffers of the plurality of buffers are already assigned to valid data associated with streams of instructions, at806.

At step806, the control circuitry, while executing the storage device driver, determines a next step for the process800based on whether all buffers of the plurality of buffers are already assigned to data associated with a corresponding stream of instructions. In some embodiments, if the control circuitry determines that all buffers of the plurality of buffers are already assigned to valid data associated with streams of instructions, the control circuitry, while executing the storage device driver, is to determine a buffer of the plurality of buffers to be reused, at808. However, if the control circuitry, while executing the storage device driver, determines that there is either an available, unassigned buffer or a stale buffer, the control circuitry is to assign one of the unassigned buffer or stale buffer to the data associated with the new stream of instructions, at810.

At step808, the control circuitry, while executing the storage device driver, determines a buffer of the plurality of buffers to be reused. In some embodiments, when each buffer of the plurality of buffers is determined to store valid data associated with a stream of instructions, the control circuitry may have to determine which was the least recently used buffer, the least frequently used buffer for the accessing data associated with a predicted stream of instructions by the control circuitry, or a buffer that is storing data of addresses close to the predicted addresses of the new stream of instructions. The least recently used buffer is the buffer with the longest time to the last access by the control circuitry, which in some examples may indicate that the control circuitry, while executing the storage device driver, is unlikely to receive a stream of instructions that will match the corresponding stream of instructions associated with the stored data of the least recently used buffer. Additionally, other implementations of the present disclosure may have the control circuitry, while executing the storage device driver, determine a buffer to be reused based on which is least frequently used. In such an implementation, the control circuitry may, while executing the storage device driver, maintain a counter for each buffer, wherein the counter increments every time the control circuitry, while executing the storage device driver, accesses the data associated with the corresponding buffer. Therefore, the control circuitry is able to determine a least frequently used buffer as indicated by the buffer with the smallest corresponding counter value. In some embodiments, the control circuitry, while executing the storage device driver, may use a combination of least frequently used and least recently used in order to determine a buffer to reuse. In some embodiments, the buffer that is storing data of addresses close to the predicted addresses of the new stream of instructions may be a buffer that prefetched a first portion of predicted addresses of a stream of instructions, however, the data of a second portion of predicted addresses are also to be prefetched. In some embodiments, if there are no other available buffers, the control circuitry is to reuse the buffer that stored the prefetched data of the first portion of predicted addresses in order to store the prefetched data of the second portion of predicted addresses. Once a buffer is determined, the determined data stored on the buffer is to be cleared in order for data associated with the newly identified stream of instructions to be stored.

At step810, the control circuitry, while executing the storage device driver, assigns one of an unassigned buffer or stale buffer of the plurality of buffers to data associated with the new stream of instructions. When the control circuitry, while executing the storage device driver, determines that there is at least one of an unassigned buffer or a stale buffer, the control circuitry may, while executing the storage device driver, store data associated with the newly identified onto the unassigned buffer or clear the stale buffer to allow for data associated with the newly identified buffer to be stored. However, for example, if there is one unassigned buffer and one stale buffer available, the control circuitry may, while executing the storage device driver, determine to store the data associated with the newly identified stream of instructions onto an unassigned buffer as it requires less steps to store data associated with the new stream of instructions.

FIG.9shows a flowchart illustrating a process900for handling an incoming instruction with software-based prefetching, in accordance with some embodiments of the present disclosure. In some embodiments, the referenced control circuitry, storage device driver, instruction of a stream of instructions, hardware buffer, and a buffer of a plurality of buffers may be implemented as control circuitry106, storage device driver118, instruction108of a stream of instructions110, hardware buffer112, and buffer114of plurality of buffers116, respectively. In some embodiments, the process900can be modified by, for example, having steps rearranged, changed, added, and/or removed.

At step902, the control circuitry, while executing the storage device driver, identifies an incoming instruction. In some embodiments, an incoming instruction may be one instruction of a stream of instructions detected by the control circuitry, while executing the storage device driver. In some embodiments, the control circuitry, while executing the storage device driver, is then to determine the next step of process900based on whether the hardware buffer is storing less than two hardware instructions (i.e., or exactly one instructions), at904.

At step904, the control circuitry, while executing the storage device driver, determines whether the hardware buffer is storing less than two hardware instructions. In some embodiments, if the control circuitry, while executing the storage device driver, determines that the hardware buffer is storing at least two hardware instructions, the control circuitry is then to handle the incoming instruction without software-based prefetching, at908. In other embodiments, when the control circuitry, while executing the storage device driver, determines that the hardware buffer is storing less than two hardware instructions, the control circuitry is then to determine the next step of process900based on whether the instruction is a read instruction of proper size, at906.

At step906, the control circuitry, while executing the storage device driver, determines a next step for the process900based on whether the instruction is a read instruction of proper size (e.g., 4 KB, 8 KB, . . . , 128 KB). In some embodiments, if the control circuitry, while executing the storage device driver, determines that the instruction is not a read instruction or not of a proper size, the control circuitry is then to handle the incoming instruction without software-based prefetching, at908. In other embodiments, when the control circuitry, while executing the storage device driver, determines that the instruction is a read instruction of proper size, the control circuitry is then to determine the next step of process900by determining if there is an identified buffer of the plurality of buffers that is storing data associated with a matching stream of instructions, at910.

At step908, the control circuitry, while executing the storage device driver, handles the incoming instruction without software-based prefetching. In some embodiments, a hardware buffer with a depth greater than two hardware instructions may not leverage the advantages of software-based-prefetching. Additionally, prefetching data associated to a stream of instructions that includes write instructions does not guarantee accurate prefetched data, because the write instructions may alter the data that has already been prefetched.

At step910, the control circuitry, while executing the storage device driver, determines a next step for the process900by determining if there is an identified buffer of the plurality of buffers that is storing data associated with a matching stream of instructions. In some embodiments, if the control circuitry, while executing the storage device driver, determines that there is an identified buffer that stores data associated with a matching stream of instructions, the control circuitry is then to use the data stored on the identified buffer to process at least the instruction, at912. In other embodiments, when the control circuitry, while executing the storage device driver, determines that there is not an identified that stores data associated with a matching stream of instructions, the control circuitry is then to determine the next step of process900by determining if sequential instruction detection is in progress, at914.

At step912, the control circuitry, while executing the storage device driver, uses data stored on the identified buffer to process at least the incoming instruction. In some embodiments, the data associated on the identified buffer is of an instruction stream that matches the incoming stream of instructions.

At step914, the control circuitry, while executing the storage device driver, determines a next step for the process900by determining if sequential instruction detection is in progress. In some embodiments, the control circuitry, while executing the storage device driver, is configured to monitor a particular number of sequential instructions of a stream of instructions before determining a buffer from which to prefetch data. If the control circuitry, while executing the storage device driver, determines that sequential detection is in progress, the control circuitry is to process incoming instruction as part of sequential detection, at916. In some embodiments, when control circuitry, while executing the storage device driver, determines that sequential detection is not in progress, the control circuitry is to then determine the next step of process900by determining if there is an available or reusable/stale buffer among the plurality of buffers, at918.

At step916, the control circuitry, while executing the storage device driver, processes the incoming instruction as part of sequential detection. In some embodiments, the instruction is processed and used by the control circuitry, while executing the storage device driver, in order to determine a predicted stream of instructions for software-based prefetching.

At step918, the control circuitry, while executing the storage device driver, determines a next step for the process900by determining if there is an available or reusable/stale buffer among the plurality of buffers. In some embodiments, a buffer of the plurality of buffers may be empty, or not currently storing any data associated with a stream of instructions. In some embodiments, a corresponding valid bit in a valid bit map may denote that a buffer of the plurality of buffers is stale. The data stored on a stale buffer may be cleared or deleted and used for other data associated with a new stream of instructions. In some embodiments, the control circuitry, while executing the storage device driver, determines that there is an available buffer or reusable/stale buffer among the plurality of buffers, the control circuitry is to initialize an available or reusable/stale buffer to store data associated with a stream of instructions, at920. In some embodiments, when control circuitry, while executing the storage device driver, determines that there is no available or reusable/stale buffer among the plurality of buffers, the control circuitry is to then handle the incoming instruction without software-based prefetching, at908.

At step920, the control circuitry, while executing the storage device driver, is to initialize an available or reusable/stale buffer to store data associated with a stream of instructions. In some embodiments, to initialize a stale buffer, the control circuitry is to delete or clear the stale data stored or overwrite the stale data with new data associated with the stream of instructions.

FIG.10shows a flowchart illustrating a process1000for performing independent multi-plane read operation using snap reads caused by a sequential read command, in accordance with some embodiments of the present disclosure. In some embodiments, the referenced control circuitry and memory may be implemented as control circuitry106and memory124. Performing process1000may improve the efficiency of accessing memory124. In some embodiments, the process1000can be modified by, for example, having steps rearranged, changed, added, and/or removed.

At step1002, the control circuitry106receives a read command. In some embodiments, the read command may be of an external source, outside of the device.

At step1004, the control circuitry106determines whether the read command is a sequential read command. If the read command is a sequential read command, the control circuitry106is then to determine if the control circuitry106can request a cache read, at step1006. If the read command is not a sequential read command, the control circuitry106is to issue an independent multi-plane read operation (IMPRO) using snap reads to memory124.

At step1006, the control circuitry106determines whether the control circuitry106can request a cache read. In some embodiments, there may not be a cache available to the control circuitry106. If there is no readable cache available to the control circuitry106, the control circuitry106issues IMPRO using snap reads to the memory124, at step1010. If the control circuitry106is able to access a cache, the control circuitry106issues a multi-plane sequential read to the memory, at step1008.

At step1008, the control circuitry106issues a multi-plane sequential read to memory124. In some embodiments, the multi-plane sequential read is an independent multi-plane read operation (IMPRO), which accesses portions of at least two different planes of the memory124. Once the IMPRO is complete and the control circuitry106accesses the requested data, the control circuitry106responds to the received read command, at1012

At step1010, the control circuitry106issues an IMPRO using snap reads to memory124. The control circuitry106is configured to perform IMPRO using snap reads. This allows the control circuitry106to perform multi-plane snap reads to access at least two planes of the memory124. A snap read is used to access a4K,8K, or16K of data from memory124. In some embodiments, a snap read can be used to access any other suitable size of data from memory124. Once the IMPRO using snap reads is complete and the control circuitry106accesses the requested data, the control circuitry106responds to the received read command, at1012.

At step1012, the control circuitry106generates a response for the received read command, with the accessed data from step1008or step1010. The destination of the response is the same as the source of the received read command.

A description of an embodiment with several components in communication with each other does not imply that all such components are required. On the contrary a variety of optional components are described to illustrate the wide variety of possible embodiments. Further, although process steps, method steps, algorithms or the like may be described in a sequential order, such processes, methods, and algorithms may be configured to work in alternate orders. In other words, any sequence or order of steps that may be described does not necessarily indicate a requirement that the steps be performed in that order. The steps of processes described herein may be performed in any order practical. Further, some steps may be performed simultaneously.

The foregoing description of various embodiments has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to be limited to the precise forms disclosed. Many modifications and variations are possible in light of the above teaching.