KR102750797B1 - Apparatus and method for performing garbage collection to predicting required time - Google Patents

Abstract

The present technology relates to a memory system supporting garbage collection and an operating method of the memory system, comprising: a nonvolatile memory device including a plurality of pages each including a plurality of memory cells, a plurality of blocks each including the pages, a plurality of planes each including the blocks, and a plurality of dies each including the planes, and including page buffers for catching data input/output to/from the blocks in units of pages; and a controller which groups N blocks capable of parallel reading among the blocks according to set conditions and manages them as a plurality of super blocks, and generates estimated times calculated by predicting the time required to extract valid data from the blocks for garbage collection in units of super blocks, and selects a victim block for garbage collection among the blocks with reference to the estimated times required.

Description

{APPARATUS AND METHOD FOR PERFORMING GARBAGE COLLECTION TO PREDICTING REQUIRED TIME}

The present invention relates to a memory system, and more particularly, to a memory system supporting garbage collection and an operating method of the memory system.

Recently, the paradigm of the computer environment is shifting to ubiquitous computing, which allows the use of computer systems anytime and anywhere. This has led to a rapid increase in the use of portable electronic devices such as mobile phones, digital cameras, and laptop computers. Such portable electronic devices generally use memory systems that utilize memory devices, or in other words, data storage devices. Data storage devices are used as main or auxiliary memory devices of portable electronic devices.

Data storage devices using nonvolatile memory devices have the advantages of excellent stability and durability because they do not have mechanical drive parts, unlike hard disks, and also have very fast information access speeds and low power consumption. Examples of memory systems with these advantages include data storage devices such as USB (Universal Serial Bus) memory devices, memory cards with various interfaces, and solid state drives (SSDs).

An embodiment of the present invention provides a memory system and an operating method of the memory system capable of predicting the time required to extract valid data from a block for garbage collection by superblock unit and then selecting a victim block for garbage collection based on the predicted time required.

A memory system according to an embodiment of the present invention comprises: a nonvolatile memory device including a plurality of pages, each including a plurality of memory cells; a plurality of blocks, each including the pages; a plurality of planes, each including the blocks; and a plurality of dies, each including the planes; and page buffers for catching data output from the blocks in units of pages; and a controller for grouping N blocks capable of parallel reading among the blocks according to set conditions and managing them as a plurality of super blocks, and generating estimated times calculated by predicting the time required to extract valid data from the blocks for garbage collection in units of super blocks, and selecting a victim block for the garbage collection among the blocks with reference to the estimated times required, wherein N can be a natural number greater than or equal to 2.

In addition, the controller calculates a first time obtained by multiplying a read prediction time by a first number obtained by subtracting the number of valid pages in the same position from a first number obtained by adding the numbers of valid pages in each of the N blocks grouped in the first superblock, and a second time obtained by multiplying a transmission prediction time by the first number, and then adding the first time and the second time to generate a required prediction time corresponding to the first superblock, and applies the required prediction time generation method applied to the first superblock to each of the superblocks to generate the required predicted times, and the read prediction time may be a time predicted to be taken to cache data of the blocks in the page buffers, and the transmission prediction time may be a time predicted to be taken to transmit data cached in the page buffers to the controller.

In addition, the controller calculates a third time obtained by multiplying the read prediction time by the largest number of valid pages of each of the N blocks grouped in the second superblock among the superblocks, and a fourth time obtained by multiplying the transmission prediction time by the sum of the valid pages of each of the N blocks, if parallel reading is possible for pages at different locations in each of the N blocks grouped in the second superblock, and then adds the third time and the fourth time to generate a required prediction time corresponding to the second superblock, and applies the required prediction time generation method applied to the second superblock to each of the superblocks to generate the required predicted times, and the read prediction time may be a time predicted to be taken to cache data of the blocks in the page buffers, and the transmission prediction time may be a time predicted to be taken to transmit data cached in the page buffers to the controller.

In addition, the controller can re-predict the value of the required prediction time corresponding to the superblock in which the blocks with the variable number of valid pages are grouped whenever a block with a variable number of valid pages occurs among the blocks.

In addition, the controller can check whether there is a block among the blocks with a variable number of valid pages at each set time, and if the check result shows that there is a block, the value of the required predicted time corresponding to the superblock in which the block with a variable number of valid pages is grouped can be re-predicted.

Additionally, the controller may select, as the victim block, a block including at least one valid page among N blocks grouped in a superblock corresponding to a relatively smallest predicted time among the predicted times required.

In addition, the controller may select, as the victim block, N blocks grouped in the selected one superblock, if there is one superblock in which the sum of the numbers of valid pages of each of N blocks grouped in each of the superblocks is less than or equal to a set number, and, if there are at least two or more, select, as the victim block, a block including at least one valid page among N blocks grouped in a superblock corresponding to a relatively smallest value among the values of required predicted times corresponding to at least two or more superblocks.

In addition, the controller may set the expected time corresponding to the third superblock to a target value when N blocks grouped in a third superblock among the superblocks are selected as the sacrifice blocks and all valid data is moved to the target block through the garbage collection.

In addition, the controller may generate and manage the required predicted times in a section where the number of free blocks among the blocks is equal to or less than a first number, and may not manage the required predicted times in a section where the number is equal to or greater than a second number that is greater than the first number.

In addition, a first die among the dies is connected to a first channel, a second die among the dies is connected to a second channel, planes included in the first die are connected to a plurality of first ways sharing the first channel, planes included in the second die are connected to a plurality of second ways sharing the second channel, and the controller includes in the set condition grouping a first block included in the first plane of the first die with a second block included in the second plane of the first die, and a third block included in the third plane of the second die with a fourth block included in the fourth plane of the second die, or includes in the set condition grouping a first block included in the first plane of the first die with a third block included in the third plane of the second die, and a second block included in the second plane of the first die with a fourth block included in the fourth plane of the second die, Alternatively, the set condition may include grouping a first block included in the first plane of the first die, a second block included in the second plane of the first die, a third block included in the third plane of the second die, and a fourth block included in the fourth plane of the second die.

According to another embodiment of the present invention, a method of operating a memory system includes a nonvolatile memory device including a plurality of pages, each including a plurality of memory cells, a plurality of blocks, each including the pages, a plurality of planes, each including the blocks, and a plurality of dies, each including the planes, and page buffers for catching data output from the blocks in units of pages, the method comprising: a step of grouping N blocks capable of parallel reading among the blocks according to set conditions and managing them as a plurality of super blocks; a step of generating estimated times calculated by predicting the required times for extracting valid data from the blocks for garbage collection in units of super blocks; and a step of selecting a victim block for the garbage collection among the blocks with reference to the estimated times, wherein N can be a natural number greater than or equal to 2.

In addition, if parallel reading is possible only for pages in the same position in each of the N blocks grouped in the first superblock among the superblocks, the generation step includes: calculating a first time by multiplying a read prediction time by a first number obtained by subtracting the number of valid pages in the same position in the N blocks grouped in the first superblock from a total number of valid pages in each of the N blocks grouped in the first superblock; calculating a second time by multiplying the first number by a transmission prediction time; generating a required prediction time corresponding to the first superblock by adding the first time and the second time; and applying a required prediction time generation method applied to the first superblock to each of the superblocks to generate the required prediction times, wherein the read prediction time may be a time predicted to be taken to cache data of the blocks in the page buffers, and the transmission prediction time may be a time predicted to be taken to transmit data cached in the page buffers to the controller.

In addition, if parallel reading is possible for pages at different locations in each of the N blocks grouped in the second superblock among the superblocks, the generation step includes: calculating a third time by multiplying the read prediction time by the largest number among the valid page numbers of each of the N blocks grouped in the second superblock; calculating a fourth time by multiplying the transmission prediction time by the sum of the valid page numbers of each of the N blocks grouped in the second superblock; generating a required prediction time corresponding to the second superblock by adding the third time and the fourth time; and generating the required predicted times by applying the required predicted time generation method applied to the second superblock to each of the superblocks, wherein the read predicted time may be a time predicted to be taken to cache data of the blocks in the page buffers, and the transmission predicted time may be a time predicted to be taken to transmit data cached in the page buffers to the controller.

In addition, whenever a block with a variable number of valid pages occurs among the above blocks, the step of re-predicting the value of the required prediction time corresponding to the superblock in which the block with a variable number of valid pages is grouped may be further included.

In addition, the method may further include a step of checking whether there is a block among the blocks with a variable number of valid pages at each set time point, and, if the checking result shows that there is a block, re-predicting the value of the required predicted time corresponding to the superblock in which the block with a variable number of valid pages is grouped.

In addition, the selection step may select, as the victim block, a block including at least one valid page among N blocks grouped in a superblock corresponding to a relatively smallest predicted time among the predicted times required.

In addition, the selection step may include: a step of selecting N blocks grouped in the selected one superblock as the victim block, if there is one superblock in which the sum of the valid pages of each of N blocks grouped in each of the superblocks is less than or equal to a set number; and a step of selecting a block including at least one valid page among N blocks grouped in the superblock corresponding to a relatively smallest value among the values of required predicted times corresponding to the at least two or more superblocks, if there are at least two or more superblocks in which the sum of the valid pages of each of N blocks grouped in each of the superblocks is less than or equal to a set number, as the victim block.

In addition, if N blocks grouped in a third superblock among the above superblocks are selected as the sacrifice blocks and all valid data is moved to the target block through the garbage collection, a step of setting the expected time corresponding to the third superblock to a target value may be further included.

In addition, the generation step may include a step of generating and managing the required predicted times in a section where the number of free blocks among the blocks is a first number or less; and a step of not managing the required predicted times in a section where the number of free blocks among the blocks is a second number or greater than the first number.

In addition, a first die among the dies is connected to a first channel, a second die among the dies is connected to a second channel, planes included in the first die are connected to a plurality of first ways sharing the first channel, planes included in the second die are connected to a plurality of second ways sharing the second channel, and the set condition includes grouping a first block included in the first plane of the first die with a second block included in the second plane of the first die, and grouping a third block included in the third plane of the second die with a fourth block included in the fourth plane of the second die, or grouping a first block included in the first plane of the first die with a third block included in the third plane of the second die, and grouping a second block included in the second plane of the first die with a fourth block included in the fourth plane of the second die, or the first It may include grouping a first block included in a first plane of the die, a second block included in a second plane of the first die, a third block included in a third plane of the second die, and a fourth block included in a fourth plane of the second die.

This technology can predict the time required to extract valid data from blocks for garbage collection by superblock unit, and then select a victim block for garbage collection based on the predicted time.

This has the effect of minimizing the time it takes to perform garbage collection.

Additionally, it has the effect of minimizing the decrease in the performance of the memory system due to the performance of garbage collection.

FIG. 1 is a schematic diagram illustrating an example of a data processing system including a memory system according to an embodiment of the present invention.
FIG. 2 is a drawing illustrating a controller within a memory system according to another embodiment of the present invention.
FIG. 3 is a diagram for explaining an example of garbage collection used in a memory system according to an embodiment of the present invention.
FIG. 4 is a diagram illustrating the concept of a super memory block used in a memory system according to an embodiment of the present invention.
FIGS. 5A and 5B are diagrams illustrating garbage collection for a super memory block in a memory system according to the first embodiment of the present invention.
FIG. 6 is a diagram illustrating an operation of selecting a victim block when performing garbage collection on a super memory block in a memory system according to the first embodiment of the present invention described through FIGS. 5a and 5b.
FIGS. 7A and 7B are diagrams illustrating garbage collection for a super memory block in a memory system according to a second embodiment of the present invention.
FIG. 8 is a diagram illustrating an operation of selecting a victim block when performing garbage collection on a super memory block in a memory system according to the second embodiment of the present invention described through FIGS. 7a and 7b.

Hereinafter, preferred embodiments of the present invention will be described with reference to the attached drawings. However, the present invention is not limited to the embodiments disclosed below, but may be configured in various different forms, and the present embodiments are provided only to ensure that the disclosure of the present invention is complete and to fully inform a person having ordinary skill in the art of the scope of the present invention.

FIG. 1 is a schematic diagram illustrating an example of a data processing system including a memory system according to an embodiment of the present invention.

Referring to FIG. 1, a data processing system (100) includes a host (102) and a memory system (110).

And, the host (102) includes electronic devices, such as portable electronic devices such as mobile phones, MP3 players, laptop computers, or electronic devices such as desktop computers, game consoles, TVs, projectors, etc., i.e., wired and wireless electronic devices.

In addition, the host (102) includes at least one operating system (OS), and the operating system generally manages and controls the functions and operations of the host (102) and provides interaction between a user using the data processing system (100) or the memory system (110) and the host (102). Here, the operating system supports functions and operations corresponding to the user's usage purpose and use, and may be divided into a general operating system and a mobile operating system, for example, depending on the mobility of the host (102). In addition, the general operating system system in the operating system may be divided into a personal operating system and an enterprise operating system, depending on the user's usage environment. For example, the personal operating system is a system specialized to support a service provision function for general users, and may include Windows and Chrome, and the enterprise operating system is a system specialized to secure and support high performance, and may include Windows server, Linux, Unix, and the like. In addition, the mobile operating system in the operating system is a system specialized to support the function of providing mobility services to users and the power saving function of the system, and may include Android, iOS, Windows Mobile, etc. At this time, the host (102) may include a plurality of operating systems, and also executes the operating system to perform an operation with the memory system (110) corresponding to a user request. Here, the host (102) transmits a plurality of commands corresponding to the user request to the memory system (110), and accordingly, the memory system (110) performs operations corresponding to the commands, that is, operations corresponding to the user request.

In addition, the memory system (110) operates in response to a request from the host (102), and in particular, stores data accessed by the host (102). In other words, the memory system (110) can be used as a main memory device or an auxiliary memory device of the host (102). Here, the memory system (110) can be implemented as any one of various types of storage devices according to a host interface protocol connected to the host (102). For example, the memory system (110) may be implemented as one of various types of storage devices, such as a solid state drive (SSD), a multi media card (MMC) in the form of an MMC, an embedded MMC (eMMC), a reduced size MMC (RS-MMC), a micro-MMC, a secure digital (SD) card in the form of an SD, mini-SD, or micro-SD, a universal storage bus (USB) storage device, a universal flash storage (UFS) device, a compact flash (CF) card, a smart media card, a memory stick, and the like.

In addition, storage devices implementing the memory system (110) may be implemented as volatile memory devices such as DRAM (Dynamic Random Access Memory), SRAM (Static RAM), etc., and nonvolatile memory devices such as ROM (Read Only Memory), MROM (Mask ROM), PROM (Programmable ROM), EPROM (Erasable ROM), EEPROM (Electrically Erasable ROM), FRAM (Ferromagnetic ROM), PRAM (Phase change RAM), MRAM (Magnetic RAM), RRAM (Resistive RAM), flash memory, etc.

And, the memory system (110) includes a memory device (150) that stores data accessed by the host (102), and a controller (130) that controls data storage to the memory device (150).

Here, the controller (130) and the memory device (150) may be integrated into one semiconductor device. For example, the controller (130) and the memory device (150) may be integrated into one semiconductor device to configure an SSD. When the memory system (110) is used as an SSD, the operating speed of the host (102) connected to the memory system (110) may be further improved. In addition, the controller (130) and the memory device (150) may be integrated into one semiconductor device to configure a memory card, and for example, the controller (130) and the memory device (150) may be integrated into one semiconductor device to configure a memory card, such as a PC card (PCMCIA: Personal Computer Memory Card International Association), a compact flash card (CF), a smart media card (SM, SMC), a memory stick, a multimedia card (MMC, RS-MMC, MMCmicro), an SD card (SD, miniSD, microSD, SDHC), a universal flash memory device (UFS), etc.

In addition, as another example, the memory system (110) may be used in a computer, an Ultra Mobile PC (UMPC), a workstation, a net-book, a PDA (Personal Digital Assistants), a portable computer, a web tablet, a tablet computer, a wireless phone, a mobile phone, a smart phone, an e-book, a portable multimedia player (PMP), a portable game console, a navigation device, a black box, a digital camera, a DMB (Digital Multimedia Broadcasting) player, a 3-dimensional television, a smart television, a digital audio recorder, a digital audio player, a digital picture recorder, a digital picture player, a digital video recorder, a digital video player, a storage constituting a data center, and information in a wireless environment. It may comprise a device capable of transmitting and receiving, one of various electronic devices forming a home network, one of various electronic devices forming a computer network, one of various electronic devices forming a telematics network, an RFID (radio frequency identification) device, or one of various components forming a computing system.

Meanwhile, the memory device (150) in the memory system (110) can maintain stored data even when power is not supplied, and in particular, stores data provided from the host (102) through a write operation, and provides the stored data to the host (102) through a read operation. Here, the memory device (150) may include a plurality of memory blocks (152, 154, 156). In addition, each of the memory blocks (152, 154, 156) may include a plurality of pages (P<0>, P<1>, P<2>, P<3>, P<4>,...>). In addition, each of the pages (P<0>, P<1>, P<2>, P<3>, P<4>,...>) may include a plurality of memory cells (not shown). And, each of the memory blocks (152, 154, 156) includes page buffers (not shown) for caching input/output data in units of pages. And, the memory device (150) may include a plurality of planes (not shown) each including a plurality of memory blocks (152, 154, 156). In addition, the memory device (150) may include a plurality of memory dies (not shown) each including a plurality of planes. In addition, the memory device (150) may be a nonvolatile memory device, for example, a flash memory, and in this case, the flash memory may have a three-dimensional (3D) stack structure.

And, the controller (130) in the memory system (110) controls the memory device (150) in response to a request from the host (102). For example, the controller (130) provides data read from the memory device (150) to the host (102) and stores data provided from the host (102) in the memory device (150). To this end, the controller (130) controls operations such as read, write, program, and erase of the memory device (150).

More specifically, the controller (130) includes a host interface (HOST INTERFACE, 132), a processor (PROCESS, 134), a memory interface (MEMORY INTERFACE, 142), and a memory (MEMORY, 144).

In addition, the host interface (132) processes commands and data of the host (102), and may be configured to communicate with the host (102) through at least one of various interface protocols, such as Universal Serial Bus (USB), Multi-Media Card (MMC), Peripheral Component Interconnect-Express (PCI-E), Serial-attached SCSI (SAS), Serial Advanced Technology Attachment (SATA), Parallel Advanced Technology Attachment (PATA), Small Computer System Interface (SCSI), Enhanced Small Disk Interface (ESDI), Integrated Drive Electronics (IDE), and Mobile Industry Processor Interface (MIPI). Here, the host interface (132) may be driven through firmware called a Host Interface Layer (HIL, hereinafter referred to as 'HIL') as an area that sends and receives data with the host (102).

In addition, the memory interface (142) is a memory/storage interface that performs interfacing between the controller (130) and the memory device (150) so that the controller (130) can control the memory device (150) in response to a request from the host (102). Here, the memory interface (142) is a NAND flash controller (NFC) when the memory device (150) is a flash memory, particularly, for example, a NAND flash memory, and generates a control signal of the memory device (150) and processes data under the control of the processor (134). And, the memory interface (142) is an interface that processes commands and data between the controller (130) and the memory device (150), for example, the operation of a NAND flash interface, particularly, supports data input/output between the controller (130) and the memory device (150), and can be driven through firmware called the Flash Interface Layer (FIL, hereinafter referred to as 'FIL') as an area that exchanges data with the memory device (150).

In addition, the memory (144) stores data for driving the memory system (110) and the controller (130) as an operating memory of the memory system (110) and the controller (130). More specifically, the memory (144) stores data necessary for the controller (130) to control the memory device (150) in response to a request from the host (102). For example, the controller (130) stores data necessary when controlling operations such as read, write, program, and erase of the memory device (150) for an operation of providing data read from the memory device (150) to the host (102) and an operation of storing data provided from the host (102) in the memory device (150).

Here, the memory (144) may be implemented as a volatile memory, and may be implemented as, for example, a static random access memory (SRAM) or a dynamic random access memory (DRAM). In addition, the memory (144) may be included in the controller (130), as illustrated in FIG. 1. In addition, the memory (144) may exist outside the controller (130), differently from that illustrated in FIG. 1, and in this case, it may be implemented as an external volatile memory in which data is input/output from the controller (130) through a separate memory interface (not illustrated).

In addition, the memory (144), as described above, stores data required to perform operations such as data write and read between the host (102) and the memory device (150), and data when performing operations such as data write and read, and may include a program memory, a data memory, a write buffer/cache, a read buffer/cache, a data buffer/cache, a map buffer/cache, etc. for storing such data.

And, the processor (134) controls the overall operation of the memory system (110), and in particular, controls a program operation or a read operation for the memory device (150) in response to a write request or a read request from the host (102). Here, the processor (134) drives firmware called a flash translation layer (FTL, hereinafter referred to as 'FTL') to control the overall operation of the memory system (110). In addition, the processor (134) may be implemented as a microprocessor or a central processing unit (CPU), etc.

For example, the controller (130) performs an operation requested from the host (102) in the memory device (150) through a processor (134) implemented as a microprocessor or a central processing unit (CPU), or in other words, performs a command operation corresponding to a command received from the host (102) with the memory device (150). Here, the controller (130) may perform a foreground operation as a command operation corresponding to the command received from the host (102), for example, a program operation corresponding to a write command, a read operation corresponding to a read command, an erase operation corresponding to an erase command, a parameter set operation corresponding to a set parameter command or a set feature command as a set command, etc.

In addition, the controller (130) may perform a background operation for the memory device (150) through a processor (134) implemented as a microprocessor or a central processing unit (CPU). Here, the background operation for the memory device (150) may include an operation of copying and processing data stored in any memory block among the memory blocks (152, 154, 156) of the memory device (150) to another arbitrary memory block, for example, a garbage collection (GC) operation. In this way, since the processor (134) can control the garbage collection operation as a background operation for the memory device (150), a garbage collection control unit (196) may be included within the processor (134) as shown in the drawing. And, the background operation for the memory device (150) may include an operation for processing by swapping between memory blocks (152, 154, 156) of the memory device (150) or between data stored in the memory blocks (152, 154, 156), for example, a wear leveling (WL) operation. And, the background operation for the memory device (150) may include an operation for storing map data stored in the controller (130) into memory blocks (152, 154, 156) of the memory device (150), for example, a map flush operation. Additionally, the background operation for the memory device (150) may include a bad management operation for the memory device (150), for example, a bad block management operation for checking and processing bad blocks in a plurality of memory blocks (152, 154, 156) included in the memory device (150).

And, the processor (134) of the controller (130) may include a component (not shown) for performing bad management of the memory device (150). At this time, the component for performing bad management of the memory device (150) performs bad block management that checks for bad blocks in a plurality of memory blocks (152, 154, 156) included in the memory device (150) and then processes the checked bad blocks as bad. Here, bad management means that when the memory device (150) is a flash memory, for example, a NAND flash memory, a program fail may occur during data writing, for example, a data program, due to the characteristics of NAND, and after processing the memory block in which the program failure occurred as bad, the data in which the program failure occurred is written, i.e., programmed, to a new memory block.

FIG. 2 is a diagram illustrating a controller within a memory system according to another embodiment of the present invention.

Referring to FIG. 2, a controller (130) that interacts with a host (102) and a memory device (150) may include a host interface (132), a flash translation layer (FTL) (40), a memory interface (142), and a memory element (144).

The host interface (132) is for transmitting and receiving commands, data, etc. transmitted from the host (102). For example, the host interface (132) may include a command queue (56) that can sequentially store commands, data, etc. transmitted from the host (102) and output them according to the storage order, a buffer manager (52) that can classify commands, data, etc. transmitted from the command queue (56) or adjust the processing order, and an event queue (54) that can sequentially transmit events for processing commands, data, etc. transmitted from the buffer manager (52).

From the host (102), multiple commands and data with the same characteristics may be transmitted sequentially, or commands and data with different characteristics may be transmitted mixed together. For example, multiple commands for reading data may be transmitted, or read and program commands may be transmitted alternately. The host interface (132) first sequentially stores commands, data, etc. transmitted from the host (102) in the command queue (56). Thereafter, depending on the characteristics of the commands, data, etc. transmitted from the host (102), it is possible to predict what operation the controller (130) will perform, and based on this, the processing order or priority of the commands, data, etc. may be determined. In addition, depending on the characteristics of the commands, data, etc. transmitted from the host (102), the buffer manager (52) in the host interface (132) may determine whether to store the commands, data, etc. in the memory device (144) or transmit them to the flash translation layer (FTL) (40). The event queue (54) can receive events that the memory system or controller (130) must internally perform or process based on commands, data, etc. transmitted from the host (102) from the buffer manager (52), and then transmit them to the flash translation layer (FTL) (40) in the order in which they were received.

According to an embodiment, the flash translation layer (FTL) (40) may include a host request manager (HRM) 46 for managing events received from an event manager (54), a map data manager (MM) 44 for managing map data, a state manager (42) for performing garbage collection or wear leveling, and a block manager (48) for performing commands to blocks within a memory device.

For example, the host request manager (HRM, 46) can process read and program commands, and requests based on events received from the host interface (132) using the map data manager (MM, 44) and the block manager (48). The host request manager (HRM, 46) can process a read request by sending an inquiry request to the map data manager (MM, 44) to find out a physical address corresponding to a logical address of the transmitted request and sending a flash read request to the memory interface (142) for the physical address. Meanwhile, the host request manager (HRM, 46) can first program data into a specific page of an unrecorded (data-free) memory device by sending a program request to the block manager (48), and then update the contents of the programmed data in the mapping information of the logical-physical address by sending a map update request for the program request to the map data manager (MM, 44).

Here, the block manager (48) can manage blocks within the memory device (150) by converting program requests requested by the host request manager (HRM, 46), the map data manager (MM, 44), and the state manager (42) into program requests for the memory device (150). In order to maximize the program or write performance of the memory system (110, see FIG. 1), the block manager (48) can collect the program requests and send flash program requests for multi-plane and one-shot program operations to the memory interface (142). In addition, multiple outstanding flash program requests can be sent to the memory interface (142) in order to maximize the parallel processing of the multi-channel and multi-directional flash controller.

Meanwhile, the block manager (48) manages flash blocks according to the number of valid pages, and if a spare block is needed, it can select and erase a block without a valid page, and if garbage collection is needed, it can select a block containing the fewest valid pages. In order for the block manager (48) to have sufficient empty blocks, the state manager (42) can perform garbage collection to collect valid data and move it to empty blocks, and delete blocks containing the moved valid data. When the block manager (48) provides information about a block to be deleted to the state manager (42), the state manager (42) can first check all flash pages of the block to be deleted to check whether each page is valid. For example, in order to determine the validity of each page, the state manager (42) can identify a logical address recorded in a spare (Out Of Band, OOB) area of each page, and then compare the actual address of the page with the actual address mapped to the logical address obtained from the query request of the map manager (44). The state manager (42) sends a program request to the block manager (48) for each valid page, and when the program work is completed, the mapping table can be updated through an update of the map manager (44).

The map manager (44) manages the logical-physical mapping table and can process requests such as inquiry and update generated by the host request manager (HRM, 46) and the state manager (42). The map manager (44) can store the entire mapping table in flash memory and can also cache mapping items according to the capacity of the memory device (144). If a map cache miss occurs while processing the inquiry and update requests, the map manager (44) can transmit a read request to the memory interface (142) to load the mapping table stored in the memory device (150). If the number of dirty cache blocks of the map manager (44) exceeds a certain threshold value, a program request can be sent to the block manager (48) to create a clean cache block and store the dirty map table in the memory device (150).

Meanwhile, when garbage collection is performed, while the state manager (42) is copying a valid page, the host request manager (HRM, 46) can program the latest version of data for the same logical address of the page and issue an update request at the same time. If the state manager (42) requests a map update while the copying of the valid page is not completed normally, the map manager (44) may not perform a mapping table update. The map manager (44) can ensure accuracy by performing a map update only when the latest map table still points to the previous physical address.

According to an embodiment, at least one of the block manager (48), map manager (44) or state manager (42) described in FIG. 2 may include a garbage collection control unit (196) described in FIG. 3 below.

The memory device (150) may include a plurality of memory blocks, such as a single-level cell (SLC) memory block and a multi-level cell (MLC) memory block, depending on the number of bits that can be stored or expressed in a single memory cell. Here, the SLC memory block includes a plurality of pages implemented by memory cells that store 1-bit data in a single memory cell, and has fast data operation performance and high durability. In addition, the MLC memory block includes a plurality of pages implemented by memory cells that store multi-bit data (e.g., 2 bits or more bits) in a single memory cell, and has a larger data storage space than the SLC memory block, in other words, can be highly integrated. In particular, the memory device (150) may include, as an MLC memory block, a triple level cell (TLC) memory block including a plurality of pages implemented by memory cells capable of storing 2-bit data in one memory cell, a quadruple level cell (QLC) memory block including a plurality of pages implemented by memory cells capable of storing 4-bit data in one memory cell, or a multiple level cell memory block including a plurality of pages implemented by memory cells capable of storing 5-bit or more bit data in one memory cell.

Here, in the embodiment of the present invention, for convenience of explanation, the memory device (150) is implemented as a non-volatile memory such as a flash memory, for example, a NAND flash memory, as an example, but may be implemented as any one of memories such as a phase change random access memory (PCRAM), a resistive random access memory (RRAM (ReRAM): Resistive Random Access Memory), a ferroelectric random access memory (FRAM: Ferroelectrics Random Access Memory), and a spin transfer torque magnetic random access memory (STT-RAM (STT-MRAM): Spin Transfer Torque Magnetic Random Access Memory).

FIG. 3 is a diagram for explaining an example of garbage collection used in a memory system according to an embodiment of the present invention.

Referring to FIG. 3, garbage collection (GC) can be performed by the memory system itself without a command transmitted from the host. The controller (130) in the memory system can read user data from a plurality of data blocks (40_1) in the memory device (150), store the user data in the memory (144) arranged in the controller (130), and then program the user data in the free block (40_2) in the memory device (150). Here, the plurality of data blocks (40_1) may include blocks in which data can no longer be programmed. According to an embodiment, the memory (144) may be arranged outside the controller (130) and may be linked with the controller (130).

Specifically, the garbage collection control unit (196) included in the controller (130) can select at least one of the plurality of data blocks (40_1) in the memory device (150) as a target block. In addition, the garbage collection control unit (196) searches for and extracts valid data in the block selected as the target block, and moves the valid data to the free block (40_2). At this time, data determined to be no longer valid in at least one target block selected from the plurality of data blocks (40_1) in the memory device (150) may be discarded (i.e., may not be moved to the free block (40_2)). If valid data stored in a specific block (40_1) in the memory device (150) is moved to the free block (40_2), the controller (130) does not consider the specific block (40_1) to have valid data any longer. Afterwards, if there is a need to program new data in a specific block (40_1), all data stored in that block (40_1) can be erased (erase).

Depending on the embodiment, the controller (130) may use internal memory (144) to temporarily store valid data selected during garbage collection until it is programmed into a free block (40_2).

For garbage collection, the controller (130) must distinguish between valid data and invalid data in multiple data blocks (40_1). Information about the valid page count (VPC) corresponding to each data block (40_1) only indicates the amount of valid data or valid pages in each data block (40_1) and does not indicate which data or which page is valid. Therefore, the controller (130) needs to determine which data or which page is valid using operation information including map data as well as the number of valid pages. In this case, data to be stored in the free block (40_2) for garbage collection can be easily distinguished, thereby reducing resources (e.g., time and power) required for garbage collection.

A plurality of blocks (40_1, 40_2) in a memory device (150) can store large volume data. According to an embodiment, the controller (130) can divide each block into a plurality of unit blocks to more efficiently control and manage the plurality of blocks (40_1, 40_2) storing large volume data. When one block is divided into a plurality of unit blocks, the controller (130) can generate map data (e.g., L2P table, P2L table) for each unit block.

Depending on the embodiment, the number of unit blocks into which one block is divided may vary. For example, the number of unit blocks into which one block is divided may be determined based on the structure of the memory device (150), the size of the map data, the location of the map data, etc. Each block in the memory device (150) may program data in units of multiple pages. At this time, the size of data that can be stored in each page may vary depending on the structure of the unit cell of each block. When the map data is written in a bitmap format, an area corresponding to one or several times the size of the map data may be determined as the size of the unit block.

In the data block (40_1), data can be programmed sequentially from the first page to the last page. When data is programmed on the last page of the block, the block changes from an open state in which new data can be programmed to a closed state in which new data can no longer be programmed. According to an embodiment, when a specific block among the data blocks (40_1) is in a closed state, the garbage collection control unit (196) can compare the number of map data corresponding to the data stored in the unit block within the block with the number of valid pages to determine the validity of the data stored in the block.

Specifically, when a data block (40_1) in a memory device becomes a state (closed state) in which data can no longer be recorded without an erase operation, the controller (130) can compare the number of valid pages with the sum total of map data of a plurality of unit blocks. If the number of valid pages and the sum total of map data in a specific block do not match, it can be assumed that unnecessary map data is included in the block. The controller (130) can check whether map data corresponding to data stored in the block is valid. If map data that is no longer valid exists, the controller (130) can update the map data by deleting or invalidating the invalid map data.

According to an embodiment, the garbage collection control unit (196) may determine whether to designate a block as a target block for garbage collection based on a ratio of the sum of map data of multiple unit blocks within a specific block divided by the number of pages of the block. Here, the number of pages of the block is a fixed value determined during the design and manufacturing process of the memory device (150), and may represent the maximum amount of valid data that can be stored in one block. When a specific block is divided into multiple unit blocks and map data is generated for each unit block, the sum of the map data of multiple unit blocks within the block may represent the amount of currently valid data in the block. Accordingly, the garbage collection control unit (196) may recognize the amount of valid data in each block based on a ratio of the sum of map data of multiple unit blocks within a specific block divided by the number of pages of the block. The lower the ratio described above, the more the garbage collection control unit (196) may preferentially designate the block as a target block for garbage collection. In addition, the garbage collection control unit (196) can determine whether to select a block as a target block for garbage collection based on whether the aforementioned ratio falls within a preset range.

In the above-described embodiment, for garbage collection, the controller (130) must search for valid data in a plurality of data blocks (40_1). At this time, the controller (30) may search for valid data not for all data blocks (40_1) in the memory device (150), but may search for valid data limited to a preset range of the data blocks (40_1). In this case, resources (e.g., time, power) required to search for data to be stored in a free block (40_2) for garbage collection can be reduced.

The search for a valid page is related to a garbage collection (GC) operation, and is intended to manage the time of garbage collection through a device and method for searching for a block on which garbage collection is to be performed. Garbage collection includes an operation of searching for an area among dynamically allocated memory areas that can no longer be used or that no longer needs to be used, deleting data in the area, and preparing to program new data. The time required to delete data included in a specific area in a nonvolatile memory device may vary depending on the cell structure or cell characteristics of the nonvolatile memory device. On the other hand, the time required to search for an area to be erased in a nonvolatile memory device may vary depending on a method and device for controlling the nonvolatile memory device according to various embodiments.

FIG. 4 is a diagram illustrating the concept of a super memory block used in a memory system according to an embodiment of the present invention.

Referring to FIG. 4, it can be seen that components included in the memory device (150) among the components of the memory system (110) according to the embodiment of the present invention with reference to FIG. 1 are specifically illustrated.

The memory device (150) includes a plurality of memory blocks (BLOCK000, BLOCK001, BLOCK002, ..., BLCOK00N, BLOCK010, BLOCK011, BLOCK012, ..., BLCOK01N, BLOCK100, BLOCK101, BLOCK102, ..., BLCOK10N, BLOCK110, BLOCK111, BLOCK112, ..., BLCOK11N).

In addition, the memory device (150) includes a first memory die (DIE0) capable of inputting/outputting data through a 0th channel (CH0) and a second memory die (DIE1) capable of inputting/outputting data through a first channel (CH1). At this time, the 0th channel (CH0) and the first channel (CH1) can input/output data in an interleaving manner.

Additionally, the first memory die (DIE0) includes a plurality of planes (PLANE00, PLANE01) each corresponding to a plurality of paths (WAY0, WAY1) that can input/output data in an interleaved manner by sharing the zeroth channel (CH0).

Additionally, the second memory die (DIE1) includes a plurality of planes (PLANE10, PLANE11) each corresponding to a plurality of paths (WAY2, WAY3) that can input/output data in an interleaved manner by sharing the first channel (CH1).

Additionally, the first plane (PLANE00) of the first memory die (DIE0) includes a predetermined number of memory blocks (BLOCK000, BLOCK001, BLOCK002, ..., BLCOK00N, BLOCK010, BLOCK011, BLOCK012, ..., BLCOK01N, BLOCK100, BLOCK101, BLOCK102, ..., BLCOK10N, BLOCK110, BLOCK111, BLOCK112, ..., BLCOK11N).

Additionally, the second plane (PLANE01) of the first memory die (DIE0) includes a predetermined number of memory blocks (BLOCK010, BLOCK011, BLOCK002, ..., BLCOK00N, BLOCK010, BLOCK011, BLOCK012, ..., BLCOK01N, BLOCK100, BLOCK101, BLOCK102, ..., BLCOK10N, BLOCK110, BLOCK111, BLOCK112, ..., BLCOK11N).

Additionally, the first plane (PLANE10) of the second memory die (DIE1) includes a predetermined number of memory blocks (BLOCK100, BLOCK101, BLOCK102, ..., BLCOK00N, BLOCK010, BLOCK011, BLOCK012, ..., BLCOK01N, BLOCK100, BLOCK101, BLOCK102, ..., BLCOK10N, BLOCK110, BLOCK111, BLOCK112, ..., BLCOK11N).

Additionally, the second plane (PLANE11) of the second memory die (DIE1) includes a predetermined number of memory blocks (BLOCK110, BLOCK111, BLOCK112, ..., BLCOK11N) among a plurality of memory blocks (BLOCK000, BLOCK001, BLOCK002, ..., BLCOK00N, BLOCK010, BLOCK011, BLOCK012, ..., BLCOK01N, BLOCK100, BLOCK101, BLOCK102, ..., BLCOK10N, BLOCK110, BLOCK111, BLOCK112, ..., BLCOK11N).

In this way, a plurality of memory blocks (BLOCK000, BLOCK001, BLOCK002, ..., BLCOK00N, BLOCK010, BLOCK011, BLOCK012, ..., BLCOK01N, BLOCK100, BLOCK101, BLOCK102, ..., BLCOK10N, BLOCK110, BLOCK111, BLOCK112, ..., BLCOK11N) included in the memory device (150) can be distinguished according to their 'physical locations', such as using the same path or the same channel.

For reference, in FIG. 4, it is exemplified that a memory device (150) includes two memory dies (DIE0, DIE1), each memory die (DIE0, DIE1) includes two planes (PLANE00, PLANE01 / PLANE10, PLANE11), and each plane (PLANE00, PLANE01 / PLANE10, PLANE11) includes a predetermined number of memory blocks (BLOCK000, BLOCK001, BLOCK002, ..., BLCOK00N / BLOCK010, BLOCK011, BLOCK012, ..., BLCOK01N / BLOCK100, BLOCK101, BLOCK102, ..., BLCOK10N / BLOCK110, BLOCK111, BLOCK112, ..., BLCOK11N). However, this is only one embodiment. In reality, the memory device (150) may include more or fewer memory dies than two, depending on the designer's choice, and each memory die may include more or fewer planes than two. Of course, the 'intended number', which is the number of memory blocks included in each plane, may also be adjusted as much as the designer chooses.

Meanwhile, separately from the method of dividing a plurality of memory blocks (BLOCK000, BLOCK001, BLOCK002, ..., BLCOK00N, BLOCK010, BLOCK011, BLOCK012, ..., BLCOK01N, BLOCK100, BLOCK101, BLOCK102, ..., BLCOK10N, BLOCK110, BLOCK111, BLOCK112, ..., BLCOK11N) included in the memory device (150) into 'physical locations' such as a plurality of memory dies (DIE0, DIE1) or a plurality of planes (PLANE00, PLANE01 / PLANE10, PLANE11), the controller (130) may use a method of dividing based on which of the plurality of memory blocks are selected and operated at the same time. That is, the controller (130) can manage multiple memory blocks, which were previously divided into different dies or different planes through the method of distinguishing 'physical locations', by grouping them into blocks that can be selected simultaneously and distinguishing them into super memory blocks. In this case, 'simultaneous selection' can mean 'parallel selection'.

In this way, there are various ways to manage a plurality of memory blocks (BLOCK000, BLOCK001, BLOCK002, ..., BLCOK00N, BLOCK010, BLOCK011, BLOCK012, ..., BLCOK01N, BLOCK100, BLOCK101, BLOCK102, ..., BLCOK10N, BLOCK110, BLOCK111, BLOCK112, ..., BLCOK11N) by dividing them into super memory blocks in the controller (130), and three methods will be exemplified here.

The first method is a method in which the controller (130) groups any one memory block (BLOCK000) in the first plane (PLANE00) of the first memory die (DIE0) among the plurality of memory dies (DIE0, DIE1) included in the memory device (150) and manages them as one super memory block (A1). When the first method is applied to the second memory die (DIE1) among the plurality of memory dies (DIE0, DIE1) included in the memory device (150), the controller (130) can group any one memory block (BLOCK100) in the first plane (PLANE10) of the second memory die (DIE1) and manage them as one super memory block (A2).

The second method is a method in which a controller (130) groups any one memory block (BLOCK002) included in a first plane (PLANE00) of a first memory die (DIE0) among a plurality of memory dies (DIE0, DIE1) included in a memory device (150) and any one memory block (BLOCK102) included in a first plane (PLANE10) of a second memory die (DIE1) and manages them as a single super memory block (B1). Applying the second method again, the controller (130) can group any one memory block (BLOCK012) included in the second plane (PLANE01) of the first memory die (DIE0) among the multiple memory dies (DIE0, DIE1) included in the memory device (150) and any one memory block (BLOCK112) included in the second plane (PLANE11) of the second memory die (DIE1) and manage them as one super memory block (B2).

The third method is a method in which a controller (130) groups any one memory block (BLOCK001) included in a first plane (PLANE00) of a first memory die (DIE0) among a plurality of memory dies (DIE0, DIE1) included in a memory device (150), any one memory block (BLOCK011) included in a second plane (PLANE01) of the first memory die (DIE0), any one memory block (BLOCK101) included in a first plane (PLANE10) of the second memory die (DIE1), and any one memory block (BLOCK111) included in a second plane (PLANE11) of the second memory die (DIE1) and manages them as a single super memory block (C).

For reference, simultaneously selectable memory blocks included in a super memory block can be substantially simultaneously selected through an interleaving method, such as a channel interleaving method, a memory die interleaving method, a memory chip interleaving method, or a way interleaving method.

<Example 1>

FIGS. 5A and 5B are diagrams illustrating garbage collection for a super memory block in a memory system according to the first embodiment of the present invention.

First, it can be seen that in the first embodiment of the present invention illustrated in FIGS. 5a and 5b, the third method among the methods of distinguishing super memory blocks in the controller (130) described in FIG. 4 above is used.

That is, in FIGS. 5A and 5B, the controller (130) selects one random memory block from each of the four planes (PLANE<00, 01, 10, 11>) included in the memory device (150) and manages it as one super memory block (SUPER BLOCK<0> or SUPER BLOCK<1>). Accordingly, one super memory block (SUPER BLOCK<0> or SUPER BLOCK<1>) includes four memory blocks.

For example, referring to FIGS. 4 and 5a, a first super memory block (SUPER BLOCK<0>) groups a first memory block (BLOCK000) of a first plane (PLANE00) of a first memory die (DIE0), a first memory block (BLOCK010) of a second plane (PLANE01) of the first memory die (DIE0), a first memory block (BLOCK100) of a first plane (PLANE10) of a second memory die (DIE1), and a first memory block (BLOCK110) of a second plane (PLANE11) of the second memory die (DIE1).

And, referring to FIG. 4 and FIG. 5b, the second super memory block (SUPER BLOCK<1>) groups the second memory block (BLOCK001) of the first plane (PLANE00) of the first memory die (DIE0), the second memory block (BLOCK011) of the second plane (PLANE01) of the first memory die (DIE0), the second memory block (BLOCK101) of the first plane (PLANE10) of the second memory die (DIE1), and the second memory block (BLOCK111) of the second plane (PLANE11) of the second memory die (DIE1).

And, each of the super memory blocks (SUPER BLOCK<0, 1>) exemplified through FIGS. 5a and 5b can select four memory blocks (BLOCK<000, 010, 100, 110>, BLOCK<001, 011, 101, 111>) contained therein in parallel and input/output data in page units, respectively.

Here, it can be assumed that when each of the super memory blocks (SUPER BLOCK<0, 1>) illustrated through FIGS. 5a and 5b selects four memory blocks (BLOCK<000, 010, 100, 110>, BLOCK<001, 011, 101, 111>) contained therein in parallel, parallel reading is possible only for pages at the same location.

For example, selecting four memory blocks (BLOCK<000, 010, 100, 110>) included therein in parallel from the first super memory block (SUPER BLOCK<0>) exemplified through FIG. 5a means selecting pages having the same location in each of the four memory blocks (BLOCK<000, 010, 100, 110>). That is, it means simultaneously selecting the first page (P<0>) of each of the four memory blocks (BLOCK<000, 010, 100, 110>) included therein from the first super memory block (SUPER BLOCK<0>) exemplified through FIG. 5a or simultaneously selecting the second page (P<1>) of each of them. This means that it is impossible to simultaneously select pages in different locations, such as selecting the first page (P<0>) in the first and second memory blocks (BLOCK<000, 010>) among the four memory blocks (BLOCK<000, 010, 100, 110>) included in the first super memory block (SUPER BLOCK<0>) as illustrated in Fig. 5a, and selecting the second page (P<1>) in the third and fourth memory blocks (BLOCK<100, 110>).

Similarly, selecting four memory blocks (BLOCK<001, 011, 101, 111>) included therein in parallel from the second super memory block (SUPER BLOCK<1>) exemplified through FIG. 5b means selecting pages having the same location in each of the four memory blocks (BLOCK<001, 011, 101, 111>) at the same time. That is, it means simultaneously selecting the third page (P<2>) of each of the four memory blocks (BLOCK<001, 011, 101, 111>) included therein from the second super memory block (SUPER BLOCK<1>) exemplified through FIG. 5b or simultaneously selecting the fourth page (P<3>) of each of them. This means that it is impossible to simultaneously select pages in different locations, such as selecting the third page (P<2>) in the first and second memory blocks (BLOCK<001, 011>) among the four memory blocks (BLOCK<001, 011, 101, 111>) included in the second super memory block (SUPER BLOCK<1>) as illustrated in Fig. 5b, and selecting the fourth page (P<3>) in the third and fourth memory blocks (BLOCK<101, 111>).

Meanwhile, each of the super memory blocks (SUPER BLOCK<0, 1>) exemplified through FIGS. 5a and 5b includes four memory blocks (BLOCK<000, 010, 100, 110>, BLOCK<001, 011, 101, 111>) contained therein, and each of the multiple pages (P<0, 1, 2,...>) contained therein can independently become a valid page (VAILD PAGE) or an invalid page (INVALID PAGE).

For example, as illustrated in Fig. 5a, in the first super memory block (SUPER BLOCK<0>), only the first page (P<0>) of each of the first to third memory blocks (BLOCK<000, 010, 100>) may be a valid page (VAILD PAGE), and all remaining pages may be invalid pages (INVALID PAGE).

In addition, as illustrated in FIG. 5b, in the second super memory block (SUPER BLOCK<1>), only the first page (P<0>) of the first memory block (BLOCK001), the third page (P<2>) of the second memory block (BLOCK011), and the second page (P<1>) of the fourth memory block (BLOCK111) may be valid pages (VAILD PAGE), and all remaining pages may be invalid pages (INVALID PAGE).

In this way, it can be seen that the first super memory block (SUPER BLOCK<0>) illustrated in Fig. 5a and the second super memory block (SUPER BLOCK<1>) illustrated in Fig. 5b each contain three valid pages.

Additionally, for garbage collection, four memory blocks (MEMORY BLOCK<000, 010, 100, 110>, MEMORY BLOCK<001, 011, 101, 111>) included in each of the super memory blocks (SUPER BLOCK<0, 1>) illustrated in FIGS. 5a and 5b can be selected as victim blocks.

In this way, when the first super memory block (SUPER BLOCK<0>) illustrated in Fig. 5a is selected as a sacrifice block for garbage collection, the time required to extract data from three valid pages included in the four memory blocks (MEMORY BLOCK<000, 010, 100, 110>) included therein can be referred to as the first time required (TOTAL<0>). In addition, when the second super memory block (SUPER BLOCK<1>) illustrated in Fig. 5b is selected as a sacrifice block for garbage collection, the time required to extract data from three valid pages included in the four memory blocks (MEMORY BLOCK<001, 011, 101, 111>) included therein can be referred to as the second time required (TOTAL<1>).

At this time, the first time required (TOTAL<0>) and the second time required (TOTAL<1>) may differ significantly for the following reasons:

Specifically, in the garbage collection, the first super memory block (SUPER BLOCK<0>) illustrated in Fig. 5a is selected as a victim block, and the locations of three valid pages included in the four memory blocks (MEMORY BLOCK<000, 010, 100, 110>) included therein can be identified to extract data from the three valid pages.

As a result of the verification, it can be seen that in the first super memory block (SUPER BLOCK<0>), only the first page (P<0>) of each of the first to third memory blocks (BLOCK<000, 010, 100>) is a valid page (VAILD PAGE), and all remaining pages are invalid pages (INVALID PAGE).

According to the verification result, we can see that the three valid pages (VAILD PAGE) included in the first super memory block (SUPER BLOCK<0>) have the same location. In other words, we can see that one read (P<0>_READ) must be performed to extract three valid data from three valid pages (VAILD PAGE).

Therefore, the controller (130) performs one read (P<0>_READ) on the first page (P<0>) of each of the four memory blocks (BLOCK<000, 010, 100, 110>) included in the first super memory block (SUPER BLOCK<0>) at time 0 (t0). Through one read (P<0>_READ), four page data (B000P0_VD, B010P0_VD, B100P0_VD, B110P0_IVD) are cached in four page buffers (PB<000, 010, 100, 110>). Next, the controller (130) selects only three valid data (VALID DATA: B000P0_VD, B010P0_VD, B100P0_VD, B110P0_IVD) among four page data (B000P0_VD, B010P0_VD, B100P0_VD) cached in the page buffers (PB<000, 010, 100, 110>) at the first time point (t1) and transfers (DATA TRANSFER) them to the internal memory (144). Of course, the controller (130) discards one invalid data (INVALID DATA: B110P0_IVD) among the four page data (B000P0_VD, B010P0_VD, B100P0_VD, B110P0_IVD) cached in the page buffers (PB<000, 010, 100, 110>) at the first time point (t1) without transmitting it to the internal memory (144).

In this way, the controller (130) can extract all three valid data (VALID DATA: B000P0_VD, B010P0_VD, B100P0_VD) stored in three valid pages (VAILD PAGE: BLOCK000_P<0>, BLOCK010_P<0>, BLOCK110_P<0>) included in the first super memory block (SUPER BLOCK<0>) through one read (P<0>_READ).

Here, the time required to perform one read (P<0>_READ) can be assumed as the read time (tREAD). In addition, the time required to transfer one page data (B000P0_VD or B010P0_VD or B100P0_VD) stored in one page buffer (PB<000> or PB<010> or PB<100>) to the internal memory (144) can be assumed as the transfer time (tTX). In this assumption, the first required time (TOTAL<0>) required to extract data by selecting the first super memory block (SUPER BLOCK<0>) as a victim block in garbage collection will be '{read time (tREAD) * 1} + {transfer time (tTX) * 3}'. For example, assuming that the read time (tREAD) is 50us and the transfer time (tTX) is 10us, the first time required to extract data by selecting the first super memory block (SUPER BLOCK<0>) as a victim block in garbage collection (TOTAL<0>) will be 80us.

And, in the garbage collection, the second super memory block (SUPER BLOCK<1>) illustrated in Fig. 5b can be selected as a victim block to check the locations of three valid pages included in the four memory blocks (MEMORY BLOCK<001, 011, 101, 111>) included therein in order to extract data from the three valid pages.

As a result of the verification, it can be seen that in the second super memory block (SUPER BLOCK<1>), only the first page (P<0>) of the first memory block (BLOCK001), the third page (P<2>) of the second memory block (BLOCK011), and the second page (P<1>) of the fourth memory block (BLOCK111) are valid pages (VAILD PAGE), and all remaining pages are invalid pages (INVALID PAGE).

According to the verification result, we can see that the three valid pages (VAILD PAGE) included in the second super memory block (SUPER BLOCK<1>) do not have the same locations as each other. That is, we can see that three reads (P<0>_READ, P<1>_READ, P<2>_READ) must be performed to extract three valid data from the three valid pages (VAILD PAGE).

Accordingly, the controller (130) performs a first read (P<0>_READ) on the first page (P<0>) of each of the four memory blocks (BLOCK<001, 011, 101, 111>) included in the second super memory block (SUPER BLOCK<1>) at time 0 (t0). Through the first read (P<0>_READ), four page data (B001P0_VD, B011P0_IVD, B101P0_IVD, B111P0_IVD) are cached in four page buffers (PB<001, 011, 101, 111>). Next, the controller (130) selects only one valid data (VALID DATA: B001P0_VD) among four page data (B001P0_VD, B011P0_IVD, B101P0_IVD, B111P0_IVD) cached in the page buffers (PB<001, 011, 101, 111>) at a first time point (t1) and transfers (DATA TRANSFER) the selected valid data to the internal memory (144). Of course, the controller (130) discards three invalid data (INVALID DATA: B011P0_IVD, B101P0_IVD, B111P0_IVD) among the four page data (B001P0_VD, B011P0_IVD, B101P0_IVD, B111P0_IVD) cached in the page buffers (PB<001, 011, 101, 111>) without transmitting them to the internal memory (144).

In this way, the controller (130) can extract one valid data (VALID DATA: B001P0_VD) stored in one valid page (VAILD PAGE: BLOCK001_P<0>) included in the second super memory block (SUPER BLOCK<1>) through the first read (P<0>_READ).

Next, the controller (130) performs a second read (P<1>_READ) on the second page (P<1>) of each of the four memory blocks (BLOCK<001, 011, 101, 111>) included in the second super memory block (SUPER BLOCK<1>) at a second time point (t2). Through the second read (P<1>_READ), four page data (B001P1_IVD, B011P1_IVD, B101P1_IVD, B111P1_VD) are cached in four page buffers (PB<001, 011, 101, 111>). Next, the controller (130) selects only one valid data (VALID DATA: B111P1_VD) among four page data (B001P1_IVD, B011P1_IVD, B101P1_IVD, B111P1_VD) cached in the page buffers (PB<001, 011, 101, 111>) at a third time point (t3) and transfers (DATA TRANSFER) it to the internal memory (144). Of course, the controller (130) discards three invalid data (INVALID DATA: B001P1_IVD, B011P1_IVD, B101P1_IVD, B111P1_VD) among the four page data (B001P1_IVD, B011P1_IVD, B101P1_IVD) cached in the page buffers (PB<001, 011, 101, 111>) without transmitting them to the internal memory (144).

In this way, the controller (130) can extract one valid data (VALID DATA: B111P1_VD) stored in one valid page (VAILD PAGE: BLOCK111_P<1>) included in the second super memory block (SUPER BLOCK<1>) through the second read (P<1>_READ).

Next, the controller (130) performs a third read (P<2>_READ) on the third page (P<2>) of each of the four memory blocks (BLOCK<001, 011, 101, 111>) included in the second super memory block (SUPER BLOCK<1>) at a fourth time point (t4). Through the third read (P<2>_READ), four page data (B001P2_IVD, B011P2_VD, B101P2_IVD, B111P2_IVD) are cached in four page buffers (PB<001, 011, 101, 111>). Next, the controller (130) selects only one valid data (VALID DATA: B011P2_VD) among four page data (B001P2_IVD, B011P2_VD, B101P2_IVD, B111P2_IVD) cached in the page buffers (PB<001, 011, 101, 111>) at the fifth time point (t5) and transfers (DATA TRANSFER) it to the internal memory (144). Of course, the controller (130) discards three invalid data (INVALID DATA: B001P2_IVD, B101P2_IVD, B111P2_IVD) among the four page data (B001P2_IVD, B011P2_VD, B101P2_IVD, B111P2_IVD) cached in the page buffers (PB<001, 011, 101, 111>) without transmitting them to the internal memory (144).

In this way, the controller (130) can extract one valid data (VALID DATA: B011P2_VD) stored in one valid page (VAILD PAGE: BLOCK011_P<2>) included in the second super memory block (SUPER BLOCK<1>) through the third read (P<2>_READ).

In summary, it can be seen that the controller (130) requires three reads (P<0>_READ, P<1>_READ, P<2>_READ) to extract all three valid data (VALID DATA: B001P0_VD, B011P2_VD, B111P1_VD) stored in three valid pages (VAILD PAGE: BLOCK001_P<0>, BLOCK011_P<2>, BLOCK111_P<1>) included in the second super memory block (SUPER BLOCK<1>).

Here, the time required to perform one read (P<0>_READ or P<1>_READ or P<2>_READ) can be assumed as the read time (tREAD). In addition, the time required to transfer one page data (B001P0_VD or B011P2_VD or B111P1_VD) stored in one page buffer (PB<001> or PB<011> or PB<111>) to the internal memory (144) can be assumed as the transfer time (tTX). In this case, the time required to extract data by selecting the second super memory block (SUPER BLOCK<1>) as a victim block in garbage collection (TOTAL<1>) will be '{Read time (tREAD) * 3} + {Transfer time (tTX) * 3}'. For example, assuming that the read time (tREAD) is 50us and the transfer time (tTX) is 10us, the second time required to extract data by selecting the second super memory block (SUPER BLOCK<1>) as a victim block in garbage collection (TOTAL<1>) will be 180us.

In summary, as illustrated in Fig. 5a, the first super memory block (SUPER BLOCK<0>) and as illustrated in Fig. 5b, the second super memory block (SUPER BLOCK<1>), each contain three valid pages, so it can be seen that the same conditions apply when selecting a victim block for garbage collection based on the number of valid pages.

However, when each of the super memory blocks (SUPER BLOCK<0, 1>) illustrated in FIGS. 5a and 5b is selected as a sacrifice block for garbage collection, the first time required (TOTAL<0>) to extract data from the first super memory block (SUPER BLOCK<0>) illustrated in FIG. 5a is 80us, whereas the second time required (TOTAL<1>) to extract data from the second super memory block (SUPER BLOCK<1>) illustrated in FIG. 5b is 180us, which is more than twice the difference.

That is, in order to effectively perform garbage collection, it is desirable for the controller (130) to select the first super memory block (SUPER BLOCK<0>) among the super memory blocks (SUPER BLOCK<0, 1>) illustrated in FIGS. 5a and 5b as a sacrifice block.

FIG. 6 is a diagram illustrating an operation of selecting a victim block when performing garbage collection on a super memory block in a memory system according to the first embodiment of the present invention described through FIGS. 5a and 5b.

Referring to FIG. 6, a memory system (110) according to the first embodiment of the present invention includes a controller (130) and a memory device (150).

And, the controller (130) may include a garbage collection control unit (196) and a memory (144). Here, the general operation of the garbage collection control unit (196) has been described through the aforementioned FIG. 3, so it will not be described in more detail here.

And, as described through FIG. 4, the memory device (150) includes a plurality of memory blocks (MEMORY BLOCK<000, 001,...>). In addition, the controller (130) groups N memory blocks capable of parallel reading among the memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150) according to set conditions and manages them as a plurality of super memory blocks (SUPER BLOCK<0:N>). At this time, N is a natural number greater than or equal to 2, and it is assumed in FIGS. 5A and 5B that N is 4. Here, it is assumed that one super memory block (SUPER BLOCK<2>) in a free state is included in the memory device (150) together with two super memory blocks (SUPER BLOCK<0, 1>) described through FIGS. 5A and 5B. Of course, the details exemplified in Fig. 6 are simplified for convenience of explanation, and in reality, they can be expanded into other forms (such as a form in which a greater number of super memory blocks are included in a memory device).

Specifically, the controller (130) generates required predicted times (PRE_TOTAL<0, 1>) by predicting the time required for extracting valid data from memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150) for garbage collection by superblock unit through the garbage collection control unit (196) included therein, and manages the generated required predicted times (PRE_TOTAL<0, 1>) as a required predicted time table (600).

In addition, the controller (130) counts the number of valid pages (VPC<0:1>) of each memory block (MEMORY BLOCK<000, 001,...>) included in the memory device (150) in superblock units through the garbage collection control unit (196), and manages the counted number of valid pages (VPC<0:1>) as a valid page count table (610).

More specifically, the controller (130) calculates the first time (FIRST_TIME<0:1>) by multiplying the number obtained by subtracting the number of valid pages (DP_CNT<0:1>) having the same location among four memory blocks (BLOCK<000, 010, 100, 110>, BLOCK<001, 011, 101, 111>) grouped in each of the multiple super memory blocks (SUPER BLOCK<0:1>) from the number of valid pages (VPC<0:1>) of each of the multiple super memory blocks (SUPER BLOCK<0:1>) by the read prediction time (PRE_tREAD). (FIRST_TIME<0:1> = (VPC<0:1> - DP_CNT<0:1>) * PRE_tREAD)

In addition, the controller (130) calculates a second time (SECOND_TIME<0:1>) by multiplying the number of valid pages (VPC<0:1>) of each of a plurality of super memory blocks (SUPER BLOCK<0:1>) by the predicted transmission time (PRE_tTX) (SECOND_TIME<0:1> = VPC<0:1> * PRE_tTX).

In addition, the controller (130) calculates a value that adds the first time (FIRST_TIME<0:1>) and the second time (SECOND_TIME<0:1>) (TOTAL<0:1> = FIRST_TIME<0:1> + SECOND_TIME<0:1>) and generates the predicted required times (PRE_TOTAL<0, 1>) for each of a plurality of super memory blocks (SUPER BLOCK<0:1>).

Referring to FIG. 5a together with FIG. 6 for example to explain, it can be seen that in the first super memory block (SUPER BLOCK<0>), only the first page (P<0>) of each of the first to third memory blocks (BLOCK<000, 010, 100>) is a valid page (VAILD PAGE), and all the remaining pages are invalid pages (INVALID PAGE).

Therefore, the controller (130) can know that the number of first valid pages (VPC<0>) included in the first super memory block (SUPER BLOCK<0>) is 3.

In addition, the controller (130) can know that all three valid pages included in the first super memory block (SUPER BLOCK<0>) are the first page (P<0>), and the number of first valid pages (DP_CNT<0>) having the same location is 2. Here, based on the first valid page (BLOCK000/P<0>), the second and third valid pages (BLOCK010/P<0>, BLOCK100/P<0>) are in the same location as the first valid page (BLOCK000/P<0>). Therefore, the second and third valid pages (BLOCK010/P<0>, BLOCK100/P<0>) are included in the valid pages having the same location in the first super memory block (SUPER BLOCK<0>), and through this, the number of first valid pages (DP_CNT<0>) becomes 2.

Therefore, the first first time (FIRST_TIME<0>) corresponding to the first super memory block (SUPER BLOCK<0>) becomes the time corresponding to one read prediction time (PRE_tREAD) through calculation such as '(3 ?? 2) * PRE_tREAD'. In addition, the first second time (SECOND_TIME<0>) corresponding to the first super memory block (SUPER BLOCK<0>) becomes the time corresponding to three transmission prediction times (PRE_tTX) through calculation such as '3 * PRE_tTX'. In conclusion, the first predicted time (PRE_TOTAL<0>) corresponding to the first super memory block (SUPER BLOCK<0>) is the sum of the first first time (FIRST_TIME<0>) corresponding to one read predicted time (PRE_tREAD) and the first second time (SECOND_TIME<0>) corresponding to three transmission predicted times (PRE_tTX).

For example, assuming that the read prediction time (PRE_tREAD) is 50us and the transmission prediction time (PRE_tTX) is 10us, the first predicted time required (PRE_TOTAL<0>) corresponding to the first super memory block (SUPER BLOCK<0>) will be 80us, which is the sum of the first first time (FIRST_TIME<0>) of 50us and the first second time (SECOND_TIME<0>) of 30us.

Similarly, referring to FIG. 5b together with FIG. 6 for illustration purposes, it can be seen that in the second super memory block (SUPER BLOCK<1>), only the first page (P<0>) of the first memory block (BLOCK001), the third page (P<2>) of the second memory block (BLOCK011), and the second page (P<1>) of the fourth memory block (BLOCK111) are valid pages (VAILD PAGE), and all the remaining pages are invalid pages (INVALID PAGE).

Accordingly, the controller (130) can know that the number of second valid pages (VPC<1>) included in the second super memory block (SUPER BLOCK<1>) is 3.

In addition, the controller (130) can know that the positions of each of the three valid pages included in the second super memory block (SUPER BLOCK<1>) are different, and thus the number of second valid pages (DP_CNT<1>) having the same position is 0. Here, with the first valid page (BLOCK001/P<0>) as a standard, the second valid page (BLOCK011/P<3>) and the third valid page (BLOCK111/P<0>) are each in different positions from the first valid page (BLOCK000/P<0>). In addition, the second valid page (BLOCK011/P<3>) and the third valid page (BLOCK111/P<0>) are also in different positions. Therefore, there is no valid page in the second super memory block (SUPER BLOCK<1>) having the same position, and thus the number of second valid pages (DP_CNT<1>) becomes 0.

Therefore, the second first time (FIRST_TIME<1>) corresponding to the second super memory block (SUPER BLOCK<1>) becomes the time corresponding to three read prediction times (PRE_tREAD) through calculations such as '(3 ?? 0) * PRE_tREAD'. In addition, the second second time (SECOND_TIME<1>) corresponding to the second super memory block (SUPER BLOCK<1>) becomes the time corresponding to three transmission prediction times (PRE_tTX) through calculations such as '3 * PRE_tTX'. In conclusion, the second estimated time (PRE_TOTAL<1>) corresponding to the second super memory block (SUPER BLOCK<1>) is the sum of the second first time (FIRST_TIME<1>) corresponding to three read estimated times (PRE_tREAD) and the second second time (SECOND_TIME<1>) corresponding to three transmission estimated times (PRE_tTX).

For example, assuming that the read prediction time (PRE_tREAD) is 50us and the transmission prediction time is 10us, the second predicted time required (PRE_TOTAL<1>) corresponding to the second super memory block (SUPER BLOCK<1>) will be 180us, which is the sum of the second first time (FIRST_TIME<1>) of 150us and the second second time (SECOND_TIME<1>) of 30us.

For reference, the controller (130) may set information on the read prediction time (PRE_tREAD) and the transmission prediction time (PRE_tTX) for the memory device (150). That is, the designer may set the read prediction time (PRE_tREAD) and the transmission prediction time (PRE_tTX) for the memory device (150) in advance through a test depending on the type or state of the memory device (150).

As described above, the controller (130) can predict the expected time required (PRE_TOTAL<0, 1>) for each of a plurality of super memory blocks (SUPER BLOCK<0:1>) before performing garbage collection.

And, the controller (130) can refer to the estimated times (PRE_TOTAL<0, 1>) for a plurality of super memory blocks (SUPER BLOCK<0:1>) included in the estimated time table (600) through the garbage collection control unit (196) included therein to determine which memory block among the memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150) to select as a sacrifice block for garbage collection.

At this time, the controller (130) may refer to the required predicted times (PRE_TOTAL<0, 1>) for a number of super memory blocks (SUPER BLOCK<0:1>) included in the required predicted time table (600) in the following two ways, and may select one of the two ways.

The first method is a method in which a controller (130) selects a memory block including at least one valid page among N memory blocks grouped in a super memory block corresponding to a relatively smallest value of the required predicted time (PRE_TOTAL<0, 1>) among a plurality of super memory blocks (SUPER BLOCK<0:1>) as a victim block.

For example, as described above, the expected time required (PRE_TOTAL<0>) for the first super memory block (SUPER BLOCK<0>) is 80us, and the expected time required (PRE_TOTAL<1>) for the second super memory block (SUPER BLOCK<1>) is 180us, so the expected time required (PRE_TOTAL<0>) for the first super memory block (SUPER BLOCK<0>) is smaller. Accordingly, the controller (130) selects three memory blocks (MEMORY BLOCK<000, 010, 100, 110>) that include at least one valid page among the four memory blocks (MEMORY BLOCK<000, 010, 100>) grouped in the first super memory block (SUPER BLOCK<0>) as victim blocks.

In this way, since the three memory blocks (MEMORY BLOCK<000, 010, 100>) included in the first super memory block (SUPER BLOCK<0>) are selected as victim blocks, in the section where garbage collection is performed, the three valid pages included in the first super memory block (SUPER BLOCK<0>) will be transferred to the memory (144) within the controller (130) and then stored in the third super memory block (SUPER BLOCK<2>), which is the target block.

The second method is a method in which, before using the first method described above, the controller (130) checks the number of super memory blocks whose combined number of valid pages (VPC<0:1>) of each of the N memory blocks included in each of the plurality of super memory blocks (SUPER BLOCK<0:1>) is less than or equal to a 'set number'. That is, the controller (130) does not use the first method described above if there is 'one' super memory block less than or equal to the 'set number' among the valid number of pages (VPC<0:1>) of each of the plurality of super memory blocks (SUPER BLOCK<0:1>). On the other hand, the controller (130) uses the first method described above if there are 'at least two' super memory blocks less than or equal to the 'set number' among the valid number of pages (VPC<0:1>) of each of the plurality of super memory blocks (SUPER BLOCK<0:1>).

For example, unlike in the above-described description, the number of valid pages (VPC<0>) of the first super memory block (SUPER BLOCK<0>) may be 5, and the number of valid pages (VPC<1>) of the second super memory block (SUPER BLOCK<1>) may be 1. In addition, the controller (130) may set the 'set number' to 2. In this case, the controller (130) may confirm that one super memory block, that is, the second super memory block (SUPER BLOCK<1>), has a number of valid pages less than or equal to the 'set number'. Therefore, the controller (130) selects, as a victim block, a memory block including at least one valid page among the N memory blocks included in the second super memory block (SUPER BLOCK<1>) having a number of valid pages less than or equal to the 'set number', without using the first method described above.

On the other hand, as described above, the number of valid pages (VPC<0>) of the first super memory block (SUPER BLOCK<0>) may be 3, and the number of valid pages (VPC<1>) of the second super memory block (SUPER BLOCK<1>) may also be 3. In addition, the controller (130) may set the 'set number' to 2. In this case, the controller (130) may confirm that both super memory blocks, that is, the first super memory block (SUPER BLOCK<0>) and the second super memory block (SUPER BLOCK<1>), have a number of valid pages less than or equal to the 'set number'. Therefore, the controller (130) selects, as a victim block, a memory block including at least one valid page among the N memory blocks included in the first super memory block (SUPER BLOCK<0>) having a relatively smaller estimated time required (PRE_TOTAL<0>).

Meanwhile, as described above, the controller (130) generates required predicted times (PRE_TOTAL<0, 1>) and manages the generated required predicted times (PRE_TOTAL<0, 1>) as a required predicted time table (600).

At this time, the controller (130) can update the estimated time required (PRE_TOTAL<0, 1>) using one of the following two methods.

In the first method, the controller (130) can update the expected time required for a super memory block in which a specific memory block is grouped whenever a specific memory block with a variable number of valid pages occurs among the memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150).

For example, referring to FIGS. 4 and 5A together, the number of valid pages of a first memory block (BLOCK000) of a first plane (PLANE00) of a first memory die (DIE0) may vary depending on whether a first foreground operation or a background operation is performed. Subsequently, the number of valid pages of a second memory block (BLOCK001) of a first plane (PLANE00) of the first memory die (DIE0) may vary depending on whether a second foreground operation or a background operation is performed.

In this case, the controller (130) can re-predict the value of the first estimated time required (PRE_TOTAL<0>) corresponding to the first super memory block (SUPER BLOCK<0>) in which the memory block (BLOCK000) is grouped in response to the change in the valid page of the first memory block (BLOCK000) of the first plane (PLANE00) of the first memory die (DIE0). Then, the controller (130) can re-predict the value of the second estimated time required (PRE_TOTAL<1>) corresponding to the second super memory block (SUPER BLOCK<1>) in which the memory block (BLOCK001) is grouped in response to the change in the number of valid pages of the second memory block (BLOCK001) of the first plane (PLANE00) of the first memory die (DIE0).

In the second method, the controller (130) checks whether there is a specific memory block among the memory blocks (MEMORY BLOCK<000, 001,...>) with a variable number of valid pages at each 'set point in time', and if the result of the check shows that there is a specific memory block with a variable number of valid pages, the controller can update the expected time required for the super memory block in which the specific memory block is grouped.

For example, referring to FIGS. 4 and 5A together, at least two consecutive foreground operations or background operations may be performed between a first set point in time (not shown) and a second set point in time (not shown) so that the number of valid pages of a first memory block (BLOCK000) of a first plane (PLANE00) of a first memory die (DIE0) and the number of valid pages of a second memory block (BLOCK001) may be varied.

In this case, the controller (130) checks whether there is a memory block among the memory blocks (MEMORY BLOCK<000, 001,...>) with a variable number of valid pages at the second set time point, and based on the check result, it can be known that the number of valid pages of each of the first memory block (BLOCK000) and the second memory block (BLOCK001) of the first plane (PLANE00) of the first memory die (DIE0) has varied. Accordingly, the controller (130) can simultaneously re-predict the value of the first predicted time required (PRE_TOTAL<0>) corresponding to the first super memory block (SUPER BLOCK<0>) in which the first memory block (BLOCK000) of the first plane (PLANE00) of the first memory die (DIE0) is grouped at the second set time point, and the value of the second predicted time required (PRE_TOTAL<1>) corresponding to the second super memory block (SUPER BLOCK<1>) in which the second memory block (BLOCK001) of the first plane (PLANE00) of the first memory die (DIE0) is grouped.

For reference, a 'set point in time' is a point in time that can be predefined by the designer, and can be a point in time that is repeated whenever data of a set size is written, or a point in time that is repeated whenever the performance of a specific operation is completed.

Meanwhile, when garbage collection is performed and all valid pages included in the first super memory block (SUPER BLOCK<0>) selected as a victim block are transferred to the memory (144) within the controller (130) and then moved to the third super memory block (SUPER BLOCK<2>), which is a target block, there will be no more valid pages in the first super memory block (SUPER BLOCK<0>). Therefore, the first super memory block (SUPER BLOCK<0>) after garbage collection does not need to be involved in any operation as an invalid super memory block other than the operation of becoming a free super memory block through an erase operation. However, since the controller (130) generates the first estimated time required (PRE_TOTAL<0>) for the first super memory block (SUPER BLOCK<0>) before performing garbage collection, its value may remain in the estimated time required table (600) even after performing garbage collection. In this way, an unknown abnormal operation may be performed for the first super memory block (SUPER BLOCK<0>) due to the value of the first estimated time required (PRE_TOTAL<0>) remaining in the estimated time required table (600). Accordingly, the controller (130) sets the first estimated time required (PRE_TOTAL<0>) corresponding to the first super memory block (SUPER BLOCK<0>) to a ‘planned value’ after garbage collection is performed on the first super memory block (SUPER BLOCK<0>) selected as the sacrifice block, thereby preventing an unknown abnormal operation from being performed on the first super memory block (SUPER BLOCK<0>).

In summary, the controller (130) can set the expected time required for a specific super memory block to an 'expected value' to prevent the specific super memory block from performing an unknown erroneous operation when the specific super memory block is selected as a sacrifice block and all valid pages inside are moved to the target super memory block through garbage collection.

Meanwhile, if the number of free memory blocks among the memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150) is sufficiently large, the probability of performing garbage collection is not high. That is, garbage collection is generally an operation performed when the number of free memory blocks included in the memory device (150) is reduced below a 'certain number'.

Accordingly, the controller (130) according to the first embodiment of the present invention generates and manages the aforementioned required predicted times (PRE_TOTAL<0, 1>) in a section where the number of free memory blocks among the memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150) is equal to or less than the 'first number'. Of course, the controller (130) does not generate and manage the required predicted times (PRE_TOTAL<0, 1>) in a section where the number of free memory blocks among the memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150) is equal to or greater than the 'second number' which is greater than the 'first number'.

Note that the 'first number' may be set differently from the 'schedule number' used to determine the trigger point of a general garbage collection operation. For example, the 'schedule number' may be smaller than the 'first number'.

<Example 2>

FIGS. 7A and 7B are diagrams illustrating garbage collection for a super memory block in a memory system according to a second embodiment of the present invention.

First, it can be seen that in the second embodiment of the present invention illustrated in FIGS. 7a and 7b, the third method among the methods of distinguishing super memory blocks in the controller (130) described in FIG. 4 above is used.

That is, in FIGS. 7a and 7b, the controller (130) selects one random memory block from each of the four planes (PLANE<00, 01, 10, 11>) included in the memory device (150) and manages it as one super memory block (SUPER BLOCK<0> or SUPER BLOCK<1>). Accordingly, one super memory block (SUPER BLOCK<0> or SUPER BLOCK<1>) includes four memory blocks.

For example, referring to FIG. 4 and FIG. 7a, a first super memory block (SUPER BLOCK<0>) groups a first memory block (BLOCK000) of a first plane (PLANE00) of a first memory die (DIE0), a first memory block (BLOCK010) of a second plane (PLANE01) of the first memory die (DIE0), a first memory block (BLOCK100) of a first plane (PLANE10) of a second memory die (DIE1), and a first memory block (BLOCK110) of a second plane (PLANE11) of the second memory die (DIE1).

And, referring to FIG. 4 and FIG. 7b, the second super memory block (SUPER BLOCK<1>) groups the second memory block (BLOCK001) of the first plane (PLANE00) of the first memory die (DIE0), the second memory block (BLOCK011) of the second plane (PLANE01) of the first memory die (DIE0), the second memory block (BLOCK101) of the first plane (PLANE10) of the second memory die (DIE1), and the second memory block (BLOCK111) of the second plane (PLANE11) of the second memory die (DIE1).

And, each of the super memory blocks (SUPER BLOCK<0, 1>) exemplified through FIGS. 7a and 7b can select four memory blocks (BLOCK<000, 010, 100, 110>, BLOCK<001, 011, 101, 111>) contained therein in parallel and input/output data in page units, respectively.

Here, each of the super memory blocks (SUPER BLOCK<0, 1>) exemplified through FIGS. 7a and 7b can be assumed to be capable of parallel reading for pages at different locations when selecting four memory blocks (BLOCK<000, 010, 100, 110>, BLOCK<001, 011, 101, 111>) contained therein in parallel. Of course, even if parallel reading is possible for pages at different locations, it is possible to select and read only one page at a time from one block.

For example, selecting four memory blocks (BLOCK<000, 010, 100, 110>) contained therein in parallel from the first super memory block (SUPER BLOCK<0>) illustrated through Fig. 7a means selecting one page regardless of its location from each of the four memory blocks (BLOCK<000, 010, 100, 110>). That is, in the first super memory block (SUPER BLOCK<0>) illustrated in Fig. 7a, among the four memory blocks (BLOCK<000, 010, 100, 110>) included therein, the first page (P<0>) is selected in the first memory block (BLOCK000), the third page (P<2>) is selected in the second memory block (BLOCK010), and the second page (P<1>) is selected in the third and fourth memory blocks (BLOCK<100, 110>), respectively. Of course, it is impossible to read in the same way as selecting two pages each from the first and second memory blocks (BLOCK<000, 010>) among the four memory blocks (BLOCK<000, 010, 100, 110>) and not selecting any pages from the third and fourth memory blocks (BLOCK<100, 110>).

Similarly, selecting four memory blocks (BLOCK<001, 011, 101, 111>) included therein in parallel in the second super memory block (SUPER BLOCK<1>) exemplified through FIG. 7b means selecting one page simultaneously from each of the four memory blocks (BLOCK<001, 011, 101, 111>) regardless of the position. That is, it means selecting the first page (P<0>) from the first memory block (BLOCK001) among the four memory blocks (BLOCK<001, 011, 101, 111>) included therein in the second super memory block (SUPER BLOCK<1>) exemplified through FIG. 7b, and selecting the second page (P<1>) from the second to fourth memory blocks (BLOCK<011, 101, 111>), respectively. Of course, it is impossible to read in the same way as selecting two pages each from the second and third memory blocks (BLOCK<011, 101>) among the four memory blocks (BLOCK<001, 011, 101, 111>) and not selecting any pages from the first and fourth memory blocks (BLOCK<001, 111>).

Meanwhile, each of the super memory blocks (SUPER BLOCK<0, 1>) exemplified through FIGS. 7a and 7b includes four memory blocks (BLOCK<000, 010, 100, 110>, BLOCK<001, 011, 101, 111>) contained therein, and each of the multiple pages (P<0, 1, 2,...>) contained therein can independently become a valid page (VAILD PAGE) or an invalid page (INVALID PAGE).

For example, as illustrated in FIG. 7a, in the first super memory block (SUPER BLOCK<0>), only the first page (P<0>) of the first memory block (BLOCK000), the third page (P<2>) of the second memory block (BLOCK010), and the second page (P<1>) of each of the third and fourth memory blocks (BLOCK<100, 110>) may be valid pages (VAILD PAGE), and all remaining pages may be invalid pages (INVALID PAGE).

In addition, as illustrated in FIG. 7b, in the second super memory block (SUPER BLOCK<1>), only the first page (P<0>) of the first memory block (BLOCK001), the second and third pages (P<1, 2>) of the second memory block (BLOCK011), and the second page (P<1>) of the fourth memory block (BLOCK111) may be valid pages (VAILD PAGE), and all remaining pages may be invalid pages (INVALID PAGE).

In this way, it can be seen that the first super memory block (SUPER BLOCK<0>) illustrated in Fig. 7a and the second super memory block (SUPER BLOCK<1>) illustrated in Fig. 7b each contain four valid pages.

Additionally, for garbage collection, four memory blocks (MEMORY BLOCK<000, 010, 100, 110>, MEMORY BLOCK<001, 011, 101, 111>) included in each of the super memory blocks (SUPER BLOCK<0, 1>) illustrated in FIGS. 7a and 7b can be selected as victim blocks.

In this way, when the first super memory block (SUPER BLOCK<0>) illustrated in Fig. 7a is selected as a victim block for garbage collection, the time required to extract data from four valid pages included in the four memory blocks (MEMORY BLOCK<000, 010, 100, 110>) included therein can be referred to as the first time required (TOTAL<0>). In addition, when the second super memory block (SUPER BLOCK<1>) illustrated in Fig. 7b is selected as a victim block for garbage collection, the time required to extract data from four valid pages included in the four memory blocks (MEMORY BLOCK<001, 011, 101, 111>) included therein can be referred to as the second time required (TOTAL<1>).

At this time, the first time required (TOTAL<0>) and the second time required (TOTAL<1>) may differ significantly for the following reasons:

Specifically, in the garbage collection, the first super memory block (SUPER BLOCK<0>) illustrated in Fig. 7a is selected as a victim block, and the locations of the four valid pages included in the four memory blocks (MEMORY BLOCK<000, 010, 100, 110>) included therein can be identified in order to extract data from the four valid pages.

As a result of the verification, it can be seen that in the first super memory block (SUPER BLOCK<0>), only the first page (P<0>) of the first memory block (BLOCK000), the third page (P<2>) of the second memory block (BLOCK010), and the second page (P<1>) of each of the third and fourth memory blocks (BLOCK<100, 110>) are valid pages (VAILD PAGE), and all the remaining pages are invalid pages (INVALID PAGE).

According to the verification result, it can be seen that the four valid pages (VAILD PAGE) included in the first super memory block (SUPER BLOCK<0>) have different locations and the same locations. In addition, it can be seen that each of the four memory blocks (MEMORY BLOCK<000, 010, 100, 110>) included in the first super memory block (SUPER BLOCK<0>) includes one valid page. In other words, it can be seen that the largest number of valid pages in each of the four memory blocks (MEMORY BLOCK<000, 010, 100, 110>) included in the first super memory block (SUPER BLOCK<0>) is 1. This means that one read (FIRST_READ) must be performed to extract four valid data from the four valid pages included in the first super memory block (SUPER BLOCK<0>).

Accordingly, the controller (130) performs one read (FIRST_READ) on the first page (P<0>) of the first memory block (BLOCK000) included in the first super memory block (SUPER BLOCK<0>), the third page (P<2>) of the second memory block (BLOCK010), and the second page (P<1>) of each of the third and fourth memory blocks (BLOCK<100, 110>) at time 0 (t0). Through one read (FIRST_READ), four page data (B000P0_VD, B010P2_VD, B100P1_VD, B110P1_VD) are cached in four page buffers (PB<000, 010, 100, 110>). Next, the controller (130) transmits (DATA TRANSFER) all four page data (B000P0_VD, B010P2_VD, B100P1_VD, B110P1_VD) cached in the page buffers (PB<000, 010, 100, 110>) at the first time point (t1) to the internal memory (144) because all four page data (B000P0_VD, B010P2_VD, B100P1_VD, B110P1_VD) are valid data (VALID DATA).

In this way, the controller (130) can extract all four valid data (VALID DATA: B000P0_VD, B010P2_VD, B100P1_VD, B110P1_VD) stored in four valid pages (VAILD PAGE: BLOCK000_P<0>, BLOCK010_P<2>, BLOCK100_P<1>, BLOCK110_P<1>) included in the first super memory block (SUPER BLOCK<0>) through one read (FIRST_READ).

Here, the time required to perform one read (FIRST_READ) can be assumed as the read time (tREAD). In addition, the time required to transfer one page data (B000P0_VD or B010P2_VD or B100P1_VD or B110P1_VD) stored in one page buffer (PB<000> or PB<010> or PB<100> or PB<110>) to the internal memory (144) can be assumed as the transfer time (tTX). In this assumption, the first time required (TOTAL<0>) to extract data by selecting the first super memory block (SUPER BLOCK<0>) as a victim block in garbage collection will be '{read time (tREAD) * 1} + {transfer time (tTX) * 4}'. For example, assuming that the read time (tREAD) is 50us and the transfer time (tTX) is 10us, the first time required to extract data by selecting the first super memory block (SUPER BLOCK<0>) as a victim block in garbage collection (TOTAL<0>) will be 90us.

And, in the garbage collection, the second super memory block (SUPER BLOCK<1>) illustrated in Fig. 7b can be selected as a victim block to check the locations of the four valid pages included in the four memory blocks (MEMORY BLOCK<001, 011, 101, 111>) included therein in order to extract data from the four valid pages.

As a result of the verification, it can be seen that in the second super memory block (SUPER BLOCK<1>), only the first page (P<0>) of the first memory block (BLOCK001), the second and third pages (P<1, 2>) of the second memory block (BLOCK011), and the second page (P<1>) of the fourth memory block (BLOCK111) are valid pages (VAILD PAGE), and all the remaining pages are invalid pages (INVALID PAGE).

According to the verification result, it can be seen that the four valid pages (VAILD PAGE) included in the second super memory block (SUPER BLOCK<1>) have different locations and the same locations for some of them. In addition, among the four memory blocks (MEMORY BLOCK<001, 011, 101, 111>) included in the second super memory block (SUPER BLOCK<1>), the first and fourth memory blocks (BLOCK<001, 111>) each include one valid page, the second memory block (BLOCK011) includes two valid pages, and the third memory block (BLOCK101) does not include any valid pages. That is, we can see that the largest number of valid pages in each of the four memory blocks (MEMORY BLOCK<001, 011, 101, 111>) included in the second super memory block (SUPER BLOCK<1>) is 2. This means that two reads (FIRST_READ, SECOND_READ) must be performed to extract four valid data from the four valid pages included in the second super memory block (SUPER BLOCK<1>).

Accordingly, the controller (130) performs a first read (FIRST_READ) on the first page (P<0>) of the first memory block (BLOCK001) included in the second super memory block (SUPER BLOCK<1>) at time 0 (t0) and the second page (P<1>) of each of the second to fourth memory blocks (BLOCK<011, 101, 111>). Through the first read (FIRST_READ), four page data (B001P0_VD, B011P1_VD, B101P1_IVD, B111P1_VD) are cached in four page buffers (PB<001, 011, 101, 111>). Next, the controller (130) selects only three valid data (VALID DATA: B001P0_VD, B011P1_VD, B111P1_VD) among four page data (B001P0_VD, B011P1_VD, B101P1_IVD, B111P1_VD) cached in the page buffers (PB<001, 011, 101, 111>) at the first time point (t1) and transfers (DATA TRANSFER) them to the internal memory (144). Of course, the controller (130) discards one invalid data (INVALID DATA: B101P1_IVD) among the four page data (B001P0_VD, B011P1_VD, B101P1_IVD, B111P1_VD) cached in the page buffers (PB<001, 011, 101, 111>) without transmitting it to the internal memory (144).

In this way, the controller (130) can extract three valid data (VALID DATA: B001P0_VD, B011P1_VD, B111P1_VD) stored in three valid pages (VAILD PAGE: BLOCK001_P<0>, BLOCK011_P<1>, BLOCK111_P<1>) included in the second super memory block (SUPER BLOCK<1>) through the first read (FIRST_READ).

Next, the controller (130) performs a second read (SECOND_READ) on the third page (P<2>) of each of the four memory blocks (BLOCK<001, 011, 101, 111>) included in the second super memory block (SUPER BLOCK<1>) at a second time point (t2). Through the second read (SECOND_READ), four page data (B001P2_IVD, B011P2_VD, B101P2_IVD, B111P2_IVD) are cached in four page buffers (PB<001, 011, 101, 111>). Next, the controller (130) selects only one valid data (VALID DATA: B011P2_VD) among four page data (B001P2_IVD, B011P2_VD, B101P2_IVD, B111P2_IVD) cached in the page buffers (PB<001, 011, 101, 111>) at a third time point (t3) and transfers (DATA TRANSFER) it to the internal memory (144). Of course, the controller (130) discards three invalid data (INVALID DATA: B001P2_IVD, B101P2_IVD, B111P2_IVD) among the four page data (B001P2_IVD, B011P2_VD, B101P2_IVD, B111P2_IVD) cached in the page buffers (PB<001, 011, 101, 111>) without transmitting them to the internal memory (144).

In this way, the controller (130) can extract one valid data (VALID DATA: B011P2_VD) stored in one valid page (VAILD PAGE: BLOCK011_P<2>) included in the second super memory block (SUPER BLOCK<1>) through the second read (SECOND_READ).

In summary, it can be seen that the controller (130) requires two reads (FIRST_READ, SECOND_READ) to extract all four valid data (VALID DATA: B001P0_VD, B011P1_VD, B011P2_VD, B111P1_VD) stored in four valid pages (VAILD PAGE: BLOCK001_P<0>, BLOCK011_P<1>, BLOCK011_P<2>, BLOCK111_P<1>) included in the second super memory block (SUPER BLOCK<1>).

Here, the time required to perform one read (FIRST_READ or SECOND_READ) can be assumed as the read time (tREAD). Also, the time required to transfer one page data (B001P0_VD or B011P1_VD or B011P2_VD or B111P1_VD) stored in one page buffer (PB<001> or PB<011> or PB<101> or PB<111>) to the internal memory (144) can be assumed as the transfer time (tTX). In this case, the second time required (TOTAL<1>) to extract data by selecting the second super memory block (SUPER BLOCK<1>) as a victim block in garbage collection will be '{read time (tREAD) * 2} + {transfer time (tTX) * 4}'. For example, assuming that the read time (tREAD) is 50us and the transmit time (tTX) is 10us, the second time required to extract data by selecting the second super memory block (SUPER BLOCK<1>) as a victim block in garbage collection (TOTAL<1>) will be 140us.

In summary, as illustrated in Fig. 7a, the first super memory block (SUPER BLOCK<0>) and as illustrated in Fig. 7b, the second super memory block (SUPER BLOCK<1>), each contain four valid pages, so it can be seen that the same conditions apply when selecting a victim block for garbage collection based on the number of valid pages.

However, when each of the super memory blocks (SUPER BLOCK<0, 1>) illustrated in FIGS. 7a and 7b is selected as a sacrifice block for garbage collection, the first time required (TOTAL<0>) to extract data from the first super memory block (SUPER BLOCK<0>) illustrated in FIG. 7a is 90us, whereas the second time required (TOTAL<1>) to extract data from the second super memory block (SUPER BLOCK<1>) illustrated in FIG. 7b is 140us, which is a very large difference.

That is, in order to effectively perform garbage collection, it is desirable for the controller (130) to select the first super memory block (SUPER BLOCK<0>) among the super memory blocks (SUPER BLOCK<0, 1>) illustrated in FIGS. 7a and 7b as a sacrifice block.

FIG. 8 is a diagram illustrating an operation of selecting a victim block when performing garbage collection on a super memory block in a memory system according to the second embodiment of the present invention described through FIGS. 7a and 7b.

Referring to FIG. 8, a memory system (110) according to the second embodiment of the present invention includes a controller (130) and a memory device (150).

And, the controller (130) may include a garbage collection control unit (196) and a memory (144). Here, the general operation of the garbage collection control unit (196) has been described through the aforementioned FIG. 3, so it will not be described in more detail here.

And, as described through FIG. 4, the memory device (150) includes a plurality of memory blocks (MEMORY BLOCK<000, 001,...>). In addition, the controller (130) groups N memory blocks capable of parallel reading among the memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150) according to set conditions and manages them as a plurality of super memory blocks (SUPER BLOCK<0:N>). At this time, N is a natural number greater than or equal to 2, and it is assumed in FIGS. 7a and 7b that N is 4. Here, it is assumed that one super memory block (SUPER BLOCK<2>) in a free state is included in the memory device (150) together with two super memory blocks (SUPER BLOCK<0, 1>) described through FIGS. 7a and 7b. Of course, the details exemplified in Fig. 8 are simplified for convenience of explanation, and in reality, they can be expanded into any number of different forms (such as a form in which a greater number of super memory blocks are included in a memory device).

Specifically, the controller (130) generates required predicted times (PRE_TOTAL<0, 1>) by predicting the time required for extracting valid data from memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150) for garbage collection by superblock unit through the garbage collection control unit (196) included therein, and manages the generated required predicted times (PRE_TOTAL<0, 1>) as a required predicted time table (600).

In addition, the controller (130) counts the number of valid pages (VPC<0:1>) of each memory block (MEMORY BLOCK<000, 001,...>) included in the memory device (150) in superblock units through the garbage collection control unit (196), and manages the counted number of valid pages (VPC<0:1>) as a valid page count table (610).

More specifically, the controller (130) calculates the first time (FIRST_TIME<0:1>) by multiplying the largest number (MB_CNT<0:1>) among the valid page numbers of each of four memory blocks (BLOCK<000, 010, 100, 110>, BLOCK<001, 011, 101, 111>) grouped in each of a plurality of super memory blocks (SUPER BLOCK<0:1>) by the read prediction time (PRE_tREAD) (FIRST_TIME<0:1> = MB_CNT<0:1> * PRE_tREAD).

In addition, the controller (130) calculates a second time (SECOND_TIME<0:1>) by multiplying the number of valid pages (VPC<0:1>) of each of a plurality of super memory blocks (SUPER BLOCK<0:1>) by the predicted transmission time (PRE_tTX) (SECOND_TIME<0:1> = VPC<0:1> * PRE_tTX).

In addition, the controller (130) calculates a value that adds the first time (FIRST_TIME<0:1>) and the second time (SECOND_TIME<0:1>) (TOTAL<0:1> = FIRST_TIME<0:1> + SECOND_TIME<0:1>) and generates the predicted required times (PRE_TOTAL<0, 1>) for each of a plurality of super memory blocks (SUPER BLOCK<0:1>).

For example, referring to FIG. 7a together with FIG. 8 to explain, it can be seen that in the first super memory block (SUPER BLOCK<0>), only the first page (P<0>) of the first memory block (BLOCK000), the third page (P<2>) of the second memory block (BLOCK010), and the second page (P<1>) of each of the third and fourth memory blocks (BLOCK<100, 110>) are valid pages (VAILD PAGE), and all the remaining pages are invalid pages (INVALID PAGE).

Therefore, the controller (130) can know that the number of first valid pages (VPC<0>) included in the first super memory block (SUPER BLOCK<0>) is 4.

In addition, the controller (130) can know that each of the four memory blocks (BLOCK<000, 010, 100, 110>) grouped in the first super memory block (SUPER BLOCK<0>) includes one valid page. That is, it can be known that the largest number (MB_CNT<0>) among the numbers of valid pages of each of the four memory blocks (MEMORY BLOCK<000, 010, 100, 110>) included in the first super memory block (SUPER BLOCK<0>) is 1.

Therefore, the first first time (FIRST_TIME<0>) corresponding to the first super memory block (SUPER BLOCK<0>) becomes the time corresponding to one read prediction time (PRE_tREAD) through calculation such as '1 * PRE_tREAD'. In addition, the first second time (SECOND_TIME<0>) corresponding to the first super memory block (SUPER BLOCK<0>) becomes the time corresponding to four transmission prediction times (PRE_tTX) through calculation such as '4 * PRE_tTX'. In conclusion, the first predicted time (PRE_TOTAL<0>) corresponding to the first super memory block (SUPER BLOCK<0>) is the sum of the first first time (FIRST_TIME<0>) corresponding to one read predicted time (PRE_tREAD) and the first second time (SECOND_TIME<0>) corresponding to four transmission predicted times (PRE_tTX).

For example, assuming that the read prediction time (PRE_tREAD) is 50us and the transmission prediction time (PRE_tTX) is 10us, the first predicted time required (PRE_TOTAL<0>) corresponding to the first super memory block (SUPER BLOCK<0>) will be 90us, which is the sum of the first first time (FIRST_TIME<0>) of 50us and the first second time (SECOND_TIME<0>) of 40us.

Similarly, referring to FIG. 7b together with FIG. 8 for illustration purposes, it can be seen that, in the second super memory block (SUPER BLOCK<1>), only the first page (P<0>) of the first memory block (BLOCK001), the second and third pages (P<1, 2>) of the second memory block (BLOCK011), and the second page (P<1>) of the fourth memory block (BLOCK111) are valid pages (VAILD PAGE), and all the remaining pages are invalid pages (INVALID PAGE).

Accordingly, the controller (130) can know that the number of second valid pages (VPC<1>) included in the second super memory block (SUPER BLOCK<1>) is 4.

In addition, the controller (130) can know that among the four memory blocks (MEMORY BLOCK<001, 011, 101, 111>) included in the second super memory block (SUPER BLOCK<1>), the first and fourth memory blocks (BLOCK<001, 111>) each include one valid page, the second memory block (BLOCK011) includes two valid pages, and the third memory block (BLOCK101) does not include a valid page. That is, it can be known that the largest number (MB_CNT<1>) among the numbers of valid pages of each of the four memory blocks (MEMORY BLOCK<001, 011, 101, 111>) included in the second super memory block (SUPER BLOCK<1>) is 2.

Therefore, the second first time (FIRST_TIME<1>) corresponding to the second super memory block (SUPER BLOCK<1>) becomes the time corresponding to two read prediction times (PRE_tREAD) through calculations such as '2 * PRE_tREAD'. In addition, the second second time (SECOND_TIME<1>) corresponding to the second super memory block (SUPER BLOCK<1>) becomes the time corresponding to four transmission prediction times (PRE_tTX) through calculations such as '4 * PRE_tTX'. In conclusion, the second estimated time (PRE_TOTAL<1>) corresponding to the second super memory block (SUPER BLOCK<1>) is the sum of the second first time (FIRST_TIME<1>) corresponding to two read estimated times (PRE_tREAD) and the second second time (SECOND_TIME<1>) corresponding to four transmission estimated times (PRE_tTX).

For example, assuming that the read prediction time (PRE_tREAD) is 50us and the transmission prediction time is 10us, the second predicted time required (PRE_TOTAL<1>) corresponding to the second super memory block (SUPER BLOCK<1>) will be 140us, which is the sum of the second first time (FIRST_TIME<1>) of 100us and the second second time (SECOND_TIME<1>) of 40us.

For reference, the controller (130) may set information on the read prediction time (PRE_tREAD) and the transmission prediction time (PRE_tTX) for the memory device (150). That is, the designer may set the read prediction time (PRE_tREAD) and the transmission prediction time (PRE_tTX) for the memory device (150) in advance through a test depending on the type or state of the memory device (150).

As described above, the controller (130) can predict the expected time required (PRE_TOTAL<0, 1>) for each of a plurality of super memory blocks (SUPER BLOCK<0:1>) before performing garbage collection.

And, the controller (130) can refer to the estimated times (PRE_TOTAL<0, 1>) for a plurality of super memory blocks (SUPER BLOCK<0:1>) included in the estimated time table (600) through the garbage collection control unit (196) included therein to determine which memory block among the memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150) to select as a sacrifice block for garbage collection.

At this time, the controller (130) may refer to the required predicted times (PRE_TOTAL<0, 1>) for a number of super memory blocks (SUPER BLOCK<0:1>) included in the required predicted time table (600) in the following two ways, and may select one of the two ways.

The first method is a method in which a controller (130) selects a memory block including at least one valid page among N memory blocks grouped in a super memory block corresponding to a relatively smallest value of the required predicted time (PRE_TOTAL<0, 1>) among a plurality of super memory blocks (SUPER BLOCK<0:1>) as a victim block.

For example, as described above, the expected time required (PRE_TOTAL<0>) for the first super memory block (SUPER BLOCK<0>) is 90us, and the expected time required (PRE_TOTAL<1>) for the second super memory block (SUPER BLOCK<1>) is 140us, so the expected time required (PRE_TOTAL<0>) for the first super memory block (SUPER BLOCK<0>) is smaller. Accordingly, the controller (130) selects four memory blocks (MEMORY BLOCK<000, 010, 100, 110>) that include at least one valid page among the four memory blocks (MEMORY BLOCK<000, 010, 100, 110>) grouped in the first super memory block (SUPER BLOCK<0>) as victim blocks.

In this way, since the four memory blocks (MEMORY BLOCK<000, 010, 100, 110>) included in the first super memory block (SUPER BLOCK<0>) are selected as sacrifice blocks, in the section where garbage collection is performed, the four valid pages included in the first super memory block (SUPER BLOCK<0>) will be transferred to the memory (144) within the controller (130) and then stored in the third super memory block (SUPER BLOCK<2>), which is the target block.

The second method is a method in which, before using the first method described above, the controller (130) checks the number of super memory blocks whose combined number of valid pages (VPC<0:1>) of each of the N memory blocks included in each of the plurality of super memory blocks (SUPER BLOCK<0:1>) is less than or equal to a 'set number'. That is, the controller (130) does not use the first method described above if there is 'one' super memory block less than or equal to the 'set number' among the valid number of pages (VPC<0:1>) of each of the plurality of super memory blocks (SUPER BLOCK<0:1>). On the other hand, the controller (130) uses the first method described above if there are 'at least two' super memory blocks less than or equal to the 'set number' among the valid number of pages (VPC<0:1>) of each of the plurality of super memory blocks (SUPER BLOCK<0:1>).

For example, unlike in the above-described description, the number of valid pages (VPC<0>) of the first super memory block (SUPER BLOCK<0>) may be 5, and the number of valid pages (VPC<1>) of the second super memory block (SUPER BLOCK<1>) may be 1. In addition, the controller (130) may set the 'set number' to 2. In this case, the controller (130) may confirm that one super memory block, that is, the second super memory block (SUPER BLOCK<1>), has a number of valid pages less than or equal to the 'set number'. Therefore, the controller (130) selects, as a victim block, a memory block including at least one valid page among the N memory blocks included in the second super memory block (SUPER BLOCK<1>) having a number of valid pages less than or equal to the 'set number', without using the first method described above.

On the other hand, as described above, the number of valid pages (VPC<0>) of the first super memory block (SUPER BLOCK<0>) may be 4, and the number of valid pages (VPC<1>) of the second super memory block (SUPER BLOCK<1>) may also be 4. In addition, the controller (130) may set the 'set number' to 2. In this case, the controller (130) may confirm that both the first super memory block (SUPER BLOCK<0>) and the second super memory block (SUPER BLOCK<1>) have a number of valid pages less than or equal to the 'set number'. Therefore, the controller (130) selects, as a victim block, a memory block including at least one valid page among the N memory blocks included in the first super memory block (SUPER BLOCK<0>) having a relatively smaller estimated time required (PRE_TOTAL<0>).

Meanwhile, as described above, the controller (130) generates required predicted times (PRE_TOTAL<0, 1>) and manages the generated required predicted times (PRE_TOTAL<0, 1>) as a required predicted time table (600).

At this time, the controller (130) can update the estimated time required (PRE_TOTAL<0, 1>) using one of the following two methods.

In the first method, the controller (130) can update the expected time required for a super memory block in which a specific memory block is grouped whenever a specific memory block with a variable number of valid pages occurs among the memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150).

For example, referring to FIG. 4 and FIG. 7A together, the number of valid pages of a first memory block (BLOCK000) of a first plane (PLANE00) of a first memory die (DIE0) may vary depending on whether a first foreground operation or a background operation is performed. Subsequently, the number of valid pages of a second memory block (BLOCK001) of a first plane (PLANE00) of the first memory die (DIE0) may vary depending on whether a second foreground operation or a background operation is performed.

In this case, the controller (130) can re-predict the value of the first estimated time required (PRE_TOTAL<0>) corresponding to the first super memory block (SUPER BLOCK<0>) in which the memory block (BLOCK000) is grouped in response to the change in the valid page of the first memory block (BLOCK000) of the first plane (PLANE00) of the first memory die (DIE0). Then, the controller (130) can re-predict the value of the second estimated time required (PRE_TOTAL<1>) corresponding to the second super memory block (SUPER BLOCK<1>) in which the memory block (BLOCK001) is grouped in response to the change in the number of valid pages of the second memory block (BLOCK001) of the first plane (PLANE00) of the first memory die (DIE0).

In the second method, the controller (130) checks whether there is a specific memory block among the memory blocks (MEMORY BLOCK<000, 001,...>) with a variable number of valid pages at each 'set point in time', and if the result of the check shows that there is a specific memory block with a variable number of valid pages, the controller can update the expected time required for the super memory block in which the specific memory block is grouped.

For example, referring to FIG. 4 and FIG. 7a together, at least two consecutive foreground operations or background operations may be performed between a first set point in time (not shown) and a second set point in time (not shown) so that the number of valid pages of a first memory block (BLOCK000) of a first plane (PLANE00) of a first memory die (DIE0) and the number of valid pages of a second memory block (BLOCK001) may be varied.

In this case, the controller (130) checks whether there is a memory block among the memory blocks (MEMORY BLOCK<000, 001,...>) with a variable number of valid pages at the second set time point, and based on the check result, it can be known that the number of valid pages of each of the first memory block (BLOCK000) and the second memory block (BLOCK001) of the first plane (PLANE00) of the first memory die (DIE0) has varied. Accordingly, the controller (130) can simultaneously re-predict the value of the first predicted time required (PRE_TOTAL<0>) corresponding to the first super memory block (SUPER BLOCK<0>) in which the first memory block (BLOCK000) of the first plane (PLANE00) of the first memory die (DIE0) is grouped at the second set time point, and the value of the second predicted time required (PRE_TOTAL<1>) corresponding to the second super memory block (SUPER BLOCK<1>) in which the second memory block (BLOCK001) of the first plane (PLANE00) of the first memory die (DIE0) is grouped.

For reference, a 'set point in time' is a point in time that can be predefined by the designer, and can be a point in time that is repeated whenever data of a set size is written, or a point in time that is repeated whenever the performance of a specific operation is completed.

Meanwhile, when garbage collection is performed and all valid pages included in the first super memory block (SUPER BLOCK<0>) selected as a victim block are transferred to the memory (144) within the controller (130) and then moved to the third super memory block (SUPER BLOCK<2>), which is a target block, there will be no more valid pages in the first super memory block (SUPER BLOCK<0>). Therefore, the first super memory block (SUPER BLOCK<0>) after garbage collection does not need to be involved in any operation as an invalid super memory block other than the operation of becoming a free super memory block through an erase operation. However, since the controller (130) generates the first estimated time required (PRE_TOTAL<0>) for the first super memory block (SUPER BLOCK<0>) before performing garbage collection, its value may remain in the estimated time required table (600) even after performing garbage collection. In this way, an unknown abnormal operation may be performed for the first super memory block (SUPER BLOCK<0>) due to the value of the first estimated time required (PRE_TOTAL<0>) remaining in the estimated time required table (600). Accordingly, the controller (130) sets the first estimated time required (PRE_TOTAL<0>) corresponding to the first super memory block (SUPER BLOCK<0>) to a ‘planned value’ after garbage collection is performed on the first super memory block (SUPER BLOCK<0>) selected as the sacrifice block, thereby preventing an unknown abnormal operation from being performed on the first super memory block (SUPER BLOCK<0>).

In summary, the controller (130) can set the expected time required for a specific super memory block to an 'expected value' to prevent the specific super memory block from performing an unknown erroneous operation when the specific super memory block is selected as a sacrifice block and all valid pages inside are moved to the target super memory block through garbage collection.

Meanwhile, if the number of free memory blocks among the memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150) is sufficiently large, the probability of performing garbage collection is not high. That is, garbage collection is generally an operation performed when the number of free memory blocks included in the memory device (150) is reduced below a 'certain number'.

Accordingly, the controller (130) according to the second embodiment of the present invention generates and manages the aforementioned required predicted times (PRE_TOTAL<0, 1>) in a section where the number of free memory blocks among the memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150) is equal to or less than the 'first number'. Of course, the controller (130) does not generate and manage the required predicted times (PRE_TOTAL<0, 1>) in a section where the number of free memory blocks among the memory blocks (MEMORY BLOCK<000, 001,...>) included in the memory device (150) is equal to or greater than the 'second number' which is greater than the 'first number'.

Note that the 'first number' may be set differently from the 'schedule number' used to determine the trigger point of a general garbage collection operation. For example, the 'schedule number' may be smaller than the 'first number'.

The present invention described above is not limited to the above-described embodiments and the attached drawings, and it will be apparent to a person skilled in the art to which the present invention pertains that various substitutions, modifications, and changes are possible within a scope that does not depart from the technical spirit of the present invention.

Claims (20)

A nonvolatile memory device comprising a plurality of pages, each page including a plurality of memory cells, a plurality of blocks, each page including the pages, a plurality of planes, each page including the blocks, and a plurality of dies, each page including the planes, and including page buffers for catching data output from the blocks in units of pages;
A controller is included that groups N blocks among the above blocks that can be read in parallel according to set conditions and manages them as a plurality of super blocks, generates predicted times by calculating the time required to extract valid data from the blocks for garbage collection in units of super blocks, and selects a victim block for the garbage collection among the blocks with reference to the predicted times.
The above controller,
A memory system that generates and manages the predicted times required in a section where the number of free blocks among the above blocks is equal to or less than a first number, and does not manage the predicted times required in a section where the number of free blocks among the above blocks is equal to or greater than a second number greater than the first number, and where N is a natural number greater than or equal to 2.
In the first paragraph,
The above controller,
In the case where parallel reading is possible only for pages in the same position in each of the N blocks grouped in the first superblock among the above superblocks, a first time is calculated by multiplying a read prediction time by a first number obtained by subtracting the number of valid pages in the same position in the N blocks grouped in the first superblock from a first number obtained by adding all the numbers of valid pages in each of the N blocks, and a second time is calculated by multiplying the first number by a transmission prediction time, and then adding the first time and the second time to generate a required predicted time corresponding to the first superblock, and applying the required predicted time generation method applied to the first superblock to each of the above superblocks to generate the required predicted times,
The above lead prediction time is the time predicted to be taken to cache the data of the above blocks in the above page buffers.
The above transmission prediction time is a memory system that predicts the time it will take to transmit data cached in the page buffers to the controller.
In the first paragraph,
The above controller,
In the case where parallel reading is possible for pages at different locations in each of the N blocks grouped in the second superblock among the above superblocks, a third time is calculated by multiplying the read prediction time by the largest number of valid pages of each of the N blocks, and a fourth time is calculated by multiplying the transmission prediction time by the sum of the valid pages of each of the N blocks, and then the third time and the fourth time are added to generate the required predicted times corresponding to the second superblock, and the required predicted times are generated by applying the method of generating the required predicted times applied to the second superblock to each of the above superblocks,
The above lead prediction time is the time predicted to be taken to cache the data of the above blocks in the above page buffers.
The above transmission prediction time is a memory system that predicts the time it will take to transmit data cached in the page buffers to the controller.
In the first paragraph,
The above controller,
A memory system that re-predicts the value of the required prediction time corresponding to the superblock in which the blocks with the variable number of valid pages are grouped whenever a block with a variable number of valid pages occurs among the above blocks.
In the first paragraph,
The above controller,
A memory system that checks whether there is a block with a variable number of valid pages among the above blocks at each set point in time, and if there is a block with a variable number of valid pages among the above blocks, re-predicts the value of the expected time corresponding to the superblock in which the blocks with a variable number of valid pages are grouped.
In the first paragraph,
The above controller,
A memory system that selects a block including at least one valid page among N blocks grouped in a superblock corresponding to a relatively smallest predicted time among the above predicted times as the sacrifice block.
In the first paragraph,
The above controller,
A superblock in which the sum of the number of valid pages of each of the N blocks grouped in each of the above superblocks is less than or equal to a set number,
In case of 1, select N blocks grouped in 1 selected superblock as the sacrifice block,
A memory system for selecting, as the victim block, a block including at least one valid page among N blocks grouped in a superblock corresponding to a relatively smallest value among the values of at least two or more required prediction times corresponding to at least two or more superblocks, when there are at least two or more.
In the first paragraph,
The above controller,
A memory system that sets the expected time corresponding to the third superblock to a target value when N blocks grouped in the third superblock among the above superblocks are selected as the sacrifice blocks and all valid data is moved to the target block through the garbage collection.
delete In the first paragraph,
A first die among the dies is connected to a first channel, a second die among the dies is connected to a second channel, planes included in the first die are connected to a plurality of first ways sharing the first channel, and planes included in the second die are connected to a plurality of second ways sharing the second channel.
The above controller,
Including in the set condition grouping a first block included in the first plane of the first die and a second block included in the second plane of the first die, and grouping a third block included in the third plane of the second die and a fourth block included in the fourth plane of the second die, or
Including in the set condition grouping a first block included in the first plane of the first die and a third block included in the third plane of the second die, and grouping a second block included in the second plane of the first die and a fourth block included in the fourth plane of the second die, or
A memory system including in the set condition grouping a first block included in a first plane of the first die, a second block included in a second plane of the first die, a third block included in a third plane of the second die, and a fourth block included in a fourth plane of the second die.
A method of operating a memory system including a controller and a nonvolatile memory device including a plurality of pages each including a plurality of memory cells, a plurality of blocks each including the pages, a plurality of planes each including the blocks, and a plurality of dies each including the planes, and including page buffers for catching data output from the blocks in units of pages,
A step of grouping N blocks among the above blocks capable of parallel reading according to set conditions and managing them as a plurality of super blocks;
A generation step for generating predicted times by predicting the time required to extract valid data from the above blocks for garbage collection in units of superblocks; and
It includes a selection step of selecting a victim block for the garbage collection among the blocks by referring to the above-mentioned estimated times,
The above generation steps are:
A step of generating and managing the required predicted times in a section where the number of free blocks among the above blocks is less than or equal to a first number; and
A method of operating a memory system, comprising a step of not managing the required predicted times in a section in which the number of free blocks among the above blocks is a second number or greater than the first number, and N is a natural number greater than or equal to 2.
In Article 11,
If parallel reading is possible only for pages at the same location in each of the N blocks grouped in the first superblock among the above superblocks, the generation step is
A step of calculating a first time by multiplying a first number obtained by adding the number of valid pages of each of the N blocks grouped in the first superblock to a number obtained by subtracting the number of valid pages having the same location in the N blocks grouped in the first superblock, by the read prediction time;
A step of calculating a second time by multiplying the transmission prediction time by the first number;
A step of generating a required predicted time corresponding to the first superblock by adding the first time and the second time; and
A step of generating the predicted times required by applying the method of generating the predicted times required applied to the first superblock to each of the superblocks is included.
The above read prediction time is the time predicted to be taken to cache data of the blocks in the page buffers, and the above transfer prediction time is the time predicted to be taken to transmit data cached in the page buffers to the controller. The operation method of the memory system.
In Article 11,
If parallel reading is possible for pages at different locations in each of the N blocks grouped in the second superblock among the above superblocks, the generation step is
A third step of calculating a third time by multiplying the largest number of valid pages of each of the N blocks grouped in the second superblock by the read prediction time;
A fourth time step of calculating the transmission prediction time multiplied by the sum of the number of valid pages of each of the N blocks grouped in the second superblock;
A step of generating a required predicted time corresponding to the second superblock by adding the third time and the fourth time; and
It includes a step of generating the predicted time required by applying the method of generating the predicted time required applied to the second superblock to each of the superblocks,
The above read prediction time is the time predicted to be taken to cache data of the blocks in the page buffers, and the above transfer prediction time is the time predicted to be taken to transmit data cached in the page buffers to the controller. The operation method of the memory system.
In Article 11,
A method of operating a memory system further comprising the step of re-predicting the value of the required prediction time corresponding to the superblock in which the block with the variable number of valid pages is grouped whenever a block with a variable number of valid pages occurs among the above blocks.
In Article 11,
An operating method of a memory system further comprising the step of checking whether there is a block among the blocks with a variable number of valid pages at each set time point, and, if there is a block among the blocks, re-predicting the value of the required predicted time corresponding to the superblock in which the block with a variable number of valid pages is grouped.
In Article 11,
The above selection step is,
An operating method of a memory system, characterized in that a block including at least one valid page among N blocks grouped in a superblock corresponding to a relatively smallest predicted time among the above predicted times required is selected as the sacrifice block.
In Article 11,
The above selection step is,
A step of selecting N blocks grouped in one selected superblock as the victim block, if there is one superblock in which the sum of the number of valid pages of each of N blocks grouped in each of the above superblocks is less than or equal to a set number; and
A method of operating a memory system, comprising the step of selecting, as the victim block, a block including at least one valid page among the N blocks grouped in a superblock corresponding to a relatively smallest value among the values of the required predicted time corresponding to the at least two or more superblocks, when there are at least two superblocks in which the sum of the numbers of valid pages of each of the N blocks grouped in each of the above superblocks is less than or equal to a set number.
In Article 11,
A method of operating a memory system further comprising the step of setting a predicted time corresponding to the third superblock to a target value when N blocks grouped in a third superblock among the above superblocks are selected as the sacrifice blocks and all valid data is moved to the target block through the garbage collection.
delete In Article 11,
A first die among the dies is connected to a first channel, a second die among the dies is connected to a second channel, planes included in the first die are connected to a plurality of first ways sharing the first channel, and planes included in the second die are connected to a plurality of second ways sharing the second channel.
The conditions set above are:
Grouping a first block included in a first plane of the first die and a second block included in a second plane of the first die, and grouping a third block included in a third plane of the second die and a fourth block included in a fourth plane of the second die, or
Grouping a first block included in a first plane of the first die and a third block included in a third plane of the second die, and grouping a second block included in a second plane of the first die and a fourth block included in a fourth plane of the second die, or
An operating method of a memory system, comprising grouping a first block included in a first plane of the first die, a second block included in a second plane of the first die, a third block included in a third plane of the second die, and a fourth block included in a fourth plane of the second die.

Images