USOO8285940B2
`
`(12) United States Patent
`Reid
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,285,940 B2
`Oct. 9, 2012
`
`(54) METHOD AND APPARATUS FOR HIGH
`SPEED CACHE FLUSHING INA
`NON-VOLATILE MEMORY
`(75) Inventor: Robert Alan Reid, Superior, CO (US)
`
`4/2006 Madter et al. ................. 365,232
`2006/0072369 A1
`1/2007 Ono et al. ..........
`... 711,103
`2007, OO16719 A1
`2007/0168698 A1* 7/2007 Coulson et al. ................... 714/5
`2009,0193193 A1* 7/2009 Kern ............................. T11 128
`* cited by examiner
`
`(*) Notice:
`
`(73) Assignee: Cadence Design Systems, Inc., San
`Jose, CA (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 555 days.
`(21) Appl. No.: 12/040,782
`
`(22) Filed:
`
`Feb. 29, 2008
`
`(65)
`
`Prior Publication Data
`US 2009/0222627 A1
`Sep. 3, 2009
`(51) Int. Cl
`Goof i2/00
`711A135: 711/144
`(52) U.S. Cl
`(58) Field of Classification Search ................... 711/135
`See application file for complete search history.
`
`(2006.01)
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`365,232
`2004/0085849 A1* 5/2004 Myoung et al. ......
`2006/0064556 A1
`3f2006 Aasheim et al. .............. T11 156
`
`Primary Examiner — Tuan Thai
`Assistant Examiner — Ngoc Dinh
`(74) Attorney, Agent, or Firm — Sawyer Law Group, P.C.
`
`ABSTRACT
`(57)
`An invention is provided for performing flush cache in a
`non-volatile memory. The invention includes maintaining a
`plurality of free memory blocks within a non-volatile
`memory. When a flush cache command is issued, a flush
`cache map is examined to obtain a memory address of a
`memory block in the plurality of free memory blocks within
`the non-volatile memory. The flush cache map includes a
`plurality of entries, each entry indicating a memory block of
`the plurality of free memory blocks. Then, a cache block is
`written to a memory block at the obtained memory address
`within the non-volatile memory. In this manner, when a flush
`cache command is received, the flush cache map allows cache
`blocks to be written to free memory blocks in the non-volatile
`memory without requiring a non-volatile memory search for
`free blocks or requiring erasing of memory blocks storing old
`data.
`
`14 Claims, 7 Drawing Sheets
`
`y 300
`
`
`
`3O2
`
`3O8
`
`310
`
`316 N HOST
`PROCESSOR
`
`306
`
`NON-VOLATILE
`MEMORY
`
`Non-volatile
`Memory
`File System
`
`MEMORY
`CONTROLLER
`
`
`
`SYSTEM
`MEMORY
`Block :
`h
`" .
`Cache
`Table
`Map
`
`i
`
`318'
`
`322
`
`
`
`CACHE
`MEMORY
`
`314
`
`BUFFER
`BUFFER
`
`Vervain Ex. 2016, p.1
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Oct. 9, 2012
`
`Sheet 1 of 7
`
`US 8,285,940 B2
`
`100
`
`yr
`
`102
`
`102
`
`a
`
`ofooooo
`
`Pooo-o°
`
`Po-----o
`
`o-
`
`me,~.,.....
`
`Ms,~.......
`
`Ms,~......~......
`
`4°-o---
`
`104
`
`Ss...,
`
`Ss,.,
`
`102
`
`FIG. 1
`(Prior Art)
`
`Vervain Ex. 2016, p.2
`Micron v. Vervain
`IPR2021-01547
`
`Vervain Ex. 2016, p.2
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Oct. 9, 2012
`
`Sheet 2 of 7
`
`US 8,285,940 B2
`
`200
`1.
`
`204 NU
`Search Non-Volatile Memory
`Ho
`for Free Memory Block
`
`
`
`
`
`
`
`208
`
`
`
`Free
`Block Exist
`
`Erase Old
`No-o:
`Memory Block
`
`t
`
`
`
`Write Cache Block to Free
`Memory Block
`
`
`
`
`
`Cache Blocks
`
`
`
`No
`
`214
`
`FIG. 2
`(Prior Art)
`
`Vervain Ex. 2016, p.3
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Oct. 9, 2012
`
`Sheet 3 of 7
`
`US 8,285,940 B2
`
`o0€A
`
`OLE80€
`
`ZOE
`
`PLE
`
`ZLE
`
`AYOWSANJ1ILV1IOA-NON
`
`ReyAiowey
`
`SLEAYOINSAW
`
`YATIONLNOD
`
`YOSssad0udd
`
`LSOH
`
`a|IJE]OA-UON
`
`Mowe
`
`washeld
`
`_---=====
`
`WALSAS
`
`AYOWSIN
`
`90€
`
`€‘Sls
`
`AHOV)D
`
`AYOWSAN
`
`Vervain Ex. 2016, p.4
`Micron v. Vervain
`IPR2021-01547
`
`Vervain Ex. 2016, p.4
`Micron v. Vervain
`IPR2021-01547
`
`
`

`

`U.S. Patent
`
`Oct. 9, 2012
`
`Sheet 4 of 7
`
`US 8,285,940 B2
`
`:
`
`
`
`(~~~~)7607
`
`007
`
`Vervain Ex. 2016, p.5
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Oct. 9, 2012
`
`Sheet 5 Of 7
`
`US 8,285,940 B2
`
`500
`1.
`
`"N-G start
`
`504 NU
`Write Cache Block to Memory
`Block indicated by First
`Pointer in Flush Cache Map
`
`508 P
`
`Write Cache Block to Memory
`Yes—D Block indicated by Next
`Pointer in Flush Cache Map
`
`
`
`
`
`Cache Blocks
`
`"N-O Done
`
`FIG. 5
`
`Vervain Ex. 2016, p.6
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Oct. 9, 2012
`
`Sheet 6 of 7
`
`US 8,285,940 B2
`
`
`
`Vervain Ex. 2016, p.7
`Micron v. Vervain
`IPR2021-01547
`
`

`

`U.S. Patent
`
`Oct. 9, 2012
`
`Sheet 7 Of 7
`
`US 8,285,940 B2
`
`1. 700
`
`"N-O start
`
`704 Nu
`Write Cache Block to Memory
`Block indicated by First
`Pointer in Flush Cache Map
`
`
`
`708 P
`
`Write Cache Block to Memory
`Block indicated by Next
`Pointer in Flush Cache Map
`
`Write Block Table to Memory
`Block indicated by Next
`Pointer in Flush Cache Map
`
`
`
`FIG. 7
`
`Vervain Ex. 2016, p.8
`Micron v. Vervain
`IPR2021-01547
`
`

`

`US 8,285,940 B2
`
`1.
`METHOD AND APPARATUS FOR HIGH
`SPEED CACHE FLUSHING INA
`NON-VOLATILE MEMORY
`
`BACKGROUND OF THE INVENTION
`
`2
`erally comprises a fixed plurality of pages 104, which is the
`smallest size element that can be written or read from the
`non-volatile memory 100.
`Unlike many other storage devices, non-volatile memory
`devices generally cannot be overwritten. Instead, to update
`data in a particular storage location within non-volatile
`memory, the location must first be erased, then the new data
`written in its place. Moreover, when erasing data in a flash
`device, an entire block must be erased instead of just the
`particular page or pages of the block that were updated. To
`facilitate this process, a typical flash controller will find a
`block of memory that has been previously erased and write
`the updated page to this new block at the same page offset.
`Then, the remaining pages of the old block are copied to the
`new block. Later, the old block is erased and made available
`for use by Some other operation. Thus, when performing a
`flush cache command, the system generally is required to find
`free memory for the data stored in cache memory prior to
`flushing the cache memory.
`FIG. 2 is a flowchart showing a prior art method 200 for
`flushing cache when utilizing a non-volatile memory for data
`storage. In an initial operation 202, preprocess operations are
`performed. Preprocess operations can include, for example,
`detecting a pending power loss, receiving a low power mode
`request, and other preprocess operations that will be apparent
`to those skilled in the art.
`In a search operation 204, the non-volatile memory is
`searched for a free memory block. After receiving a flush
`cache command, the non-volatile memory is searched to find
`a free memory block for each cache block in cache memory.
`A free memory block is a memory block that is a good
`memory block (i.e., not damaged or worn out), not currently
`storing data, and has been erased. This search can be per
`formed by searching the actual memory array, or by search
`ing, for example, a table storing data regarding the current
`contents of the non-volatile memory array.
`A decision is then made as to whether a free memory block
`currently exists in the non-volatile memory, in operation 206.
`If a free memory block currently exists in the non-volatile
`memory, the method 200 continues to operation 210. Other
`wise, the method 200 branches to operation 208.
`When the non-volatile memory does not currently include
`a free memory block, an old memory is erased to enable the
`cache data to be written in its place, in operation 208. As
`mentioned above, non-volatile memory generally cannot be
`overwritten. Thus, if a free memory block does not currently
`exist in the non-volatile memory, memory needs to be freed
`up to make room for the cache data. When data is no longer
`being used in non-volatile memory, the memory block storing
`the data is marked as storing old data. Generally, the memory
`block is erased during idle periods. However, it is possible
`that old data will be present in the non-volatile memory at the
`time a flush cache command is issued. When this occurs, the
`memory block storing the old data is erased to enable the
`memory block to be used to store cache data.
`If a free memory block currently exists in the non-volatile
`memory, or after a memory block storing old data has been
`erased in operation 208, the cache block is written to the free
`block in non-volatile memory, in operation 210. Cached data
`for non-volatile memory often is stored as a cache block in
`cache memory. Each cache block corresponds to a memory
`block in non-volatile memory. Thus, during operation 210,
`the current cache block is written to non-volatile memory.
`Another decision is then made as to whether more cache
`blocks need to be written to non-volatile memory, in opera
`tion 212. If more cache blocks need to be written to non
`volatile memory, the method 200 continues with another
`
`10
`
`15
`
`1. Field of the Invention
`This invention relates generally to non-volatile memory,
`and more particularly to providing high speed cache flushing
`in a non-volatile memory.
`2. Description of the Related Art
`Today, data processing systems often reduce memory
`access time through the use of cache memory. Cache memory
`generally is a small high speed memory utilized to tempo
`rarily replicate portions of main memory that are frequently
`accessed. As a result, the average memory access time is
`reduced because most memory access is to the cache memory,
`which generally is faster than main memory. Thus, Software
`executing on the system generally executes faster because
`most software tends to access the same portions of memory
`many times. Hence, the system is able to perform fewer
`memory accesses to slower main memory when the fre
`quently accessed data is stored in cache.
`In general, each memory access request is passed to a cache
`controller, which tracks which portions of main memory are
`currently stored in cache memory. If a memory access request
`(i.e., read request or write request) is made to data currently
`stored in cache memory, a "cache hit’ occurs and the cache
`memory is utilized to complete the memory access request.
`However, if the memory access request is made to data not
`currently stored in cache memory, a "cache miss’ occurs, and
`the data is accessed from main memory. In some systems,
`when a miss occurs, the cache controller can assign the
`requested miss address to the cache memory and fetch the
`data from main memory to store in the cache memory.
`While cache memory is useful during memory access,
`problems can occur during Sudden losses in power. When the
`system detects a pending power problem, the system gener
`ally needs to prepare itself for the power loss by flushing the
`cache memory. This can also occur at other times, such as
`when the system prepares to power down. Cache flushing
`refers to the method by which a system writes the data cur
`rently stored in cache memory back to main memory. That is,
`when the system prepares to shut down or detects a pending
`power problem, the system generates a flush cache command.
`In response, the data stored in the cache memory is written to
`the corresponding addresses in main memory. The flush
`cache process is generally straightforward interms of volatile
`memory; however, the process is more complex when using
`non-volatile memory.
`Non-volatile memory is memory that stores data when
`power is disconnected from the system. Phase-change
`memory (PCM) and flash memory are examples of non
`Volatile computer memory. Flash memory is a non-volatile
`computer memory that can be electrically erased and repro
`grammed. Because flash memory retains stored data even
`when power to the memory is turned off, flash memory is
`widely used in battery-portable devices. For example, flash
`memory often is utilized in digital audio players, digital cam
`60
`eras, mobile phones, and USB flash drives, which are used for
`general storage and transfer of data between computers.
`FIG. 1 is an illustration showing a typical prior art non
`Volatile memory arrangement. As illustrated in FIG. 1, a
`non-volatile memory 100 generally comprises a plurality of
`memory blocks 102, which generally is the smallest portion
`of memory that can be erased. Each memory block 102 gen
`
`45
`
`25
`
`30
`
`35
`
`40
`
`50
`
`55
`
`65
`
`Vervain Ex. 2016, p.9
`Micron v. Vervain
`IPR2021-01547
`
`

`

`3
`search operation 204. Otherwise, the method 200 completes
`in operation 214. Then, in operation 214, post process opera
`tions are performed. Post process operations can include sys
`tem shutdown, and other post process operations that will be
`apparent to those skilled in the art.
`Unfortunately, searching for free memory blocks and eras
`ing old memory blocks can take considerable time, depending
`on the size of the cache memory and the amount of non
`Volatile memory data cached. For example, the worst case
`scenario is represented by equation 1 below:
`
`10
`
`where N is the number of cache blocks, T1 is the erase time
`for a memory block, and T2 is the program/write time for a
`memory block. In typical prior art systems, this can take in the
`range of about N*20 Msecs, which is a relatively long time
`particularly when a power loss is pending.
`In view of the foregoing, there is a need for systems and
`methods for providing high speed cache flushing in a non
`Volatile memory. The systems and methods should decrease
`the amount of time required to complete a flush cache com
`mand. In addition, the systems and methods should not
`unduly burden the system or have prohibitive costs associated
`with them.
`
`15
`
`25
`
`SUMMARY OF THE INVENTION
`
`30
`
`35
`
`Broadly speaking, the present invention addresses these
`needs by providing high speed cache flushing in a non-vola
`tile memory utilizing a flush cache map. For example, in one
`embodiment, a method for performing a cache flush in a
`non-volatile memory is disclosed. The method includes
`maintaining a plurality of free memory blocks within a non
`Volatile memory. When a flush cache command is issued, a
`flush cache map is examined to obtain a memory address of a
`memory block in the plurality of free memory blocks within
`the non-volatile memory. The flush cache map includes a
`plurality of entries, such as pointers, each entry indicating a
`memory block of the plurality of free memory blocks. Then,
`a cache block is written to a memory block at the obtained
`40
`memory address within the non-volatile memory. In this man
`ner, when a flush cache command is received, the flush cache
`map allows cache blocks to be written to free memory blocks
`in the non-volatile memory without requiring a non-volatile
`memory search for free blocks or requiring erasing of
`45
`memory blocks storing old data. In general, each entry of the
`plurality of entries indicates a different free memory block of
`the plurality of free memory blocks in the non-volatile
`memory. In this case, the plurality of free memory blocks
`comprises a predetermined number of free memory blocks
`based on a predetermined number of cache blocks being
`utilized with the system. In this manner, the plurality of
`entries in the flush cache map can be examined sequentially to
`obtain addresses of free memory blocks in which to store
`cache blocks.
`A further method for performing a cache flush in a non
`volatile memory is disclosed in an additional embodiment of
`the present invention. Similar to above, the method includes
`maintaining a plurality of free memory blocks within a non
`Volatile memory. The method also includes examining a flush
`cache map to obtain a memory address of a memory block of
`the plurality of free memory blocks within the non-volatile
`memory and writing a cache block to a free memory block at
`the obtained memory address within the non-volatile
`memory. However, in this embodiment, the flush cache map
`also is examined to obtain an additional memory address of a
`memory block of the plurality of free memory blocks within
`
`50
`
`55
`
`60
`
`65
`
`US 8,285,940 B2
`
`4
`the non-volatile memory. In this manner, a block table can be
`written to a free memory block at the obtained additional
`memory address within the non-volatile memory. The block
`table generally includes data utilized by the non-volatile
`memory file system, such as a plurality of entries mapping a
`physical blockaddress of the non-volatile memory to a logi
`cal blockaddress. In one aspect, the plurality of entries in the
`flush cache map can be examined sequentially to obtain
`addresses of free memory blocks in which to store cache
`blocks and the block table.
`A flush cache map for high speed cache flush in a non
`volatile memory is disclosed in a further embodiment of the
`present invention. The flush cache map includes a predeter
`mined number of entries, where each entry indicates a free
`memory block within a non-volatile memory. As above, each
`of these free memory blocks is maintained free of data during
`operation of the non-volatile memory. An additional entry
`also is included, where a block table is written to the addi
`tional free memory block at the within the non-volatile
`memory. Generally, the predetermined number is based on a
`predetermined number of cache blocks. Hence, to ensure a
`free memory block is available to store the block table during
`a flush cache command, the predetermined number can be
`based on a predetermined number of cache blocks plus one. In
`one aspect, each entry is generated during system power-up.
`In this manner, embodiments of the present invention advan
`tageously allow each cache block and the block table to be
`quickly saved in the non-volatile memory without requiring
`searches for free memory blocks. Moreover, because free
`memory blocks are reserved for cache flushing, embodiments
`of the present invention also do not require erasing of old
`memory blocks, thus saving additional time during a flush
`cache command. Other aspects and advantages of the inven
`tion will become apparent from the following detailed
`description, taken in conjunction with the accompanying
`drawings, illustrating by way of example the principles of the
`invention.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The invention, together with further advantages thereof,
`may best be understood by reference to the following descrip
`tion taken in conjunction with the accompanying drawings in
`which:
`FIG. 1 is an illustration showing a typical prior art non
`Volatile memory arrangement;
`FIG. 2 is a flowchart showing a prior art method for flush
`ing cache when utilizing a non-volatile memory for data
`Storage;
`FIG. 3 is a diagram showing a system, which includes a
`flush cache map stored in memory, in accordance with an
`embodiment of the present invention;
`FIG. 4 is a block diagram showing an exemplary flush
`cache map, in accordance with an embodiment of the present
`invention;
`FIG. 5 is a flowchart showing a method for high speed
`cache flushing in a non-volatile memory, in accordance with
`an embodiment of the present invention;
`FIG. 6 is an illustration showing an exemplary block table,
`in accordance with an embodiment of the present invention;
`and
`FIG. 7 is a flowchart showing a method for high speed
`cache flushing in a non-volatile memory utilizing a block
`table and a flush cache map, in accordance with an embodi
`ment of the present invention.
`
`Vervain Ex. 2016, p.10
`Micron v. Vervain
`IPR2021-01547
`
`

`

`5
`DETAILED DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`US 8,285,940 B2
`
`6
`a free memory block is a memory block that is a good memory
`block (i.e., not damaged or worn out), not currently storing
`data, and that has been erased. In general, the number of
`pointers 400 included in the flush cache map 322 can be
`dependent on the amount of cache being utilized in the system
`3OO.
`In one embodiment, the flush cache map 322 is generated
`during power up and updated during system operation. More
`specifically, a predetermined number of free memory blocks
`within the non-volatile memory 310 are reserved for use with
`the flush cache map 322. That is, each of the reserved free
`memory blocks is maintained for use during a flush cache
`command. In one embodiment, the addresses of reserved
`memory locations can change during operation, as long as the
`number of reserved free memory blocks remains adequate to
`store all the cache blocks being utilized. Particular reserved
`memory blocks may change, for example, to maintain wear
`leveling. However, embodiments of the present invention
`reserved enough free memory blocks to store all the cache
`blocks being utilized by the system.
`The flush cache map 322 is utilized to store the cache
`blocks during a flush cache command. That is, when a flush
`cache command is generated, each cache block is written to a
`memory block pointed to by a pointer 400 in the flush cache
`map 322. For example, when a flush cache command is gen
`erated, the flush cache map 322 in the example of FIG. 4
`indicates that the first cache block will be written to the
`memory block at address 2 in the non-volatile memory array
`312. The second cache block is written to the memory block
`at address 2023, and so on, until the last cache block is written
`to the memory block at address 4094. Although particular
`addresses are shown in FIG. 4 for illustration purposes, it
`should be noted that the pointers 400 of the flush cache map
`322 can store any value as is appropriate for the particular
`non-volatile memory being utilized.
`FIG. 5 is a flowchart showing a method 500 for high speed
`cache flushing in a non-volatile memory, in accordance with
`an embodiment of the present invention. In an initial opera
`tion 502, preprocess operations are performed. Preprocess
`operations can include, for example, generating a flush cache
`map having pointers to reserved free memory blocks in non
`Volatile memory, detecting a pending power loss, receiving a
`low power mode request, and other preprocess operations that
`will be apparent to those skilled in the art after a careful
`reading of the present disclosure.
`In operation 504, the first cache block in cache memory
`replicating a memory block in non-volatile memory is written
`to the memory block in non-volatile memory indicated by the
`first pointer in the flush cache map. As mentioned above, a
`particular number of free memory blocks within the non
`volatile memory are reserved for use with the flush cache
`map. In one embodiment, the addresses of reserved memory
`locations can change during operation, as long as the number
`of reserved memory blocks remains adequate to store all the
`cache blocks being utilized. The flush cache map includes a
`plurality of pointers, each pointing to a reserved free memory
`block in the memory array of the non-volatile memory. In
`general, the number of pointers included in the flush cache
`map can be dependent on the amount of cache being utilized
`in the system.
`A decision is then made as to whether more cache blocks
`need to be flushed from cache memory, in operation 506. The
`cache memory may include a plurality of cache blocks repli
`cating memory blocks in the non-volatile memory. Each of
`these cache blocks are written to non-volatile memory when
`a flush cache command is generated. Hence, if more cache
`
`15
`
`25
`
`30
`
`35
`
`40
`
`An invention is disclosed for providing high speed cache
`flushing in a non-volatile memory utilizing a flush cache map.
`Broadly speaking, embodiments of the present invention uti
`lize a map that comprises a plurality of entries, such as point
`ers, indicating free memory blocks in non-volatile memory.
`The entries can be updated as the non-volatile memory is
`utilized during normal operation. When a flush cache com
`10
`mand is received, the flush cache map is utilized to write
`cache blocks to free memory blocks in non-volatile memory
`without requiring a non-volatile memory search for free
`blocks or requiring erasing of memory blocks storing old
`data.
`In the following description, numerous specific details are
`set forth in order to provide a thorough understanding of the
`present invention. It will be apparent, however, to one skilled
`in the art that the present invention may be practiced without
`some or all of these specific details. In other instances, well
`known process steps have not been described in detail in order
`not to unnecessarily obscure the present invention.
`FIGS. 1 and 2 were described in terms of the prior art. FIG.
`3 is a diagram showing a system 300, which includes a flush
`cache map 322 stored in memory, in accordance with an
`embodiment of the present invention. The system 300
`includes a host processor 302 coupled to system memory 306,
`cache memory 320, and a memory controller 308. The
`memory controller 308 is in communication with a non
`volatile memory 310, which includes a memory array 312
`coupled to a buffer 314. It should be noted that the non
`volatile memory 310 can be any type of non-volatile memory,
`such as PCM, flash memory, or any other type of non-volatile
`memory as will be apparent to those skilled in the art after a
`careful reading of the present disclosure.
`Executing on the host processor 302 is a non-volatile
`memory file system 316, which is utilized by the system 300
`to access data stored in the non-volatile memory 310.
`Although the non-volatile memory file system 316 is shown
`executing on the host processor 302 in the example of FIG.3,
`it should be noted that the non-volatile memory file system
`316 can run on other processors as needed by the system 300.
`A flush cache map 322 is stored in system memory 306. As
`will be described in greater detail subsequently, the flush
`cache map 322 includes a plurality of entries, such as point
`ers, indicating free memory blocks in the non-volatile
`memory 310, which can be updated as the non-volatile
`memory 310 is utilized during normal operation. In addition,
`in one embodiment of the present invention a block table 318
`is stored in a memory block of the memory array 312 of the
`non-volatile memory 310. As will be described in greater
`detail subsequently, the block table 318 stores much of the
`data needed by the non-volatile memory file system 316 for
`accessing data stored in the non-volatile memory 310. For
`example, the block table 318 includes address mapping,
`block status, and wear leveling data for the non-volatile
`memory 310.
`During power up, and during idle times, the flush cache
`map 322 can be constructed. FIG. 4 is a block diagram show
`ing an exemplary flush cache map 322, in accordance with an
`embodiment of the present invention. The flush cache map
`322 includes a plurality of entries, such as pointers, indicating
`free memory blocks. For example, in FIG. 4, the flush cache
`map 322 includes a plurality of pointers 400, each pointing to
`a free memory block in the memory array 312. Each pointer
`400 can be, for example, an address of a memory block within
`the non-volatile memory array 312. As mentioned previously,
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Vervain Ex. 2016, p.11
`Micron v. Vervain
`IPR2021-01547
`
`

`

`7
`blocks need to be flushed from cache memory, the method
`500 continues with operation 508. Otherwise, the method
`completes in operation 510.
`In operation 508, the next cache block in cache memory
`replicating a memory block in non-volatile memory is written
`to the memory block in non-volatile memory indicated by the
`next pointer in the flush cache map. For example, during
`operation 504, using the flush cache map 322 in the example
`of FIG. 4, the first cache block is written to the memory block
`at address 2 in the non-volatile memory 310. Then, in opera
`tion 508, the next cache block in cache memory is written to
`the memory block indicated by the next pointer in the flush
`cache map 322, in this case address 2023, and so on, until the
`last cache block is written to the memory block at address
`4094.
`When no more cache blocks need to be flushed from cache
`memory, the method 500 completes in operation 510. Post
`process operations are performed in operation 510. Post pro
`cess operations can include, for example, performing cache
`flush for other system memory, power down operations, and
`other post process operations that will be apparent to those
`skilled in the art after a careful reading of the present disclo
`Sure. In addition to pointers for cache blocks, in one embodi
`ment an additional pointer is maintained in the flush cache
`map 322 to a memory block for storing the block table 318.
`FIG. 6 is an illustration showing an exemplary block table
`318, in accordance with an embodiment of the present inven
`tion. The block table 318 includes logical block addresses
`600, memory block status flags 602, physical blockaddresses
`604, wear level indicators 606, and read count data 608. It
`should be noted, however, that a block table 318 of the
`embodiments of the present invention can include any data
`useful to the non-volatile file system in the operation of the
`non-volatile memory, as will be apparent to those skilled in
`the art after a careful reading of the present disclosure.
`Each row of the bock table 318 corresponds to a particular
`logical blockaddress 600, which is the memory blockaddress
`used by the system when requesting access to data from the
`non-volatile memory. Thus, the data in each row of the block
`table 318 corresponds to the particular logical address 600
`listed in the logical block address column of the block table
`318. For example, the memory block status flags 602, physi
`cal address data 604, wear level indicators 606, and read
`count data 608 on row 1 of the block table 318 correspond to
`the logical address 1.
`As mentioned above, each row of the block table 318
`includes memory block status flags 602, a physical block
`address 604, a wear level indicator 606, and read count data
`608. The memory block status flags 602 indicate the avail
`ability of a particular block. For example, the memory block
`status flags 602 can be utilized to indicate whetheraparticular
`block is bad (i.e., worn out), currently in use, free, or old data
`but not yet erased. The physical blockaddress 604 stores the
`actual physical address in the non-volatile memory of the data
`associated with the corresponding logical address 600. The
`wear level indicator 606 stores the wear level for the associ
`ated physical block address 604. Generally, the wear level
`indicator 606 provides an indication of the wear level of the
`particular physical blockaddress relative to the other physical
`block addresses in the non-volatile memory. The wear level
`data is utilized by the non-volatile memory file system to
`provide more even wear or use of the different memory block
`locations in the non-volatile memory. The read count data 608
`provides an indication of the number of reads occurring
`within the associated memory block. In operation, the read
`count data 608 associated with a particular memory block is
`increment each time a page from the associated memory
`
`5
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 8,285,940 B2
`
`8
`block is read from the non-volatile memory. When the read
`count 508 reaches a predetermined threshold value, the data
`stored in the associated memory block is moved to another
`memory block in physical memory.
`In one embodiment, the block table 318 is loaded from the
`non-volatile memory 310 into system memory 306. The
`block table 318' loaded in system memory 306 then is utilized
`by the non-volatile memory file system 316 to access data in
`the non-volatile memory 310. For example, to access data in
`the non-volatile memory 310, the non-volatile memory file
`system 316 examines the block table 318' stored in system
`memory 306 to determine the physical address of a particular
`logical address that the system 300 wants to access. The
`non-volatile memory file system 316 then instructs the
`memory controller 308 to access the data in the memory array
`312 at the particular physical address. As data is being
`accessed and moved in the non-volatile memory 310, the
`block table 318' in system memory 306 is updated to reflect
`the changes in the data stored in the non-volatile memory 310.
`Periodically, and at system shutdown, the block table 318'
`stored in system memory 306 is written to the non-volatile
`memory 310. The block table 318 can be written to a different
`location within the memory array 312 of the non-volatile
`memory 310 each time the block table 318 is written to the
`non-volatile memory 310.
`As with cache blocks in the cache memory, when the
`system detects a pending loss of power and generates a flush
`cache command, the block table 318' stored is system
`memory 306 is written to a free memory block in non-volatile
`memory 310 based on the flush cache map