Error correction in solid state drives (SSD)

Patent metadata

Field	Value
Publication number	US-9262267-B2
Application number	US-201314093936-A
Country	US
Kind code	B2
Filing date	Dec 2, 2013
Priority date	Dec 2, 2013
Publication date	Feb 16, 2016
Grant date	Feb 16, 2016

Abstract

A paging scheme for a Solid State Drive (SSD) error correction mechanism that exchanges portions of a parity component, such as a page, between SRAM and less expensive DRAM, which stores the remainder of a context of pages. A parity operation applies an XOR function to corresponding memory positions in the pages of the context. Dedicated error correction (parity) SRAM need only enough memory for portions of memory, typically a cache line of a page, upon which the parity operation (XOR) is operating. The remaining portions in the context are swapped, or paged out, by cache logic such that the entire context is iteratively processed (XORed) by the parity operation.

First claim

What is claimed is:

1. A method, comprising:
partitioning a page into a plurality of cache lines, the page based on a memory space designated for error correction; a plurality of pages defining a context;
storing corresponding cache lines of the pages of the context in a first memory area, the first memory area responsive to a parity operation for computing a parity value for the corresponding cache lines, a parity value for the context based on the plurality of pages;
applying the parity operations to the cache lines stored in the first memory area; and
iteratively replacing the cache lines in succession with other cache lines of the plurality of cache lines from a second memory area for applying the parity operation to each of the cache lines until the parity operation has been applied to all cache lines of the pages in the context, the second memory area sufficiently large for storing the entire context wherein iteratively replacing the cache lines and applying the parity operations decouples a required size of the first memory from the size of the page;
the cache lines corresponding to at least first and second pages in the context, further including a cache line for each respective page, the computed parity value contributing to a corresponding cache line in the parity value, wherein iteratively replacing the cache lines applies the parity operation to corresponding cache lines in successive pages in the context for computing a parity result for the context.

2. The method of claim 1 further comprising identifying the page, the page defining a subdivision of memory upon which parity operations are applied.

3. The method of claim 1 wherein the cache lines stored in the first memory area correspond to a cache line received by monitoring a cache channel for memory accesses; such that each of the stored cache lines include corresponding locations on respective pages for applying the parity operations.

4. The method of claim 3 wherein the cache lines represent non-contiguous sectors of the pages including the corresponding cache lines.

5. The method of claim 4 further comprising:
identifying the cache line from cache channel, the cache line defining a portion of data on the page; and
throttling the identified cache lines to evenly distribute the portions corresponding to different pages for aligning a completion time of all pages in the context.

6. The method of claim 1 further comprising:
exchanging the cache lines of the pages from the first memory area with successive cache lines of the pages stored in the second memory; and
aggregating the stored cache lines of the parity results to compute a parity result for the context.

7. The method of claim 1 further comprising identifying a context of a parity sequence, the context including memory pages aggregated for computing a parity result, the parity context defining a result from which inaccurate values can be recreated from other values in a corresponding position in the context.

8. The method of claim 7 wherein the context represents the parity result for a memory die.

9. The method of claim 1 wherein the parity operation applies an XOR function to corresponding memory positions in the pages of the context.

10. The method of claim 1 further comprising partitioning a transfer buffer memory area used for data transfer to a host for designating the first memory area as a partition of the transfer buffer memory.

11. The method of claim 1 wherein the first memory is faster than the second for receiving the results of parity operations corresponding to a subset of a page of memory.

12. The method of claim 1 wherein the cache lines define non-contiguous sectors of the pages including the corresponding portions, each cache line defining a portion of data on a page, further comprising throttling the identified cache lines to evenly distribute the portions corresponding to different pages for aligning a completion time of all pages having at least one portion in the first memory.

13. A device, comprising:
a stripe indicative of areas of memory employed for accumulating a parity result, the stripe indicative of a plurality of pages, each page in the stripe having locations corresponding to the other pages in the stripe;
a plurality of cache lines in each page, the page based on a memory space designated for error correction such that the pages in the stripe define a context;
a first memory area for storing the corresponding cache lines of the pages, the first memory area responsive to a parity operation for computing a parity value for the corresponding cache lines, a parity value for the context based a plurality of pages in the context;
a parity engine for applying the parity operations to the cache lines stored in the first memory area;
a second memory area for iteratively replacing the cache lines in succession with other cache lines of the plurality of cache lines from the second memory area for applying the parity operation to each of the cache lines until the parity operation has been applied to all cache lines of the pages in the context, the second memory area sufficiently large for storing the entire context wherein iteratively replacing the cache lines and applying the parity operations decouples a required size of the first memory from the size of the page;
the cache lines corresponding to at least first and second pages in the context, further including a cache line for each respective page, the computed parity value contributing to a corresponding cache line in the parity value, wherein iteratively replacing the cache lines applies the parity operation to corresponding cache lines in successive pages in the context for computing a parity result for the context; and
a solid state storage device (SSD), the SSD storing the data populating the context and having an interface to an attached computing device for receiving the stored data.

14. The device of claim 13 wherein each cache line is for storing memory accesses from the attached computing device.

15. The device of claim 13 further comprising cache logic for:
exchanging the cache lines of the pages from the first memory area with successive cache lines of the pages stored in the second memory; and
aggregating the parity values from the cache lines to compute a parity result for the context.

16. A computer program product having instructions encoded on a non-transitory computer readable storage medium that, when executed by a processor, perform a method for paging parity operations in a computer memory, comprising:
identifying a stripe indicative of areas of memory employed for accumulating a parity result, the stripe indicative of a plurality of pages, each page in the stripe having locations defined by cache lines and corresponding to the cache lines in other pages in the stripe;
storing corresponding cache lines of the pages in the stripe in a first memory for applying a parity operation to compute a parity result for the cache line;
alternating the storing and parity computation in succession until the parity computation has been applied to each corresponding location in the stripe, wherein alternating the storing and parity computations decouples a required size of the first memory from the size of the page;
the cache lines corresponding to at least first and second pages in the context, further including a cache line for each respective page, the computed parity value contributing to a corresponding cache line in the parity value, wherein successively alternating and storing the cache lines applies the parity operation to corresponding cache lines in success

Assignees

• Intel Corp

Inventors

• Grimsrud Knut S
• Khan Jawad B

Classifications

• G06F2211/109

  Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation · CPC title

• G06F11/1064

  in cache or content addressable memories · CPC title

• G06F11/1048

  using arrangements adapted for a specific error detection or correction feature · CPC title

• G06F11/1068

  in sector programmable memories, e.g. flash disk (G06F11/1072 takes precedence) · CPC title

• G06F11/108 Primary

  Parity data distribution in semiconductor storages, e.g. in SSD · CPC title