Multiple non-contiguous block erase in flash memory

[0002] 1. Field of the Invention

[0003] The invention pertains generally to computer systems. In particular, it pertains to erasing blocks of flash memory.

[0004] 2. Description of the Related Art

[0005] Flash memory provides a non-volatile fast-access storage medium that can be rewritten in-circuit after first erasing the old data. However, due to the characteristics of flash memory, data can be erased only in blocks, which are typically between 8 kilobytes (KB) and 128 KB in size. Once data has been written into a particular byte location, that data cannot be changed without first erasing the byte, which requires erasing the entire block in which the byte is located. This characteristic of flash memory makes it unsuitable for many applications, but suitable for applications that load a medium-to-large amount of data, retain that data for some period of time without change, and eventually delete that data in its entirety. One such application is a digital audio player.

[0006] A digital audio player is a small appliance that contains one or more flash memory components, and stores music or other audio content in one of several industry-standard formats. The user downloads songs or other pieces of music (commonly called “tracks”) one at a time, from the source to the player, until the flash memory is occupied with content. Each downloaded track occupies a number of erase blocks in the flash memory, the number depending on the length of the track. An “erase block” is the smallest unit in the flash memory that can be erased at once, and will be referred to in this document simply as a “block”. The blocks that comprise a track are generally not physically contiguous—one track may occupy blocks that are scattered throughout the flash memory device. However, they are in some way logically connected, for example through a linked-list—each block containing a data structure which points to the location of the next logical block within the track.

[0007] After downloading, the user may wish to delete one track and replace it with another. This results in the erasure of all of the blocks associated with that track. This process can take a long time, depending on the number and size of track(s) to be erased. With conventional flash memory technology, a typical 4-minute track can take about 30 seconds to erase. This wait may be unpalatable to the end user.

[0008] Currently, flash memory components have one erase command at the user interface. The user (system software) issues a single-block erase command to the device by clocking in a command with a single block address. The device then performs an erase operation on that block. When the erase operation is complete, the system software issues the next erase command for the next block, and so on. Thus, all blocks within a track are erased serially, which causes the excessive erase times noted above.

[0009] FIG. 1 illustrates this serial block erase process 10. At step 11, the flash memory controller receives a single-block erase command with the address of the block to be erased. At step 12, a confirm command is received, which triggers the flash memory to erase the specified block at step 13. Control then returns to step 11 to receive another block Erase command with the block address of the next block to erase. This loop is repeated as many times as there are blocks to erase.

[0010] FIG. 1 shows a flow chart of a single-block erase operation of the prior art.

[0011] FIG. 2 shows a flow chart of a multi-block erase operation of the invention.

[0012] FIG. 3 shows a diagram of the command decode and block address latching functions.

[0013] FIG. 4 shows a flow chart of the software for issuing a multi-block erase command.

[0014] FIG. 5 shows a portion of a system of the invention.

[0015] FIG. 6 shows a timing diagram of the signals on the flash memory bus.

[0016] The invention comprises a new flash memory interface that permits multiple blocks to be erased simultaneously. The interface can include a new flash memory command that indicates a multi-block erasure, and circuitry to interpret this command and determine which blocks to erase. The command can allow the user to clock multiple block addresses into the memory. The number of blocks can vary and may be as great as the number of physical blocks in the flash memory.

[0017] Using the multi-cycle command format that is common with flash memory devices, the user can send an initial command cycle to the device, telling the device that the following several command cycles will contain block addresses. The next cycle(s) can specify those block addresses. Finally, a “confirm command” cycle can be issued, which is a command indicating that all block addresses have been transferred and the command sequence is over. The name “confirm command” is used simply to denote a sequence termination command that, in essence, confirms the end of the command sequence. Other names can also be used without departing from the spirit of the invention. During this multi-cycle command sequence, the block addresses are received by the flash memory interface and can be retained in a series of latches. Upon receipt of the confirm command, the transfers are complete and the device begins the multiple block erase operation. Since the device can now know all the blocks that are to be erased, the internal erase controller can manage simultaneous erasure of all blocks.

[0018] The invention speeds up the erase process by allowing multiple blocks to be erased simultaneously. Furthermore, the blocks to be erased can be non-contiguous—they may comprise a set of blocks scattered randomly throughout the flash memory device. This capability benefits digital audio applications, where the user may desire to erase a track without disturbing others, and the track comprises many non-contiguous blocks. Other applications, such as digital telephone voicemail machines, can also benefit from this capability. A feature of this invention can be a multi-cycle command that allows the system to specify multiple blocks, load identifiers of those blocks into the device, and then direct the device to erase those blocks simultaneously. Each cycle can be in the format of a standard command cycle on the bus, and the flash memory device can interpret the sequence of commands as a related group to perform the block erase function. The circuitry in the flash memory system can accumulate the specified block addresses, or indicators of those addresses, and initiate all erases when the command sequence is completed.

[0019] FIG. 2 shows a flow chart for a command sequence 20 that can be used by the flash controller, and can also serve as the basis for a state machine to control the command sequence. In the idle state at step 21, the device is waiting for commands. When the command, “Multi-block Erase” is received at step 22, the device begins to accept and save block addresses at step 23. As long as a Confirm command is not detected at step 24, the device keeps accepting block addresses at step 23. When a Confirm command is detected at step 24, the device begins the multiple block erase operation at step 25, erasing all of the blocks that were addressed in the previous command cycles. The erase function is a comparatively lengthy operation, and can continue until complete. Finally, when the erase function is complete at step 26, flow can return to the idle state of step 21.

[0020] Various error conditions (such as a timeout before a Confirm command is received) might occur during the command sequence that can cause the sequence to abort and return to the idle state at step 21 without erasing any blocks. For simplicity, these are not shown or described. A person of ordinary skill in the art should be able to implement such error-abort functions.

[0021] FIG. 3 shows a schematic for decoding and storing the block addresses while the block addresses are being received during the command sequence. After the first command cycle, each subsequent cycle can present a block address to the device. The address can be decoded by decoding logic 32, which can convert that address into a form suitable for storing. The addresses could be stored in their original format (a binary number), which would require a table of entries with enough bit width to contain the address and as many entries as there are blocks in the flash memory. However, more efficient use of circuit real estate can be realized by designating a simple latch for each erasable block, and storing a representation of the address by storing a logic ‘1’ in each latch whose associated block is to be erased. The number of latches 33(1)-33(N) can be the same as the number of physical blocks existing in the flash memory. Each block can be associated with a specific one of those latches. If a block is addressed during the command sequence, that block's corresponding latch can be loaded with a logic “1”. Otherwise, the latch can be loaded with whatever its previous data was, as shown by the looping connections from the output of the latches to the OR gates 31(1)-31(N) at the inputs to of the latches. To initialize the latches, they can all be reset to a logic “0” before receiving any addresses in the command sequence. This “store and loop” design is only one way to write and save the identification of the specified blocks in the latches. As will be appreciated by a person of ordinary skill in the art, there are other circuits that will permit writing and saving the contents of the latches, and these are included within the scope of the invention.

[0022] Once the Confirm command is given, the erase controller can take over and look at the signals from the outputs of individual latches 33(1)-33(N). These signals can gate the individual block Source Switches and Negative Wordline Switches (not shown). The Source Switches and Negative Wordline Switches are conventional circuits that must be ON for an individual block to be erased. They are known elements in flash memory design and are not further described herein. By getting simultaneous outputs from multiple ones of latches 33(1)-33(N), the flash memory device is able to simultaneously select certain ones of the Source Switches and Negative Wordline Switches, and the erase controller can erase those specified blocks simultaneously based on which Source Switches and Negative Wordline Switches are selected by latches 33(1)-33(N).

[0023] FIG. 4 shows a flow chart 40 of an operation that can be followed by the software in the processor used to erase the blocks. At step 41, the software can transmit the multi-block erase command to the flash memory device on the first cycle of the command sequence. In a subsequent cycle, the software can transmit a block address at step 42. As long as the final block address has not been transmitted, as detected at step 43, the software can continue transmitting block addresses at step 42. Once the final block address has been transmitted, the software can transmit the Confirm command at step 44, which can directs the flash memory to erase all the specified blocks.

[0024] FIG. 5 shows a block diagram of the relevant portions of a system 50 of the invention. CPU 51, under the direction of appropriate software, can issue commands and data to flash memory system 52 over bus 55. Flash controller 53 can receive the commands, store the address indicators, configure the control signals, and perform a block erase on selected ones of blocks 54(1)-54(N).

[0025] It should be understood that, in addition to block erase, there are various other commands that can be issued by CPU 51 to flash memory 52 over bus 55, such as Write Data, Read Data, Read Status, etc. Most of these are not part of the invention, and in at least one embodiment may continue to operate in the conventional manner. FIG. 6 shows a timing diagram of the bus signals during a command sequence for one embodiment of the invention. In this particular embodiment, an asynchronous bus is used, meaning that it does not use a clock signal to synchronize signals. Instead, the Write Enable (WE#) signal is used to provide a timing reference for examining the other signal lines in a command. The “#” symbol on this and other signals indicates a low-active signal, i.e., the indicated function is asserted when the signal is low. When WE# goes low, a write operation on the bus is indicated, and when WE# goes from low to high, as indicated by the vertical lines in FIG. 6, the address and data lines are examined by the target device. On this bus, the Chip Enable (CE#) signal can select the target device so that the device can recognize and respond to the operation in progress. When CE# is high (de-asserted) the device is not selected and can be placed in a low-power standby mode. Each device on the bus can have its own separate CE# line, so normally only the device intended to receive the command will be enabled. The signal Output Enable (OE#) can be used to enable the data line drivers of the selected device so that it can place data on the data lines. This typically only occurs during a read operation. Since the block erase function is a write operation, the OE# signal in FIG. 6 is shown deactivated (high) throughout the period in question.

[0026] Multiple address lines AD provide the address(es) of the target device for the command. For a flash memory device, the AD lines can address any location within the range of the flash memory. Since a flash memory is typically embedded in the address scheme of a much larger memory system, the memory range in the flash memory will typically be a small subset of the range that can be addressed by address lines AD. Multiple flash memory devices can be on the bus, each with its own address range.

[0027] Multiple DATA lines provide the data to be transferred to or from the target device. In one embodiment, there are sixteen bi-directional DATA lines for data and command transfers. Data can be transferred from the CPU to a target device over this bus by placing an address of the device on the ADDRESS lines and selecting the device by asserting its CE# line, as shown at cycle 1. The data to be written can be placed on the DATA lines. When the WE# line is asserted and then de-asserted, the selected device can read the address and data lines, and perform whatever action is indicated by the command.

[0028] In the invention, a series of these commands can be combined into a command sequence, so that CE# and WE# will be activated multiple times, with each activation being used to transfer information over the bus. For example, after activating the CE# line to the flash memory device, a multi-block Erase Command can be initiated by placing any address within the flash memory on the ADDRESS lines, indicated in the figure as AD_EC, and placing a specific code on the DATA lines, indicated in the figure by EC. In one embodiment, the code 20(h) is placed on the lower byte of the DATA lines to indicate the multi-block erase command. When this code is read by the flash memory controller, the controller knows that a multi-block erase function is being initiated, and that the following commands received by the flash memory controller will identify the blocks to be erased. At the completion of this first cycle, CE# and WE# can both be deactivated, and the bus can become available for other transfers by other devices.

[0029] At a later time, shown as cycle 2 in FIG. 6, CE# and WE# can again be activated to initiate another write function to the flash memory controller on the bus. This second cycle in the sequence is devoted to transferring an address, shown as AD₁, of one of the blocks to be erased. The block can be specified by placing its address on the ADDRESS lines. In one embodiment, any address within that particular block can be placed on the ADDRESS lines, and the flash memory controller will interpret the command to mean the particular block containing that address is one of the blocks to be erased. This can be accomplished simply by ignoring the lower bits of the address, which specify a location within the block, so that the remaining address bits uniquely identify the block itself. During this cycle, the DATA lines can be examined for a Confirm command. If it is not seen, then this cycle can be interpreted as an address cycle as described above.

[0030] In other subsequent cycles, other block addresses can be conveyed in this manner. Cycle 3 shows a second block address, AD₂, being transferred in the same manner as was AD₁. After the last block address has been transferred in this manner, a Confirm command can be issued by placing another specific bit pattern on the DATA lines, such as DO(h) on the lower eight bits of the data lines. The Confirm command is shown as CC in cycle 4 of FIG. 6. Again, the ADDRESS lines during the CC command can be any address within the flash memory. The Confirm command is the command that tells the flash memory that the command sequence is now complete. This can trigger the flash memory to begin the block erase process on the blocks specified during the previous commands in the sequence.

[0031] The block erase process may take a full second or more, and the flash memory might not be available for reading or writing data during that time. The software can determine when the erase process is complete by reading the status of the flash memory, which can be done with a conventional READ STATUS command (not shown).

[0032] In the just-described embodiment, the primary distinction between a command that transfers a block number, and a command that signifies Erase or Confirm, is the presence of the command code on the DATA lines. For this reason, it is important to make sure the data lines do not inadvertently create a viable command when a block address command was intended. This can be accomplished by placing a code (such as all 0's) on the data lines during a block address transfer that does not correspond to any code that would cause the transfer to terminate prematurely.

[0033] For clarity, FIG. 6 shows the aforementioned command sequence taking place over four consecutive cycles on the bus (from the processor's point of view). However, it is not necessary to use consecutive cycles. Since the CE# line to the flash memory controller is inactive between the command cycles that address the flash memory controller, that controller has no knowledge of what transpires on the bus during those inactive periods. Thus it is possible for other devices to use the bus between the memory controller cycles. For simplicity, this possibility is not illustrated in FIG. 6, and those of skill in the art will appreciate that the presence of other bus cycles to other bus devices would have no effect on the operation of the controller, other than possibly to increase the total elapsed time it takes to complete the command sequence.

[0034] An asynchronous bus with particular signal configurations has been used to demonstrate an embodiment of the invention. However, another bus, including a synchronous bus, could be used without departing from the spirit of the invention.

[0035] Various aspects of the invention can be implemented in circuitry or as a method. The invention can also be implemented as instructions stored on a machine-readable medium, which can be read and executed by at least one processor to perform the functions described herein. A machine-readable medium includes any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computer). For example, a machine-readable medium can include read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; electrical, optical, acoustical or other form of propagated signals (e.g., carrier waves, infrared signals, digital signals, etc.), and others.

[0036] The foregoing description is intended to be illustrative and not limiting. Variations will occur to those of skill in the art. Those variations are intended to be included in the invention, which is limited only by the spirit and scope of the appended claims.