# US 11,030,094 B2 · Apparatus and method for performing garbage collection by predicting required time > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,030,094 B2 - Document ID: US11030094B2 - Status: Granted - Kind: B2 - Application number: 16/502,964 - Filed: 2019-07-03 - Published: 2020-02-06 - Granted: 2021-06-08 - Earliest claimed: 2018-07-31 - Assignees: SK hynix Inc. - Applicants: SK hynix Inc. - Inventors: Yeong-Sik Yi; Jin-Woong Kim - Web page: https://patentgrep.com/patent/US11030094B2 ## CPC - G06F 12/0246: {in block erasable memory, e.g. flash memory} - G06F 12/0253: {Garbage collection, i.e. reclamation of unreferenced memory} - G06F 12/0891: using clearing, invalidating or resetting means - G06F 2212/1024: Latency reduction - G06F 2212/1036: Life time enhancement - G06F 2212/1044: Space efficiency improvement - G06F 2212/7203: Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks - G06F 2212/7205: Cleaning, compaction, garbage collection, erase control - G06F 2212/7208: Multiple device management, e.g. distributing data over multiple flash devices - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A memory system includes a nonvolatile memory device including a plurality of dies, each die including a plurality of planes, each plane including a plurality of blocks, each block including a plurality of pages, and further includes a plurality of page buffers, each page buffer for caching data in a unit of a page to be inputted to, and outputted from, each of the blocks; and a controller suitable for managing a plurality of super blocks according to a condition, each super block including N blocks capable of being read in parallel among the blocks, generating predicted required times for the super blocks, respectively, each of the predicted required times representing a time needed to extract valid data from the corresponding super block, and selecting a victim block for garbage collection from among the blocks based on the predicted required times. ## Claims ### Claim 1 A memory system comprising: a nonvolatile memory device including a plurality of dies, each die including a plurality of planes, each plane including a plurality of blocks, each block including a plurality of pages, and further including a plurality of page buffers, each page buffer for caching data in a unit of a page to be inputted to, and outputted from, each of the blocks; and a controller suitable for managing a plurality of super blocks according to a condition, each super block including N blocks capable of being read in parallel among the blocks, generating predicted required times for the super blocks, respectively, each of the predicted required times representing a time needed to extract valid data from the corresponding super block, and selecting a victim block for garbage collection from among the blocks based on the predicted required times, wherein N is a natural number of 2 or greater, and wherein the controller generates and manages the predicted required times during a period in which a number of free blocks among the blocks is less than or equal to a first number, and the controller does not manage the predicted required times during a period in which the number of free blocks among the blocks is greater than or equal to a second number, which is greater than the first number. ### Claim 2 (depends on 1) The memory system according to claim 1, wherein, when parallel read is enabled only for pages at a same position in respective N blocks in a first super block of the super blocks, the controller generates the predicted required time corresponding to the first super block by summing a first time and a second time, the first time calculated by multiplying a number by a predicted read time, the number representing a difference between a count of valid pages of which positions are the same among the N blocks of the first super block, and a first count representing a sum of valid page counts of the N blocks and a predicted read time, the second time representing a product of the first count and a predicted transmission time, wherein the predicted read time is a time that is predicted to be required to cache data of the first super block in the page buffers, and wherein the predicted transmission time is a time that is predicted to be required to transmit the data cached in the page buffers to the controller. ### Claim 3 (depends on 1) The memory system according to claim 1, wherein, when parallel read is enabled for pages at different positions in respective N blocks in a second super block of the super blocks the controller generates the predicted required time corresponding to the second super block by summing a third time and a fourth time, the third time calculated by multiplying a largest count among valid page counts of the N blocks by a predicted read time, the fourth time calculated by multiplying a count representing a sum of the valid page counts of the N blocks by a predicted transmission time, wherein the predicted read time is a time that is predicted to be required to cache data of the second super block in the page buffers, and wherein the predicted transmission time is a time that is predicted to be required to transmit the data cached in the page buffers to the controller. ### Claim 4 (depends on 1) The memory system according to claim 1, wherein, whenever a valid page count of a block among the blocks, changes, the controller calculates an updated predicted required time corresponding to the super block that includes the block of which the valid page count has changed. ### Claim 5 (depends on 1) The memory system according to claim 1, wherein the controller checks, at each set time, whether a block of which a valid page count has changed exists among the blocks of the super blocks, and when a block of which a valid page count has changed exists, calculates an updated predicted required time corresponding to the super block that includes the block of which the valid page count has changed. ### Claim 6 (depends on 1) The memory system according to claim 1, wherein the controller selects, as a victim block, a block including at least one valid page among the N blocks of a super block corresponding to a lowest predicted required time among the predicted required times. ### Claim 7 (depends on 1) The memory system according to claim 1, wherein, when only one superblock among the super blocks has a number of valid pages less than or equal to a set count, the controller selects N blocks of the one super block, as victim blocks, and when at least two superblocks among the super blocks each have a number of valid pages less than or equal to the set count, the controller selects, as the victim block, a block including at least one valid page among the N blocks of a super block having a lowest predicted required time among at least two predicted required times respectively corresponding to the at least two super blocks. ### Claim 8 (depends on 1) The memory system according to claim 1, wherein, when the N blocks of a super block among the super blocks are selected as victim blocks and all valid data are moved to a target block, the controller sets a predicted required time corresponding to the selected super block to a specific value. ### Claim 9 (depends on 1) The memory system according to claim 1, wherein a first die of the plurality of dies is coupled to a first channel, a second die of the plurality of dies is coupled to a second channel, planes included in the first die are coupled to a plurality of first ways which share the first channel, and planes included in the second die are coupled to a plurality of second ways which share the second channel, and wherein the controller manages a first super block including a first block which is in a first plane of the first die and a second block which is in a second plane of the first die and manages a second super block including a third block which is in a third plane of the second die and a fourth block which is in a fourth plane of the second die, according to the condition, wherein the controller manages a third super block including a first block which is in a first plane of the first die and a third block which is in a third plane of the second die and manages a fourth super block including a second block which is in a second plane of the first die and a fourth block which is in a fourth plane of the second die, according to the condition, or wherein the controller manages a fifth super block including a first block which is in a first plane of the first die, a second block which is in a second plane of the first die, a third block which is in a third plane of the second die and a fourth block which is in a fourth plane of the second die, according to the condition. ### Claim 10 A method for operating a memory system including a controller and a nonvolatile memory device including a plurality of dies, each die including a plurality of planes, each plane including a plurality of blocks, each block including a plurality of pages, and including a plurality of page buffers, each page buffer for caching data in a unit of a page to be inputted to, and outputted from, each of the blocks, the method comprising: managing a plurality of super blocks according to a set condition, each super block including N blocks capable of being read in parallel among the blocks; generating predicted required times for the super blocks, respectively, each of the predicted required times representing a time needed to extract valid data from the corresponding super block; and selecting a victim block for garbage collection from among the blocks based on the predicted required times, wherein N is a natural number of 2 or greater, and wherein the generating of the predicted required times comprises: generating and managing the predicted required times during a period in which a number of free blocks among the blocks is less than or equal to a first number; and not managing the predicted required times during a period in which the number of free blocks among the blocks is greater than or equal to a second number, which is greater than the first number. ### Claim 11 (depends on 10) The method according to claim 10, wherein, when parallel read is enabled only for pages at a same position in respective N blocks in a first super block among the super blocks, the generating of the predicted required times comprises: calculating a first time by multiplying a number by a predicted read time, the number representing a difference between a count of valid pages of which positions are the same among the N blocks of the first super block and a first count representing a sum of valid page counts of the N blocks of the first super block and a predicted read time; calculating a second time by multiplying the first count by a predicted transmission time; generating the predicted required time for each super block by summing the first time and the second time for that super block, wherein the predicted read time is a time that is predicted to be required to cache data of the first super block in the page buffers, and the predicted transmission time is a time that is predicted to be required to transmit the data cached in the page buffers to the controller. ### Claim 12 (depends on 10) The method according to claim 10, wherein, when parallel read is enabled for pages at different positions in respective N blocks in a second super block among the super blocks, the generating of the predicted required times comprises: calculating a third time by multiplying a largest count among valid page counts of the N blocks in the second super block by a predicted read time; calculating a fourth time by multiplying a count obtained by summing the valid page counts of the N blocks in the second super block by a predicted transmission time; generating the predicted required time corresponding to the second super block by summing the third time and the fourth time, wherein the predicted read time is a time that is predicted to be required to cache data of the second super block in the page buffers, and the predicted transmission time is a time that is predicted to be required to transmit the data cached in the page buffers to the controller. ### Claim 13 (depends on 10) The method according to claim 10, further comprising: calculating, whenever a valid page count of a block among the blocks, changes, an updated predicted required time corresponding to the super block that includes the block of which the valid page count has changed. ### Claim 14 (depends on 10) The method according to claim 10, further comprising: checking, at each set time, whether a block of which a valid page count has changed exists among the blocks, and when a block of which a valid page count has changed exists, calculating an updated predicted required time corresponding to the super block that includes the block of which the valid page count has changed. ### Claim 15 (depends on 10) The method according to claim 10, wherein the selecting of the victim block comprises selecting, as a victim block, a block including at least one valid page among N blocks of a super block corresponding to a lowest predicted required time among the predicted required times. ### Claim 16 (depends on 10) The method according to claim 10, wherein the selecting of the victim block comprises: selecting, when only one super block has a number of valid pages less than or equal to a set count, N blocks of the one super block, as victim blocks; and selecting, when at least two super blocks each have a number of valid pages less than or equal to the set count, as the victim block, a block including at least one valid page among N blocks of a super block a lowest predicted required time among at least two predicted required times respectively corresponding to the at least two super blocks. ### Claim 17 (depends on 10) The method according to claim 10, further comprising: setting, when N number of blocks of a super block among the super blocks are selected as victim blocks and all valid data are moved to a target block, a predicted required time corresponding to the selected super block to a specific value. ### Claim 18 (depends on 10) The method according to claim 10, wherein a first die of the plurality of dies is coupled to a first channel, a second die of the plurality of dies is coupled to a second channel, planes included in the first die are coupled to a plurality of first ways which share the first channel, and planes included in the second die are coupled to a plurality of second ways which share the second channel, and wherein the set condition includes managing a super block including a first block which is in a first plane of the first die and a second block which is in a second plane of the first die and managing a super block including a third block which is in a third plane of the second die and a fourth block which is in a fourth plane of the second die, wherein the set condition includes managing a super block including a first block which is in a first plane of the first die and a third block which is in a third plane of the second die and managing a super block including a second block which is in a second plane of the first die and a fourth block which is in a fourth plane of the second die, or wherein the set condition includes managing a super block including a first block which is in a first plane of the first die, a second block which is in a second plane of the first die, a third block which is in a third plane of the second die and a fourth block which is in a fourth plane of the second die.