CN117396858A - System and method for enhancing flash memory channel utilization - Google Patents

Abstract

An apparatus and method for scheduling flash commands are disclosed. The apparatus includes a plurality of queues, wherein each queue includes: an input for receiving a flash command, an output for sending a flash command, and a null signal output for signaling when the queues are null, wherein each queue is assigned a unique ordered priority. The apparatus includes a selector, the selector comprising: a plurality of flash command inputs, a flash command output to a flash target, and a select input, wherein each flash command input is coupled to a corresponding queue output. The apparatus includes an arbiter that includes an input to receive each queue empty signal and an input to receive a lock bit from the flash command output of the selector, and includes a select output coupled to the select input of the selector. The flash command includes a lock bit and a plurality of control bits to be output to a control input on a flash target.

Description

System and method for enhancing flash memory channel utilization

Related patent application

This application claims priority from commonly owned U.S. provisional patent application 63/276,742, which is hereby incorporated by reference.

Technical Field

The present application relates to systems and methods for scheduling requests to flash memory.

Background

Flash memory storage devices provide high throughput, low latency long term storage of computer data. Some types of requests are faster than others. For example, some control operations are almost instantaneously completed. For example, the control request may increase or decrease the operating voltage of the flash memory target by updating a control register and may be accomplished in nanoseconds. The read request may require the establishment of a control line and read from the NAND cell into a local buffer. Flash reads may take on the order of microseconds to complete. The write request may require establishment of a control line and programming operations in the NAND cell. Flash writing can take on the order of milliseconds to complete.

Disclosure of Invention

In some examples, an apparatus is provided, the apparatus comprising: a plurality of queues, wherein each queue comprises: an input for receiving a flash command, an output for sending a flash command, and a null signal output for signaling when the queues are null, wherein each queue is assigned a unique ordered priority. The apparatus includes a selector, the selector comprising: a plurality of flash command inputs, a flash command output to a flash target, and a select input, wherein each flash command input is coupled to a corresponding queue output. And the apparatus includes an arbiter that includes an input to receive each queue empty signal and an input to receive the lock bit from the flash command output of the selector, and includes a select output coupled to the select input of the selector. In the apparatus, a flash command includes a lock bit and a plurality of control bits to be output to a control input on a flash target. In some examples, the arbiter maintains the value of the select output when the lock bit of the flash command output is asserted. In some examples, the arbiter maintains the value of the select output when the lock bit of the flash command output is asserted. In some examples, the arbiter includes logic to identify a set of non-empty queues and to set the select output to a highest priority non-empty queue of the non-empty queues. In some examples, the plurality of queues includes a low priority queue, a high priority queue, and a super priority queue, and the arbiter sets the value of the select output to the super priority queue unless it is empty, the arbiter sets the value of the select output to the high priority queue unless it is empty, the arbiter sets the value of the select output to the low priority queue. In some examples, the arbiter receives the start of transfer signal and the end of transfer signal, and when the lock bit is asserted, the arbiter maintains the current value at the select output, otherwise the arbiter sets the value at the select output to the super-priority queue, unless it is empty, the arbiter maintains the current value at the select output between the assertion of the start of transfer signal and the assertion of the end of transfer signal, otherwise the arbiter sets the value at the select output to the high-priority queue, unless it is empty, the arbiter sets the value at the select output to the low-priority queue. In some examples, the arbiter receives the transfer start signal, the transfer end signal, and the write transfer signal, and when the lock bit is asserted, the arbiter maintains the current value at the select output, otherwise the arbiter sets the value at the select output to the super-priority queue unless it is empty, and when the write transfer signal is asserted, the arbiter maintains the current value at the select output between the assertion of the transfer start signal and the assertion of the transfer end signal, otherwise the arbiter sets the value at the select output to the high priority queue unless it is empty. In some examples, the plurality of queues are stored in a single memory.

In some examples, a method is performed in a system that includes a plurality of queues, where each queue is assigned a unique ordered priority. The method comprises the following steps: storing a new flash command having a lock flag and associated with a first priority in one of the plurality of queues corresponding to the first priority, selecting a current queue from which to schedule the flash command, and scheduling an oldest flash command from the current queue to a flash memory target. In some examples, the lock flag is asserted, maintaining the current queue selection. In some examples, selecting the current queue includes selecting a highest priority non-empty queue. In some examples, selecting the current queue is performed by the arbiter to: the super-priority queue is selected, the high-priority queue is selected unless it is empty, and the low-priority queue is selected unless it is empty. In some examples, selecting the current queue is performed by the arbiter to: the super-priority queue is selected when the lock flag is asserted, the super-priority queue is selected unless it is empty, the high-priority queue is selected unless it is empty, and the low-priority queue is selected, unless it is empty. In some examples, selecting the current queue is performed by the arbiter to: the super-priority queue is selected unless it is empty, the current selection is maintained between assertion of the transfer start signal and assertion of the transfer end signal when the write transfer signal is asserted, and the high-priority queue is selected unless it is empty. In some examples, the plurality of queues are maintained as a data structure in a single memory.

In some examples, a non-transitory computer readable memory is provided that includes an RTL structure and logic that when emulated form a machine that includes: a plurality of queues, wherein each queue comprises: an input for receiving a flash command, an output for sending a flash command, and a null signal output for signaling when the queues are null, wherein each queue is assigned a unique ordered priority. The machine includes a selector, the selector comprising: a plurality of flash command inputs, a flash command output to a flash target, and a select input, wherein each flash command input is coupled to a corresponding queue output. The machine includes an arbiter that includes an input to receive each queue empty signal and an input to receive a lock bit from a flash command output of the selector, and includes a select output coupled to a select input of the selector. In some examples, the received lock bit is asserted and the arbiter holds the value of the select output. In some examples, the arbiter includes logic to identify a set of non-empty queues and to set the select output to the highest priority non-empty queue. In some examples, the plurality of queues includes a low priority queue, a high priority queue, and a super priority queue, and the arbiter sets the value of the select output to the super priority queue unless it is empty, the arbiter sets the value of the select output to the high priority queue unless it is empty, the arbiter sets the value of the select output to the low priority queue. In some examples, the arbiter receives the start of transfer signal and the end of transfer signal, and when the lock bit is asserted, the arbiter holds the current select output, otherwise the arbiter will set the value of the select output to the super-priority queue, unless it is empty, the arbiter holds the current select output between the assertion of the start of transfer signal and the assertion of the end of transfer signal, otherwise the arbiter sets the value of the select output to the high priority queue, unless it is empty, the arbiter sets the value of the select output to the low priority queue. In some examples, the arbiter receives the transfer start signal, the transfer end signal, and the write transfer signal, and when the lock bit is asserted, the arbiter maintains the current value at the select output, otherwise the arbiter sets the value of the select output to the super-priority queue, unless it is empty, and when the write transfer signal is asserted, the arbiter maintains the current select output between the assertion of the transfer start signal and the assertion of the transfer end signal, otherwise the arbiter sets the value of the select output to the high priority queue, unless it is empty, the arbiter sets the value of the select output to the low priority queue.

Drawings

Fig. 1 is an illustration of a system for scheduling requests for flash memory according to an example of the present disclosure.

Fig. 2 is a flow chart of a method for scheduling requests for flash memory according to some examples of the present disclosure.

Fig. 3 is an illustration of a system for modeling a register transfer language description of a circuit according to certain examples of the present disclosure.

Detailed Description

Fig. 1 is an illustration of a system for scheduling requests for flash memory according to an example of the present disclosure. Requests may be queued based on priority and scheduled according to an arbitration scheme. Arbitration schemes may allow various types of overrides to accommodate bursts (particularly high priority requests) and transactions across multiple requests. The arbitration scheme may allow execution of an ultra-high priority control command to instruct the first flash target to begin adjusting the voltage for reading. These control commands may be scheduled quickly, but may require significant deferral before a read command is issued. The arbitration scheme may follow those control commands with a low priority burst of write commands to a different flash memory target that was previously configured to write. The arbitration scheme may atomically schedule the entire write command sequence to maintain data coherency. The operation of the arbitration scheme is "pipelined" in order to improve flash memory performance. The system 100 is coupled to a flash controller CPU 102 and a flash memory target 104. The system 100 may be incorporated within a flash memory controller integrated circuit. The system 100 includes queues 106a through 106c coupled to and receiving flash memory commands from the CPU 102. Each queue may be a first-in-first-out queue that stores zero or more flash command records. Queues 106 a-106 c are associated with priority levels. As shown, queue 106a is associated with a low priority level, queue 106b is associated with a high priority level, and queue 106c is associated with an ultra-high priority level. In some examples, write requests are assigned to low priority queue 106a, read requests are assigned to high priority queue 106b, and control requests are assigned to ultrahigh priority queue 106c. Queues 106 a-106 c have read ports coupled to inputs of parallel multiplexer 108. The multiplexer 108 has an output coupled to the flash memory target 104 or a set of addressable flash memory targets 104. Arbiter 110 is coupled to the empty output signals of queues 106 a-106 c to enable it to determine when each queue is empty. An arbiter 110 is also coupled to some of the output lines of the multiplexer 108. In some examples, the arbiter 110 receives a signal 122 from the scheduled flash command record conveying the value of the arbitration flag. The signal 133 may include indicia representing the start of a transfer, the end of a transfer, a write transfer, a read transfer, and a lock. Each flag may be set by CPU 102 and stored within or in conjunction with each flash command record in queues 106 a-106 c. The arbiter 110 drives a queue select input on the multiplexer 108 to select the queue from which the next request will be passed to the flash target 104 via the command line 120.

In one mode of operation, the arbiter 110 is configured to arbitrate between the queues 106 a-106 c on a strict priority basis. At each arbitration decision, the arbiter 110 will select the highest priority queue containing requests. For example, if all three queues contain requests, the arbiter 110 will select from the super-priority queue 106c until the queue is empty, and will then decimate from the high-priority queue 106b until the queue is empty, and will then decimate from the low-priority queue 106 a. If the arbiter 110 is drawing from the low priority queue 106a and a new request arrives at the super priority queue 106c, the arbiter 110 will draw from the super priority queue 106c at the next arbitration decision.

In some examples, CPU 102 may have set a lock bit for a series of requests in a particular queue to force the arbiter to draw from that queue until the lock signal has been cleared. In some examples, the arbiter 110 may exit its lock mode when the queue is empty.

In some examples, the series of requests may be logically related. For example, a burst read operation may sequentially read 32KB of data from a flash memory target. Flash memory targets may be internally organized in a single block as 16KB pages with a transfer size of 4 KB. In this example, CPU 102 may issue a series of ten requests to complete the entire operation. The CPU 102 may issue a read command for the first page followed by four sequential read transfer commands. The first read transfer command of the four read transfer commands may include an xfer_begin tag and a rd_xfer tag, and the last read transfer command of the four read transfer commands may include an xfer_end tag and a rd_xfer tag. The CPU 102 may then issue a second page read command and four read transfer commands to complete the entire transfer.

In another example, the CPU 102 may issue a series of five requests to complete a 16KB write transaction to the flash target 104, e.g., four write transfer requests followed by a write request. Because the write requests are low priority, read requests arriving before all five requests in the write sequence can be interrupted can be immediately scheduled by the arbiter 110, thus interrupting larger write transactions. In some examples, the arbiter 110 may mark all five requests as outstanding and return them to the queue. In some examples, the arbiter 110 may signal to the CPU 102 that the write transaction is preempted. The CPU 102 may re-queue or cancel the preempted write transaction.

In some examples, the CPU 102 may flag the command sequences to indicate that they are part of a burst transfer. The CPU 102 may mark the first command in the sequence as rd_xfer signaling the start of a burst read. The CPU 102 may flag the second command xfer_begin signaling the start of a series of burst transfers and the last command in the sequence xfer_end signaling the end of the read sequence. In some examples, the arbiter 110 may continue to schedule from the high priority queue 106b until the xfer_end signal is observed by the arbiter 110.

Fig. 2 is a flow chart of a method for scheduling requests for flash memory according to some examples of the present disclosure. The method 200 schedules flash memory commands. At block 201, commands are received from the CPU 102 and queued in the priority queues 106 a-106 c. Write requests are queued in low priority queue 106 a. The read requests are queued in the high priority queue 106 b. Other requests are queued in the ultra-high priority queue 106c. In some examples, additional queues may be used to further differentiate command types. When any of the queues 106 are full, block 201 may signal the CPU 102 to prevent queue overflow.

At block 202, if the superqueue 106c is empty, the arbiter 110 will proceed to block 208. Otherwise, at block 204, the arbiter 110 schedules a command from the ultra-high priority queue 106c, schedules the command to the flash target 104, and drives one or more of the signals xfer_begin, xfer_end, wr_xfer, rd_xfer, and lock with the value set by the field in the scheduled command. At block 206, if the lock bit is asserted, the arbiter 110 will return to block 202 to schedule another ultra high priority command, and otherwise will proceed to block 208.

At block 208, if the high priority queue 106b is empty, the arbiter 110 will proceed to block 214. Otherwise, at block 210, the arbiter 110 schedules a command from the high priority queue 106b, schedules the command to the flash target 104, and drives one or more of the signals xfer_begin, xfer_end, wr_xfer, rd_xfer, and lock with the value set by the field in the scheduled command. At block 212, if the lock signal is asserted, the arbiter 110 will return to block 208 to schedule another high priority command, otherwise it will return to block 202.

At block 214, if the low priority queue 106a is empty, the arbiter 110 will proceed to block 202. Otherwise, at block 216, the arbiter 110 schedules a command from the low priority queue 106a, schedules the command to the flash target 104, and drives one or more of the signals xfer_begin, xfer_end, wr_xfer, rd_xfer, and lock with the value set by the field in the scheduled command. At block 218, if the lock signal is asserted, the arbiter 110 will return to block 214 to schedule another low priority command, otherwise it will return to block 202.

Fig. 3 is an illustration of a system for modeling a register transfer language description of a circuit according to certain examples of the present disclosure. The system 300 includes a CPU 302 and a memory 304. The memory 304 includes Electronic Design Automation (EDA) software 306 and a Register Transfer Level (RTL) description 308. The CPU 302 may be a conventional personal computer or workstation processor and the memory 304 may be conventional memory. The EDA may be conventional software for simulating, analyzing, and verifying circuit designs. The EDA may include design capabilities and may prepare a mask data file for manufacturing a circuit of a specified design. RTL 308 may be described in one or more hardware description language files and may define the structure and operation of system 100.

Although example embodiments have been described above, other variations and embodiments can be made by the present disclosure without departing from the spirit and scope of these embodiments.

Claims (20)

1. An apparatus, the apparatus comprising:

a plurality of queues, wherein each queue comprises: an input for receiving a flash command, an output for sending a flash command, and a null signal output for signaling when the queues are null, wherein each queue is assigned a unique ordered priority;

a selector, the selector comprising: a plurality of flash command inputs, a flash command output to a flash target, and a select input, wherein each flash command input is coupled to a corresponding queue output; and

an arbiter comprising an input for receiving each queue empty signal and an input for receiving a lock bit from the flash command output of the selector, and comprising a select output coupled to the select input of the selector;

wherein the flash command includes a lock bit and a plurality of control bits to be output to a control input on a flash target.

2. The apparatus of claim 1, wherein the arbiter will hold a value of the select output when the lock bit of the flash command output is asserted.

3. The apparatus of any of claims 1-2, wherein the arbiter comprises logic to identify a set of non-empty queues and to set the select output to a highest priority non-empty queue of the non-empty queues.

4. The apparatus of any of claims 1-3, wherein the plurality of queues includes a low priority queue, a high priority queue, and a super priority queue, and wherein:

the arbiter will set the value of the select output to the super-priority queue unless the super-priority queue is empty

The arbiter will set the value of the select output to the high priority queue unless the high priority queue is empty

The arbiter will set the value of the select output to the low priority queue.

5. The apparatus of any one of claims 1 to 4, wherein the arbiter is to receive a start of transmission signal and an end of transmission signal, and wherein:

when the lock bit is asserted, the arbiter will hold the current value at the select output, otherwise

The arbiter will set the value of the select output to the super-priority queue unless the super-priority queue is empty

The arbiter will maintain the current value at the select output between the assertion of the transfer start signal and the assertion of the transfer end signal, otherwise

The arbiter will set the value of the select output to the high priority queue unless the high priority queue is empty

The arbiter will set the value of the select output to the low priority queue.

6. The apparatus of any one of claims 1 to 5, wherein the arbiter is to receive a transfer start signal, a transfer end signal, and a write transfer signal, and wherein:

when the lock bit is asserted, the arbiter will hold the current value at the select output, otherwise

The arbiter will set the value of the select output to the super-priority queue unless the super-priority queue is empty

When the write transfer signal is asserted, the arbiter will maintain the current value at the select output between the assertion of the transfer start signal and the assertion of the transfer end signal, otherwise

The arbiter will set the value of the select output to the high priority queue unless the high priority queue is empty

The arbiter will set the value of the select output to the low priority queue.

7. The apparatus of any of claims 1-6, wherein the plurality of queues are to be stored in a single memory.

8. A method performed in a system comprising a plurality of queues, wherein each queue is assigned a unique ordered priority, the method comprising:

storing a new flash command having a lock flag and associated with a first priority in one of the plurality of queues corresponding to the first priority,

selecting a current queue from which to schedule flash commands

The oldest flash command is dispatched from the current queue to a flash memory target.

9. The method of claim 8, wherein the current queue selection is maintained when the lock flag is asserted.

10. The method of any of claims 8-9, wherein selecting the current queue comprises selecting a highest priority non-empty queue.

11. The method of any of claims 8 to 10, wherein selecting the current queue is performed by an arbiter to:

selecting the super-priority queue unless it is empty

Selecting the high priority queue unless it is empty

The low priority queue is selected.

12. The method of any of claims 8 to 11, wherein selecting the current queue is performed by an arbiter to:

maintaining the current selection while the lock flag is asserted, otherwise

Selecting the super-priority queue unless it is empty

Maintaining the current selection between the assertion of the transfer start signal and the assertion of the transfer end signal, otherwise

Selecting the high priority queue unless it is empty

The low priority queue is selected.

13. The method of any of claims 8 to 12, wherein selecting the current queue is performed by an arbiter to:

maintaining the current selection while the lock flag is asserted, otherwise

Selecting the super-priority queue unless it is empty

Maintaining the current selection between assertion of the transfer start signal and assertion of the transfer end signal when the write transfer signal is asserted, otherwise

Selecting the high priority queue unless it is empty

The low priority queue is selected.

14. The method of any of claims 8 to 13, wherein the plurality of queues are maintained as a data structure in a single memory.

15. A non-transitory computer readable memory comprising an RTL structure and logic that when emulated form a machine, the machine comprising:

a plurality of queues, wherein each queue comprises: an input for receiving a flash command, an output for sending a flash command, and a null signal output for signaling when the queues are null, wherein each queue is assigned a unique ordered priority;

a selector, the selector comprising: a plurality of flash command inputs, a flash command output to a flash target, and a select input, wherein each flash command input is coupled to a corresponding queue output; and

an arbiter comprising an input for receiving each queue empty signal and an input for receiving a lock bit from the flash command output of the selector, and comprising a select output coupled to the select input of the selector.

16. The medium of claim 15, wherein the arbiter is to maintain a value of the select output when the received lock bit is asserted.

17. The medium of any of claims 15 to 16, wherein the arbiter comprises logic to identify a set of non-empty queues and to set the select output to a highest priority non-empty queue.

18. The medium of any of claims 15-17, wherein the plurality of queues includes a low priority queue, a high priority queue, and a super priority queue, and wherein:

the arbiter will set the value of the select output to the super-priority queue unless the super-priority queue is empty

The arbiter will set the value of the select output to the high priority queue unless the high priority queue is empty

The arbiter will set the value of the select output to the low priority queue.

19. The medium of any of claims 15 to 18, wherein the arbiter is to receive a start of transfer signal and an end of transfer signal, and wherein:

the arbiter will hold the currently selected output when the lock bit is asserted, otherwise

The arbiter will set the value of the select output to the super-priority queue unless the super-priority queue is empty

The arbiter will maintain the current select output between the assertion of the transfer start signal and the assertion of the transfer end signal, otherwise

The arbiter will set the value of the select output to the high priority queue unless the high priority queue is empty

The arbiter will set the value of the select output to the low priority queue.

20. The medium of any of claims 15 to 19, wherein the arbiter is to receive a transfer start signal, a transfer end signal, and a write transfer signal, and wherein:

when the lock bit is asserted, the arbiter will hold the current value at the select output, otherwise

The arbiter will set the value of the select output to the super-priority queue unless the super-priority queue is empty

When the write transfer signal is asserted, the arbiter will maintain a current select output between the assertion of the transfer start signal and the assertion of the transfer end signal, otherwise

The arbiter will set the value of the select output to the high priority queue unless the high priority queue is empty

The arbiter will set the value of the select output to the low priority queue.