`
`WO 03/027828 Al
`
`1111111111111111 IIIIII 111111111111111111111111111111 lllll lllll 11111111111111111111111
`
`European patent (AT, BE, BG, CH, CY, CZ, DE, DK, EE,
`ES, FI, FR, GB, GR, IE, IT, LU, MC, NL, PT, SE, SK,
`TR), OAPI patent (BF, BJ, CF, CG, CI, CM, GA, GN, GQ,
`GW, ML, MR, NE, SN, TD, TG).
`
`before the expiration of the time limit for amending the
`claims and to be republished in the event of receipt of
`amendments
`
`Published:
`with international search report
`
`For two-letter codes and other abbreviations, refer to the "Guid(cid:173)
`ance Notes on Codes and Abbreviations" appearing at the begin(cid:173)
`ning of each regular issue of the PCT Gazette.
`
`Micron Ex. 1050, p. 2
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`1
`
`METHOD OF WRITING DATA TO NON-VOLATILE MEMORY
`
`The present invention relates to a method of writing
`
`data to non volatile memory and in particular to a method
`
`of writing data to flash memory in order to ensure the
`
`uniform distribution of use over a prolonged period of
`
`operation.
`
`In
`
`known memory
`
`systems
`
`it is
`
`common
`
`for non
`
`volatile memory such as
`
`the flash memory of the memory
`
`systems ta-bave wear out mechanisms within their physical
`
`structures which mean
`
`that
`
`a block within
`
`the
`
`flash
`
`memory may experience failure after a cumulative number
`
`of operations. However,
`
`known data management methods
`
`typically do not perform block erasure in Flash memory in
`
`real time leading to the accumulation of blocks in Flash
`
`memory which contain obsolete versions of sectors. It is
`
`also the case that in known systems the physical address
`
`for writing a sector is dependant on the logical address
`
`of the sector thus logically non-contiguous sectors are
`
`written in non-contiguous physical address and logical to
`
`physical.
`
`In particular . an object of the present invention is
`
`to reduce the number of read and write accesses
`
`to the
`
`Micron Ex. 1050, p. 3
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`2
`
`PCT/GB02/04381
`
`non-volatile memory for control data structures, thereby
`
`increasing the write speed of the memory system for host
`
`data.
`
`A second object of the invention is t.o obtain even
`
`use of blocks in the non-volatile memory for storage of
`
`data over a
`
`long period of operation, and to avoid "hot(cid:173)
`
`spots" in non-volatile memory usage,
`
`thereby increasing
`
`the reliability of the memory system.
`
`According to a first aspect of the invention, there
`
`is provided a controller connected
`
`to a non-volatile
`
`memory and including a volatile memory, wherein
`
`the controller maintains lists in volatile memory of
`
`blocks in the non-volatile memory allovated for storage
`
`of logical sector data and of block:s recently erased in
`
`the non-volatile memory
`
`the controller transfers information from the lists
`
`in volatile memory to control data structures in the non(cid:173)
`
`volatile memory less frequently than the contents ·of the
`
`lists in volatile memory ?re changed
`
`such
`
`that
`
`the
`
`lists
`
`in volatile memory can be
`
`reconstructed at any time from existing informaion in the
`
`non-volatile memory.
`
`Preferably,
`
`information from
`
`the lists in volatile
`
`memory is transferred to control data struci:ures in the
`
`non-volatile memory concurrently with logical to physical
`
`Micron Ex. 1050, p. 4
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`3
`
`mapping
`
`information
`
`for sectors
`
`from other
`
`lists
`
`in
`
`volatile memory.
`
`According to a second aspect of the invention, there
`
`is provided a controller connected
`
`to a non-volatile
`
`memory and including a volatile memory, wherein
`
`the controller maintains a first list of all blocks
`
`in the non-volatile memory which are in the erased state
`
`and which are not included in other lists
`
`the controller maintains a second list of,blo~ks in
`
`the non-volatile memory which have beery recently erased.
`
`These and other aspects of the invention will become
`
`apparent
`
`from
`
`the
`
`following
`
`description
`
`taken
`
`in
`
`combination with
`
`the
`
`following drawings
`
`in which
`
`is
`
`shown:
`
`Figure 1
`
`-
`
`a host system and flash memory system
`
`arrangement which the present invention is implemented;
`
`Figure
`
`2
`
`the
`
`hardware
`
`architecture of
`
`the
`
`controller of the system of Figure 1 in which the .present
`
`invention is implemented;
`
`Figure 3
`
`the
`
`layered
`
`firmware structure which
`
`performs the media management operations according to the
`
`present invention;
`
`Figure 4a
`
`-
`
`schematic representation of
`
`the write
`
`operation according to the present invention;
`
`Micron Ex. 1050, p. 5
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`4
`
`PCT/GB02/04381
`
`Figure 4b
`
`-
`
`.schematic representation of the write
`
`and relocate operations of the present invention;
`
`Figure 5
`
`-
`
`a schematic representation of the three
`
`level hierarchy of mapping structures of
`
`the address
`
`translation process according to the present invention;
`
`Figure 6
`
`-
`
`a schematic representation of the data
`
`structures in the memory system of the present invention;
`
`Figure 7 -
`
`a schematic representation of the control
`
`..
`operations of the memory system according to the present
`
`invention;
`
`Figure 8 -
`
`a schematic representation of the flow of
`
`operations of the address translation operation of the
`
`present invention;
`
`Figure 9 - A schematic representation of the control
`
`write operation of
`
`the memory system according
`
`to the
`
`present invention;
`
`Figure 10
`
`-
`
`a schematic representation of the EBM
`
`sector write function operation of the memory system of
`
`the present invention;
`
`Figure 11 -
`
`a schematic representation of the state
`
`of
`
`the data structures at
`
`the sta~t of a map write
`
`operation;
`
`Figure 12 -
`
`a schematic representation of the state
`
`of the data structures following the CSL map operation;
`
`Micron Ex. 1050, p. 6
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`5
`
`Figure 13 -
`
`a schematic representation of the state
`
`of
`
`the data
`
`structures
`
`following
`
`·the ABL
`
`and CBL
`
`compaction operation;
`
`Figure 14
`
`-
`
`a schematic representation of the state
`
`of
`
`the data
`
`structure
`
`following
`
`the map
`
`to CBL
`
`operation;
`
`Figure 15 -
`
`a schematic representation of the state
`
`of
`
`the data
`
`structures
`
`following
`
`the CBL
`
`to
`
`EBL
`
`operation;
`
`Figure 16 -
`
`a schematic representation of the state
`
`of
`
`the data
`
`structures
`
`following
`
`· the EBL
`
`to ABL
`
`operation;
`
`Figure
`
`17
`
`a
`
`schematic
`
`representation of
`
`an
`
`al terna ti ve host system and flash system in which
`
`the
`
`present invention may be implemented.
`
`A Flash disk device, such as that shown in Figure 1,
`
`is
`
`a
`
`memory
`
`system which
`
`presents
`
`the
`
`logical
`
`characteristics of a disk storage device to a h6st· system
`
`1 2 , and which uses Flash semiconductor memory 20 as its
`
`physical data storage medium. A Flash disk memory system
`
`10
`
`requires
`
`a controller 12
`
`to manage
`
`the physical
`
`storage medium of the system 10 according to algorithms
`
`which create the logical characteristics of a disk and,
`
`in this case, it is the flash memory 20 and controller 16
`
`which are connected by physical interface 16 which form
`
`Micron Ex. 1050, p. 7
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`6
`
`the memory system 10. The controller 16 of
`
`the memory
`
`system 10 connects
`
`the system 10
`
`to
`
`the host 12 via
`
`logical interface 14.
`
`In
`
`this case
`
`the
`
`flash memory
`
`20
`
`comprises
`
`a
`
`plurality of flash chips which are formed of a plurality
`
`of flash blocks. The logical interface 14
`
`to the memory
`
`system 10 allows data to be written to and read from the
`
`system 10
`
`in
`
`fixed-size units called sectors,
`
`each
`
`containing 512 bytes of data, ~hich can b~
`
`ri~domly
`
`accessed. Each sector is identified by a logical address
`
`which in this case is a sequential Logical Block Address
`
`( LBA) .
`
`In the present arrangement data may be written to a
`
`sector even if the sector already contains data.
`
`The
`
`protocols at the logical interface 14 can, in this case,
`
`support, read or write access to the system 10 in multi(cid:173)
`
`sector blocks of logically contiguous sector addresses,
`
`these protocols conform
`
`to
`
`industry standards such as
`
`ATA, CompactFlash, or ~ultiMediaCard
`
`thus allowing
`
`the
`
`memory system 10 to be interchangeable between different
`
`host systems and not limited to use with host 12.
`
`The physical
`
`interface 18
`
`from controller 16
`
`to
`
`Flash Memory 20 allows data to be written
`
`to and read
`
`from Flash memory 20
`
`in fixed-size units which in this
`
`Micron Ex. 1050, p. 8
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`7
`
`case are called physical sectors and each of which can be
`
`a·cces sed randomly with each typically having sufficient
`
`capacity for 512 bytes of data from the host system plus
`
`16 bytes of overhead data appended by the controller 16.
`
`Each physical sector is identified by a physical sector
`
`address, which normally has separate components which
`
`respectively identify the Flash chip within
`
`the memory
`
`subsystem, the Flash block within the Flash chip, and the
`
`physical sector within the Flash block of the' mem·ory 20
`
`to which the physical sector is written.
`
`Within the system 10 shown, data may only be written
`
`to a physical sector if the sector has previously been
`
`eras .ed. The Flash memory 20 is erased in response to a
`
`command at the physical interface in uni ts of a Flash
`
`block, which typically contains 32 physical sectors. The
`
`relative times for performing operations within the Flash
`
`system 10 to read a physical sector, program a physical
`..
`typically . in
`
`sector, and erase a Flash block are
`
`the
`
`ratio 1
`
`: 20
`
`: 200.
`
`In the arrangement of Figure 1 the controller 16 is
`
`a Cyclic Storage controller which
`
`is
`
`a Flash media
`
`management controller
`
`in which
`
`a method of ensuring
`
`uniformity of distribution of use is implemented wherein
`
`the media management algorithms which
`
`implement
`
`this
`
`Micron Ex. 1050, p. 9
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`8
`
`method are implemented as firmware by a processor within
`
`the controller.
`
`With reference to Figure 2 there.is shown optimized
`
`hardware architecture which
`
`is defined for
`
`the Cyclic
`
`Storage controller 16.
`
`In
`
`this case
`
`the controller
`
`hardware
`
`is
`
`a dedicated architecture
`
`in
`
`a
`
`separate
`
`integrated circuit.
`
`The controller 16 comprises host interface control
`
`block-
`
`22, microprocessor 24,
`
`flash
`
`interface control
`
`block 26, ROM 28, SRAM 30 and expansion port 32, each of
`
`these being inter-connected by memory access control bus
`
`34.
`
`Cyclic Storage Flash media management plgorithms are
`
`implemented by firmware running on microprocessor 24 and
`
`the controller 16 is responsible for all Flash media
`
`management functions and for the characteristics of the
`
`logical interface 14 presented to host 12.
`
`The host
`
`interface control block 22 provides
`
`the
`
`path for data flow to and from host system 12 via logical
`
`interface 14.
`
`As,
`
`in this case,
`
`the controller 16 is in the form
`
`of a dedicated
`
`integrated circuit
`
`the host
`
`interface
`
`control block 2 2 provides
`
`logical
`
`interface 14 which
`
`conforms to an industry standard protocol as well as a
`
`Micron Ex. 1050, p. 10
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`9
`
`command
`
`register and set of
`
`taskfile registers which
`
`provide the route for
`
`the microprocessor 24
`
`to control
`
`the logical characteristics of the interface 14.
`
`The host interface control block 22 also allows for
`
`a sector of data to be transferred in either direction
`
`across
`
`the
`
`logical
`
`interface 14 between
`
`to
`
`the host
`
`system 12 and the controller's SRAM 30 by a direct memory
`
`access
`
`(DMA)
`
`operation without
`
`intervention
`
`from
`
`the
`
`microprocessor 24.
`
`The Flash interface control block 26 provides
`
`the
`
`path for data
`
`flow
`
`to and
`
`from Flash memory 20,
`
`and
`
`controls all operations which
`
`take place
`
`in
`
`the Flash
`
`memory 20.
`
`The operations taking pL~ce in Flash memory
`
`20 are defined and initiated by the microprocessor 24,
`
`which
`
`loads parameter and address
`
`information
`
`to
`
`the
`
`flash interface control block 26.
`
`The set of operations which typically take place are
`
`the transfer of a physical sector to Flash memory 20, the
`
`transfer of a physical sector from Flash memory 2 0,
`
`the
`
`programming of a physical sector into flash memory 20,
`
`the erasing of a Flash block, and
`
`the reading of
`
`the
`
`status of flash memory 20.
`
`Similarly
`
`a
`
`physical
`
`sector of data may
`
`be
`
`transferred
`
`in either direction across
`
`the physical
`
`Micron Ex. 1050, p. 11
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`10
`
`interface
`
`16
`
`between
`
`the Flash memory
`
`20
`
`and
`
`the
`
`controller's
`
`SRAM
`
`30
`
`by
`
`OMA
`
`operations without
`
`intervention
`
`from
`
`the microprocessor
`
`24.
`
`The
`
`organization of the 512 bytes of host data and 16 bytes
`
`of overhead data within
`
`a physical sector which
`
`is
`
`transferred to Flash memory 20 is determined within the
`
`Flash interface control block 26, under the control of
`
`parameters loaded by the microprocessor 24.
`
`The Flash interface control block 26 also generates
`
`a
`
`12-byte
`
`error
`
`correcting
`
`code
`
`(ECC)
`
`which
`
`is
`
`transferred to Flash memory 20 and programmed as overhead
`
`data within each physical sector,
`
`and which
`
`is also
`
`verified when a physical sector is transferred from Flash
`
`memory 20.
`
`The microprocessor 24 controls
`
`the
`
`flow of data
`
`sectors
`
`through
`
`the memory
`
`access control bus,
`
`or
`
`datapath,
`
`34 or of
`
`the controller 16,
`
`implements
`
`the
`
`Flash media management algorithms which define the sector
`
`and control data storag~ organisation in the Flash memory
`
`20,
`
`and defines
`
`the a characteristics of
`
`the
`
`logical
`
`interface
`
`14
`
`to host
`
`system 12.
`
`In
`
`this case
`
`che
`
`microprocessor 24 is a 32-bit RISC processor.
`
`The memory access control bus 34 allows transfe_r of
`
`information between the microprocessor 24, host interface
`
`Micron Ex. 1050, p. 12
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`11
`
`PCT/GB02/04381
`
`control block 22, and the Flash interface control blocks
`
`16, as well as between the host interface control block
`
`22,
`
`the flash interface control block 26 and a memory
`
`block 30 . .
`
`The microprocessor 24, host interface control block
`
`22, and Flash interface control block 26 may each be the
`
`master for a transaction on the memory access control bus
`
`34.
`
`Bus access is granted to requesting masters on a
`
`cycle-by-cycle basis.
`
`The SRAM block 30 stores all temporary information
`
`within the controller 16, this storing function includes
`
`the buffering of sector data and storage of control data
`
`structures and variables, as well as firmware code.
`
`The ROM
`
`28
`
`is. included
`
`in
`
`the controller 16
`
`for
`
`storage of code for execution by the microprocessor 2 4,
`
`or of
`
`information
`
`required by other hardware blocks
`
`within the controller.
`
`The inclusion in the controller architecture of an
`
`expansion port
`
`32 gives access
`
`to external hardware
`
`functions, RAM or ROM
`
`from the memory system 10.
`
`During
`
`the operation of
`
`the controller all sector
`
`data being transferred between the logical interface 14
`
`to host system 12, and the physical interface 18 to Flash
`
`memory
`
`20
`
`is buffered
`
`in
`
`the
`
`SRAM
`
`30.
`
`.Sufficient
`
`Micron Ex. 1050, p. 13
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`12
`
`capacit y in the SRAM 30 is allocated for buffering of two
`
`sectors
`
`of data
`
`to
`
`allow
`
`concurrent
`
`transfers
`
`of
`
`successive sectors at the host and Flash interfaces. Data
`
`transfer between
`
`the logical host interface 14 and SRAM
`
`30 is performed by OMA with
`
`the host interface control
`
`block 22 acting as bus master. Data transfer between the
`
`physical Flash interface 18 and SRAM 30 is performed by
`
`DMA with the Flash interface control block 2 6 acting as
`
`bus master.
`
`As the controller 16 is in the form of a dedicated
`
`integrated circuit, the host interface control block 22
`
`provides
`
`a
`
`logical
`
`interface which
`
`conforms
`
`to
`
`an
`
`industry standard protocol, and a command register and
`
`set of
`
`taskfile registers provide
`
`the
`
`route
`
`for
`
`the
`
`microprocessor 24
`
`to control the logical characteristics
`
`of
`
`the
`
`interface 14.
`
`Command, address and parameter
`
`information is written to these task file registers by
`
`the host 12,
`
`and
`
`read by
`
`the microprocessor · 24
`
`for
`
`execution of the command.
`'
`
`Information is also be written
`
`to the registers by the microprocessor 24 for return to
`
`the host 12.
`
`In Figure
`
`3
`
`there
`
`is
`
`illustrated
`
`the
`
`layered
`
`structure of
`
`the
`
`firmware which performs
`
`th~ Cyclic
`
`Storage flash media management operations. The firmware
`
`Micron Ex. 1050, p. 14
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`13
`
`PCT/GB02/04381
`
`has
`
`three
`
`layers,
`
`the first being
`
`the host
`
`in te rf ace
`
`layer 40,
`
`the
`
`second
`
`layer 42 comprising
`
`the sector
`
`transfer sequencer 42a and the media management layer 42b
`
`and the third being the flash control layer 44.
`
`These three firmware layers 40,42 and 44 control the
`
`transfer of data sectors between the l~gical interface 14
`
`to host 12 and the physical interface 18 to Flash memory
`
`20. However,
`
`the firmware
`
`layers do not directly pass
`
`data,
`
`instead data
`
`sectors
`
`are
`
`transferred by
`
`the
`
`hardware blocks of the controller 16 and therefore do not
`
`pass through the microprocessor 24.
`
`The host
`
`interface
`
`layer
`
`40
`
`supports
`
`the
`
`full
`
`command set
`
`for
`
`the host protocol.
`
`It
`
`interprets
`
`commands at the host interface 14, controls the logical
`
`behaviour
`
`of
`
`the
`
`interface
`
`14
`
`according
`
`to host
`
`protocols, executes host commands not associated with the
`
`transfer of data, and passes host commands which relate
`
`to data
`
`in Flash memory
`
`to be
`
`invoked
`
`in
`
`the layers
`
`below. Example of such commands are.
`
`I
`
`Read logical sector (single or multiple),
`
`Write logical sector (single or multiple),
`
`Erase iogical sector
`
`( single or multiple) , as well
`
`as other disk formatting and identification commands.
`
`Micron Ex. 1050, p. 15
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`14
`
`The
`
`sector
`
`transfer
`
`sequencer
`
`42a
`
`receives
`
`interpreted commands
`
`relating
`
`to
`
`logical data sectors
`
`from
`
`the host interface layer 40 and
`
`thus
`
`invokes
`
`the
`
`Flash media management layer 42b for logical to physical
`
`transformation operations, and invokes the Flash control
`
`layer for physical sector transfers· to or
`
`from Flash
`
`memory. The sector transfer sequencer 42a also perform
`
`sector buffer memory management. Another function of the
`
`sequencer
`
`42a
`
`is
`
`to create
`
`a
`
`sequence of
`
`sector
`
`transfers, at
`
`the host
`
`interface 14 and Flash memory
`
`interface 18, and a sequence of operations in the media
`
`management
`
`layer 42b,
`
`in accordance with
`
`the command
`
`received from the host 12 and the level of concurrent
`
`operations which is configured for the Flash memory 20.
`
`The media management layer 42b performs the logical
`
`to physical transformation operations which are required
`
`to support the write, read or erasure of a single logical
`
`sector. This layer is responsible for the implementation
`
`of Cyclic Storage media management algorithms.
`
`The Flash control
`
`layer 44 configures
`
`the Flash
`
`interface control block 26 hardware to execute operations
`
`according to calls from the sector transfer sequencer 42a
`
`or media management layer 42b.
`
`Micron Ex. 1050, p. 16
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`PCT/GB02/04381
`
`15
`
`The media management functions which are implemented
`
`within
`
`the media management layer 4 2b of the controller
`
`firmware create
`
`the
`
`logical characteristics of a disk
`
`storage device in the memory system 10 which uses Flash
`
`semiconductor memory 20 as
`
`the physical data storage
`
`medium.
`
`The effectiveness of the media management performed
`
`by the media management functions of the media management
`
`layer
`
`42b
`
`is measured by
`
`its speed
`
`for performing
`
`sustained writing of data to the memory system 10, its
`
`efficiency in maintaining its level of performance when
`
`operating with different file systems, and in this case,
`
`in host 12, and the long-term reliability of the Flash
`
`memory 20.
`
`Data write speed is defined as the speed which can
`
`be sustained when writing a
`
`large volume of contiguous
`
`data to the memory system 10.
`
`In some cases, when
`
`the
`
`sustained data write rate of a memory system is being
`
`tested,
`
`the volume of data to be written may exceed the
`
`capacity of the memory system 10 and therefore logical
`
`addresses may be repeated.
`
`Sustained write speed is determined by
`
`the sector
`
`data transfer speed at the logical interface U
`
`to the
`
`host 1 2 , and the physical interface 18
`
`to Flash memory
`
`Micron Ex. 1050, p. 17
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`16
`
`PCT/GB02/04381
`
`20, as well as
`
`the overhead percentage of accesses
`
`to
`
`Flash memory 20 at the physical interface 18 for Flash
`
`page
`
`read and write operations . and Flash block erase
`
`operations which are not directly associated with storage
`
`of data sectors written by
`
`the host 12 at the logical
`
`interface 14.
`
`In this case the control data structures
`
`and algorithms which are employed should ensure
`
`that
`
`access
`
`to Flash memory 20
`
`for control
`
`functions
`
`is
`
`required at a much
`
`lower frequency than for host sector
`
`write. The sustained write speed is also determined by
`
`the processing time within .the controller 16 for media
`
`management operations,
`
`and
`
`the page
`
`read and program
`
`times, and block erase times within the Flash memory 20.
`
`In
`
`order
`
`for
`
`the memory
`
`system
`
`to
`
`operate
`
`efficiently when having
`
`file
`
`systems with different
`
`characteristics, the Media management algorithms for the
`
`organization of host data and control-data structures on
`
`Flash · memory 20 are appropriately defined and data write
`
`performance is maintained in each environment.
`
`In a first embodiment, the file systems implementing
`
`the MS-DOS standard are provided with at least one of the
`
`following characteristics:
`
`the host
`
`12 writing data
`
`sectors in clusters using multiple sector write commands;
`
`the host 12 writing data sectors using single sector
`
`write commands;
`
`the host 12 writing some sectors with
`
`Micron Ex. 1050, p. 18
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`17
`
`PCT/GB02/04381
`
`single sector write commands in an address space which is
`
`shared with clustered file data; the host 12 writing non(cid:173)
`
`contiguous sectors for MS-DOS directory and FAT entries
`
`with single sector write commands;
`
`the host 12 writing
`
`non-contiguous
`
`sectors
`
`for MS-DOS directory and
`
`FAT
`
`entries
`
`interspersed with contiguous sectors for file
`
`data; and/or
`
`the host may rewrite sectors for MS-DOS directory
`
`and FAT entries on a frequent basis.
`
`It is a feature of flash memory, and in this case
`
`the Flash memory 20 of the memory system 10, that it has
`
`a wear-out mechanism within the physical structure of its
`
`cells whereby a block of flash memory may experience
`
`failure
`
`after
`
`a
`
`cumulative
`
`number
`
`of
`
`operations.
`
`Typically, this is in the range of 100,000 to 1,000,000
`
`program/erase cycles.
`
`In
`
`light of
`
`this
`
`the cyclic
`
`storage
`
`controller
`
`16
`
`of
`
`the
`
`p~esent
`
`arrangement
`
`implements
`
`a process of wear-leveling
`
`to ensure
`
`that
`
`"hot-spots" do not occur in the physical address space of
`
`the Flash memory 20 and that utilization of Flash blocks
`
`is uniformly distributed over a prolonged period of
`
`operation.
`
`The Cyclic Storage media management algorithms 2.re
`
`implemented within memory system 10 and perform the Media
`
`management operation of
`
`the physical Flash memory 2 0
`
`Micron Ex. 1050, p. 19
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`18
`
`PCT/GB02/04381
`
`within the system 10. The cyclic storage media management
`
`algorithms comprise four separate algorithms, namely the
`
`Data Write algorithm which controls
`
`the
`
`location
`
`for
`
`writing host
`
`information to,
`
`the Block Erase algorithm
`
`which controls erasure of areas of Flash memory 20
`
`containing obsolete
`
`information,
`
`the Block Sequencing
`
`algorithm which controls
`
`the sequence of use of Flash
`
`blocks
`
`for
`
`storing
`
`information,
`
`and
`
`the Address
`
`Translation algorithm which controls the mappiflg of host
`
`logical addresses to physical memory addresses.
`
`The method of Cyclic Storage media management
`
`implemented by
`
`these algorithms embodies
`
`the principle
`
`that data is written at physical sector
`
`locations
`
`in
`
`Flash memory 20 which
`
`follow
`
`the
`
`same order as
`
`th~
`
`sequence in which the data is written. This is achieved
`
`by writing each logical data sector at a physical sector
`
`position defined by a cyclic write pointer.
`
`A schematic representation of the· write operation of
`
`the cyclic storage media management method · is shown
`
`I
`
`in
`
`Figures 4A.
`
`The write pointer, in this case data write
`
`pointer
`
`(DWP)
`
`4 6 moves sequentially through
`
`the sector
`
`positions of Flash block X
`
`in Flash memory 20,
`
`and
`
`continues through the chain of blocks Y and Zin a manner
`
`defined by the block sequencing algorithm. Each block X,
`
`Micron Ex. 1050, p. 20
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`19
`
`PCT/GB02/04381
`
`Y and Z is a physical structure in Flash memory 20 which,
`
`in this case, comprises 32 sector loca ti ans which can be
`
`erased in a single operation.
`
`Logical data sectors are generally writ ten in files
`
`by a file system in the host 12, and the Cyclic Storage
`
`Data Write Algorithm locates the first sector of a file
`
`at the next available physical sector position following
`
`the last sector of the preceding file. When a file is
`
`written by host 12 using logical sectors for w'hich· valid
`
`data already e x ists in the device, the previous versions
`
`of the sectors become obsolete and the blocks containing
`
`them are erased according to the Block Erase Algorithm.
`
`In order
`
`to erase
`
`a block containing obsolete file
`
`sectors it is, in some cases necessary to relocate some
`
`valid sectors of another file. This generally occurs when
`
`a block contc;tins sectors of the head of a file, as well
`
`as sectors with unrelated logical addresses from the tail
`
`of a different file.
`
`A second write poi,nter in this case data relocate
`
`pointer DRP 47 is used for writing relocated sectors in
`
`order to avoid sectors of one file fragmenting a block
`
`containing sectors of another file. The use of a separate
`
`relocation
`
`pointer
`
`significantly
`
`reduces
`
`the
`
`fragmentation of blocks containing
`
`a
`
`file,
`
`leading
`
`to
`
`Micron Ex. 1050, p. 21
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`20
`
`PCT/GB02/04381
`
`minimum requirement for sector relocation and consequent
`
`maximum file write performance.
`
`A host file system is used which also writes sectors
`
`containing system information, such as directory or FAT
`
`sectors in the DOS file system, and these are generally
`
`written immediately before and after a group of sectors
`
`forming a file.
`
`A separate system pointer, system write
`
`pointer SWP 48 is used for this host file system in order
`
`to define the physical write location ior system sectors,
`
`which are identified by their logical address,
`
`in order
`
`to separate system sectors from file data sectors and
`
`a void them being treated in the same way. This ·avoids a
`
`small group of system sectors being "sandwichedn between
`
`the tail of one file and the head of another.
`
`These
`
`system sectors contain information about many files, and
`
`are generally re-written much more frequently than data
`
`for a file.
`
`"Sandwiched" system sectors would cause
`
`frequent relocation of file data sectors and thus the use
`
`of system pointer SWP ~8 minimises
`
`the requirement for
`
`data
`
`sector
`
`relocation
`
`and maximises
`
`file write
`
`performance.
`
`A fourth pointer, system relocate pointer SRP 4 9 is
`
`used for relocation of system sec;:tors, analogous
`
`to the
`
`relocation pointer DRP 47 for file data sectors.
`
`Micron Ex. 1050, p. 22
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`21
`
`PCT/GB02/04381
`
`To summarise the four write pointers are:
`
`Data write pointer, DWP 4 6 which is used to define
`
`the physical
`
`location
`
`for writing file data sectors
`
`transmitted by a host system;
`
`System write pointer, SWP 4 8 which is used to define
`
`the
`
`physical
`
`location
`
`for writing
`
`system
`
`sectors
`
`transmitted by a host · system wherein system sectors are
`
`identified by their logical address,
`
`in acco.r;s:!ance with
`
`the characteristics of the host file system in use;
`
`Data relocation pointer, DRP 47 which is used to
`
`define
`
`the physical
`
`location
`
`for writing
`
`file data
`
`sectors which must occasionally be relocated prior to a
`
`bLock erasure
`
`for
`
`recovery of capacity occupied by
`
`obsolete file data sectors; and
`
`System relocation pointer, SRP 4 9 which is used to
`
`define the physical location for writing system sectors
`
`which are being relocated prior to a block er-asure for
`
`recovery of capacity occupied by obsolete system sectors.
`
`A block must contain data associated with only a
`
`single write pointer and this results in four separate
`
`chains of blocks existing, one for each write pointer,
`
`this is shown in Figure. 4b. However, the same write and
`
`relocation algorithms of
`
`the cyclic storage algorithms
`
`apply to each write pointer 46, 47, 48 and 49.
`
`Micron Ex. 1050, p. 23
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`22
`
`PCT/GB02/04381
`
`This scheme for locating a sector to be ,vritten at
`
`the first available
`
`location
`
`following
`
`the preceding
`
`sector, combined with usage of multiple write pointers,
`
`is fully
`
`flexible,
`
`and provides high performance and
`
`total comp a tibi li ty for all host write con£ igura tions,
`
`including single sector data and data in clusters of any
`
`size.
`
`However,
`
`the Cyclic Storage media managem€nt method
`
`is defined not to allow the existence of a
`
`large number
`
`of obsolete data sectors and nor to implement background
`
`operations
`
`for
`
`functions
`
`such as garbage collection.
`
`Typically only
`
`two block containing obsolete sectors is
`
`allowed to exist for each of the Data Write Pointer DWP
`
`46 and System Write Pointer SWP 48, and block erasure is
`
`performed as a
`
`foreground operation during sector write
`
`sequences.
`
`This method of management means
`
`that
`
`the logical
`
`capacity of the flash memory does not have to be reduced
`
`to allow for the existence of a large volume of obsolete
`
`data, the data integrity is significantly improved by the
`
`absence of background operations, which are susceptible
`
`to interruption by power-down initiated by the host; and
`
`the pauses
`
`in data write sequences are short because
`
`Micron Ex. 1050, p. 24
`Micron v. Vervain
`IPR2021-01550
`
`
`
`WO 03/027828
`
`23
`
`PCT/GB02/04381
`
`erase operations are required for only a single block at
`
`a time.
`
`If an obsolete data sector is created in a new block
`
`associated with either of the write pointers,
`
`then
`
`the
`
`existing
`
`"obsolete block"
`
`is eliminated by erasure,
`
`following
`
`sector
`
`relocation within
`
`the
`
`blocks
`
`if
`
`required.
`
`Erase sector
`
`commands
`
`sent
`
`from
`
`a
`
`ho.st
`
`12 are
`
`supported by· marking the target sector as obsolete, and
`
`allowing its erasure to follow acco~ding
`
`to
`
`the Block
`
`Erasure algorithm.
`
`The Cyclic Storage
`
`block
`
`sequencing
`
`algorithm
`
`determines the sequence in which blocks within the flash
`
`memory 20 are used for the writing of new or relocated
`
`data, and is therefore responsible for ensuring that no
`
`block experiences a number of write/erase cycles which
`
`exceeds
`
`the endurance
`
`limit specified
`
`for
`
`the Flash
`
`memory system 20 which is being used.
`
`When a logical sector is written by the host, any
`
`previous version which exists in the memorys system is
`
`treated as obsolete data.
`
`The block erase algorithm
`
`ensures
`
`t.hat blocks which contain obsolete data sectors
`
`are erased immediately, to allow recovery of the capacity
`
`occupied by these se
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
