15;
`United States Patent
`[11] Patent Number:
`Assaret al.
`[45] Date of Patent:
`
`
`5,479,638
`Dec. 26, 1995
`
`NTCTYA
`
`US005479638A
`
`[54]
`
`[75]
`
`[73]
`
`[21]
`
`[22]
`
`[51]
`[52]
`
`{58]
`
`[56]
`
`FLASH MEMORYMASS STORAGE
`ARCHITECTURE INCORPORATION WEAR
`LEVELING TECHNIQUE
`
`Inventors: Mahmud Assar, Morgan Hill; Siamack
`Nemazie, San Jose; Petro Estakhri,
`Pleasonton, all of Calif.
`
`Assignee: Cirrus Logic, Inc., Palo Alto, Calif.
`
`Appl. No.: 37,893
`
`Filed:
`
`Mar. 26, 1993
`
`Tint, Cho icceccccccecceteecssneeee GO6F 12/02; GO6F 12/14
`TS. Ce cecssscssescsessserseesnee 395/430; 395/435; 395/483;
`395/412; 395/492; 395/490; 365/900; 364/DIG.1;
`364/244.6; 364/245.2; 364/246.8; 364/255.1;
`364/249
`Field of Search ou... 395/425; 365/900,
`365/218, 189.07
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`
`
`0489204A1
`0509184A1
`0501289A2
`59-45695
`62-283497
`62-283496
`
`12/1990 European Pat. Off..
`4/1991 European Pat. Off. .
`2/1992 European Pat. Off. .
`3/1984
`Japan .
`12/1987
`Japan .
`12/1987
`Japan .
`OTHER PUBLICATIONS
`
`Kai Hwang & Faye A. Briggs, “Computer Architechture and
`Parallel Processing”, McGraw-Hill, p. 64, 1984.
`T. Nozaki et al., “A 1-Mb EEPROM with MONOS Memory
`Cell for Semiconductor Disk Application,” IEEE Journal of
`Solid-State Circuits, vol. 26, No. 4, pp. 497-501, Apr. 1991,
`8S.
`Leibson,
`“Nonvolatile
`in-circuit-reprogrammable
`memories,” EDN,Jan. 3, 1991, pp. 89-102.
`W.Lahti and D. McCarron,“Store Data in a Flash,” BYTE,
`Nov. 1990, pp. 311-318.
`D. Auclair, “Optimal Solid State Disk Architecture For
`Portable Computers,” SunDisk, presented at The Silicon
`Valley PC Design Conference, Jul. 9, 1991.
`S. Mehroura et al., “Serial 9Mb Flash EEPROMforSolid
`State Disk Applications,” 1992 Symposium on VLSI Cir-
`cuits Digest of Technical Papers, pp. 24-25,
`
`Primary Examiner—Eddie P. Chan
`Assistant Examiner—Reginald G, Bragdon
`Attorney, Agent, or Firm—Haverstock & Associates
`ABSTRACT
`[57]
`
`4,943,962
`7/1990 Umamiya etal. ........c0s 365/230,08
`5,043,940
`8/1991 Harari ..........
`- 365/168
`
`5,053,990 10/1991 Kreifels et al.
`..
`w- 395/425
`
`5,065,364 11/1991 Atwood et al...
`». 365/185
`we 297/328
`5,095,344
`3/1992 Harari
`......
`A semiconductor mass storage device can be substituted for
`5,134,589
`7/1992 Hamano...
`365/238.5
`a rotating hard disk. The device avoids an erase cycle each
`5,155,705
`10/1992 Gotoet al.
`w. 365/218
`time information stored in the mass storage is changed. (The
`5,163,021
`11/1992 Mehrotra ..
`~- 365/185
`erase cycle is understood to include, fully programming the
`«. 257/320
`5,168,465
`12/1992 Harari
`..........
`
`block to be erased, and then erasing the block.) Erase cycles
`12/1992 Mehrotra et al.
`+. 365/185
`5,172,338
`
`are avoided by programming an altered data file into an
`w. 365/218
`5,270,979 12/1993 Harari et al.
`.
`.....
`we 395/425
`5,283,882
`2/1994 Smith etal.
`empty mass storage block rather than overitself as a hard
`
`
`5,303,198 4/1994 Adachi et al.0.0.0...cece 365/218
`
`disk would. Periodically, the mass storage will need to be
`
`8/1994 Garner.........
`«= 365/189.01
`5,337,275
`cleaned up. Secondly, a circuit for evenly using all blocks in
`5,341,330
`8/1994 Wells et al.
`«. 365/185
`the mass storage is provided. These advantagesare achieved
`
`a» 365/218
`5,341,339
`8/1994 Wells...
`through the use of several flags, a map to directly correlate
`
`8/1994 Henning et al.
`.
`» 370/58.1
`5,341,368
`a logical address of a block to a physical address of that
`5,353,256 10/1994 Fandrich et al.
`.
`. 365/230.03
`block and a count register for each block.In particular,flags
`
`10/1994 Hasbunetal. ...
`w. 365/218
`5,357,475
`are provided for defective blocks, used blocks, old version
`4/1995 Bath .....csecscssescsesssecsseccseseeeenees 395/425
`5,404,485
`of a block, a count to determine the numberoftimes a block
`has been erased and written and erase inhibit.
`
`FOREIGN PATENT DOCUMENTS
`
`0424191A2
`
`9/1990 European Pat. Off. .
`
`41 Claims, 8 Drawing Sheets
`
`200
`
`RECEIVEWRITEINSTRUCTION
`‘TO PROGRAMMASSSTORAGE
`
`7 | ERASEFLAGSAND DATAFOR
`ALL.ALOCKS HAVINGASET
`OLDUNEWELAG
`
`
`
`
`
`
`UPDATEMAFTOCORRELATE
`LOG-CAL ADDRESS 70PHYSICAL
`ADDRESS
`
`
`
`NetApp
`
`Exhibit1008
`
`Page 1
`
`NetApp Exhibit 1008 Page 1
`
`

`

`US. Patent
`
`Dec. 26, 1995
`
`Sheet 1 of 8
`
`5,479,638
`
`>f
`
`am
`
`308
`
`O=u
`
`u =
`
`408
`
`NetApp
`
`Exhibit1008
`
`Page 2
`
`NetApp Exhibit 1008 Page 2
`
`

`

`U.S. Patent
`
`Dec. 26, 1995
`
`Sheet 2 of 8
`
`5,479,638
`
`AYOWSIN
`
`NetApp
`
`Exhibit1008
`
`Page3
`
`NetApp Exhibit 1008 Page 3
`
`

`

`U.S. Patent
`
`Dec.26, 1995
`
`Sheet 3 of 8
`
`APPLICATIONS|.—— 452
`SOFTWARE
`|
`
`5,479,638 COMMERCIAL
`
`———- 154
`
`—+———- 156
`
`150
`
`Fig. 3
`
`NetApp
`
`Exhibit1008
`
`Page 4
`
`NetApp Exhibit 1008 Page 4
`
`

`

`U.S. Patent
`
`5,479,638
`
`Dec. 26, 1995
`
`Sheet 4 of 8
`
`
`
`Fig. 4
`
`NetApp
`
`Exhibit1008
`
`Page5
`
`NetApp Exhibit 1008 Page 5
`
`

`

`U.S. Patent
`
`Dec. 26, 1995
`
`Sheet 5 of 8
`
`5,479,638
`
`200
`
`TO PROGRAM MASS STORAGE
`
`RECEIVE WRITE INSTRUCTION
`
`LOCATE BLOCK WITH
`UNSET USED/FREE
`
`
`
`
`ERASE FLAGS AND DATAFOR
`ALL BLOCKS HAVING A SET
`OLD/NEW FLAG
`
`204
`
`PROGRAM DATA FILE
`
`SET USED/FREE FLAG AND
`
`
` 208
`
`WILL DATA SUPERCEDE
`PREVIOUS DATA
`
`
` 210
`
`ADDRESS
`
`SET OLD/NEW FLAG ON
`SUPERCEDED BLOCK
`
`
`
`212
`UPDATE MAP TO CORRELATE
`LOGICAL ADDRESS TO PHYSICAL
`
`Fig. 5
`
`NetApp
`
`Exhibit1008
`
`Page6é
`
`NetApp Exhibit 1008 Page 6
`
`

`

`US. Patent
`
`Dec. 26, 1995
`
`Sheet 6 of 8
`
`5,479,638
`
`ERASE INHIBIT
`STATUSBIT
`
`ERASE COUNT
`
`FLASH MEMORYDEVICE
`
` 200
`
`Block 0
`
`Block 1
`
`
`
`
`
`Fig. 6
`
`NetApp
`
`Exhibit1008
`
`Page7
`
`NetApp Exhibit 1008 Page 7
`
`

`

`U.S. Patent
`
`8&7
`
`Axa
`
`OFZ
`
`LYVLS
`
`
`
`/Gasn)TinsSIMsid
`
`TTvdavSOVdead
`
`
`
`
`
`MAN/T1OHLOGdey
`
`ANNILNOO
`
`Dec. 26, 1995
`
`LASDNIAVHSNDO'INTIVASVUTASVUdCNVLASOVVIVAFYOLS
`
`
`agvuaCNVOV'dMANICTOLASNNOV"LIETHNIvd
`
`
`
`
`LIGIHNISSVugANVINN
`
`Sheet 7 of 8
`
`5,479,638
`
`SHOOTTTvAOSOVTA
`
`Ove
`
`
`
`
`
`MOOTJONOSYOAOVTdMAN/GTOLES
`
`bye
`
`
`
`
`ONIAVHSHOO1dT1vFsSvuad)
`
`aSVadGNVLYSOV’THMAN/UTO
`
`LAUSNNOVLIGTHNI
`
`
`
`
`
`guUNdsdooddASVYEALNOAXA
`
`
`
`MOOTNOLLVNILSHCWOdLidLIGIHNI
`
`SLIALIAHOOTEFaeOL
`
`ANTVALNNOOLSVd7TALIAHOOTGesnAON
`
`
`HLIMMOOTdVAUdHLSI
`LOSNNOWTddaadsd/dasn
`
`aSVadFHLLASNAHLCXVADLINNOO=LNNO0O
`
`
`XVW)INNOO=LNNODUNV
`
`NetApp
`
`Exhibit1008
`
`Page 8
`
`NetApp Exhibit 1008 Page 8
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Dec. 26, 1995
`
`Sheet 8 of 8
`
`5,479,638
`
`270
`
`READ MASS STORAGE
`
`RECEIVE INSTRUCTION TO
`
`271
`RECEIVE LOGICAL ADDRESS
`
`272
`
`CONCATENATE SET USED/FREEBIT AND
`
`UNSET NEW/OLDBIT UNSET DEFECT BIT
`
`NO
`
`
`
`
`MATCH FOUND???
`
`
`274
`SEND MATCH-NOT-FOUND
`SIGNAL
`
`MATCHED LOGICAL ADDRESS
`
`275
`READ DATAFILE FROM THE
`PHYSICAL FILE ASSOCIATED WITH
`
`Fig. 8
`
`NetApp
`
`Exhibit1008
`
`Page9
`
`NetApp Exhibit 1008 Page 9
`
`

`

`5,479,638
`
`1
`FLASH MEMORYMASS STORAGE
`ARCHITECTURE INCORPORATION WEAR
`LEVELING TECHNIQUE
`FIELD OF THE INVENTION
`
`This invention relates to the field of mass storage for
`computers. More particularly, this invention relates to an
`architecture for replacing a hard disk with a semiconductor
`non-volatile memory and fin particular flash memory.
`BACKGROUND OF THE INVENTION
`
`Computers have used rotating magnetic media for mass
`storage of data, programs and information. Though widely
`used and commonly accepted, such hard disk drives suffer
`from a variety of deficiencies. Because ofthe rotation of the
`disk, there is an inherent latency in extracting information
`from a hard disk drive.
`
`Other problemsare especially dramatic in portable com-
`puters. In particular, hard disks are unable to withstand many
`of the kinds of physical shock that a portable computerwill
`likely sustain. Further,
`the motor for rotating the disk
`consumessignificant amounts of power decreasing the bat-
`tery life for portable computers.
`Solid state memory is an ideal choice for replacing a hard
`disk drive for mass storage because it can resolve the
`problems cited above. Potential solutions have been pro-
`posed for replacing a hard disk drive with a semiconductor
`memory. For such a system to be truly useful, the memory
`must be non-volatile and altcrable. The inventors have
`determined that flash memory is preferred for such a
`replacement. It should be noted that E? PROM is also
`suitable as a replacement for a hard disk drive.
`Flash memory is a single transistor memory cell which is
`programmable through hot electron injection and erasable
`through Fowler-Nordheim tunneling. The programming and
`erasing of such a memory cell requires current to pass
`through the dielectric surrounding a floating gate electrode.
`Becauseofthis, such types of memory havea finite number
`of erase-write cycles. Eventually, the dielectric will fail.
`Manufacturers of flash cell devices specify the limit for the
`numbererase-write cycles as between 10,000 and 100,000.
`Accordingly, unlike rotating magnetic media, a flash
`memory mass storage device does not have an indefinite
`lifetime.
`
`Another requirement for a semiconductor mass storage
`device to be successful is that its use in lieu of a rotating
`media hard disk mass storage device be transparent to the
`system designer andtheuser. In other words, the designer of
`a computer incorporating such a semiconductor massstor-
`age device could simply remove the hard disk and replace it
`with a semiconductor mass storage. All presently available
`commercial software should operate on a system employing
`such a semiconductor hard disk without the necessity of any
`modification.
`
`SunDisk proposed an architecture for a semiconductor
`mass storage using flash memory at the Silicon Valley PC
`Design Conference Jul. 9, 1991. That mass storage system
`included read-write block sizes of 512 Bytes (or multiples
`thereof) just like IBM PC compatible hard disk sector sizes.
`(IBM PC is a trademark of IBM Corporation.) During an
`erase cycle, an entire block is first fully programmed and
`then erased.
`
`Asin conventional hard disks, it appears in the SunDisk
`architecture that there is an erase-before-write cycle each
`time data is changed in the mass storage. Thus, if a program
`or data block is to be changed, the data is written to RAM
`and appropriately changed, the flash block is fully pro-
`grammed, then erased and then reprogrammedto the new
`
`20
`
`25
`
`30
`
`35
`
`40
`
`55
`
`60
`
`65
`
`2
`memory condition. Unlike a hard disk device, in a flash
`memory device an erase cycle is slow which can signifi-
`cantly reduce the performance of a system utilizing flash
`memory as its mass storage.
`Though such an architecture provides a workable semi-
`conductor mass storage, there are several inefficiencies. First
`of all, each time a memory block is changed,thereis a delay
`to the entire system due to the necessary erase-before-write
`cycle before reprogramming the altered information back
`into the block. The overhead associated with erase-before-
`write cycles is costly in terms of system performance.
`Secondly, hard disk users typically store both information
`whichis rarely changed and information whichis frequently
`changed. For example, a commercial spread sheet or word
`processing software programsstored on a user’s system are
`rarely, if ever, changed. However, the spread sheetdatafiles
`or word processing documents are frequently changed.
`Thus, different sectors of a hard disk typically have dra-
`matically different usage in terms of the number oftimes the
`information stored thereon is changed. Whilethis disparity
`has no impact on a hard disk becauseofits insensitivity to
`data changes, in a flash memory device, this variance can
`cause sections of the mass storage to wear out and be
`unusable significantly sooner than othersections of the mass
`storage.
`
`SUMMARYOF THE INVENTION
`
`The present invention discloses two primary algorithms
`and an associated hardware architecture for a semiconductor
`mass storage device. It will be understood that data file in
`this patent document refers to any computer file including
`commercial sofiware, a user program, word processing
`software document, spread sheetfile and the like. Thefirst
`algorithm provides means for avoiding an erase-before-
`write cycle when writing a modified data file back onto the
`mass storage device. Instead, no erase is performed and the
`modified data file is written onto an empty portion of the
`mass storage. In addition, the second algorithm prevents any
`portion of the mass storage from being erased a substantially
`larger numberof times than any other portion. This prevents
`any one block of the mass storage from failing and becoming
`unusable earlier than any other block thereby extending the
`life of the entire mass storage.
`The semiconductor mass storage architecture has blocks
`sized to conform with commercial hard disk sector sizes.
`The blocks are individually erasable. In one embodiment,
`the semiconductor mass storage of the present invention can
`be substituted for a rotating hard disk with no impactto the
`user, so that such a substitution will be transparent. Means
`are provided for avoiding the erase-before-write cycle each
`time information stored in the mass storage is changed. (The
`erase cycle is understood to include, fully programming
`each bit in the blockto be erased, and thenerasingall the bits
`in the block.)
`Accordingto thefirst algorithm, erase cycles are avoided
`by programming an altered data file into an empty mass
`storage block rather than overitself after an erase cycle of
`that block as done on a conventional hard disk. This would
`ordinarily not be possible when using conventional mass
`storage because the central processor and commercial soft-
`ware available in conventional computer systems are not
`configured to track continually changing physical locations
`of data files. The present invention includes a programmable
`map to maintain a correlation between the logical address
`408 and the physical address 408 of the updated information
`files.
`
`Periodically, the mass storage will fill up because there
`have been no erase cycles. At such times, the mass storage
`needs to be cleaned up with a multi-sector erase as fully
`described in the detailed description below.
`
`NetApp
`
`Exhibit1008
`
`Page 10
`
`NetApp Exhibit 1008 Page 10
`
`

`

`5,479,638
`
`3
`According to the second algorithm, means are provided
`for evenly using all blocks in the mass storage. A counter
`tracks the numberof times each block is erased. A program-
`mable maximum value for the counter is also provided. As
`the numberoferase cycles for a block becomesoneless than
`the maximum, the block is erased one last time and written
`with another file having a then smallest numberof erase
`cycles. It is also prevented from being erased thereafter by
`setting its erase inhibit flag. After all blocks approach this
`maximum,all the erase counters and inhibit flags are cleared
`and the second algorithm is then repeated. In this way, no
`block can be erased a substantial numberof times more than
`any other block.
`These advantages are achieved through the useof several
`flags and a count register for each block. In particular, flags
`are provided for defective blocks, used blocks, old version
`of a block, a count to determine the numberof times a block
`has been erased and written and an erase inhibit flag.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 shows an architecture for a semiconductor mass
`storage of the present invention.
`FIG. 2 showsthe architecture of FIG. 1 wherein the data
`in one block has been altered and stored in a new physical
`address.
`
`FIG. 3 shows a block diagram of an erase cycle usage
`according to algorithm 1 of the present invention.
`FIG. 4 showsa simplified block diagram of the old/new
`flag system integrally formed with the memory of the
`present invention.
`FIG. 5 shows a flow chart block diagram for algorithm 1
`according to the present invention.
`FIG. 6 shows an additional architecture according to the
`preferred embodiment of the present invention.
`FIG. 7 shows a flow chart block diagram of algorithm 2
`of the present invention.
`FIG. 8 shows a flow chart block diagram of a read
`algorithm according to the present invention.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`FIG. 1 shows an architecture for a semiconductor mass
`storage according to the present invention. In the preferred
`embodiment,all of the memory storage is flash EEPROM.
`It is possible to substitute E7PROM for someorall of the
`data bits shown. A memory storage 100 is arranged into N
`blocks of data from zero through N-1. Eachofthe blocks of
`data is M Bytes long. In the preferred embodiment, each
`block is 512 Bytes long to correspond with a sector length
`in a commercially available hard disk drive. In addition to
`the memory data block 102,a flag 104 is directly related to
`each data block 102. The memory 100 can contain as much
`memory storage as a user desires. An example of a mass
`storage device might include 100 MByte of addressable
`storage.
`Anon-volatile content addressable memory (CAM) 106is
`associated with the memory storage 100. In the preferred
`embodiment, the CAM 106 is formed of flash memory. The
`CAM 106can also be E7PROM.There is oneentry in the
`CAM 106 for every one of the N blocks in the mass storage
`100. Each entry includes a numberof fields which will be
`described below. The CAM 106 is also formed of a non-
`volatile memory becauselossofits information would make
`retrieval of the data files stored in the mass storage 100
`impossible.
`
`20
`
`235
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`As described above in the Backgroundof the Invention,
`conventional computer systems are not configured to track
`continually changing physical
`locations of data files.
`According to the present invention, each time a data file is
`changedit is stored into a new physical location in the mass
`storage. Thus, implementation of the architecture of the
`present invention requires a mapping ofthe logical address
`308,i.c., the address where the computer system believes the
`datafile is stored to the physical address 408,i.e., the actual
`location the data file can be found is stored in the mass
`storage.
`The logical address 308 portion of the map 108 and the
`flags 112, 116 and 118 form part of the CAM 106. It is
`possible to use other storage means than a CAM tostore the
`address map, such as a look-up table. However, a CAM is
`the most efficient means known to the inventors. It is not
`necessary that the physical address 408 portion of the map
`108 form part of the CAM.Indeed,the physical address 408
`portion of the map 108 can be ordinary flash memory,
`E”PROM or even ROM.If ROMisselected for the physical
`address 408 array of the map 108, a defect in the ROM will
`preventthe block correspondingto that physical address 408
`from ever being addressed. Accordingly, a changeable non-
`volatile memory is preferred. Note that any replacement
`circuit for the CAM should be nonvolatile. Otherwise, loss
`or removal of power to the system will result in loss of the
`ability to find the data files in the mass storage.
`Assume for example that a user is preparing a word
`processing document and instructs the computerto save the
`document. The documentwill be stored in the mass storage
`system as shownin FIG. 1. The computer system will assign
`it a logical address 308, for example 526H. The massstorage
`system of the present invention will select a physical address
`408 of an unused block or blocks in the mass storage 100 for
`storing the document, e.g. 728H. That map correlating the
`logical address 308 to the physical address 408 is stored in
`the CAM 106.Asthe data is programmed,the system of the
`present invention also sets the used/free flag 112 to indicate
`that this block has been written without being erased. The
`used/free flag 112 also forms a portion of the CAM 106. One
`used/free flag 112 is provided for each entry of the CAM
`106.
`
`Later, assume the user retrieves the document, makes a
`change and again instrucis the computer to store the docu-
`ment. To avoid an erase-before-write cycle, the system of the
`present invention provides means for locating a block hav-
`ing its used/free flag 112 unset (not programmed) which
`indicates that the associated block is erased. The system then
`sets the used/free flag for the new block 114 (FIG. 2) and
`then stores the modified document in that new block 114.
`Next, the system sets the old/new flag 116 of the previous
`version of the document
`indicating that this is an old
`unneeded version of the document. Lastly,
`the system
`updates the correlation between the logical address 308 and
`the actual physical address 408. In this way, the system of
`the present invention avoids the overhead of an erase cycle
`which is required in the erase-before-write of conventional
`systems to store a modified version of a previous document.
`The writing to mass storage process outlined above is
`repeated until the entire mass storage memory 100 has been
`filled. A full mass storage is indicated by no unset used/free
`flags 112 in the CAM 106. Atthat time a multi-sector erase
`is necessary and those blocks in the memory 100 and their
`associated CAM 106 entrics having an old/new flag 116 set
`are all erased simultaneously. Note that it is not necessary
`for 100% of the blocks to have a set used/free flag 112 for
`a multi-.sector erase to occur. For example, if a data file
`
`NetApp
`
`Exhibit1008
`
`Page 11
`
`NetApp Exhibit 1008 Page 11
`
`

`

`5,479,638
`
`5
`requiring three blocks were being written and only two
`blocks having unset used/free flags 112 were available a
`multi-sector erase can be run.
`
`A simultaneous erase is not needed with prior art imple-
`mentations because those embodiments utilize an erase-
`before-write cycle rather than retaining superseded versions
`of datafiles. In suchcircuits a latch of volatile logic circuits
`is set to couple the voltage necessary to erase theflash cells
`in the block. Becauseof the likely large number of memory
`blocks in the mass storage 100, if the CAM 106 and mass
`storage 100 are on the sameintegrated circuit (chip) cou-
`pling the old/new flag 116 to the latches in parallel would
`typically be very expensive in terms of surface area of the
`chip and coupling the old/new flags 116 serially to the
`latches would be expensivein terms of system performance.
`If the CAM 106 and the mass storage 100 are on separate
`chips, it is doubtful that either device could have sufficient
`T/O capability to interconnect the old/new flags 116 to the
`latches in parallel and thus, the system would suffer from a
`serial transfer of that information for a multi-sector erase.
`
`Because of these problemsit is preferable that no updat-
`ing of the latches be performed priorto an eraseofall blocks
`having a set old/new flag 116. To avoidthis step, a plurality
`of old/new flag systems 104 are intimately associated with
`each block in the memory 102 and is programmed by the
`same sequenceof instructions as the old/new flag 116of the
`CAM 106.
`
`FIG.4 showsa simplified block diagram of the old/new
`flag system 104 whichincludesa non-volatile bit 120 having
`data which mirrors the old/new flag 116. In addition there is
`a volatile latch 122 coupled to receive the data in the bit 120
`from the latch during an erase cycle. At the timeof an erase,
`the data in each of the bits 120 is simultaneously coupled to
`each appropriate ones of the latches 122 undercontrol of a
`load signal coupled to each latch 122 over a load line L.
`Upon receiving a signal to perform the erase, the latch for
`every block havingits associated bit 120 set then couples the
`voltage necessary to perform an erase of that block andits
`associated bit 120. After the erase is complete and verified,
`all the latches 122 are individually reset to a predetermined
`state under controlof a reset signal coupled to eachlatch 122
`over a reset line R.
`
`For certain applications of the present invention, espe-
`cially for low Dower portable computers, a simultaneous
`erase of all blocks having their respective old/new flags set
`may be undesirable. For such applications, the blocks can be
`segregated into groups of blocks. Each group has a unique
`control line to load the latches from the nonvolatile bits. In
`this mode, during an erase cycle,
`the control
`lines are
`sequentially activated and the groups of blocks sequentially
`erased.
`
`FIG. 5 showsalgorithm 1 according to the present inven-
`tion. When the system of the present invention receives an
`instruction to program data into the massstorage(step 200),
`then the system attempts to locate a free block (step 202),
`ie., a block having an unset (not programmed) used/free
`flag. If successful, the system sets the used/free flag for that
`block and programsthe data into that block (step 206).
`If on the other hand, the system is unable to locate a block
`having an unset used/free flag, the system erases the flags
`(used/free and old/new) and data for all blocks having a set
`old/newflag (step 204) and then searchesfor a block having
`an unset used/free flag (step 202). Such a block hasjust been
`formed by step 204. The system thensets the used/free flag
`for that block and programsthedata file into that block(step
`206).
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`35
`
`60
`
`65
`
`6
`If the data file is a modified version of a previously
`existingfile, the system must prevent the superseded version
`from being accessed. The system determines whether the
`data file supersedesa previous datafile (step 208). If so, the
`system sets the old/new flag associated with the superseded
`block (step 210). If on the other hand, the data file to be
`stored is a newly created data file, the step of setting the
`old/new flag (step 210) is skipped because there is no
`supersededblock. Lastly, the map for correlating the logical
`address 308 to the physical address 408 is updated (step
`212).
`Byfollowing the procedure outlined above, the overhead
`associated with an erase cycle is avoided for each write to
`the memory 100 except
`for periodically. This vastly
`improves the performance of the overall computer system
`employing the architecture of the present invention.
`In the preferred embodimentof the present invention, the
`programming of the fiash memory follows the procedure
`commonly understood by those of ordinary skill in the art.
`In other words,
`the program impulses are appropriately
`applied to the bits to be programmed and then compared to
`the data being programmed to ensure that proper program-
`ming has occurred. In the event that a bit fails to be erased
`or programmed properly, a defect flag 118 in the CAM 106
`is set preventing that block from being used again.
`In addition to saving the overhead of the erase cycle all
`but periodically, utilization of the present invention tends to
`more evenly distribute the erase cycles amongst certain
`portions of the blocks of the mass storage. FIG. 3 schemati-
`cally shows the types of information stored in utilizing a
`mass storage media 150. One portion of the mass storage
`150 contains commercial applications software 152 such as
`word processing, spreadsheet, calendaring, calculators and
`the like. These portions of the mass storage 150 rarely, if
`ever, require an erase-reprogram cycle according to the
`algorithm described above.
`A second section of the mass storage 150 contains user
`data 154. The user data 154 is frequently altered requiring
`the information to be reprogrammed into blocks of the free
`space 156 under the algorithm described above. A third
`portion of the mass storage 150 contains free space 156 of
`unprogrammed blocks.
`Byfollowing the algorithm above, the storage blocks in
`the portions 154 and 156 of the memory 150 will recycle
`data files and thus be erased and reprogrammed significantly
`more often than the commercial applications software por-
`tion 152 of the memory 150. Accordingly, the mass storage
`150 will wear out more quickly in the user data 154 and the
`free space 156 sections of the memory requiring earlier
`replacementthan in sections 152 of the mass storage having
`data files which are rarely changed. As the numberof free
`blocks diminishes providing a smaller number of blocks
`through which to recycle data files, the remaining blocks
`become erased more frequently exacerbating the problem.
`A secondalgorithm is provided for leveling erase cycles
`amongstall the blocks within the entire mass storage device
`as shownin FIG. 6. A counter is provided for each block to
`count the number of times each block has been erased and
`reprogrammed. An erase inhibit flag is also provided for
`each block. Once the erase count has reached the maximum
`for any block, the erase inhibit flag is set for that block. After
`that time that block cannot be erased until a clean-out erase
`is performed. Referring to FIG.3, if only algorithm 1 is used
`eventually all of the blocks in the user data 154 andthefree
`space 156 portions of the mass storage 150 will reach the
`maximum count and havetheir respective erase inhibit flags
`
`NetApp
`
`Exhibit1008
`
`Page 12
`
`NetApp Exhibit 1008 Page 12
`
`

`

`5,479,638
`
`7
`set. Because of this, a reallocation of the rarely erased data
`files stored in the memory 152 is made into the memory 154
`and/or 156. In this way, sections of the mass storage which
`have been erased numerous times are programmed with a
`reallocated data file which is rarely changed thereby allow-
`ing all sections of the mass storage to eventually approach
`parity of erase cycles. Like the multi-sector erase, a clean-
`out erase can be performed in the event
`that there is
`insufficient available storage for a data file presently being
`performed. For example, if all but two blocks have their
`respective erase inhibit flags set, and a three or more block
`data file is being programmed, a clean-out erase can be
`performed to provide sufficient storage for the datafile.
`Once the erase inhibit flag is set for all the blocks,
`indicating that all the blocks have achieved parity in erase
`cycles, the erase inhibit and erase count registers are erased
`and the cycle is repeated. The selection of the maximum
`count depends upon the system requirements. As the value
`for the maximum count increases, the disparity between
`erase count cycles of various blocks can also increase.
`However, because data is shifted as a result of achieving
`maximum erase count this process of smoothing cycles
`throughout the mass storage ofitself introduces additional
`erase cycles because a block of information is transferred
`from a physical block having few erases to a block having
`the maximum number of erases. Accordingly, though low
`maximum count values reduce the disparity between erase
`cycles amongst the blocks it also increases the number of
`erase cycles to which the blocks are subjected. Accordingly,
`individual users may select an erase count depending upon
`the system needs.
`In the preferred embodiment, algorithm 2 is merged with
`algorithm 1 as shown in FIG. 7. An instruction is provided
`by the computer system to write a data file to the mass
`storage (step 230) which starts the combined algorithm 1
`and algorithm 2 sequence.It is first determined whether the
`mass storageis full (step 232). If the mass storage is not full,
`ie., it has a block with its used/free flag unset, the algorithm
`continues and stores the data file into such a block (step
`234).
`If on the other hand,it is determined that there are no free
`blocks, then it is next determined whether there are any
`blocks which have both the old/new flag set AND the erase
`inhibit flag unset (step 236). If there are no blocks which
`have both the old/new flag set AND the erase inhibit flag
`unset (step 236), the system of the present invention erases
`the data file, used/free flag and old/new flag in each block
`havingits old/new flag set, and erases the counter and erase
`inhibit flag for every block (step 238). Step 238 is also
`performed in the event there are insufficient blocks remain-
`ing to store a pending data file. The algorithm then returns
`to block (step 232) to determine whether the disk is full.
`If the system can find a block having both the old/new flag
`sct AND the erase inhibit flag unset (step 236), then the
`system executes an erase procedure anderases the datafile,
`used/free flag and old/new fiag in each block having its
`old/new flag set. The counter is incremented and the crase
`inhibit flag for such blocks is not disturbed.
`It is then determined whether any block having its used/
`free flag unset has its counter at the maximum count (step
`242). If not, then the system ofthe present invention returns
`to decision step 232 and investigates again whetherthereis
`any block having its used/free flag unset (step 232).
`Onthe other hand,if there is a block having its erase count
`at the maximum value, a data file is copied from another
`block having the then least count value (step 244) into the
`location having COUNT=COUNT,,,,. The erase inhibit flag
`is then set (step 244). Note that a data file will not be copied
`from a block having its erase count at one less than the
`
`20
`
`25
`
`30
`
`45
`
`50
`
`60
`
`65
`
`8
`maximum value, COUNT,,,,-1. Making such a reallocation
`from a source block having COUNTy,,,-1 to a destination
`block having COUNT,,,,. results in having both blocks at
`COUNT,,,, and no net gain. Further, the block p