News Column

Researchers Submit Patent Application, "Maintaining Ordering via a Multi-Level Map of a Solid-State Media", for Approval

March 6, 2014

By a News Reporter-Staff News Editor at Politics & Government Week -- From Washington, D.C., VerticalNews journalists report that a patent application by the inventors Cohen, Earl T. (Oakland, CA); Baryudin, Leonid (San Jose, CA), filed on September 10, 2013, was made available online on February 20, 2014.

The patent's assignee is LSI Corporation.

News editors obtained the following quote from the background information supplied by the inventors: "Flash memory is a non-volatile memory (NVM) that is a specific type of electrically erasable programmable read-only memory (EEPROM). One commonly employed type of flash memory technology is NAND flash memory. NAND flash memory requires small chip area per cell and is typically divided into one or more banks or planes. Each bank is divided into blocks; each block is divided into pages. Each page includes a number of bytes for storing user data, error correction code (ECC) information, or both.

"There are three basic operations for NAND devices: read, write and erase. The read and write operations are performed on a page-by-page basis. Page sizes are generally 2.sup.N bytes of user data (plus additional bytes for ECC information), where N is an integer, with typical user data page sizes of, for example, 2,048 bytes (2 KB), 4,096 bytes (4 KB), 8,192 bytes (8 KB) or more per page. A 'read unit' is the smallest amount of data and corresponding ECC information that can be read from the NVM and corrected by the ECC, and might typically be between 4K bits and 32K bits (e.g., there is generally an integer number of read units per page). Pages are typically arranged in blocks, and an erase operation is performed on a block-by-block basis. Typical block sizes are, for example, 64, 128 or more pages per block. Pages must be written sequentially, usually from a low address to a high address within a block. Lower addresses cannot be rewritten until the block is erased. Associated with each page is a spare area (typically 100-640 bytes) generally used for storage of ECC information and/or other metadata used for memory management. The ECC information is generally employed to detect and correct errors in the user data stored in the page, and the metadata might be used for mapping logical addresses to and from physical addresses. In NAND flash chips with multiple banks, multi-bank operations might be supported that allow pages from each bank to be accessed substantially in parallel.

"NAND flash memory stores information in an array of memory cells made from floating gate transistors. These transistors hold their voltage level, also referred to as charge, for long periods of time, on the order of months or years, without external power being supplied. In single-level cell (SLC) flash memory, each cell stores one bit of information. In multi-level cell (MLC) flash memory, each cell can store more than one bit per cell by choosing between multiple levels of electrical charge to apply to the floating gates of its cells. MLC NAND flash memory employs multiple voltage levels per cell with a serially linked transistor arrangement to allow more bits to be stored using the same number of transistors. Thus, considered individually, each cell has a particular programmed charge corresponding to the logical bit value(s) stored in the cell (e.g., 0 or 1 for SLC flash; 00, 01, 10, 11 for MLC flash), and the cells are read based on one or more threshold voltages for each cell. However, increasing the number of bits per cell increases cell-to-cell interference and retention noise, increasing the likelihood of read errors and, thus, the bit error ratio (BER) of the system. Further, the read threshold voltages of each cell change over operating time of the NVM, for example due to read disturb, write disturb, retention loss, cell aging and process, voltage and temperature (PVT) variations, also increasing BER.

"As described, typical NVMs require that a block be erased before new data can be written to the block. Thus, NVM systems, such as solid-state disks (SSDs) employing one or more NVM chips, typically periodically initiate a 'garbage collection' process to erase data that is 'stale' or out-of-date to prevent the flash memory from filling up with data that is mostly out-of-date, which would reduce the realized flash memory capacity. However, NVM blocks can be erased only a limited number of times before device failure. For example, a SLC flash might only be able to be erased on the order of 100,000 times, and a MLC flash might only be able to be erased on the order of 10,000 times. Therefore, over the operational life (e.g., over a rated number of program/erase (P/E) cycles for NAND flash) of an NVM, the NVM wears and blocks of flash memory will fail and become unusable. Block failure in NVMs is analogous to sector failures in hard disk drives (HDDs). Typical NVM systems might also perform wear-leveling to distribute, as evenly as possible, P/E cycles over all blocks of the NVM. Thus, over the lifetime of an NVM system, the overall storage capacity might be reduced as the number of bad blocks increases and/or the amount of storage used for system data requirements (e.g., logical-to-physical translation tables, logs, metadata, ECC, etc.) increases. Thus, it can be important to reduce the amount of data written to the NVM during the garbage collection process.

"During the garbage collection process, user data in a block which is still valid is moved to new location on the storage media in a background process. 'Valid' user data might be any address that has been written at least once, even if the host device is no longer using this data. To reduce the amount of 'valid' but no longer needed data that is rewritten during garbage collection, some storage protocols support commands that enable an NVM to designate blocks of previously saved data as unneeded or invalid such that the blocks are not moved during garbage collection, and the blocks can be made available to store new data. Examples of such commands are the SATA TRIM (Data Set Management) command, the SCSI UNMAP command, the MultiMediaCard (MMC) ERASE command, and the Secure Digital (SD) card ERASE command. Generally, such commands improve NVM performance such that a fully trimmed NVM has performance approaching that of a newly manufactured (i.e., empty) NVM of the same type. However, performing these commands for large numbers of blocks at once can be time consuming and reduce operating efficiency of the NVM."

As a supplement to the background information on this patent application, VerticalNews correspondents also obtained the inventors' summary information for this patent application: "This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

"Described embodiments provide a media controller that processes requests from a host device that include a logical address and address range. A map of the media controller determines physical addresses of a solid-state media associated with the logical address and address range of the request. The map is a multi-level map having a plurality of leaf-level map pages that are stored in the solid-state media, with a subset of the leaf-level map pages stored in a map cache. Each leaf-level map page includes map entries that are each associated with physical addresses of the solid-state media. Based on the logical address and address range, it is determined whether a corresponding leaf-level map page is stored in the map cache. If the leaf-level map page is stored in the map cache, a cache index and control indicators of the map cache entry are returned in order to enforce ordering rules that selectively enable access to a corresponding leaf-level map page based on the control indicators and a determined request type.


"Other aspects, features, and advantages of described embodiments will become more fully apparent from the following detailed description, the appended claims, and the accompanying drawings in which like reference numerals identify similar or identical elements.

"FIG. 1 shows a block diagram of a flash memory storage system in accordance with exemplary embodiments;

"FIG. 2 shows an exemplary functional block diagram of a single standard flash memory cell;

"FIG. 3 shows an exemplary NAND MLC flash memory cell in accordance with exemplary embodiments;

"FIG. 4 shows a block diagram of an exemplary arrangement of the flash memory of the flash memory storage system of FIG. 1;

"FIG. 4 shows a block diagram of an exemplary arrangement of the solid state media of the flash memory storage system of FIG. 1;

"FIG. 5 shows a block diagram of an exemplary mapping of a logical page number (LPN) portion of a logical block number (LBA) of the flash memory storage system of FIG. 1;

"FIG. 6 shows a block diagram of an exemplary two-level mapping structure of the flash memory storage system of FIG. 1;

"FIG. 7 shows a block diagram of exemplary map page headers employed by the flash memory storage system of FIG. 1;

"FIG. 8 shows an exemplary flow diagram of a Mega-TRIM operation employed by the flash memory storage system of FIG. 1

"FIG. 9 shows an exemplary block diagram of a lower-level map page cache data structure employed by the flash memory storage system of FIG. 1;

"FIG. 10 shows an exemplary flow diagram of a host request processing operation employed by the flash memory storage system of FIG. 1; and

"FIG. 11 shows an exemplary flow diagram of a host request processing operation employed by the flash memory storage system of FIG. 1."

For additional information on this patent application, see: Cohen, Earl T.; Baryudin, Leonid. Maintaining Ordering via a Multi-Level Map of a Solid-State Media. Filed September 10, 2013 and posted February 20, 2014. Patent URL:

Keywords for this news article include: LSI Corporation.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC

For more stories covering the world of technology, please see HispanicBusiness' Tech Channel

Source: Politics & Government Week

Story Tools