Read level grouping algorithms for increased flash performance

Abstract

A plurality of flash memory wordlines of a flash storage device are divided into a plurality of wordline groups based on read error counts associated with the wordlines and a plurality of read level offsets. Each wordline group is associated with one of a plurality of read level offsets determined while dividing the plurality of flash memory wordlines, and associations between the plurality of read level offsets and the plurality of wordline groups are stored for use in connection with read levels to read the flash memory wordlines of the respective wordline groups.

What is claimed is: 
     
       1. A machine-implemented method, the method comprising:
 dividing a plurality of flash memory wordlines of a flash storage device into a plurality of wordline groups based on read error counts associated with the wordlines and a plurality of read level offsets; 
 associating each wordline group with one of the plurality of read level offsets determined while dividing the plurality of flash memory wordlines; and 
 storing associations between the plurality of read level offsets and the plurality of wordline groups for use in connection with read levels to read the flash memory wordlines of the respective wordline groups. 
 
     
     
       2. The machine-implemented method of  claim 1 , wherein each of the plurality of wordline groups comprises consecutively ordered wordlines of a flash memory block. 
     
     
       3. The machine-implemented method of  claim 1 , wherein dividing the plurality of flash memory wordlines into the plurality of wordline groups comprises:
 selecting respective permutations of consecutive wordline subgroups from within a predetermined set of wordline candidate groups based on a minimum of total error counts associated with the respective permutations, the consecutive wordline subgroups each being associated with a read level offset corresponding to a minimum of error counts associated with a plurality of possible read level offsets. 
 
     
     
       4. The machine-implemented method of  claim 3 , wherein dividing the plurality of flash memory wordlines into the plurality of wordline groups comprises:
 (a) selecting first and second consecutive candidate wordline groups from the predetermined set of candidate wordline groups; 
 (b) providing a plurality of subgroup permutations for the selected first and second consecutive candidate wordline groups, each subgroup permutation comprising multiple consecutive wordline subgroups of wordlines spanning the first and second consecutive wordline groups; 
 (c) for each wordline subgroup of a respective subgroup permutation, identifying from the plurality of possible read level offsets a respective read level offset that when used with the read level to read the wordlines in the wordline subgroup generates the least number of errors for the wordline subgroup; and 
 (d) choosing one of the plurality of subgroup permutations having a lowest total error count for consecutive wordline subgroups in the subgroup permutation based on the identified read level offsets for the consecutive wordline subgroups, wherein the plurality of wordline groups are based at least in part on one or more read level offsets corresponding to the selected one of the plurality of subgroup permutations. 
 
     
     
       5. The machine-implemented method of  claim 4 , wherein dividing the plurality of flash memory wordlines into the plurality of wordline groups further comprises:
 (e) storing an association between a first of the consecutive wordline subgroups in the chosen subgroup permutation and a corresponding identified read level offset; and 
 (f) repeating steps (a) through (e) using a second of the consecutive wordline subgroups in the chosen subgroup permutation as the first consecutive candidate wordline group and a next candidate group from the predetermined set of candidate wordline groups as the second consecutive candidate wordline group, the repeating ending when associations have been stored for all wordlines in the predetermined set of candidate wordline groups. 
 
     
     
       6. The machine-implemented method of  claim 5 , wherein dividing the plurality of flash memory wordlines into the plurality of wordline groups further comprises:
 repeating steps (a) through (f) until wordline boundaries of the consecutive wordline subgroups do not change from one iteration to a next iteration, or until an overall bit error rate measured based on identified read level offsets for the consecutive wordline subgroups does not change from one iteration to a next iteration, or a certain number of iterations is reached. 
 
     
     
       7. The machine-implemented method of  claim 3 , wherein each consecutive wordline subgroup of a respective permutation is generated based on an interleaving of consecutive wordlines within the predetermined set of candidate wordline groups. 
     
     
       8. The machine-implemented method of  claim 1 , wherein dividing the plurality of flash memory wordlines into the plurality of wordline groups comprises:
 selecting respective permutations of consecutive wordline subgroups from within a predetermined set of candidate groups based on selecting a minimum of maximum error counts associated with the respective permutations, the consecutive wordline subgroups each being associated with a read level offset corresponding to a minimum of respective error counts associated with a plurality of possible read level offsets. 
 
     
     
       9. The machine-implemented method of  claim 8 , wherein dividing the plurality of flash memory wordlines into the plurality of wordline groups comprises:
 (a) selecting first and second consecutive candidate wordline groups from the predetermined set of candidate groups; 
 (b) providing a plurality of subgroup permutations for the selected first and second consecutive candidate wordline groups, each subgroup permutation comprising multiple consecutive wordline subgroups of wordlines spanning the first and second consecutive wordline groups; 
 (c) for each consecutive wordline subgroup of a respective subgroup permutation, determining a maximum error count associated with reading wordlines in the wordline subgroup for each possible read level offset used with the read level to read the wordlines of the wordline subgroup, and selecting from the plurality of possible read level offsets a read level offset corresponding to the minimum of the determined maximum error counts for the wordline subgroup; 
 (d) for each subgroup permutation, determining a maximum error count of the error counts associated with the wordline subgroups of the subgroup permutation; and 
 (e) choosing one of the plurality of subgroup permutations having a minimum of the determined maximum error counts. 
 
     
     
       10. The machine-implemented method of  claim 9 , wherein dividing the plurality of flash memory wordlines into the plurality of wordline groups further comprises:
 (f) storing an association between a first of the consecutive wordline subgroups in the chosen subgroup permutation and a corresponding identified read level offset; and 
 (g) repeating steps (a) through (f) using a second of the consecutive wordline subgroups in the chosen subgroup permutation as the first consecutive candidate wordline group and a next candidate group from the predetermined set of candidate groups as the second consecutive candidate wordline group, the repeating ending when associations have been stored for all wordlines in the predetermined set of candidate groups. 
 
     
     
       11. The machine-implemented method of  claim 10 , wherein dividing the plurality of flash memory wordlines into the plurality of wordline groups further comprises:
 repeating steps (a) through (g) until wordline boundaries of the consecutive wordline subgroups do not change from one iteration to a next iteration, or until an overall bit error rate measured for the consecutive wordline subgroups does not change from one iteration to a next iteration, or a certain number of iterations is reached. 
 
     
     
       12. The machine-implemented method of  claim 3 , further comprising:
 generating an error count table, each error count in the table being indexed based on a respective read level offset and a respective flash memory wordline; and 
 generating a respective normalized read level offset group based on: indexing the error count table by a plurality of consecutive flash memory wordlines to identify corresponding read level offsets having a lowest error count for each consecutive flash memory wordline, and determining a group of the consecutive flash memory wordlines that when associated with a single identified offset have a minimum possible error count for the group of the consecutive flash memory wordlines. 
 
     
     
       13. The machine-implemented method of  claim 1 , wherein the read level is a voltage to read flash memory cells that are programmed to a programming level. 
     
     
       14. The machine-implemented method of  claim 2 , wherein each memory cell of the flash memory block is configured to be programmed to one of a plurality of possible programming levels, with each level capable of being determined by a respective read level, and wherein a respective plurality of wordline groups is generated and stored for each respective read level. 
     
     
       15. The machine-implemented method of  claim 1 , wherein each read level offset is a voltage bias that, when summed with a corresponding read level, reduces an amount of errors produced from a read operation performed on a group of flash memory cells. 
     
     
       16. The machine-implemented method of  claim 1 , wherein each flash memory wordline comprises flash memory cells programmed with one or more pages of data. 
     
     
       17. The machine-implemented method of  claim 1 , further comprising:
 configuring the storage device to retrieve a read level offset for a read operation based on a respective read level being used in the read operation and an address of a wordline that is a subject of the read operation being associated with a flash memory wordline group associated with the read level offset. 
 
     
     
       18. The machine-implemented method of  claim 1 , wherein the plurality of read level offsets are stored by the storage device in a lookup table. 
     
     
       19. A machine-implemented method, comprising:
 dividing a plurality of flash memory wordlines into a plurality of wordline group offset pairs, each pair comprising an offset value for a group of consecutive wordlines in a flash memory block; and 
 storing the plurality of wordline group offset pairs, including the corresponding offset values, for use in connection with a read level in reading memory cells associated with the flash memory block during operation of a storage device. 
 
     
     
       20. The machine-implemented method of  claim 19 , wherein dividing the plurality of wordlines comprises:
 selecting respective permutations of consecutive wordline subgroups from within a predetermined set of wordline candidate groups based on a minimum of total error counts associated with the respective permutations, the consecutive wordline subgroups each being associated with a read level offset corresponding to a minimum of error counts associated with a plurality of possible read level offsets. 
 
     
     
       21. The machine-implemented method of  claim 19 , wherein dividing the plurality of wordlines comprises:
 selecting respective permutations of consecutive wordline subgroups from within a predetermined set of candidate groups based on selecting a minimum of maximum error counts associated with the respective permutations, the consecutive wordline subgroups each being associated with a read level offset corresponding to a minimum of maximum error counts associated with a plurality of possible read level offsets. 
 
     
     
       22. A data storage system, comprising:
 a plurality of flash memory devices, each flash memory device comprising a plurality of flash memory blocks; and 
 a controller coupled to the plurality of flash memory devices, wherein the controller is configured to: 
 store a plurality of wordline group offset pairs for use in connection with a read level voltage in reading flash memory cells during a read operation, the wordline group offset pairs being formed from a division of a plurality of flash memory wordlines, wherein each stored pair comprises an offset value for a corresponding group of consecutive wordlines in a flash memory block. 
 
     
     
       23. The data storage system of  claim 22 , wherein each of the offset values represents a voltage bias that, when summed with a corresponding read level voltage, reduces an amount of errors produced from the read operation. 
     
     
       24. The data storage system of  claim 22 , wherein the wordline group offset pairs are stored in a lookup table.