Abstract:
A method for increasing performance of a recycle operation in a solid state drive, comprising the steps of (A) creating an empty physical-to-logical address map in a memory having a plurality of entry locations, (B) filling one of the plurality of entry locations with a physical page address associated with each data write operation to a block, where the block has a plurality of pages, (C) writing the physical-to-logical address map to a last of the plurality of pages during a write to a second to last page of the block and (D) initiating a recycle operation of the block by reading the address map to determine whether the pages contain valid data.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates to memory devices generally and, more particularly, to a method and/or apparatus for implementing a physical-to-logical address map to speed up a recycle operation in a solid state drive. 
       BACKGROUND OF THE INVENTION 
       [0002]    A conventional solid state drive (SSD) operates differently than a hard disk drive (HDD). In a HDD, each logical block address (LBA) that a host wants to write has a fixed physical address space for the write operation. In an SSD, there is not an LBA limitation. In a conventional NAND flash, data is written in pages. If one page has been written with data, a new data needs to be written to the page. An erase operation needs to be performed on the block containing the page. After the erase, new data can be written on the page. If the data in some of the pages of the block is no longer needed (also called stale pages), only the pages with valid data in that block are read and re-written into another previously erased empty block. Then the free pages left by not moving the stale data are available for new data. This is called Garbage collection. In a conventional system, Garbage collection needs to be searched from all of the pages of one block, which is time consuming. 
         [0003]    It would be desirable to implement a physical-to-logical address map to speed up a recycle operation in SSD. 
       SUMMARY OF THE INVENTION 
       [0004]    The present invention concerns a method for increasing performance of a recycle operation in a solid state drive, comprising the steps of (A) creating an empty physical-to-logical address map in a memory having a plurality of entry locations, (B) filling one of the plurality of entry locations with a physical page address associated with each data write operation to a block, where the block has a plurality of pages, (C) writing the physical-to-logical address map to a last of the plurality of pages during a write to a second to last page of the block and (D) initiating a recycle operation of the block by reading the address map to determine whether the pages contain valid data. 
         [0005]    The features and advantages of the present invention include providing physical-to-logical address map that may (i) speed up recycle in an SSD, (ii) determine whether a mapped block contains garbage data, and/or (iii) be easy to implement. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0006]    These and other features and advantages of the present invention will be apparent from the following detailed description and the appended claims and drawings in which: 
           [0007]      FIG. 1  is a block diagram of an embodiment of the invention; 
           [0008]      FIG. 2  is a diagram illustrating an example write operation; 
           [0009]      FIG. 3  is a diagram of a flash memory structure; 
           [0010]      FIG. 4  is a flow diagram of a recycle operation; 
           [0011]      FIG. 5  is a diagram illustrating an example of a physical-to-logical address map; and 
           [0012]      FIG. 6  is a diagram of a process implementing a recycle operation. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0013]    An embodiment of the invention concerns a method to map physical-to-logical addresses to speed up recycle operations in a solid state drive (SSD). The physical-to-logical address comprises a table of data that writes to a NAND flash portion of the SSD. In one example, when the SSD starts a recycle operation, the firmware in the SSD will first read the map to an internal RAM, then decide which block needs to be recycled. By using physical-to-logical map, the SSD firmware accomplishes a recycle operation while only reading a few pages of the NAND flash. 
         [0014]    Referring to  FIG. 1 , a block diagram of an apparatus  80  illustrating an embodiment of the invention is shown. In one example, the apparatus  80  may be implemented as a device, such as a mobile computing device, having a nonvolatile memory circuit. However, other types of devices may be implemented to meet the design criteria of a particular implementation. The apparatus  80  generally comprises a block (or circuit)  82 , a block (or circuit)  84  and a block (or circuit)  86 . The circuit  84  may include a block (or circuit)  100 . The block  84  is shown as a controller. The block  100  may be implemented as a memory. The memory  100  may store firmware  102 , or other software, used to control the circuit  84 . The firmware  102  may operate the controller and include the recycle operations described. The memory  10  may hold the physical-to-logical map. 
         [0015]    A signal (e.g., REQ) may be generated by the circuit  82 . The signal REQ may be received by the circuit  84 . The signal REQ may be a request signal that may be used to access data from the circuit  86 . A signal (e.g., I/O) may be generated by the circuit  84  to be presented to the circuit  86 . The signal REQ may include one or more address bits. A signal (e.g., DATA) may be one or more data portions received by the circuit  82 . 
         [0016]    The circuit  82  is shown implemented as a host circuit. The circuit  82  reads and writes data to and from the circuit  86 . The circuit  86  is generally implemented as a nonvolatile memory circuit such as a NAND flash. However, other types of memory may be implemented to meet the design criteria of a particular implementation. The circuit  206  may include a number of modules  90   a - 90   n . The modules  90   a - 90   n  may be implemented as NAND flash chips. In some embodiments, the circuit  86  may be a NAND flash device. In other embodiments, the circuit  84  and/or the circuit  86  may be implemented as all or a portion of a solid state drive having one or more nonvolatile devices. The circuit  86  is generally operational to store data in a nonvolatile condition. When data is read from the circuit  86 , the circuit  82  may access a set of data (e.g., multiple bits) identified in the signal REQ. In one example, modules  90   a - 90   n  may be prefabricated modules hardwired to a printed circuit board (PCB). In another example, the modules  90   a - 90   n  may be removable modules that may be used to increase or decrease the total size of the circuit  86 . In one embodiment, the circuit  86  may include both removable and/or non-removable modules  90   a - 90   n . Additionally, each of the modules  90   a - 90   n  may include a number of individual memory elements  92   a - 92   n.    
         [0017]    Referring to  FIG. 2 , an example write operation is shown. In the example shown, writing an LPA  0  to page 0 is shown as a “1”. A write of an LPA  4  and  10  to page 1 and 2 is also shown. If the host  82  requests another write to LPA  0 , the controller  82  needs to write to other pages, for example, to page 3, shown as “2”. In such an example, the LPA  0  is stored in page 3. The next time the host  82  reads LPA  0 , the firmware  102  should read from page 3, not page 0. In this case, LPA data contained in page 0 is called garbage, because the newest data is stored in page 3. After the host  82  implements many data write operations to the media  86 , many of the LPA will be rewritten, each time to a different location. The firmware  102  keeps track of the newest location, and then the controller  84  contains a “System MAP” to record this reflection, as “3” shows. 
         [0018]    Referring to  FIG. 3 , a diagram of an organization of the memory  86  is shown. Data is written to the memory  86  in units called pages (made up of multiple cells). The memory  86  is erased in larger units called blocks (made up of multiple pages). If the data in some of the pages of the block are no longer needed (also called stale pages), only the pages with valid data in that block are read and re-written into another previously erased empty block. The free pages left by not moving the stale data are then available for storing new data. In the example shown, four pages (A-D) are written to a block (X). Individual pages may be written at any time if they are currently free (erased). Four new pages (E-H) and four replacement pages (A′-D′) are written to the block (X). The original A-D pages are now invalid (stale) data, but cannot be overwritten until the block is cleared. In order to write new data to the pages with stale data (e.g., (A-D)), all of the valid pages (e.g., E-H and A′-D′) are read and written to a new block (e.g., Y), then the old block (e.g., X) is erased. This last step is garbage collection. 
         [0019]    The firmware  102  presents a physical-to-logical address map to speed up the recycle process. The recycle process includes writing the physical-to-logical address map of each block. In one example, the physical-to-logical address map contains all information to determine whether the block contains garbage data. The physical-to-logical address map is a special table that contains “physical address” to “logical page address” mapping. The following TABLE 1 illustrates such an example: 
         [0000]    
       
         
               
               
               
             
           
               
                   
                 TABLE 1 
               
               
                   
                   
               
               
                   
                 Physical Address 
                 Logical Address 
               
               
                   
                   
               
             
             
               
                   
                 Page 0 
                 LPA 30 
               
               
                   
                 Page 1 
                 LPA 18 
               
               
                   
                 Page 2 
                 LPA 22 
               
               
                   
                 Page 3 
                 LPA 7 
               
               
                   
                 Page 4 
                 LPA 9 
               
               
                   
                 Page 5 
                 LPA 21 
               
               
                   
                 Page 6 
                 LPA 22 
               
               
                   
                 . . . 
                 . . . 
               
               
                   
                   
               
             
          
         
       
     
         [0020]    In the example shown, each block contains a physical-to-logical address map. The maps record all the LPAs of all pages (e.g., one block contains 256 pages). The last page will contain a physical-to-logical address map. In one example, the map will have 255 entries, according to 255 pages in this block, with each entry containing an LPA of that page. However, the particular number of entries may be varied (e.g., increased or decreased) to meet the design criteria of a particular implementation. 
         [0021]    Referring to  FIG. 4 , a method  200  is shown. The method  200  may be used to create the physical-to-logical address map of TABLE 1. The method  200  generally comprises a step (or state)  202 , a step (or state)  204 , a step (or state)  206 , a step (or state)  208 , and a step (or state)  210 . The step  202  may allocate an empty physical-to-logical address map in memory. The step  204  may write host data to the memory  86 . The step  206  may write host data to one page of the block X and add an entry to the physical-to-logical address map to record the LPA that writes to this page. The step  208  determines whether the controller  84  needs to write to the second to last page of the block. The step  210  writes a physical-to-logical address map from a memory. 
         [0022]    When data is written to one block, an empty physical-to-logical address map is created in the memory  100 . When data is written to one page of the block, one entry is added in physical-to-logical address map with the physical page address written and the logical page address of the data stored. When writing to the second to the last page of the block, the whole physical-to-logical address map table is written to last page of the block. 
         [0023]    Referring to  FIG. 5 , an example of a block  300  and a physical-to-logical address map table  302  is shown. In the example shown, the block  300  may contain 9 pages. However, the particular number of pages may be varied to meet the design criteria of a particular implementation. When a write is initiated by the host  80 , data is only written to the first 8 pages. The last page (e.g., page 9) does not write user data, but rather writes all the table  302  with logical address of user data that had been written to the previous pages (e.g., the previous 8 pages). The last page of the block (e.g., page 9) then becomes a physical-to-logical address map page. For example, the page contains all the physical address of the block  300  and the logical address of corresponding user data. 
         [0024]    Referring to  FIG. 6 , a flow diagram of a process for using the physical-to-logical address map  302  to implement a recycle operation is shown. To recycle one block (e.g., the block  300 ), all of the pages of the recycled block  300  do not need to be read. The last page of the block X (e.g.,  300 ) would be read. All of the logical address information of the pages in the recycled block are retrieved from the table  302 . The logical address information in the map  302  is used to look up the physical page address to decide whether the page contains the latest data. All of the valid pages are read. The data in the valid pages is then moved to another block. After the move operation, there is no valid data left in the block that intends to be recycled. The block X is erased, then put into a pool of free blocks for subsequent use. 
         [0025]    In general, with the process  400 , only one page needs to be read. All the logical addresses of data in the recycled block are made available, which saves time. In the example of a typical 25 nm process NAND, one page is typically 8 KB, and one block contains 256 pages. The maximum time to read a page is 75 us. To transfer 8 KB of data out needs around 40 us. Typically, reading one page of data and transferring data out needs 100 us. In a common recycle example, the first step involves reading 255 pages out, which may need 255*100 us=25 ms. With the controller  84 , only one page needs to be read out to recycle the whole block, which takes around 100 us. The controller  84  saves around 99.6% compared with conventional approaches. 
         [0026]    The terms “may” and “generally” when used herein in conjunction with “is(are)” and verbs are meant to communicate the intention that the description is exemplary and believed to be broad enough to encompass both the specific examples presented in the disclosure as well as alternative examples that could be derived based on the disclosure. The terms “may” and “generally” as used herein should not be construed to necessarily imply the desirability or possibility of omitting a corresponding element. 
         [0027]    While the invention has been particularly shown and described with reference to the preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made without departing from the scope of the invention.