United States Patent r19J
`Assar et al.
`
`I 1111111111111111 11111 lllll lllll 111111111111111 1111111111111111 Ill lllll llll
`5,479,638
`Dec. 26, 1995
`
`US0054 79638A
`[11] Patent Number:
`[45] Date of Patent:
`
`[54] FLASH MEMORY MASS STORAGE
`ARCHITECTURE INCORPORATION WEAR
`LEVELING TECHNIQUE
`
`[75]
`
`Inventors: Mahmud Assar, Morgan Hill; Siamack
`Nemazie, San Jose; Petro Estakhri,
`Pleasanton, all of Calif.
`
`[73] Assignee: Cirrus Logic, Inc., Palo Alto, Calif.
`
`[21] Appl. No.: 37,893
`Mar. 26, 1993
`
`[22] Filed:
`
`Int. Cl.6
`............................. G06F 12/02; G06F 12/14
`[51]
`[52] U.S. Cl . .......................... 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
`[58] Field of Search ............................. 395/425; 365/900,
`365/218, 189.07
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,943,962
`5,043,940
`5,053,990
`5,065,364
`5,095,344
`5,134,589
`5,155,705
`5,163,021
`5,168,465
`5,172,338
`5,270,979
`5,283,882
`5,303,198
`5,337,275
`5,341,330
`5,341,339
`5,341,368
`5,353,256
`5,357,475
`5,404,485
`
`7/1990 Irnamiya et al .................... 365/230.08
`8/1991 Harari ..................................... 365/168
`10/1991 Kreifels et al .......................... 395/425
`11/1991 Atwood et al. ......................... 365/185
`3/1992 Harari ..................................... 257/328
`7/1992 Hamano ............................... 365/238.5
`10/1992 Goto et al ............................... 365/218
`11/1992 Mehrotra ................................. 365/185
`12/1992 Harari ..................................... 257/320
`12/1992 Mehrotra et al. ....................... 365/185
`12/1993 Harari et al ............................. 365/218
`2/1994 Smith et al. ............................ 395/425
`4/1994 Adachi et al ........................... 365/218
`8/1994 Garner ............................... 365/189.01
`8/1994 Wells et al. ............................. 365/185
`8/1994 Wells ...................................... 365/218
`8/1994 Henning et al. ....................... 370/58.1
`10/1994 Fandrich et al. ................... 365/230.03
`10/1994 Hasbun et al ........................... 365/218
`4/1995 Ban ......................................... 395/425
`
`FOREIGN PATENT DOCUMENTS
`
`0489204Al
`0509184Al
`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.
`S. 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 EEPROM for Solid
`State Disk Applications," 1992 Symposium on VLSI Cir(cid:173)
`cuits Digest of Technical Papers, pp. 24-25.
`
`Primary Examiner-Eddie P. Chan
`Assistant Examiner-Reginald G. Bragdon
`Attorney, Agent, or Firm-Haverstock & Associates
`
`[57]
`
`ABSTRACT
`
`A semiconductor mass storage device can be substituted for
`a rotating hard disk. The device avoids an erase cycle each
`time information stored in the mass storage is changed. (The
`erase cycle is understood to include, fully programming the
`block to be erased, and then erasing the block.) Erase cycles
`are avoided by programming an altered data file into an
`empty mass storage block rather than over itself as a hard
`disk would. Periodically, the mass storage will need to be
`cleaned up. Secondly, a circuit for evenly using all blocks in
`the mass storage is provided. These advantages are achieved
`through the use of several flags, a map to directly correlate
`a logical address of a block to a physical address of that
`block 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 number of times a block
`has been erased and written and erase inhibit.
`
`0424191A2
`
`9/1990 European Pat. Off ..
`
`41 Claims, 8 Drawing Sheets
`
`NO
`
`""
`
`ERASEfLAGSANDDATAR>R
`AlLBl.OCKSHA.VINGASET
`<lU>NSWFLAG
`
`"'
`
`Ul'DA1EMAP10CORRELATE
`LOGICAL ADDRESS TO PHYSICAL
`ADDRESS
`
`INTEL-1022
`8,010,740
`
`

`

`U.S. Patent
`U.S. Patent
`
`Dec. 26, 1995
`Dec. 26, 1995
`
`Sheet 1 of 8
`Sheet 1 of 8
`
`5,479,638
`5,479,638
`
`M N
`I
`I
`
`z z z
`
`..-<
`I
`
`AYOWSW
`
`C)
`.,_
`,_
`
`♦
`
`00
`N
`t'--
`
`\0
`N
`II")
`
`....
`
`\
`
`"'-t'
`C)
`.,_
`
`~
`
`-~
`LC
`
`co C)
`.,_
`
`<o
`C)
`.,_
`
`~~ .,_
`
`....._<Q ,_
`.,_
`
`~ co ,_ ,_
`
`

`

`U.S. Patent
`U.S. Patent
`
`Dec. 26, 1995
`Dec. 26, 1995
`
`Sheet 2 of 8
`Sheet 2 of 8
`
`5,479,638
`5,479,638
`
`.....
`I
`
`('f') N
`I
`I
`
`z z z
`
`AGOWSWN
`
`co
`C)
`~
`
`~()"
`
`-.::t-
`,_
`,_
`
`~
`°'
`
`('f')
`00
`
`IO
`N
`V'l
`
`..-4
`
`C)
`,_
`,_
`
`!
`
`00
`N
`t-
`
`IO
`N
`Ir)
`
`.....
`
`.....
`
`\
`
`-.::t-
`C)
`,_
`
`(\J
`
`-~
`l(
`
`co C)
`,_
`
`(0
`C)
`,_
`
`~~ -
`
`~(() ,._
`,._
`
`~
`co
`,._
`,._
`
`

`

`U.S. Patent
`
`Dec. 26, 1995
`
`Sheet 3 of 8
`
`5,479,638
`
`COMMERCIAL
`APPLICATIONS -•--152
`SOFTWARE
`
`USER
`DATA
`
`154
`
`FREE
`
`SPACE
`
`- - - 1 5 6
`
`150
`
`Fig. 3
`
`

`

`U.S. Patent
`
`Dec. 26, 1995
`
`Sheet 4 of 8
`
`5,479,638
`
`L -
`
`122
`
`LATCH
`
`120
`
`R
`
`Fig. 4
`
`104
`
`

`

`U.S. Patent
`
`Dec. 26, 1995
`
`Sheet 5 of 8
`
`5,479,638
`
`200
`RECEIVE WRITE INSTRUCTION
`TO PROGRAM MASS STORAGE
`
`204
`....,___.i ERASE FLAGS AND DATA FOR
`AIL BLOCKS HAVING A SET
`OLD/NEW FLAG
`
`YES
`
`206
`SET USED/FREE FLAG AND
`PROGRAM DATA FILE
`
`NO
`
`YES
`
`210
`SET OLD/NEW FLAG ON
`SUPERCEDED BLOCK
`
`212
`UPDATE MAP TO CORRELATE
`LOGICAL ADDRESS TO PHYSICAL
`ADDRESS
`
`Fig. 5
`
`

`

`U.S. Patent
`
`Dec. 26, 1995
`
`Sheet 6 of 8
`
`5,479,638
`
`ERASE INHIBIT
`STATUS BIT
`
`ERASE COUNT
`
`FLASH MEMORY DEVICE
`
`N-1 Count
`
`N-1 Count
`.
`.
`.
`.
`.
`.
`.
`.
`•
`•
`.
`•
`.
`•
`.
`.
`•
`.
`.
`.
`.
`.
`. . . . .
`. . . .
`. . .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`•
`.
`.
`.
`.
`.
`.
`•
`.
`N-1 Count
`
`BlockO
`
`Block 1
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`Block (M-1)
`
`Block(M)
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`Block (N-1)
`
`~200
`
`Fig. 6
`
`

`

`00
`~
`~
`,...
`\,C
`-...;-a
`.a;.
`,...
`Ul
`
`00
`
`e,
`.......
`~
`f
`
`r:r.,_
`
`tit
`1.0
`1.0
`lo-'
`J''
`N
`~
`~
`~
`
`~ = '""""
`
`~
`•
`00
`0 •
`
`►I MOVE USED BLOCK WITH LEAST COUNT VALUE
`
`TO FREE BLOCK WITH ITS
`
`COUNT=COUNT(MAX) THEN SET THE ERASE
`
`INIDBIT BIT FOR DESTINATION BLOCK
`
`244
`
`YES
`
`>
`
`NO
`
`14----------------+ SET OLD/NEW FLAGFOR SOUCE BLOCK
`
`Fig. 7
`
`FLAGS OF ALL BLOCKS
`COUNT AND ERASE INHIBIT
`OLD/NEW FLAG AND ERASE
`
`ERASE ALL BLOCKS HA VINO SET
`
`238
`
`OLD/NEW FLAG SET AND ERASE
`
`(ERASE ALL BLOCKS HAVING
`EXECUTE ERASE PROCEDURE
`
`INHIBIT FLAG UNSET
`
`240
`
`YES
`
`FILE
`
`STORE DATA
`CONTINUE
`
`234
`
`YES
`
`NO
`
`START
`230
`
`

`

`U.S. Patent
`
`Dec. 26, 1995
`
`Sheet 8 of 8
`
`5,479,638
`
`270
`RECEIVE INSTRUCTION TO
`READ MASS STORAGE
`
`271
`RECEIVE LOGICAL ADDRESS
`
`272
`CONCAIBNATE SET USED/FREE BIT AND
`UNSET NEW/OLD BIT UNSET DEFECT BIT
`
`YES
`
`274
`SEND MATCH-NOT-FOUND
`SIGNAL
`
`275
`READ DATA FILE FROM THE
`PHYSICAL FILE ASSOCIATED WITH
`MATCHED LOGICAL ADDRESS
`
`Fig. 8
`
`

`

`5,479,638
`
`1
`FLASH MEMORY MASS 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
`
`5
`
`10
`
`2
`memory condition. Unlike a hard disk device, in a flash
`memory device an erase cycle is slow which can signifi(cid:173)
`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, there is 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(cid:173)
`write cycles is costly in terms of system performance.
`Secondly, hard disk users typically store both information
`which is rarely changed and information which is frequently
`changed. For example, a commercial spread sheet or word
`15 processing software programs stored on a user's system are
`rarely, if ever, changed. However, the spread sheet data files
`or word processing documents are frequently changed.
`Thus, different sectors of a hard disk typically have dra(cid:173)
`matically different usage in terms of the number of times the
`information stored thereon is changed. While this disparity
`20 has no impact on a hard disk because of its 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 other sections of the mass
`storage.
`
`SUMMARY 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 of the rotation of the
`disk, there is an inherent latency in extracting information
`from a hard disk drive.
`Other problems are especially dramatic in portable com(cid:173)
`puters. In particular, hard disks are unable to withstand many
`of the kinds of physical shock that a portable computer will
`likely sustain. Further, the motor for rotating the disk
`consumes significant amounts of power decreasing the bat(cid:173)
`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- 25
`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 alterable. The inventors have
`determined that flash memory is preferred for such a
`replacement. It should be noted that E2 PROM is also 30
`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 35
`through tlle dielectric surrounding a floating gate electrode.
`Because of this, such types of memory have a finite number
`of erase-write cycles. Eventually, the dielectric will fail.
`Manufacturers of flash cell devices specify the limit for the
`number erase-write cycles as between 10,000 and 100,000. 40
`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 and the user. In other words, the designer of
`a computer incorporating such a semiconductor mass stor(cid:173)
`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.
`As in 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 65
`and appropriately changed, the flash block is fully pro(cid:173)
`grammed, then erased and then reprogrammed to the new
`
`45
`
`The present invention discloses two primary algoritllms
`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 software, a user program, word processing
`software document, spread sheet file and the like. The first
`algorithm provides means for avoiding an erase-before(cid:173)
`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 algoritllm prevents any
`portion of the mass storage from being erased a substantially
`larger number of 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 tlle 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 impact to 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
`50 each bit in the block to be erased, and then erasing all the bits
`in the block.)
`According to the first algorithm, erase cycles are avoided
`by programming an altered data file into an empty mass
`storage block rather than over itself 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(cid:173)
`ware available in conventional computer systems are not
`configured to track continually changing physical locations
`60 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.
`
`55
`
`

`

`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 number of times each block is erased. A program(cid:173)
`mable maximum value for the counter is also provided. As
`the number of erase cycles for a block becomes one less than
`the maximum, the block is erased one last time and written
`with another file having a then smallest number of 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 number of times more than
`any other block.
`These advantages are achieved through the use of 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 number of times a block
`has been erased and written and an erase inhibit flag.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`10
`
`15
`
`4
`As described above in the Background of 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
`5 changed it is stored into a new physical location in the mass
`storage. Thus, implementation of the architecture of the
`present invention requires a mapping of the logical address
`308, i.e., the address where the computer system believes the
`data file fa 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 to store 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,
`E2PROM or even ROM. If ROM is selected for the physical
`20 address 408 array of the map 108, a defect in the ROM will
`prevent the block corresponding to that physical address 408
`from ever being addressed. Accordingly, a changeable non(cid:173)
`volatile memory is preferred. Note that any replacement
`circuit for the CAM should be nonvolatile. Otherwise, loss
`25 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 computer to save the
`document. The document will be stored in the mass storage
`system as shown in FIG. 1. The computer system will assign
`it a logical address 308, for example 526H. The mass storage
`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. As the 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
`40 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 instructs the computer to store the docu(cid:173)
`ment. To avoid an erase-before-write cycle, the system of the
`present invention provides means for locating a block hav(cid:173)
`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. At that time a multi-sector erase
`is necessary and those blocks in the memory 100 and their
`associated CAM 106 entries 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
`
`FIG. 1 shows an architecture for a semiconductor mass
`storage of the present invention.
`FIG. 2 shows the 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 shows a simplified block diagram of the old/new
`flag system integrally formed with the memory of the 30
`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.
`
`35
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`FIG. 1 shows an architecture for a semiconductor mass 45
`storage according to the present invention. In the preferred
`embodiment, all of the memory storage is flash EEPROM.
`It is possible to substitute E2PROM for some or all of the
`data bits shown. A memory storage 100 is arranged into N
`blocks of data from zero through N-1. Each of the blocks of 50
`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 55
`storage device might include 100 MByte of addressable
`storage.
`A non-volatile content addressable memory (CAM) 106 is
`associated with the memory storage 100. In the preferred
`embodiment, the CAM 106 is formed of flash memory. The 60
`CAM 106 can also be E2PROM. There is one entry in the
`CAM 106 for every one of the N blocks in the mass storage
`100. Each entry includes a number of fields which will be
`described below. The CAM 106 is also formed of a non(cid:173)
`volatile memory because loss of its information would make 65
`retrieval of the data files stored in the mass storage 100
`impossible.
`
`

`

`5,479,638
`
`5
`
`20
`
`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(cid:173)
`mentations because those embodiments utilize an erase(cid:173)
`before-write cycle rather than retaining superseded versions
`of data files. In such circuits a latch of volatile logic circuits
`is set to couple the voltage necessary to erase the flash cells
`in the block. Because of the likely large number of memory
`blocks in the mass storage 100, if the CAM 106 and mass
`storage 100 are on the same integrated circuit (chip) cou(cid:173)
`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 expensive in terms of system performance. 15
`If the CAM 106 and the mass storage 100 are on separate
`chips, it is doubtful that either device could have sufficient
`1/0 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 problems it is preferable that no updat(cid:173)
`ing of the latches be performed prior to an erase of all blocks
`having a set old/new flag 116. To avoid this step, a plurality
`of old/new flag systems 104 are intimately associated with
`each block in the memory 102 and is programmed by the 25
`same sequence of instructions as the old/new flag 116 of the
`CAM 106.
`FIG. 4 shows a simplified block diagram of the old/new
`flag system 104 which includes a 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 time of an erase,
`the data in each of the bits 120 is simultaneously coupled to
`each appropriate ones of the latches 122 under control 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 having its associated bit 120 set then couples the
`voltage necessary to perform an erase of that block and its
`associated bit 120. After the erase is complete and verified,
`all the latches 122 are individually reset to a predetermined 40
`state under control of a reset signal coupled to each latch 122
`over a reset line R.
`For certain applications of the present invention, espe(cid:173)
`cially for low Dower portable computers, a simultaneous 45
`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 shows algorithm 1 according to the present inven(cid:173)
`tion. When the system of the present invention receives an
`instruction to program data into the mass storage (step 200),
`then the system attempts to locate a free block (step 202),
`i.e., a block having an unset (not programmed) used/free
`flag. If successful, the system sets the used/free flag for that
`block and programs the 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/new flag (step 204) and then searches for a block having
`an unset used/free flag (step 202). Such a block has just been
`formed by step 204. The system then sets the used/free flag
`for that block and programs the data file into that block (step
`206).
`
`6
`If the data file is a modified version of a previously
`existing file, the system must prevent the superseded version
`from being accessed. The system determines whether the
`data file supersedes a previous data file (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
`superseded block. Lastly, the map for correlating the logical
`10 address 308 to the physical address 408 is updated (step
`212).
`By following 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 embodiment of the present invention, the
`programming of the flash 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(cid:173)
`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-
`30 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
`35 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.
`By following 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(cid:173)
`tion 152 of the memory 150. Accordingly, the mass storage
`150 will wear out more quickly in the user data 154 and the
`50 free space 156 sections of the memory requiring earlier
`replacement than in sections 152 of the mass storage having
`data files which are rarely changed. As the number of free
`blocks diminishes providing a smaller number of blocks
`through which to recycle data files, the remaining blocks
`55 become erased more frequently exacerbating the problem.
`A second algorithm is provided for leveling erase cycles
`amongst all the blocks within the entire mass storage device
`as shown in FIG. 6. A counter is provided for each block to
`count the number of times each block has been erased and
`60 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
`65 eventually all of the blocks in the user data 154 and the free
`space 156 portions of the mass storage 150 will reach the
`maximum count and have their respective erase inhiJ;>it flags
`
`

`

`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(cid:173)
`ing all sections of the mass storage to eventually approach
`parity of erase cycles. Like the multi-sector erase, a clean(cid:173)
`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 data file.
`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 20
`maximum erase count this process of smoothing cycles
`throughout the mass storage of itself 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 storage is full (step 232). If the mass storage is not full,
`i.e., 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 presen