Storage module and method for improving boot time during block binary searches

A storage controller is configured to find a last-written page in a block in a memory by sending a command to the memory to read a page of data, receiving at least some of the data from that page, and analyzing the at least some of the data from that page to determine if that page is a written page. In one embodiment, the storage controller instructs the memory to read the page of data using a sense time that is shorter than a sense time used to read a page of data in response to a read request from a host controller. Additionally or alternatively, the amount of the data received by the storage controller can be less than the amount of data received when reading a page of data in response to a read request from a host controller.

PRIORITY

This application claims priority to India Patent Application No. 845/MUM/2014, filed on Mar. 13, 2014, entitled “Storage Module and Method for Improving Boot Time During Block Binary Searches,” the entire disclosure of which is hereby incorporated by reference.

BACKGROUND

Many storage modules contain a controller and one or more memory units (e.g., NAND dies). When the storage module boots up, the storage module performs several functions, such as attempting to find the last written page in each of the open blocks in memory. To find the last written page, the controller can perform a binary search technique in which the controller reads various pages in the open block in a guess-and-check fashion until it finds the last written page. In this process, the controller commands the memory unit to read a certain page of data. In response to this command, the memory unit senses the memory cells in the page and stores them in latches in the memory unit. The controller then reads the data out of the latches (a process known as “toggling”) and counts the number of 0s and/or 1s in the read-out data and compares the number to some threshold to determine whether or not that page was written with data. Since pages are typically written sequentially in the block, the controller can follow a “funnel” approach in which the controller reads pages in various locations in the block (e.g., half way down the block, then a quarter way down the block, then an eighth way down the block, etc.) until the controller finds the last written page. This process is repeated for each open block in the memory. Once the last written page is located for each open block, the storage module is ready to accept commands from the host controller. Typically, a storage module will have a target boot time (e.g., 40 ms) from power on reset to being able to accept the first host command.

OVERVIEW

Embodiments of the present invention are defined by the claims, and nothing in this section should be taken as a limitation on those claims.

By way of introduction, the below embodiments relate to a storage module and method for improving boot time during block binary searches. In one embodiment, a storage module is provided comprising a memory and a storage controller. The storage controller is configured to find a last-written page in a block in the memory by (a) sending a command to the memory to read a page of data, (b) receiving at least some of the data from that page in response to the command, (c) analyzing the at least some of the data from that page to determine if that page is a written page, and (d) repeating (a)-(c) for different pages in the block until the last-written page is found. In one embodiment, the storage controller instructs the memory to read the page of data using a sense time that is shorter than a sense time used to read a page of data in response to a read request from a host controller. Additionally or alternatively, the amount of data received by the storage controller can be less than the amount of data received when reading a page of data in response to a read request from a host controller.

DETAILED DESCRIPTION OF THE PRESENTLY PREFERRED EMBODIMENTS

As mentioned in the background section above, finding the last written page for each open block of memory in a storage module using a block binary search can result in a relatively long boot time. The following embodiments can be used to improve boot time during block binary searches and better meet target boot times. Before turning to these and other embodiments, the following paragraphs provide a discussion of exemplary storage modules that can be used with these embodiments. Of course, these are just examples, and other suitable types of storage modules can be used.

As illustrated inFIG. 1, a storage module100of one embodiment comprises a storage controller110and non-volatile memory120. The storage controller110comprises a memory interface111for interfacing with the non-volatile memory120and a host interface112for placing the storage module100operatively in communication with a host controller. As used herein, the phrase “operatively in communication with” could mean directly in communication with or indirectly in (wired or wireless) communication with through one or more components, which may or may not be shown or described herein.

As shown inFIG. 2A, the storage module100can be embedded in a host210having a host controller220. That is, the host210embodies the host controller220and the storage module100, such that the host controller220interfaces with the embedded storage module100to manage its operations. For example, the storage module100can take the form of an iNAND™ eSD/eMMC embedded flash drive by SanDisk Corporation, or, more generally, any type of solid state drive (SSD), a hybrid storage device (having both a hard disk drive and a solid state drive), and a memory caching system. The host controller220can interface with the embedded storage module100using, for example, an eMMC host interface or a UFS interface. The host210can take any form, such as, but not limited to, a mobile phone, a tablet computer, a digital media player, a game device, a personal digital assistant (PDA), a mobile (e.g., notebook, laptop) personal computer (PC), or a book reader. As shown inFIG. 2A, the host210can include optional other functionality modules230. For example, if the host210is a mobile phone, the other functionality modules230can include hardware and/or software components to make and place telephone calls. As another example, if the host210has network connectivity capabilities, the other functionality modules230can include a network interface. Of course, these are just some examples, and other implementations can be used. Also, the host210can include other components (e.g., an audio output, input-output ports, etc.) that are not shown inFIG. 2Ato simplify the drawing. It should be noted that while the host controller220can control the storage module100, the storage module100can have its own controller to control its internal memory operations.

As shown inFIG. 2B, instead of being an embedded device in a host, the storage module100can have physical and electrical connectors that allow the storage module100to be removably connected to a host240(having a host controller245) via mating connectors. As such, the storage module100is a separate device from (and is not embedded in) the host240. In this example, the storage module100can be a handheld, removable memory device, such as a Secure Digital (SD) memory card, a microSD memory card, a Compact Flash (CF) memory card, or a universal serial bus (USB) device (with a USB interface to the host), and the host240is a separate device, such as a mobile phone, a tablet computer, a digital media player, a game device, a personal digital assistant (PDA), a mobile (e.g., notebook, laptop) personal computer (PC), or a book reader, for example.

InFIGS. 2A and 2B, the storage module100is in communication with a host controller220or host240via the host interface112shown inFIG. 1. The host interface112can take any suitable form, such as, but not limited to, an eMMC host interface, a UFS interface, and a USB interface. The host interface110in the storage module110conveys memory management commands from the host controller220(FIG. 2A) or host240(FIG. 2B) to the storage controller110, and also conveys memory responses from the storage controller110to the host controller220(FIG. 2A) or host240(FIG. 2B). Also, it should be noted that when the storage module110is embedded in the host210, some or all of the functions described herein as being performed by the storage controller110in the storage module100can instead be performed by the host controller220.

Returning toFIG. 1, the storage controller110comprises a central processing unit (CPU)113, an optional hardware crypto-engine114operative to provide encryption and/or decryption operations, read access memory (RAM)215, read only memory (ROM)116which can store firmware for the basic operations of the storage module100, and a non-volatile memory (NVM)117which can store a device-specific key used for encryption/decryption operations, when used. The storage controller110can be implemented in any suitable manner. For example, the storage controller110can take the form of a microprocessor or processor and a computer-readable medium that stores computer-readable program code (e.g., software or firmware) executable by the (micro)processor, logic gates, switches, an application specific integrated circuit (ASIC), a programmable logic controller, and an embedded microcontroller, for example. Suitable controllers can be obtained from SanDisk or other vendors. The storage controller110can be configured with hardware and/or software to perform the various functions described below and shown in the flow charts. Also, some of the components shown as being internal to the storage controller110can also be stored external to the storage controller110, and other component can be used. For example, the RAM115(or an additional RAM unit) can be located outside of the controller die and used as a page buffer for data read from and/or to be written to the memory120.

The non-volatile memory120can also take any suitable form. For example, in one embodiment, the non-volatile memory120takes the form of a solid-state (e.g., flash) memory and can be one-time programmable, few-time programmable, or many-time programmable. The non-volatile memory120can also use single-level cell (SLC), multiple-level cell (MLC), triple-level cell (TLC), or other memory technologies, now known or later developed. Also, the non-volatile memory120can be a two-dimensional memory or a three-dimensional memory.

Turning again to the drawings,FIG. 3is a diagram of another exemplary storage module300of an embodiment. This storage module300comprises a storage controller310in communicate with a plurality of memory dies320. The storage controller310comprises a plurality of CPUs313in communication with a plurality of Flash interface modules (FIMs) via a plurality of buses312. Each FIM is in communication with one or more memory dies320via a bus. Also, each FIM has a data mis-compare counter (DMC)315,316that can count 1s and/or 0s in data read from the memory dies320. The DMCs are used in block binary searches to find the last written page for each open block of memory. This process is described in more detail below and in conjunction withFIGS. 4 and 5.

FIG. 4illustrates a Flash block400in the memory die500shown inFIG. 5(the memory die500has M blocks in each plane of memory, and there can be one or more planes of memory). In this block400, wordlines0-3are programmed, and wordlines4-N are erased, where each wordline corresponds to a page in the block400. The storage controller310knows (e.g., via a stored pointer) which of the blocks in the memory die500are open (i.e., have unwritten pages). For example, of 32,000 blocks in memory, there may only be 12 open blocks.

To find the last-written page in the block400(here, wordline3), a binary block search is performed in which the storage controller310sends a command via the NAND bus520to the memory die500to read a page of data (the memory die500receives the command via a NAND interface module510). To read the page, the memory die500powers the wordline associated with the page and then powers each of the bitlines in the page to sense the data value stored in each of the memory cells in the page. Those data values are stored in a volatile data latch540, where they reside until the storage controller100reads the values out of the latch540in a process known as “toggling” the data.

When the storage controller310receives the data toggled from the data latch540, the storage controller310analyzes the data to determine if that page is a written page (e.g., using the DMC counters to count the number of 0s or 1s in a page, where 1 represents an unwritten memory cell in this example). This process is repeated for different pages in the block until the last-written page is found. For example, in the illustration inFIG. 4, step1of the process is to read the middle of the block (wordline N/2) to see whether or not it contains a programmed page. In step2, the storage controller310detects that wordline N/2 is not erased, so it assumes that wordlines N/2 to N are erased, as programming is done sequentially in this example. In step3, the storage controller310divides the wordline number by 2 and reads that page, but that wordline is also erased. So, in step4, the storage controller310divides the wordline number by 4 and reads that page, but that wordline is also erased. This process is repeated until, eventually, a programmed wordline is found, which here, is wordline4. The storage controller310looks at another wordline (here, wordline2) and sees that it is programmed. Finally, the storage controller310sees that wordline3is programmed, so it knows that, because wordline4is unprogrammed, wordline3must contain the last written page. If the storage module300supports partial-page programming (e.g., for SLC cells) and only part of a wordline is programmed, the storage controller310can read the entire wordline to detect where the last programmed memory cells are in the wordline.

As mentioned above, this process of finding the last written page for each open block of memory in a storage module using block binary searches can take a relatively long time, and a short boot time is desired. For example, a storage module may need to meet a boot time of 40 mS from power on reset to being able to accept the first host command. Within that 40 mS time budget, the back-end CPU may be allocated 5 ms to prepare the media management layer (MML), which is the firmware code responsible for logical-to-physical address translation. If the storage module300has multiple back-end CPUs running in parallel, each back-end CPU is budgeted the full 5 mS. Also, if each back-end CPU is managing multiple Flash interface modules (FIMs), the FIMs may require some CPU interaction (e.g., to manage the accelerators) and will run the operations slightly in parallel.

In prior approaches to find the last-written page, the storage controller senses a page (using a MLC or SLC sense) then toggles a full error correction code (ECC) codeword of data (e.g., 4 KB, which includes both data and parity bits)) and counts the number of 1s in the page to detect if the page is erased (some senses may be done within a physical page if the write is to an SLC block and the design supports partial page programming). The number of 1s is compared against a threshold to determine if the data is erased. The data is not decoded by the low density parity check (LDPC) engine, so integrity of the data is not critical.

To reduce the time spend finding the last-written page, these embodiments recognize that a “rough” sense can be performed (as compared to a “normal” sense that would be performed when a host controller is requesting data to be read) to indicate whether or not data is programmed to a given wordline. This can done by changing the parameters that control the settling time to trade off speed vs. accuracy. The concept is that the system is not trying to resolve detailed er/A/B/C states with low error rates. The system simply needs a rough approximation of whether the data has been programmed or not. The storage controller310can changes the Flash sense parameters via a command from the storage controller310to the memory die. The storage controller310can change these NAND parameters only for the erase detection operation, and, after the erased detection operation, can revert the parameters back to a normal sense.

These embodiments recognize that the storage controller310can tolerate some errors in the settled waveforms for faster waveforms by lowering the bitline settling times. The margins in case of an all-FFh pattern (erase) are better compared to a random pattern, and so, this is an advantage in determining an erased page. All settling times can be reduced to remove the margins that are normally associated with achieving a low bit error rate of MLC sensing. Also, for erase detection, MLC pages can be sensed as SLC pages (since only one threshold is used between the ER and A states), when MLC memory would normally have 3 thresholds Er-A, A-B, B-C.

Since accuracy of the data is not a concern in detecting the last-written page, the objective of the storage controller310really is to detect the presence (or absence) of data and not to decode the data itself. So, in one embodiment, the storage controller310instructs the memory to read a page of data using a sense time that is shorter than a sense time used to read a page of data in response to a read request from a host controller. For example, the storage controller310can instruct the memory to read the page of data using a sense time of about 15 micro-seconds, wherein the sense time used to read a page of data in response to a read request from a host controller can be about 40 micro-seconds. The memory still toggles the data to the storage controller310so that the data will be counted by the data mis-compare counter (DMC) part of the controller. It is expected that the data integrity of this quick sense will be less and may will require a new set of DMC thresholds to compare against (i.e., because the embodiment introduces a level of noise in the sense, the DMC thresholds may need to reflect the less-accurate reads).

In addition to or instead of reducing the sense time when reading data for the purposes of finding the last-written page, the amount of data toggled back to the storage controller310from the memory can be less than when reading a page of data in response to a read request from a host controller. The storage controller310can do this simply by controlling how much data it strobes out of the latches. For example, if the data returned from a “normal” read is about 4 KB, the data returned from a “rough” read can be about 100 bytes. (In this example, one page contains 8 or 16 KB of data, and one block has 128 wordlines, where each wordline is a page.) For example, instead of toggling out the entire error correction code (ECC) codeword, the storage controller310can instead toggle out just the parity bits of the ECC codeword. As the parity bits are typically randomly distributed, the storage controller310can sample this small subsection of the codeword and still determine whether or not the page is written.

FIG. 6is a chart that illustrates the advantages of these embodiments. This chart assumes that the memory has six open blocks and that the storage controller310will require nine reads to find the last-written page. As shown in the third line in the chart, a standard read (e.g., to read a page of data in response to a read request from a host controller) takes 40 micro-seconds, wherein the reduced sense time in this example is 15 micro-seconds. Additionally or alternatively, the amount of data toggled per read can be reduced from 4 KB to 100 bytes. This chart also shows that, because the DMC counts the ones as the data is coming across the bus, there is no time overhead in the counting process. The net result is a reduction from 2,754 micro-seconds to 2,173.5 micro-seconds if only reduced toggle is used, 1,404 micro-seconds if only reduced sense is used, and 823.5 micro-seconds if both reduced toggle and reduced sense are used. Thus, the use of these embodiments greatly reduces the boot time, helping ensure that the boot requirements are met faster, so the storage controller310can service host commands sooner.

There are many alternatives that can be used with these embodiments. For example, to avoid toggling any data at all, the memory die itself can contain a counter700to enable even faster detection of the last-written page (seeFIG. 7). As shown in the timing diagram inFIG. 8, the storage controller310can provide the block number to the memory die, and the memory die can scan the wordlines internally to locate the last-written page. More specifically, the NAND can scan the wordlines and count the 1s internally and produce the count to the storage controller310(as opposed to the NAND doing a binary and linear search). This means the high-level intelligence stays in the storage controller310, but the counting is done internal to the NAND, which frees the NAND bus from the transfer.

Multiple memory elements may be configured so that they are connected in series or such that each element is individually accessible. By way of non-limiting example, NAND devices contain memory elements (e.g., devices containing a charge storage region) connected in series. For example, a NAND memory array may be configured so that the array is composed of multiple strings of memory in which each string is composed of multiple memory elements sharing a single bit line and accessed as a group. In contrast, memory elements may be configured so that each element is individually accessible, e.g., a NOR memory array. One of skill in the art will recognize that the NAND and NOR memory configurations are exemplary, and memory elements may be otherwise configured.

The semiconductor memory elements of a single device, such as elements located within and/or over the same substrate or in a single die, may be distributed in two or three dimensions, such as a two dimensional array structure or a three dimensional array structure.

In a two dimensional memory structure, the semiconductor memory elements are arranged in a single plane or single memory device level. Typically, in a two dimensional memory structure, memory elements are located in a plane (e.g., in an x-z direction plane) which extends substantially parallel to a major surface of a substrate that supports the memory elements. The substrate may be a wafer over which the layers of the memory elements are deposited and/or in which memory elements are formed or it may be a carrier substrate which is attached to the memory elements after they are formed. As a non-limiting example, the substrate may include a semiconductor such as silicon.

A three dimensional memory array is organized so that memory elements occupy multiple planes or multiple device levels, forming a structure in three dimensions (i.e., in the x, y and z directions, where the y direction is substantially perpendicular and the x and z directions are substantially parallel to the major surface of the substrate).

As a non-limiting example, each plane in a three dimensional memory array structure may be physically located in two dimensions (one memory level) with multiple two dimensional memory levels to form a three dimensional memory array structure. As another non-limiting example, a three dimensional memory array may be physically structured as multiple vertical columns (e.g., columns extending substantially perpendicular to the major surface of the substrate in the y direction) having multiple elements in each column and therefore having elements spanning several vertically stacked memory planes. The columns may be arranged in a two dimensional configuration, e.g., in an x-z plane, thereby resulting in a three dimensional arrangement of memory elements. One of skill in the art will understand that other configurations of memory elements in three dimensions will also constitute a three dimensional memory array.

By way of non-limiting example, in a three dimensional NAND memory array, the memory elements may be connected together to form a NAND string within a single horizontal (e.g., x-z) plane. Alternatively, the memory elements may be connected together to extend through multiple horizontal planes. Other three dimensional configurations can be envisioned wherein some NAND strings contain memory elements in a single memory level while other strings contain memory elements which extend through multiple memory levels. Three dimensional memory arrays may also be designed in a NOR configuration and in a ReRAM configuration.

A monolithic three dimensional memory array is one in which multiple memory levels are formed above and/or within a single substrate, such as a semiconductor wafer. In a monolithic three dimensional array, the layers of each level of the array are formed on the layers of each underlying level of the array. One of skill in the art will understand that layers of adjacent levels of a monolithic three dimensional memory array may be shared or have intervening layers between memory levels. In contrast, two dimensional arrays may be formed separately and then packaged together to form a non-monolithic memory device. For example, non-monolithic stacked memories have been constructed by forming memory levels on separate substrates and adhering the memory levels atop each other. The substrates may be thinned or removed from the memory levels before bonding, but as the memory levels are initially formed over separate substrates, such memories are not monolithic three dimensional memory arrays. Further, multiple two dimensional memory arrays or three dimensional memory arrays (monolithic or non-monolithic) may be formed separately and then packaged together to form a stacked-chip memory device.

Associated circuitry is typically required for proper operation of the memory elements and for proper communication with the memory elements. This associated circuitry may be on the same substrate as the memory array and/or on a separate substrate. As non-limiting examples, the memory devices may have driver circuitry and control circuitry used in the programming and reading of the memory elements.

One of skill in the art will recognize that this invention is not limited to the two dimensional and three dimensional exemplary structures described but cover all relevant memory structures within the spirit and scope of the invention as described herein and as understood by one of skill in the art.