USOO8356152B2
`
`(12) United States Patent
`You
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,356,152 B2
`Jan. 15, 2013
`
`(54) INITIATIVE WEAR LEVELING FOR
`NON-VOLATILE MEMORY
`
`(75) Inventor: Guangqing You, Shanghai (CN)
`(73) Assignee: Intel Corporation, Santa Clara, CA
`(US)
`
`*) Notice:
`
`Subject to any disclaimer, the term of this
`y
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 580 days.
`
`(21) Appl. No.:
`(22) PCT Filed:
`
`12/519,521
`Dec. 27, 2006
`
`(86). PCT No.:
`
`PCT/CN2OO6/OO3615
`
`S371 (c)(1),
`Feb. 11, 2010
`(2), (4) Date:
`(87) PCT Pub. No.: WO2008/077284
`PCT Pub. Date: Jul. 3, 2008
`
`(65)
`
`Prior Publication Data
`US 2010/O161880 A1
`Jun. 24, 2010
`(51) Int. Cl
`(2006.01)
`Goof 1200
`711/165: 711/103: 711/173
`(52) U.S. Cl
`(58) Field of Classification search s
`71 1f103
`711/165,173
`See application file for complete search history.
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`5,341,339 A
`8, 1994 Wells
`5,479,638 A 12/1995 ASSar et al.
`5,485,595 A
`1/1996 ASSar et al.
`5,568,423. A 10/1996 Jou et al.
`5,835,935 A 11/1998 Estakhri et al.
`
`5,963,970 A 10, 1999 Davis
`6,000,006 A 12/1999 Bruce et al.
`6,016,275 A
`1/2000 Han
`6,081.447 A
`6/2000 Lofgren et al.
`6,230,233 B1
`5/2001 Lofgreen et al.
`6,341,085 B1
`1/2002 Yamagami et al.
`6,594, 183 B1
`7/2003 Lofgren et al.
`6,732,221 B2
`5, 2004 Ban
`6,850,443 B2
`2/2005 Lofgren et al.
`6,865,122 B2
`3/2005 Srinivasan
`(Continued)
`FOREIGN PATENT DOCUMENTS
`8-16482
`1, 1996
`Continued
`(Continued)
`OTHER PUBLICATIONS
`Non-Final Office Action for Korean Patent Application No. 10-2009
`7013437, mailed Dec. 3, 2010.
`(Continued)
`
`JP
`
`Primary Examiner — Jared Rutz
`Assistant Examiner — Gurte Bansal
`(74) Attorney, Agent, or Firm — Blakely, Sokoloff, Taylor &
`Zafman LLP
`
`ABSTRACT
`(57)
`A method and apparatus for initiative wear leveling for non
`volatile memory. An embodiment of a method includes
`counting erase cycles for each of a set of multiple memory
`blocks of a non-volatile memory, the counting of erase cycles
`for each memory block including incrementing a first count
`for a physical block address of the memory block, and if the
`memory block is not a spare memory block, incrementing a
`second count for a logical blockaddress of the memory block.
`The method also includes determining whether the non-vola
`tile memory has uneven wear of memory blocks based at least
`in part on the counting of the erase cycles of the plurality of
`memory blocks.
`
`16 Claims, 9 Drawing Sheets
`
`
`
`
`
`
`
`Background reclaim task
`spawned
`
`20S
`
`Foreverloop
`
`210
`
`Normal recai procedure
`p
`
`215
`
`Additional
`erase counts. ECMOP
`220
`
`> SOEH?
`225
`
`Yes
`Conduct worn block group
`swap
`
`230
`
`Micron Ex. 1043, p. 1
`Micron v. Vervain
`IPR2021-01547
`
`

`

`US 8,356,152 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`6,937,948 B2
`8/2005 Rajguru
`6,973,531 B1
`12/2005 Chang et al.
`6,985,992 B1
`1/2006 Chang et al.
`7,032,087 B1
`4/2006 Chang et al.
`7,035,967 B2
`4/2006 Chang et al.
`7.057,934 B2
`6/2006 Krishnamachari et al.
`7,106,636 B2
`9, 2006 Eilert et al.
`7,120,729 B2 10/2006 Gonzalez et al.
`2002fO184432 A1 12, 2002 Ban
`2003/0227804 Al 12/2003 Lofgren et al.
`2004/0083335 A1
`4/2004 Gonzalez et al. ............. T11 103
`2004/0210706 A1
`10, 2004 In et al.
`2005/0055495 A1
`3/2005 Vihmalo et al.
`5/2005 Lofgren et al.
`2005.0114589 A1
`2006, OO6985.0 A1
`3, 2006 Rudelic
`2006/0106755 A1*
`5/2006 Stuhec .............................. 707/1
`2006/0106972 A1
`5, 2006 GorobetSet al.
`
`FOREIGN PATENT DOCUMENTS
`WO WO2004/040578 A2
`5, 2004
`WO WO2004/040585 A1
`5, 2004
`
`OTHER PUBLICATIONS
`International Preliminary Report on Patentability for International
`Patent Application No. PCT/CN2006/003615, Mailed Jun. 30, 2009,
`4 pages.
`“Advantages of Large Erase Blocks'. Intel Corporation, Dec. 1998, 7
`pageS.
`
`"Electronic Tools Catalog'. http://appZone.intel.com/toolcatalog/
`list tools.asp?pid=4756&cid=588&pfamily=, Nov. 13, 2006, 2 pages.
`“Increasing Flash Solid State Disk Reliability'. http://www.
`storagesearch.com/siliconsys-art1.html. May 18, 2006, 12 pages.
`“Intel Flash Memory Software Builder'. http://www.intel.com/de
`sign? flash/Swb?psm.htm, Nov. 13, 2006, 4 pages.
`“Intel Flash Memory Software: Your Advantage for Cellular Hand
`sets”. Intel Corporation, 2006, 2 pages.
`“Intel NOR Flash Memory: Smart Choice for Cellular Handsets”.
`Intel Corporation, 2006, 2 pages.
`“NAND128-A, NAND256-A, NAND512-A, NANDO1G-A, 128
`Mbig, 256 Mbit, 512 Mbit, 1 Gbit (x8/x 16), 528 Byte/264 Word
`Page, 1.8V/3V, NAND Flash Memories, Apr. 2004, 56 pages.
`“SanDisk Flash Memory Cards Wear Leveling”, SanDisk Corpora
`tion, Oct. 2003, 6 pages.
`“TrueFFS Wear-Leveling Mechanism'. M-Systems Flash Disk Pio
`neers, Ltd., May 20, 2002, 4 pages.
`“Wear Leveling in Single Level Cell NAND Flash Memories”,
`STMicroelectronics, 2004, 6 pages.
`“What is Flash Memory?', http://www.intel.com/design/flashlar
`ticles/what.htm, Nov. 13, 2006, 7 pages.
`“Why Intel Flash Memory?', http://www.intel.com/design/flashlar
`ticles/297906.htm, Nov. 13, 2006, 2 pages.
`International Search Report and Written Opinion as issued in related
`International Patent Application No. PCT/CN2006/003615, on Sep.
`27, 2007, 9 pages.
`Office Action from JP Application No. 2009-543319 mailed Dec. 26,
`2011, 2 pages.
`
`* cited by examiner
`
`Micron Ex. 1043, p. 2
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Jan. 15, 2013
`
`Sheet 1 of 9
`
`OFl
`SM-
`@seJz]
`
`PLLLE
`ite
`
`Le
`LE
`
`O¢L
`
`SHIN-
`8selq
`
`Sel
`
`
`
`US 8,356,152 B2
`
`|bi
`OOL
`
`LL
`
`Micron Ex. 1043, p. 3
`Micron v. Vervain
`IPR2021-01547
`
`Micron Ex. 1043, p. 3
`Micron v. Vervain
`IPR2021-01547
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 15, 2013
`
`Sheet 2 of 9
`
`US 8,356,152 B2
`
`09
`
`deAWS
`
`
`
`dnou6 X100|q uJOWA ?onpuoO
`
`
`
`
`
`OLZ
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Micron Ex. 1043, p. 4
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Jan. 15, 2013
`
`Sheet 3 of 9
`
`US 8,356,152 B2
`
`CC
`CY)
`.9)
`l
`
`
`
`:
`
`s
`
`is
`co
`
`8
`
`itg
`l
`in
`3 in
`
`5
`
`g
`
`Micron Ex. 1043, p. 5
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Jan. 15, 2013
`
`Sheet 4 of 9
`
`US 8,356,152 B2
`
`09 #7
`
`07;
`
`
`
`907
`
`iz '61)
`
`Micron Ex. 1043, p. 6
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Jan. 15, 2013
`
`Sheet 5 Of 9
`
`US 8,356,152 B2
`
`
`
`
`
`G -61-I
`
`OZ7
`
`Micron Ex. 1043, p. 7
`Micron v. Vervain
`IPR2021-01547
`
`

`

`O95SSOOSPSPP44SeyOGYGé9
`
`U.S. Patent
`U.S. Patent
`
`pad
`
`
`
`j;YjA|||so
`
`WUE
`oLp
`
`MEG)
`\=OAG]
`W=03d]
`€8=098T
`OP=O3H1
`ORET
`eeOFeT
`
`Jan. 15, 2013
`
`|=
`|b
`|9
`
`po
`
`CUBESt=O8ad
`Li=ORdd
`pl=Oadd
`bl=Oaed
`9=05dd
`=088d
`
`
`
`Sheet 6 of 9
`
`US 8,356,152 B2
`US 8,356,152 B2
`
`9 B
`
`9:614
`is
`
`Ocr
`
`Micron Ex. 1043, p. 8
`Micron v. Vervain
`IPR2021-01547
`
`Micron Ex. 1043, p. 8
`Micron v. Vervain
`IPR2021-01547
`
`
`
`

`

`US 8,356,152 B2
`
`U.S. Patent
`
`09999/0979:77707#7G9#709/GZ9
`
`
`
`Micron Ex. 1043, p. 9
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Jan. 15, 2013
`
`Sheet 8 of 9
`
`US 8,356,152 B2
`
`
`
`Micron Ex. 1043, p. 10
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jan. 15, 2013
`
`Sheet 9 of 9
`
`US 8,356,152 B2
`
`6 ‘
`
`big
`
`006
`
`Micron Ex. 1043, p. 11
`Micron v. Vervain
`IPR2021-01547
`
`So6
`0s6
`
`adlAeg
`
`GE
`~~
`eq
`abelojis
`
`
`
`¢6
`
`AIUQ
`pese
`
`AJowsiyy
`
`
`
`NVI
`
`S96
`
`
`
`
`
`uoHeoIUuNWWOs
`JOSJnG)
`Josuns
`
`aolAaq
`
`Sr6
`
`joyuoy
`ealneq
`jndu|
`
`Oré
`
`Keldsiq
`
`shed
`
`Micron Ex. 1043, p. 11
`Micron v. Vervain
`IPR2021-01547
`
`
`
`
`
`
`
`
`
`
`

`

`1.
`NITIATIVE WEAR LEVELING FOR
`NON-VOLATILE MEMORY
`
`US 8,356,152 B2
`
`CROSS REFERENCE TO RELATED
`APPLICATION
`
`This patent application is a U.S. National Phase application
`under 35 U.S.C. S.371 of International Application No. PCT/
`CN2006/003615, filed on Dec. 27, 2006, entitled INITIA
`TIVE WEAR LEVELING FOR NON-VOLATILE
`MEMORY.
`
`FIELD
`
`Embodiments of the invention relate to computer memory.
`More particularly, embodiments of the invention relate to
`wear leveling for non-volatile memory.
`
`BACKGROUND
`
`10
`
`15
`
`In computer and electronic device operations, flash
`memory and similar non-volatile memory can provides great
`advantages in the maintenance of data, providing low power
`operation with low cost and high density. Because data is
`stored in a compact format that requires minimal power in
`operation and does not require power to maintain storage,
`Such memory is being used in increasing numbers of appli
`cations.
`However, non-volatile memory has certain downsides in
`operation. For example, memory such as flash memory has a
`limited lifespan in use because such memory tends to dete
`riorate with each write cycle. For this reason, if a certain
`portion of the memory is Subject to more write operations
`than other portions of the memory, then the portions with a
`greater number of writes will tend to deteriorate and ulti
`mately fail more quickly.
`In order to lengthen the overall lifespan of flash memory, a
`wear leveling process may be implemented. The wear level
`ing process is intended to more evenly distribute the wear
`over the storage device by directing write operations to less
`heavily used portions of the memory. This process may be
`handled by the memory controller, with the host system being
`unaware of the process.
`Wear leveling may include an algorithm for re-mapping
`logical block addresses to different physical block addresses
`in the device's Solid-state memory array.
`However, the algorithm used can greatly affect the effi
`ciency of memory operation and the effectiveness of the wear
`leveling process. Issues such as the timing of re-mapping
`processes, the manner in which the appropriate physical areas
`are identified for re-mapping, and related issues can greatly
`affect memory operation.
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Embodiments of the invention are illustrated by way of
`example, and not by way of limitation, in the figures of the
`accompanying drawings in which like reference numerals
`refer to similar elements:
`FIG. 1 is an illustration of an embodiment of a non-volatile
`memory;
`FIG. 2 is a flow chart to illustrate an embodiment of a wear
`leveling process;
`FIG. 3A is an illustration of a regression line generated for
`a non-volatile memory prior to wear leveling;
`
`60
`
`65
`
`2
`FIG. 3B is an illustration of a regression line generated for
`a non-volatile memory after an embodiment of wear leveling
`is implemented;
`FIGS. 4 through 7 illustrate an example of memory block
`reclaim operations in an embodiment of a wear leveling pro
`CeSS;
`FIG. 8 is an illustration of an embodiment of a non-volatile
`memory device; and
`FIG. 9 is an illustration of a computer system utilizing an
`embodiment of the invention.
`
`DETAILED DESCRIPTION
`
`An embodiment of the invention concerns initiative wear
`leveling for non-volatile memory.
`As used herein:
`“Non-volatile memory' means memory that retains
`memory contents when power is not applied to the memory.
`Non-volatile memory includes flash memory.
`“Flash memory’ means non-volatile computer memory
`that can be electrically erased and reprogrammed. Flash
`memory stores information in an array of floating gate tran
`sistors, called “cells’, each of which stores one or more bits of
`information. As used herein, “flash memory' may include
`any of the technologies for flash memory storage. For
`example, flash memory may include both NOR and NAND
`technology memory. In addition, flash memory may include
`technologies that provide varying numbers of bits of infor
`mation per memory cell, including single-bit-per-cell flash
`memory and multi-level cell structure allowing multiple bits
`per cell.
`“Wear” means usage of a non-volatile memory.
`“Block’ means a portion of a non-volatile memory array
`that may be erased in an operation, the block containing
`multiple cells. Individual cells of an erased flash memory
`block may be programmed, but cells within a block of a flash
`memory may only be changed by erasing the entire block of
`memory.
`In an embodiment of the invention, the uneven wear of
`flash or other non-volatile memory is addressed utilizing a
`wear leveling process. In an embodiment of the invention,
`wear leveling is implemented by exchanging data from a
`group of most worn memory blocks with data from a group of
`least worn memory blocks. In an embodiment, a wear level
`ing process for non-volatile memory includes the mainte
`nance of counts for erase operations for memory blocks both
`for each physical block address and for each logical block
`address. In an embodiment, the wear leveling process is trig
`gered at certain intervals when there is a determination that a
`slope of a line representing the physical block erase count and
`logical block erase count of each memory block is greater
`than a certain threshold.
`Non-volatile memory Such as flash memory has limitations
`in operation because the memory will only allow a certain
`finite number oferase-write cycles, and it is necessary to erase
`a block prior to writing any data into the cells of the block. For
`example, most commercially available flash products are
`guaranteed to withstand 1 million programming cycles. For
`this reason, care should to be taken when moving hard-drive
`based applications, such as operating systems, to flash
`memory based devices such as CompactFlash. The effect of
`uneven wear may be partially offset by certain chip firmware
`or file system drivers by counting the writes and dynamically
`remapping the blocks in order to spread the write operations
`between the sectors, or by write verification and remapping to
`
`Micron Ex. 1043, p. 12
`Micron v. Vervain
`IPR2021-01547
`
`

`

`US 8,356,152 B2
`
`10
`
`15
`
`3
`spare sectors in case of write failure. However, over time the
`variation in activity of data generally will result in uneven
`Wea.
`In the operation of nonvolatile memories, it is generally
`also recommended to implement a wear leveling process or
`algorithm to monitor and spread the number of write cycles
`that occur per block of memory. This is particularly important
`for write-intensive applications. If wear leveling is not imple
`mented, then memory blocks may be utilized at very different
`rates. Blocks with long-lived data are not required to endure
`as many erase-write cycles as the blocks with frequently
`changing data. The wear leveling process is intended to
`ensure that generally equal use is made of all the available
`write cycles for each block. In general, wear leveling may
`include exchanging data between memory blocks.
`In an embodiment of the invention, a wear leveling process
`(which may be referred to as IWL, or Initiative Wear Level
`ing) is implemented in non-volatile memory. In an embodi
`ment of the invention, the wear leveling for non-volatile
`memory includes the exchange of groups of memory blocks,
`rather than individual memory blocks. In this embodiment, a
`first group may represent the most highly worn memory
`blocks of a non-volatile memory device and a second group
`may represent the least worn memory blocks. The data may
`be exchanged between blocks in Such groups.
`In an embodiment of the invention, a process for wear
`leveling of non-volatile memory includes the recording of the
`number of erase operations for memory blocks both for physi
`cal and logical addresses. In an embodiment, in addition to
`maintaining PBEC (Physical Block Erase Count) value to
`track how many reclaim operations have occurred on a physi
`cal block, a LBEC (Logical Block Erase Count) value is
`maintained that is indexed by a logical block index for each
`memory block to track the change frequency of data per
`logical block. In this manner, each time a memory block is
`reclaimed its PBEC and LBEC values will each be increased
`by 1.
`In an embodiment, the following will be true regarding
`PBEC and LBEC values:
`1. PBEC increment=LBEC increment (the reclaiming of a
`40
`memory block with result in incrementing both PBEC
`and LBEC)
`2. Sum of total PBEC for device-Sum of total LBEC for
`the device
`3. Sum of total PBEC for device=Sum of total LBEC for the
`device if file system is initiated on a fresh memory
`device.
`If a file system is initialized and shut down and there has been
`no formatting of the memory, the LBEC and PBEC values are
`equal. If a memory device is formatted before a file system is
`initialized, then it may be assumed that the PBEC values are
`kept or restored after format is finished. However, LBEC
`values may be erased because the block data is erased. Since
`the block data in this case is used to reflect how active data is,
`there is no reason to save its LBEC after the data is deleted. As
`a result, for a fresh/new/total-erased memory device, the sum
`(LBEC)=Sum(PBEC). Once a format of the device has
`occurred, the LBECs have been erased, and subsequently the
`sum(PBEC) will be greater than sum(LBEC).
`In an embodiment of the invention, a PBEC field is utilized
`to track how many reclaim operations occurred on each
`physical block. In an embodiment, an additional LBEC field
`is indexed by logical block index to track the change fre
`quency of data by logical block. Thus, each time a logical data
`block is reclaimed, its LBEC will be increased by one, as well
`as the PBEC for the relevant physical data block being
`increased by one. In an embodiment:
`
`30
`
`4
`(1) PBEC increment=LBEC increment—each is incre
`mented by one each time a block is reclaimed
`(2) Sum of total PBEC2 sum of total LBEC
`(3) Sum of total PBEC=sum of total LBEC if file system
`initialized on a fresh flash.
`In an embodiment of the invention, at least two WBGs
`(Worn Block
`Groups) are designated in an IWL wear leveling process. A
`first group is referred to as the "high group'. The high group
`will have relatively high PBEC and high LBEC values, and
`may include any spare blocks because reclaim cycles happen
`frequently for space blocks of non-volatile memories. A sec
`ond group is referred to as the “low group' and will have
`relatively low PBEC and low LBEC, with spare blocks
`excluded. The IWL process is then intended to swap the
`high-LBEC logical blocks and low-LBEC logical blocks
`between the two groups, which may be accomplished through
`a series of reclaim operations. This procedure is referred to as
`the WBG swap. The purpose of the WBG swap is to populate
`long lived (low LBEC) data blocks to much worn (high
`PBEC) blocks and populate frequently changed (high LBEC)
`data blocks to less worn (low PBEC) blocks. In this operation,
`spare blocks have a high potential for being the next reclaim
`block and thus high-PBEC spare blocks are moved to the
`opposite group as well.
`However, a wear leveling process may affect certain com
`mon memory operations, including the normal reclaim opera
`tions. Because of this, wear leveling may require balancing
`against memory performance. In an embodiment of the inven
`tion, certain values may be set to affect the frequency of wear
`of wear leveling. In embodiment, a user may sets the ECMOD
`(erase count interval) and the SLOPETH values (slope thresh
`old). Increasing these values will reduce the performance
`cost, although at a potential cost of some life of the nonvola
`tile device.
`In an embodiment of the invention, a non-volatile memory
`includes wear leveling that is based at least in part upon the
`number of erase operations for each physical block of
`memory and the number of erase operations for each logical
`block of memory. In an embodiment, wear leveling opera
`tions are initiated when the slope of a regression line exceeds
`a threshold, the regression line being generated for the physi
`cal erase count for each block versus logical erase count for
`each Such block.
`In an embodiment of the invention, the initiation of an IWL
`process may be triggered by the slope of a line that is fit to a
`graph of the physical block and logical block erase counts for
`each memory block, with the slope of the line also being used
`to determine if the operation has been Successful. In an
`embodiment, a statistical method may be used to fit the line to
`the error count data. In a particular embodiment, linear
`regression is used to determine when an IWL operation is
`required and to measure how successful an executed IWL
`operation has been. Linear regression attempts to model the
`relationship between two variables by fitting a linear equation
`to observed data. The most common method for fitting a
`regression line is the least-squares method. The least squares
`line method applies an equation of the form f(x)=a+bX, which
`is a line graph having an interceptata and having a slope ofb.
`The method describes the trend of a raw data set (1, p1), (1.
`p2). . . . . (1, p.) as follows:
`
`25
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Micron Ex. 1043, p. 13
`Micron v. Vervain
`IPR2021-01547
`
`

`

`US 8,356,152 B2
`
`6
`is less than a second threshold, at which time the exchange
`process would cease. The process would then return to the
`original state, in which the worn block exchange process
`would be initiated when the slope of the regression line again
`exceeds the first threshold. In returning to normal operation,
`the slope of the regression line would again gradually
`increase as more erase cycles occur at certain highly active
`memory blocks.
`FIG. 1 is an illustration of an embodiment of a non-volatile
`memory.
`In this illustration, a non-volatile memory device 100
`includes an array of memory blocks 105. In one example, the
`array of memory blocks may 105 include a first memory
`block 110 having a physical blockaddress PB1 and a logical
`blockaddress LB7, and a second memory block 115 having a
`physical blockaddress PB4 and a logical blockaddress LB5.
`The addresses provided are simply an example, and any
`physical or logical address may be present. In each operation,
`each block of the memory array 105 may be subject to mul
`tiple erase and write cycles, with each cycle resulting in
`shortening the lifespan of the cells affected.
`As illustrated, the first memory block 110 may be relatively
`inactive, with the block being erased and a set of data A120
`being written 125 to the block 110. In contrast, the second
`memory block 115 is relatively active, with, for example, data
`B 130 being modified 135, resulting in multiple erase and
`write operations 140 to the cells of the second block 115, as
`each write process requiring an erasure of the data in the
`block. As a result, over time the wear on the second memory
`block 115 may be considerably greater than the wear on the
`first memory block 110.
`In an embodiment of the invention, the array of memory
`blocks is subjected to wear leveling to even the wear on the
`memory blocks. In this embodiment, the wear leveling is
`based upon a count for physical block write cycles and a count
`for logical block write cycles. In an embodiment, a wear
`leveling algorithm is initiated when the slope of a line fit to the
`physical block write cycles and the logical block write cycles
`by linear regression reaches a threshold. In an embodiment,
`the algorithm provides a data reclamation in which the data
`contained in a most wornblock group (which may include the
`second memory block 115) is exchanged for the data con
`tained in a least wornblock group (which may include the first
`memory block 110). In another example, the least worn group
`may include a spare memory block, spare blocks being very
`likely to be reclaimed. After the exchange between the des
`ignated groups, the remaining blocks may be subject to fur
`ther exchanges, with the process continuing until the slope of
`the regression line is no longer above the threshold.
`FIG. 2 is a flow chart to illustrate an embodiment of a wear
`leveling process. In this illustration, a background memory
`reclaim process is spawned 205, with the process including
`usual memory reclaiming and memory reclaiming for wear
`leveling. The reclaim process is in a form of what may be
`referred to as a “foreverloop' 210 that continues repeatedly in
`operation. In this loop normal memory reclaim processes
`occur 215.
`If ECMOD (error count modulus) additional erase counts
`have occurred 220, i.e., since the commencement of the back
`ground reclaim task or since the last wear leveling operation,
`then the wear leveling processing is initiated. The slope b of
`a regression line for physical block erase count (PBEC) and
`logical block erase count (LBEC) is evaluated in comparison
`with a threshold SLOPETH 225. If the slope b does not
`exceed the threshold, the loop continues. If the slope b
`exceeds the threshold, then a worn block group Swap is con
`ducted 230, with the data contained in the most worn group (a
`
`10
`
`15
`
`25
`
`35
`
`In the operation of a non-volatile memory device, there are
`three cases for regression line slope b:
`b=0, which may occur when a system is initialized on fresh
`flash or when wear leveling has been maintained
`b>0, which occurs when wear is unleveled; and
`b<0, which occurs in a successful process when WBGs
`have been Swapped.
`In an embodiment of the invention, wear leveling may be
`limited to occurring only after certain intervals. For example,
`ECMOD is the erase count interval that elapses prior to trig
`gering an IWL process. For example, ECMOD could be 1000
`cycles or less. Further, the triggering of the wear leveling is
`governed by SLOPETH, the PBEC-LBEC regression line
`slope threshold. In non-volatile memory, a normal reclaim
`operation may be used to reclaim a “dirty memory block
`containing invalid data, with the operation intended to free up
`the invalided memory space. In an IWL implementation, the
`normal reclaim procedure for the non-volatile memory is not
`modified, but the wear leveling process may affect the per
`formance of the background reclaim task. A user or designer
`may address the issues of memory life and customer perfor
`mance needs by adjusting the ECMOD and SLOPETH
`parameters, which operate together to determine the fre
`30
`quency of wear leveling. For example, a customer may reduce
`the performance cost of wear leveling by increasing ECMOD
`and SLOPETH.
`In an implementation of wear leveling, the processing may
`generally be handled by the solid-state memory controller,
`and thus be independent of the host system. In Such an imple
`mentation, the host system performs its reads and writes to
`logical block addresses only, and does not utilize the under
`lying physical block addresses. In this manner, the host will
`be unaware of any movements of data that occur as a result of
`40
`wear leveling. However, embodiments of the invention may
`vary with regard to memory control, and are not limited to any
`particular method of memory control.
`If a file system is initialized and shut down and there is no
`format operation, the increment of LBEC and increment of
`45
`PBEC are equal. However, before the file system is initial
`ized, if a flash is formatted PBEC is kept or restored after
`format is finished, but LBEC would be expected to be erased
`all because the block data is erased, and thus there no need to
`save its LBEC. As a result, for a fresh, new, or total-erased
`flash, its sum(LBEC)=sum(PBEC). Once a format happens,
`the LBECs are erased so the sum(PBEC) may be greater than
`sum(LBEC).
`In the examples provided, a single threshold value is uti
`lized for the determination of when to begin and when to end
`a wear leveling process. However, embodiments of the inven
`tion may utilize more than one threshold. In an embodiment
`of the invention, a process may utilize two thresholds to
`reduce the number of times that the exchange process is
`needed. In this example, a non-volatile memory is subject to
`normal use, which results in the gradual increase of a regres
`sion line fit to the values of the physical block erase count
`values and logical block erase count values of the memory
`blocks. A worn block exchange process may be initiated
`when the slope of a regression line for the memory blocks is
`above a first threshold. Once initiated, the worn block group
`exchanges may continue until the slope of the regression line
`
`50
`
`55
`
`60
`
`65
`
`Micron Ex. 1043, p. 14
`Micron v. Vervain
`IPR2021-01547
`
`

`

`US 8,356,152 B2
`
`5
`
`10
`
`15
`
`25
`
`7
`group that includes memory blocks with higher values of
`PBEC and LBEC, as well as spare memory blocks) being
`exchanged with the data contained in the least worn group (a
`group that includes memory blocks with lower values of
`PBEC and LBEC, excluding spare memory blocks). After the
`swap, the slope b is again compared to threshold SLOPETH
`225, with the Swapping process then continuing until slope b
`no longer exceeds the thresholdb SLOPETH.
`In an embodiment, the process may vary with regard to the
`threshold used for wear leveling. For example, the initiation
`of a wear leveling process may occur when the slope b
`exceeds a first threshold (SLOPETH1), and with the wear
`leveling process continuing until slope b is below a second
`threshold (SLOPETH2), where, for example, SLOPETH2
`may be less than SLOPETH1.
`FIG. 3A is an illustration of a regression line generated for
`a non-volatile memory prior to wear leveling. In this illustra
`tion, each block of a hypothetical non-volatile memory is
`presented in terms of physical block erase count (PBEC 305)
`and logical block erase count (LBEC 310). When a flash
`memory is new, there initially will be very low or zero physi
`cal block erase counts and logical block erase counts. How
`ever, as more write cycles occur, the more active memory
`blocks will develop higher count values for both physical
`block erase counts and logical block erase counts, such as
`shown in FIG. 3A.
`As shown in this illustration, over time it may be expected
`that there will be certain memory blocks having low PBEC
`and LBEC values 315, certain blocks with medium PBEC and
`LBEC values 320, and certain blocks with high PBEC and
`LBEC values 325. In an embodiment of the invention, linear
`regression is utilized to generate a regression line for the
`memory block values 335. For ease of illustration, a symme
`try line 330 is provided. The memory blocks on the right side
`of the symmetry line 330 are becoming worn in comparison to
`the memory blocks on the left side of the symmetry line 330,
`which can result in premature failure of the device if wear
`leveling is not instituted.
`In an embodiment of the invention, a wear leveling evalu
`ation may occur after a certain number of erase events have
`occurred. In the evaluation, a wear leveling process may be
`initiated if the slope of the regression line 335 is above a
`threshold value, resulting in the exchange of worn block
`groups 350. In the exchange, data contained in the blocks of
`the most worn group 325 are exchanged for blocks in the least
`45
`worn group 315. In an embodiment, the Swap is accomplished
`through a series of reclaim operations. After the exchange, a
`regression line is again generated and the slope is again com
`pared to a threshold value. The process continues until the
`slope has been sufficiently modified to fall below the thresh
`old.
`FIG. 3B is an illustration of a regression line generated for
`a non-volatile memory after an embodiment of wear leveling
`is implemented. In this illustration, each block of a hypotheti
`cal non-volatile memory is again presented in terms of physi
`cal block erase count (PBEC 355) and logical block erase
`count (LBEC 360). Subsequent to the worn group exchanges,
`the slope of the resulting regression line has changed 385.
`After the exchanges, there are memory blocks with high
`PBEC and low LBEC 365, memory blocks with medium
`PBEC and LBEC values 370 (which likely have not been
`involved in any exchanges), and memory blocks with low
`PBEC and high LBEC values 375. For ease of illustration, a
`symmetry line 380 is again provided. In essence, the memory
`blocks on the right side of the symmetry line 380 are now
`blocks with relatively low wear but now with active data that
`may result in future wear. The memory blocks on the left side
`
`8
`of the symmetry line 380 are now blocks with relatively high
`wear but now with data that is less active and thus may be
`expected to result in less future wear.
`FIGS. 4 through 7 illustrate an example of memory block
`reclaim operations in an embodiment of a wear leveling pro
`cess. The figures illustrate memory blocks of an exemplary
`non-volatile memory. As illustrated, PBn means then" physi
`cal block and LBn means then" logical block. As is shown in
`the illustration, any memory block has a physical block
`address and either has a logical blockaddress or is designated
`as a spare. In this illustration, the memory device includes
`eight memory blocks (PR0 t