Reordering a descriptor queue while searching the queue of descriptors corresponding to map segments

Provided herein may be a memory controller configured to control a memory device. The memory controller may include a map buffer, a descriptor queue, and a descriptor controller. The map buffer may sequentially store map segments of a plurality of map segments stored in the memory device. The descriptor queue may store descriptors corresponding to the respective map segments, based on a plurality of addresses of the map buffer. The descriptor controller may search for a target descriptor among the stored descriptors based on a logical address received from a host, and reorder the stored descriptors while searching for the target descriptor.

CROSS-REFERENCE TO RELATED APPLICATION

The present application claims priority under 35 U.S.C. § 119(a) to Korean patent application number 10-2020-0035952, filed on Mar. 25, 2020, which is incorporated herein by reference in its entirety.

BACKGROUND

1. Field of Invention

Various embodiments of the present disclosure generally relate to an electronic device, and more particularly, to a memory system, a memory controller and a method of operating the memory controller.

2. Description of Related Art

Generally, a storage device stores data under control of a host device such as a computer or a smartphone. The storage device may include a memory device configured to store data, and a memory controller configured to control the memory device. Generally, there are types of memory devices: volatile memory devices and nonvolatile memory devices.

A volatile memory device retains data only when power is supplied thereto; data stored therein is lost when power is turned off. Examples of a volatile memory device include a static random access memory (SRAM), and a dynamic random access memory (DRAM).

A nonvolatile memory device continues to store data even when power is turned off. Examples of a nonvolatile memory device include a read-only memory (ROM), a programmable ROM (PROM), an electrically programmable ROM (EPROM), an electrically erasable programmable ROM (EEPROM), and a flash memory.

SUMMARY

Various embodiments of the present disclosure are directed to a memory controller having improved map search performance, and a method of operating the memory controller.

An embodiment of the present disclosure may provide for a memory controller configured to control a memory device. The memory controller may include: a map buffer, a descriptor queue, and a descriptor controller. The map buffer may sequentially store map segments of a plurality of map segments stored in the memory device. The descriptor queue may store descriptors corresponding to the respective map segments, based on a plurality of addresses of the map buffer. The descriptor controller may search for a target descriptor among the stored descriptors based on a logical address received from a host, and reorder the stored descriptors while searching for the target descriptor.

An embodiment of the present disclosure may provide for a method of operating a memory controller including a map buffer and a descriptor queue. The method may include: sequentially storing map segments loaded from the memory device in the map buffer; storing descriptors corresponding to the respective loaded map segments in the descriptor queue, based on a plurality of addresses of the map buffer; searching for a target descriptor among the stored descriptors based on a logical address received from a host; and reordering the stored descriptors while searching for the target descriptor.

An embodiment of the present disclosure may provide for a memory system. The memory system may include: a memory device, a controller. The controller may include a map buffer and a descriptor queue. The controller may load a plurality of map segments in the map buffer. The controller may store descriptors for the loaded map segments in the descriptor queue. The controller may search for a target descriptor for a logical address from a host, among the stored descriptors. The controller may reorder the stored descriptors in the descriptor queue, based on the search result of the target descriptor, to arrange the descriptors in a set order.

DETAILED DESCRIPTION

Specific structural and functional description is provided only for describing embodiments of the present disclosure. The present invention, however, may be implemented in different forms and ways than described herein. Thus, the present invention is not limited by or to any of the disclosed embodiments. Also, throughout the specification, reference to “an embodiment,” “another embodiment” or the like is not necessarily to only one embodiment, and different references to any such phrase are not necessarily to the same embodiment(s).

FIG.1is a diagram illustrating a storage device50in accordance with an embodiment of the present disclosure.

Referring toFIG.1, the storage device50may include a memory device100and a memory controller200configured to control the operation of the memory device100. The storage device50may store data under control of a host300such as a cellular phone, a smartphone, an MP3 player, a laptop computer, a desktop computer, a game machine, a TV, a tablet PC, or an in-vehicle infotainment system.

The storage device50may be configured as any of various kinds of storage devices depending on a host interface, which is a communication system for communicating with the host300. For example, the data storage device50may be configured as an SSD, MMC, eMMC, RS-MMC, or micro-MMC type multimedia card, an SD, mini-SD, micro-SD type secure digital card, a universal serial bus (USB) storage device, a universal flash storage (UFS) device, a personal computer memory card international association (PCMCIA) card type storage device, a peripheral component interconnection (PCI) card type storage device, a PCI-express (PCI-e or PCIe) type storage device, a compact flash (CF) card, a smart media card, and/or a memory stick.

The storage device50may be manufactured in the form of any of various package types. For instance, the storage device50may be manufactured in the form of a package on package (POP) type, a system in package (SIP) type, a system on chip (SOC) type, a multi-chip package (MCP) type, a chip on board (COB) type, a wafer-level fabricated package (WFP) type, and/or a wafer-level stack package (WSP) type.

The memory device100may store data therein. The memory device100may operate under control of the memory controller200. The memory device100may include a memory cell array including a plurality of memory cells configured to store data therein.

Each memory cell may be a single level cell (SLC) capable of storing a single data bit, a multi-level cell (MLC) capable of storing two data bits, a triple-level cell (TLC) capable of storing three data bits, or a quad-level cell (QLC) capable of storing four data bits. In an embodiment, all memory cells of the memory cell array are of the same level.

The memory cell array may include a plurality of memory blocks. Each memory block may include a plurality of memory cells. Each memory block may include a plurality of pages. In an embodiment, each page may be the unit of sorting data in the memory device100or reading stored data from the memory device100.

The memory device100may receive a command and an address from the memory controller200and access an area of the memory cell array that is selected by the address. In other words, the memory device100may perform an operation instructed by the command on the area selected by the address. For example, the memory device100may perform a write (or program) operation, a read operation, and an erase operation. During a program operation, the memory device100may program data to an area selected by an address. During a read operation, the memory device100may read data from an area selected by an address. During an erase operation, the memory device100may erase data from an area selected by an address.

In an embodiment, the memory device100may store a plurality of map segments including mapping data between logical addresses received from the host300and physical addresses of the memory device100.

The memory controller200may control overall operation of the storage device50.

When power is applied to the storage device50, the memory controller200may execute firmware (FW). In the case where the memory device100is a flash memory device, the memory controller200may execute firmware such as a flash translation layer (FTL) for controlling communication between the host300and the memory device100.

In an embodiment, the memory controller200may receive data and a logical block address (LBA) from the host300, and translate the LBA into a physical block address (PBA) indicating addresses of memory cells to which data is to be stored, the memory cells being included in the memory device100.

The memory controller200may control the memory device100to perform a program operation, a read operation, or an erase operation in response to a request from the host300. During the program operation, the memory controller200may provide a write command, a PBA, and data to the memory device100. During the read operation, the memory controller200may provide a read command and a PBA to the memory device100. During the erase operation, the memory controller200may provide an erase command and a PBA to the memory device100.

In an embodiment, the memory controller200may autonomously generate a command, an address and data in the absence of a request from the host300, and transmit them to the memory device100. For example, the memory controller200may provide a command, an address and data to the memory device100to perform background operations such as a program operation for wear leveling, and a program operation for garbage collection.

In an embodiment, the memory controller200may control two or more memory devices100. In this case, the memory controller200may control the memory devices100in an interleaving manner so as to enhance the operating performance. The interleaving scheme may be an operating scheme at least two memory devices100operate in an overlapping period of time.

In an embodiment, the memory controller200may include a map buffer210and a map manager220.

The map buffer210may store map segments among the plurality of map segments stored in the memory device100. The map buffer210may include a storage area corresponding to each of a plurality of addresses. The map buffer210may store each map segment in the storage area corresponding to each address in a loaded sequence.

The map manager220may search for map data corresponding to a logical address received from the host300among the plurality of map segments stored in the map buffer210. The map manager220may include a descriptor queue that store descriptors corresponding to the respective map segments based on the plurality of addresses of the map buffer210. The descriptor queue may store descriptors corresponding to map segments in a sequence in which the map segments are loaded from the memory device100. The descriptor may be an index indicating a map segment.

The map manager220may determine a target descriptor based on a logical address. The target descriptor may be an index indicating a map segment including a logical address. In an embodiment, the target descriptor may be a portion of a logical address value.

The map manager220may search for a target descriptor in the descriptor queue. The map manager220may read a descriptor corresponding to a selected address among the plurality of addresses in the descriptor queue. The map manager220may determine whether the read descriptor matches the target descriptor.

If the read descriptor matches the target descriptor, the map manager220may search for a map segment including a logical address received from the host300among the map segments stored in the map buffer210, based on an address of a map buffer corresponding to the read descriptor. The map manager220may search for map data corresponding to the logical address in the corresponding map segment.

If the read descriptor differs from the target descriptor, the map manager220may change the selected address associated with the target descriptor and search again for a read descriptor that matches the target descriptor. This process may continue until the map manager220finds a descriptor that matches the target descriptor or it is determined there is no match. In the latter case, the map manager220may load, from the memory device100, a map segment indicated by the target descriptor among the plurality of map segments stored in the memory device100.

The map manager220may reorder the descriptors stored in the descriptor queue in connection with searching for the target descriptor among the descriptors stored in the descriptor queue. In an embodiment, the map manager220may order the descriptors stored in the descriptor queue in an ascending order based on their respective addresses. In another embodiment, the map manager220may order the descriptors stored in the descriptor queue in a descending order based on their respective addresses. The order of descriptors is described with reference toFIGS.5A to5I and7A to7K.

The host300may communicate with the storage device50using at least one of various communication methods such as universal serial bus (USB), serial AT attachment (SATA), serial attached SCSI (SAS), high speed interchip (HSIC), small computer system interface (SCSI), peripheral component interconnection (PCI), PCI express (PCIe), nonvolatile memory express (NVMe), universal flash storage (UFS), secure digital (SD), multimedia card (MMC), embedded MMC (eMMC), dual in-line memory module (DIMM), registered DIMM (RDIMM), and/or load reduced DIMM (LRDIMM) communication methods.

FIG.2is a diagram illustrating a configuration of the memory device100ofFIG.1.

Referring toFIG.2, the memory device100may include a memory cell array110, a peripheral circuit120, and control logic130. The peripheral circuit120may include an address decoder121, a voltage generator122, a read/write circuit123, a data input/output circuit124, and a sensing circuit125.

The memory cell array110may include a plurality of memory blocks BLK1to BLKz. The plurality of memory blocks BLK1to BLKz are coupled to the address decoder121through row lines RL. The memory blocks BLK1to BLKz may be coupled to the read/write circuit123through bit lines BL1to BLm. Each of the memory blocks BLK1to BLKz may include a plurality of memory cells. In an embodiment, the plurality of memory cells may be nonvolatile memory cells. Memory cells coupled to the same word line among the plurality of memory cells are defined as one page. In other words, the memory cell array110may be formed of a plurality of physical pages. In an embodiment, each of the memory blocks BLK1to BLKz in the memory cell array110may include a plurality of dummy cells. One or more dummy cells may be coupled in series between a drain select transistor and memory cells and between a source select transistor and the memory cells.

Each of the memory cells of the memory device100may be formed of a single level cell (SLC) capable of storing a single data bit, a multi-level cell (MLC) capable of storing two data bits, a triple-level cell (TLC) capable of storing three data bits, or a quad-level cell (QLC) capable of storing four data bits.

The peripheral circuit120may drive the memory cell array110. For example, the peripheral circuit120may drive the memory cell array110to perform a program operation, a read operation, or an erase operation.

The address decoder121is coupled to the memory cell array110through the row lines RL. The row lines RL may include drain select lines, word lines, source select lines, and a common source line. In an embodiment, the word lines may include normal word lines and dummy word lines. In an embodiment, the row lines RL may further include a pipe select line.

The address decoder121may operate under control of the control logic130. The address decoder121may receive addresses ADDR from the control logic130.

The address decoder121may decode a block address among the received addresses ADDR. The address decoder121may select at least one of the memory blocks BLK1to BLKz according to the decoded block address. The address decoder121may decode a row address among the received addresses ADDR. The address decoder121may select at least one of the word lines of the selected memory block according to the decoded row address. The address decoder121may apply, to the selected word line, an operating voltage Vop supplied with the voltage generator122.

During a program operation, the address decoder121may apply a program voltage to a selected word line and apply a pass voltage lower than that of the program voltage to unselected word lines. During a program verify operation, the address decoder121may apply a verify voltage to a selected word line and apply a verify pass voltage higher than that of the verify voltage to unselected word lines.

During a read operation, the address decoder121may apply a read voltage to a selected word line and apply a read pass voltage higher than that of the read voltage to unselected word lines.

In an embodiment, an erase operation of the memory device100may be performed on a memory block basis. During the erase operation, an address ADDR to be input to the memory device100includes a block address. The address decoder121may decode the block address and select at least one memory block according to the decoded block address. During the erase operation, the address decoder121may apply a ground voltage to word lines coupled to the selected memory block.

In an embodiment of the present disclosure, the address decoder121may decode a column address among the transmitted addresses ADDR. The decoded column address may be transmitted to the read/write circuit123. For example, the address decoder121may include components such as a row decoder, a column decoder, and an address buffer.

The voltage generator122may generate a plurality of operating voltages Vop using an external supply voltage supplied to the memory device100. The voltage generator122may operate under control of the control logic130.

In an embodiment, the voltage generator122may generate an internal supply voltage by regulating the external supply voltage. The internal supply voltage generated from the voltage generator122may be used as an operating voltage of the memory device100.

In an embodiment, the voltage generator122may generate a plurality of operating voltages Vop using an external supply voltage or an internal supply voltage. The voltage generator122may generate various voltages required from the memory device100. For example, the voltage generator122may generate a plurality of erase voltages, a plurality of program voltages, a plurality of pass voltages, a plurality of select read voltages, and a plurality of unselect read voltages.

The voltage generator122may include, so as to generate a plurality of operating voltages Vop having various voltage levels, a plurality of pumping capacitors configured to receive an internal supply voltage. The voltage generator122may generate a plurality of operating voltages Vop by selectively enabling the plurality of pumping capacitors under control of the control logic130.

The generated operating voltages Vop may be supplied to the memory cell array110by the address decoder121.

The read/write circuit123may include first to m-th page buffers PB1to PBm. The first to m-th page buffers PB1to PBm may be coupled to the memory cell array110through the first to m-th bit lines BL1to BLm, respectively. The first to m-th page buffers PB1to PBm may operate under control of the control logic130.

The first to m-th page buffers PB1to PBm may communicate data DATA with the data input/output circuit124. During a program operation, the first to m-th page buffers PB1to PBm may receive data DATA to be stored through the data input/output circuit124and data lines DL.

During a program operation, the first to m-th page buffers PB1to PBm may transmit the data DATA, received through the data input/output circuit124, to selected memory cells through the bit lines BL1to BLm when a program voltage is applied to a selected word line. The memory cells in the selected page are programmed based on the transmitted data DATA. Memory cells coupled to a bit line to which a program enable voltage (e.g., a ground voltage) is applied may have increased threshold voltages. Threshold voltages of memory cells coupled to a bit line to which a program inhibit voltage (for example, a supply voltage) is applied may be retained. During a program verify operation, the first to m-th page buffers PB1to PBm may read data DATA from selected memory cells through the bit lines BL1to BLm.

During a read operation, the read/write circuit123may read data DATA from the memory cells of the selected page through the bit lines BL, and store the read data DATA in the first to m-th page buffers PB1to PBm.

During an erase operation, the read/write circuit123may float the bit lines BL. In an embodiment, the read/write circuit123may include a column select circuit.

The data input/output circuit124is coupled to the first to m-th page buffers PB1to PBm through the data lines DL. The data input/output circuit124may operate under control of the control logic130.

The data input/output circuit124may include a plurality of input/output buffers (not shown) for receiving input data DATA. During a program operation, the data input/output circuit124may receive data DATA to be stored from an external controller (e.g., the controller200ofFIG.1). During a read operation, the data input/output circuit124may output, to the external controller, the data DATA received from the first to m-th page buffers PB1to PBm in the read/write circuit123.

During a read operation or a verify operation, the sensing circuit125may generate reference current in response to an enable bit signal VRYBIT generated by the control logic130, compare a sensing voltage VPB received from the read/write circuit123with a reference voltage generated by the reference current, and output a pass signal or a fail signal to the control logic130.

The control logic130may be coupled to the address decoder121, the voltage generator122, the read/write circuit123, the data input/output circuit124, and the sensing circuit125. The control logic130may control overall operation of the memory device100. The control logic130may operate in response to a command CMD transmitted from an external device.

The control circuit130may generate various signals in response to the command CMD and the address ADD and control the peripheral circuit120. For example, in response to the command CMD and the address ADDR, the control logic130may generate an operating signal OPSIG, an address ADDR, a read/write circuit control signal PBSIGNALS, and an enable bit VRYBIT. The control logic130may output the operating signal OPSIG to the voltage generator122, output the address ADDR to the address decoder121, output the read/write control signal to the read/write circuit123, and output the enable bit VRYBIT to the sensing circuit125. The control logic130may determine whether target memory cells have passed or failed a verification during the verify operation in response to a pass signal PASS or a fail signal FAIL that is output from the sensing circuit125.

FIG.3is a diagram illustrating a memory cell array110ofFIG.2.

Referring toFIG.3, the first to z-th memory blocks BLK1to BLKz of the memory cell array110are connected in common to the first to m-th bit lines BL1to BLm. InFIG.3, for clarity, elements of only the first memory block BLK1among the plurality of memory blocks BLK1to BLKz are illustrated. It may be understood that each of the memory blocks BLK2to BLKz has the same configuration as that of the first memory block BLK1.

The memory block BLK1may include a plurality of cell strings CS1_1to CS1_m(where m is a positive integer). The first to m-th cell strings CS1_1to CS1_mare respectively coupled to the first to nn-th bit lines BL1to BLnn. Each of the first to nn-th cell strings CS1_1to CS1_mincludes a drain select transistor DST, a plurality of memory cells MC1to MCn (where n is a positive integer) coupled in series to each other, and a source select transistor SST.

A gate terminal of the drain select transistor DST in each of the first to nn-th cell strings CS1_1to CS1_mis coupled to a drain select line DSL1. Gate terminals of the first to n-th memory cells MC1to MCn in each of the first to nn-th cell strings CS1_1to CS1_mare respectively coupled to the first to n-th word lines WL1to WLn. A gate terminal of the source select transistor SST in each of the first to nn-th cell strings CS1_1to CS1_mis coupled to a source select line SSL1.

The configuration of each cell string will be described based on the first cell string CS1_1of the plurality of cell strings CS1_1to CS1_m. It will be understood that each of the other cell strings CS1_1to CS1_mhas the same configuration as that of the first cell string CS1_1.

A drain terminal of the drain select transistor DST in the first cell string CS1_1is coupled to the first bit line BL1. A source terminal of the drain select transistor DST in the first cell string CS1_1is coupled to a drain terminal of the first memory cell MC1in the first cell string CS1_1. The first to n-th memory cells MC1to MCn are coupled in series to each other. A drain terminal of the source select transistor SST in the first cell string CS1_1is coupled to a source terminal of the n-th memory cell MCn in the first cell string CS1_1. A source terminal of the source select transistor SST in the first cell string CS1_1is coupled to a common source line CSL. In an embodiment, the common source line CSL may be coupled in common to the first to z-th memory blocks BLK1to BLKz.

The drain select line DSL1, the first to n-th word lines WL1to WLn, and the source select line SSL1are included in the row lines RL ofFIG.2. The drain select line DSL1, the first to n-th word lines WL1to WLn, and the source select line SSL1are controlled by the address decoder121. The common source line CSL is controlled by the control logic130. The first to m-th bit lines BL1to BLm are controlled by the read/write circuit123.

FIG.4is a diagram illustrating configuration and operation of the memory controller200ofFIG.1.

Referring toFIG.4, the memory device100may store a plurality of map segments including mapping data between logical addresses received from the host300and physical addresses of the memory device100.

In an embodiment, the memory controller200may include a map buffer210and a map manager220.

The map buffer210may store map data loaded from the memory device100. The map data may include at least one map segment of the plurality of map segments stored in the memory device100.

The map buffer210may include a storage area corresponding to each of a plurality of addresses. The map buffer210may store at least one map segment received from the memory device100in the storage area corresponding to each address in a loaded sequence.

The map manager220may receive a read request REQ and a logical address LBA from the host300. The map manager220may search for map data corresponding to the logical address LBA in response to the read request REQ.

In an embodiment, the map manager220may include a descriptor controller221, a descriptor queue222, and a write queue223.

The descriptor queue222may include descriptors corresponding to the respective map segments based on the plurality of addresses of the map buffer210. The descriptor queue222may store descriptors corresponding to map segments in a sequence in which the map segments are loaded from the memory device100. The descriptor may be an index indicating a map segment.

The descriptor controller221may search for a target descriptor indicating a map segment including a logical address LBA in the descriptor queue222.

The descriptor controller221may determine a target descriptor based on a logical address LBA. The target descriptor may be an index indicating a map segment including a logical address LBA. In an embodiment, the target descriptor may be a portion of an LBA value.

The descriptor controller221may read a descriptor corresponding to a selected address of the plurality of addresses in the descriptor queue222. The descriptor controller221may determine whether the read descriptor matches, i.e., is the same as, the target descriptor.

If the read descriptor differs from the target descriptor, the descriptor controller221may change the selected address and search for the target descriptor again. This process may continue until a match is found or it is determined there is no match. In the latter case, the descriptor controller221may output matching failure information indicating there is no target descriptor in the descriptor queue222. In response to the matching failure information, the map manager220may load, from the memory device100, a map segment indicated by the target descriptor among the plurality of map segments stored in the memory device100based on the logical address LBA.

The descriptor controller221may reorder the descriptors stored in the descriptor queue222in connection with searching for the target descriptor among the descriptors stored in the descriptor queue222. In an embodiment, the descriptor controller221may order the descriptors stored in the descriptor queue222in an ascending order based on their respective addresses in the map buffer210. In another embodiment, the descriptor controller221may order the descriptors stored in the descriptor queue222in a descending order based on their respective addresses in the map buffer210.

In the description that follows, it is assumed that the descriptor controller221orders the descriptors stored in the descriptor queue222in an ascending order based on the plurality of addresses.

The descriptor controller221may determine a searching direction in which the target descriptor is searched for, based on a result of the comparison between the target descriptor and a reference descriptor. If the target descriptor is greater than the reference descriptor, the descriptor controller221may determine that the searching direction is a direction in which the plurality of addresses becoming lower (reverse direction). If the target descriptor is less than the reference descriptor, the descriptor controller221may determine that the searching direction is a direction in which the plurality of addresses become higher (forward direction). The reference descriptor may be determined as an average value or a median value among descriptors corresponding to the respective map segments stored in the memory device100. In an embodiment, the reference descriptor may be determined to be any of various values depending on a map search policy of the memory controller.

The write queue223may store descriptor information for reordering the descriptors stored in the descriptor queue222.

The descriptor controller221may set a minimum value or a maximum value of one or more descriptors read from the descriptor queue222to a pop-up descriptor. The pop-up descriptor may be a descriptor temporarily stored in the descriptor controller221for comparison with the read descriptor.

In an embodiment, when searching for a target descriptor in the descriptor queue222in the forward direction, the descriptor controller221may set the maximum value of the one or more descriptors read from the descriptor queue222to the pop-up descriptor. In an embodiment, when searching for a target descriptor in the descriptor queue222in the reverse direction, the descriptor controller221may set the minimum value of the one or more descriptors read from the descriptor queue222to the pop-up descriptor.

The descriptor controller221may read a descriptor corresponding to a selected address among the plurality of addresses. The descriptor controller221may determine whether the read descriptor matches the target descriptor.

If the read descriptor differs from the target descriptor, the descriptor controller221may compare the read descriptor with the pop-up descriptor.

The descriptor controller221may store, in the write queue223, descriptor information including a previous address and the read descriptor of the selected address based on a result of the comparison between the read descriptor and the pop-up descriptor. The descriptor controller221may update a descriptor corresponding to the selected address in the descriptor queue222to the pop-up descriptor. In the case where the write queue323is full, the descriptor controller221may not update the descriptor queue222.

The descriptor controller221may update the descriptor queue222based on the descriptor information previously stored in the write queue223depending on the result of the comparison between the read descriptor and the pop-up descriptor.

In an embodiment, in the case where a searching operation is performed in the forward direction, the descriptor controller221may store, if the pop-up descriptor is greater than the read descriptor, descriptor information including a previous address and a read descriptor of a selected address in the write queue223based on a result of the comparison between the read descriptor and the pop-up descriptor. Further, the descriptor controller221may update a descriptor corresponding to the selected address in the descriptor queue222to the pop-up descriptor.

In an embodiment, when the searching operation is performed in the forward direction, the descriptor controller221may update, if the pop-up descriptor is less than the read descriptor, the descriptor queue222based on the descriptor information previously stored in the write queue223. The descriptor controller221may update the pop-up descriptor to the read descriptor.

The operation of reordering the descriptors stored in the descriptor queue222when the searching operation is performed in the forward direction is described with reference toFIGS.5A to5I.

In an embodiment, in the case where a searching operation is performed in the reverse direction, the descriptor controller221may store, if the pop-up descriptor is less than the read descriptor, descriptor information including a previous address and a read descriptor of a selected address in the write queue223based on a result of the comparison between the read descriptor and the pop-up descriptor. Further, the descriptor controller221may update a descriptor corresponding to the selected address in the descriptor queue222to the pop-up descriptor.

In an embodiment, when the searching operation is performed in the reverse direction, the descriptor controller221may update, if the pop-up descriptor is greater than the read descriptor, the descriptor queue222based on the descriptor information previously stored in the write queue223. The descriptor controller221may update the pop-up descriptor to the read descriptor.

The operation of reordering the descriptors stored in the descriptor queue222when the searching operation is performed in the reverse direction is described with reference toFIGS.7A to7K.

FIGS.5A to5Iare diagrams illustrating a forward map searching operation and a descriptor reordering operation in accordance with an embodiment.

Referring toFIG.5A, the descriptor queue may store, based on a plurality of addresses Addr1to Addr8of a map buffer210, descriptors corresponding to respective map segments stored in the map buffer210. The descriptor may be an index indicating a map segment. The descriptor queue may store descriptors corresponding to the respective map segments in a sequence in which the map segments are loaded from the memory device100.

The target descriptor may be an index indicating a map segment including a logical address received from the host300. The target descriptor may be determined based on the logical address. In an embodiment, the target descriptor may be a partial value of the logical address.

In the description with reference toFIGS.5A to5I, it is assumed that the logical address is 04405. Upper three bits of the logical address may be used as a target descriptor, and lower two bits of the logical address may be used as an offset. A method of determining the value and descriptor of the logical address is not limited to embodiments of the present disclosure.

The target descriptor that indicates a map segment including the logical address may be 44. The memory controller200may search for the target descriptor in the descriptor queue and obtain an address of a map buffer corresponding to the target descriptor. The memory controller200may obtain a map segment which is indicated by target descriptor44from the map buffer210based on the address. The memory controller200may obtain map data corresponding to logical address 04405 with reference to map data having an offset of 5 in the obtained map segment.

The searching direction may be determined depending on a result of the comparison between the target descriptor and the reference descriptor. If the target descriptor is greater than the reference descriptor, the searching direction may be determined to be the reverse direction. If the target descriptor is less than the reference descriptor, the searching direction may be determined to be the forward direction. In the description with reference toFIGS.5A to5I, it is assumed that the reference descriptor is50. InFIGS.5A to5I, since target descriptor44is less than reference descriptor50, the target descriptor may be searched for in the forward direction.

In an embodiment, the descriptor queue may store descriptors7,3,10,13,5,2,1, and44corresponding to addresses Addr1to Addr8, respectively. The number of addresses is not limited to that of the present embodiment.

Referring toFIG.5A, since the searching direction is the forward direction, a first address Addr1of the plurality of addresses Addr1to Addr8may be determined to be a selected address. Descriptor7corresponding to the selected address may be read. It may be determined whether read descriptor7matches target descriptor44. Since read descriptor7does not match target descriptor44, the operation of searching for the target descriptor may be performed in a direction in which the selected address increases.

The pop-up descriptor may be determined based on the maximum value of one or more descriptors read from the descriptor queue. Since read descriptor7is the maximum value of the one or more descriptors read from the descriptor queue, read descriptor7may be set to the pop-up descriptor.

Referring toFIG.5B, the selected address may be increased from the first address to a second address. The previous address may be the first address. Descriptor3corresponding to the selected address may be read. It may be determined whether read descriptor3matches target descriptor44. Since read descriptor3does not match target descriptor44, the operation of searching for the target descriptor may be performed in a direction in which the selected address increases.

Since read descriptor3does not match target descriptor44, read descriptor3may be compared with pop-up descriptor7. Since pop-up descriptor7is greater than read descriptor3, descriptor information including read descriptor3and the first address that is the previous address may be stored in the write queue. Descriptor3corresponding to the second address that is the selected address in the descriptor queue may be updated to7that is the pop-up descriptor.

Referring toFIG.5C, the selected address may be increased from the second address to a third address. The previous address may be the second address. Descriptor10corresponding to the selected address may be read. It may be determined whether read descriptor10matches target descriptor44. Since read descriptor10does not match target descriptor44, the operation of searching for the target descriptor may be performed in a direction in which the selected address increases.

Since read descriptor10does not match target descriptor44, read descriptor10may be compared with pop-up descriptor7. Since pop-up descriptor7is less than read descriptor10, the descriptor queue may be updated based on the descriptor information stored in the write queue. Therefore, descriptor7corresponding to the first address in the descriptor queue may be updated to descriptor3.

The pop-up descriptor may be determined to be the maximum value of one or more descriptors read from the descriptor queue. Therefore, since pop-up descriptor7is less than read descriptor10, pop-up descriptor7may be updated to read descriptor10.

Referring toFIG.5D, the selected address may be increased from the third address to a fourth address. The previous address may be the third address. Descriptor13corresponding to the selected address may be read. It may be determined whether read descriptor13matches target descriptor44. Since read descriptor13does not match target descriptor44, the operation of searching for the target descriptor may be performed in a direction in which the selected address increases.

Since read descriptor13does not match target descriptor44, read descriptor13may be compared with pop-up descriptor10. Since pop-up descriptor10is less than read descriptor13, pop-up descriptor10may be updated to read descriptor13.

Referring toFIG.5E, the selected address may be increased from the fourth address to a fifth address. The previous address may be the fourth address. Descriptor5corresponding to the selected address may be read. It may be determined whether read descriptor5matches target descriptor44. Since read descriptor5does not match target descriptor44, the operation of searching for the target descriptor may be performed in a direction in which the selected address increases.

Since read descriptor5does not match target descriptor44, read descriptor5may be compared with pop-up descriptor13. Since pop-up descriptor13is greater than read descriptor5, descriptor information including read descriptor5and the fourth address that is the previous address may be stored in the write queue. Descriptor5corresponding to the fifth address that is the selected address in the descriptor queue may be updated to13that is the pop-up descriptor.

Referring toFIG.5F, the selected address may be increased from the fifth address to a sixth address. The previous address may be the fifth address. Descriptor2corresponding to the selected address may be read. It may be determined whether read descriptor2matches target descriptor44. Since read descriptor2does not match target descriptor44, the operation of searching for the target descriptor may be performed in a direction in which the selected address increases.

Since read descriptor2does not match target descriptor44, read descriptor2may be compared with pop-up descriptor13. Since pop-up descriptor13is greater than read descriptor2, descriptor information including read descriptor2and the fifth address that is the previous address may be stored in the write queue. Descriptor2corresponding to the sixth address that is the selected address in the descriptor queue may be updated to13that is the pop-up descriptor.

Referring toFIG.5G, the selected address may be increased from the sixth address to a seventh address. The previous address may be the sixth address. Descriptor1corresponding to the selected address may be read. It may be determined whether read descriptor1matches target descriptor44. Since read descriptor1does not match target descriptor44, the operation of searching for the target descriptor may be performed in a direction in which the selected address increases.

Since read descriptor1does not match target descriptor44, read descriptor1may be compared with pop-up descriptor13. Since pop-up descriptor13is greater than read descriptor1, descriptor information including read descriptor1and the sixth address that is the previous address is required to be stored in the write queue. However, because the write queue is full, the descriptor information may not be stored in the write queue. Therefore, descriptor1corresponding to the seventh address that the selected address in the descriptor queue may not be updated to13that is the pop-up descriptor.

Referring toFIG.5H, the selected address may be increased from the seventh address to an eighth address. The previous address may be the seventh address. Descriptor44corresponding to the selected address may be read. It may be determined whether read descriptor44matches target descriptor44. Since read descriptor44matches target descriptor44, the operation of searching for the target descriptor may be terminated.

If the map buffer is read with reference to the fourth address of the map buffer that corresponds to target descriptor44, a map segment indicated by target descriptor44may be obtained. If map data having an offset of 5 is read from the obtained map segment, map data corresponding to logical address 04405 may be obtained.

Since the descriptor information stored in the write queue is present, the descriptor queue may be updated based on the descriptor information stored in the write queue. Therefore, descriptor13corresponding to the fourth address in the descriptor queue may be updated to descriptor5.

The pop-up descriptor may be determined to be the maximum value of one or more descriptors read from the descriptor queue. Therefore, since pop-up descriptor13is less than read descriptor44, pop-up descriptor13may be updated to read descriptor44.

Referring toFIG.5I, although the operation of searching for the target descriptor has been terminated, the descriptor information stored in the write queue is present, so that the descriptor queue may be updated based on the descriptor information stored in the write queue. Therefore, descriptor13corresponding to the fifth address in the descriptor queue may be updated to descriptor2.

FIG.6is a diagram illustrating a descriptor ordering operation after the map searching operation.

Referring toFIG.6, it can be understood that after a map searching operation has been performed once in the forward direction, descriptors respectively corresponding to the first and second addresses are ordered in an ascending order. As the map searching operation is performed, the descriptors may be ordered in an ascending order based on the addresses. Since the descriptors stored in the descriptor queue have been ordered based on the addresses, a reverse searching operation may be performed in a subsequent map searching operation if the target descriptor is greater than the reference value, or a forward searching operation may be performed if the target descriptor is less than or equal to the reference value. Consequently, the time it takes to perform the map searching operation may be reduced.

In various embodiments, after the map searching operation has been performed, the descriptors stored in the descriptor queue may be ordered in a descending order based on the addresses.

FIGS.7A to7Kare diagrams illustrating a reverse map searching operation and a descriptor reordering operation in accordance with an embodiment.

Referring toFIG.7A, the descriptor queue may be a descriptor queue obtained by ordering descriptors in an ascending order after the forward searching operation described with reference toFIG.5Ihas been performed once.

In the description with reference toFIGS.7A to7K, it is assumed that the logical address is 10001. Upper three bits of the logical address may be used as a target descriptor, and lower two bits of the logical address may be used as an offset. A method of determining the value and descriptor of the logical address is not limited to embodiments of the present disclosure.

The target descriptor that indicates a map segment including the logical address may be 100. The memory controller200may search for the target descriptor in the descriptor queue and obtain an address of a map buffer210corresponding to the target descriptor. The memory controller200may obtain a map segment which is indicated by target descriptor100from the map buffer210based on the address. The memory controller200may obtain map data corresponding to logical address 10001 with reference to map data having an offset of 1 in the obtained map segment.

The searching direction may be determined depending on a result of the comparison between the target descriptor and the reference descriptor. If the target descriptor is greater than the reference descriptor, the searching direction may be determined to be a reverse direction. If the target descriptor is less than the reference descriptor, the searching direction may be determined to be a forward direction. In the description with reference toFIGS.7A to7K, it is assumed that the reference descriptor is50. InFIGS.7A to7K, since target descriptor100is greater than reference descriptor50, the target descriptor may be searched for in the reverse direction.

Referring toFIGS.7A and7B, since the searching direction is the reverse direction, an eighth address of the plurality of addresses Addr1to Addr8may be determined to be a selected address. Descriptor44corresponding to the selected address may be read. It may be determined whether read descriptor44matches target descriptor100. Since read descriptor44does not match target descriptor100, the operation of searching for the target descriptor may be performed in a direction in which the selected address decreases.

The pop-up descriptor may be determined based on the minimum value of one or more descriptors read from the descriptor queue. Since read descriptor44is the minimum value of the one or more descriptors read from the descriptor queue, read descriptor44may be set to the pop-up descriptor.

Referring toFIG.7C, the selected address may be decreased from the eighth address to a seventh address. The previous address may be the eighth address. Descriptor1corresponding to the selected address may be read. It may be determined whether read descriptor1matches target descriptor100. Since read descriptor1does not match target descriptor100, the operation of searching for the target descriptor may be performed in a direction in which the selected address decreases.

Since read descriptor1differs from target descriptor100, read descriptor1may be compared with pop-up descriptor44. Since pop-up descriptor44is greater than read descriptor1, pop-up descriptor44may be updated to read descriptor1.

Referring toFIG.7D, the selected address may be decreased from the seventh address to a sixth address. The previous address may be the seventh address. Descriptor13corresponding to the selected address may be read. It may be determined whether read descriptor13matches target descriptor100. Since read descriptor13does not match target descriptor100, the operation of searching for the target descriptor may be performed in a direction in which the selected address decreases.

Since read descriptor13differs from target descriptor100, read descriptor13may be compared with pop-up descriptor1. Since pop-up descriptor1is less than read descriptor13, descriptor information including read descriptor13and the seventh address that is the previous address may be stored in the write queue. Descriptor13corresponding to the sixth address that is the selected address in the descriptor queue may be updated to1that is the pop-up descriptor.

Referring toFIG.7E, the selected address may be decreased from the sixth address to a fifth address. The previous address may be the sixth address. Descriptor2corresponding to the selected address may be read. It may be determined whether read descriptor2matches target descriptor100. Since read descriptor2does not match target descriptor100, the operation of searching for the target descriptor may be performed in a direction in which the selected address decreases.

Since read descriptor2differs from target descriptor100, read descriptor2may be compared with pop-up descriptor1. Since pop-up descriptor1is less than read descriptor2, descriptor information including read descriptor2and the sixth address that is the previous address may be stored in the write queue. Descriptor2corresponding to the fifth address that is the selected address in the descriptor queue may be updated to1that is the pop-up descriptor.

Referring toFIG.7F, the selected address may be decrease from the fifth address to a fourth address. The previous address may be the fifth address. Descriptor5corresponding to the selected address may be read. It may be determined whether read descriptor5matches target descriptor100. Since read descriptor5does not match target descriptor100, the operation of searching for the target descriptor may be performed in a direction in which the selected address decreases.

Since read descriptor5differs from target descriptor100, read descriptor5may be compared with pop-up descriptor1. Since pop-up descriptor1is less than read descriptor5, descriptor information including read descriptor5and the fifth address that is the previous address is required to be stored in the write queue. However, because the write queue is full, the descriptor information may not be stored in the write queue. Therefore, descriptor5corresponding to the fourth address that is the selected address in the descriptor queue may not be updated to1that is the pop-up descriptor.

Referring toFIG.7G, the selected address may be reduced from the fourth address to a third address. The previous address may be the fourth address. Descriptor10corresponding to the selected address may be read. It may be determined whether read descriptor10matches target descriptor100. Since read descriptor10does not match target descriptor100, the operation of searching for the target descriptor may be performed in a direction in which the selected address decreases.

Since read descriptor10differs from target descriptor100, read descriptor10may be compared with pop-up descriptor1. Since pop-up descriptor1is less than read descriptor10, descriptor information including read descriptor4and the fourth address that is the previous address is required to be stored in the write queue. However, because the write queue is full, the descriptor information may not be stored in the write queue. Therefore, descriptor10corresponding to the third address that is the selected address in the descriptor queue may not be updated to1that is the pop-up descriptor.

Referring toFIG.7H, the selected address may be decreased from the third address to a second address. The previous address may be the third address. Descriptor7corresponding to the selected address may be read. It may be determined whether read descriptor7matches target descriptor100. Since read descriptor7does not match target descriptor100, the operation of searching for the target descriptor may be performed in a direction in which the selected address decreases.

Since read descriptor7differs from target descriptor100, read descriptor7may be compared with pop-up descriptor1. Since pop-up descriptor1is less than read descriptor7, descriptor information including read descriptor7and the third address that is the previous address is required to be stored in the write queue. However, because the write queue is full, the descriptor information may not be stored in the write queue. Therefore, descriptor7corresponding to the second address that is the selected address in the descriptor queue may not be updated to1that is the pop-up descriptor.

Referring toFIG.7I, the selected address may be decreased from the second address to a first address. The previous address may be the second address. Descriptor3corresponding to the selected address may be read. It may be determined whether read descriptor3matches target descriptor100. Since read descriptor3does not matches target descriptor100and all of the descriptors stored in the descriptor queue are in the read state, the operation of searching for the target descriptor may be terminated.

Since read descriptor3differs from target descriptor100, read descriptor3may be compared with pop-up descriptor1. Since pop-up descriptor1is less than read descriptor3, descriptor information including read descriptor3and the second address that is the previous address is required to be stored in the write queue. However, because the write queue is full, the descriptor information may not be stored in the write queue. Therefore, descriptor3corresponding to the first address that is the selected address in the descriptor queue may not be updated to1that is the pop-up descriptor.

Referring toFIG.7J, although the operation of searching for the target descriptor has been terminated, the descriptor information stored in the write queue is present, so that the descriptor queue may be updated based on the descriptor information stored in the write queue. Therefore, descriptor1corresponding to the seventh address in the descriptor queue may be updated to descriptor13.

Referring toFIG.7K, although the operation of searching for the target descriptor has been terminated, the descriptor information stored in the write queue is present, so that the descriptor queue may be updated based on the descriptor information stored in the write queue. Therefore, descriptor1corresponding to the sixth address in the descriptor queue may be updated to descriptor2.

FIG.8is a diagram illustrating a descriptor ordering operation after the map searching operation.

FIG.8illustrates a descriptor queue obtained by performing the forward map searching operation described with reference toFIGS.5A to5Iand a descriptor queue obtained by performing the reverse map searching operation described with reference toFIGS.7A to7K.

It can be understood that after a map searching operation has been performed once in the forward direction, descriptors respectively corresponding to the first and second addresses are ordered in an ascending order. Thereafter, it can be understood that after a map searching operation has been performed once in the reverse direction, descriptors respectively corresponding to the fifth, sixth, and seventh addresses are ordered in an ascending order. In other words, as the map searching operation is repeatedly performed, the descriptor stored in the descriptor queue is ordered in an ascending order. Therefore, the time it takes to search for the target descriptor in a searching direction determined depending on a result of comparison between the target descriptor and the reference descriptor may be reduced.

In various embodiments, as map searching operations are repeatedly performed, the descriptor stored in the descriptor queue may be ordered in a descending order.

FIG.9is a flowchart illustrating the operation of the memory controller200in accordance with an embodiment.

Referring toFIG.9, at step S901, the memory controller200may determine a target descriptor based on a logical address received from the host300. The target descriptor may be an index indicating a map segment including a logical address. In an embodiment, the target descriptor may be determined based on a portion of a logical address value.

At step S903, the memory controller200may reorder the descriptors stored in the descriptor queue in connection with searching for the target descriptor among the descriptors stored in the descriptor queue.

In an embodiment, since the descriptors are reordered as part of the search for the target descriptor, the time required to order the descriptors stored in the descriptor queue may be reduced, and the time it takes to search for a subsequent descriptor may also be reduced.

FIG.10is a flowchart illustrating in detail the operation of the memory controller200ofFIG.9.

Referring toFIG.10, at step S1001, the memory controller200may determine whether the target descriptor is greater than the reference descriptor. As a result of the determination, if the target descriptor is greater than the reference descriptor, the process may proceed to step S1005. If the target descriptor is less than or equal to the reference descriptor, the process may proceed to step S1003.

At step S1003, the memory controller200may search for the target descriptor in the forward direction, reorder the descriptors stored in the descriptor queue in the process of searching for the target descriptor. Then, the memory controller200may terminate the process.

At step S1005, the memory controller200may search for the target descriptor in the reverse direction, reorder the descriptors stored in the descriptor queue in the process of searching for the target descriptor. Then, the memory controller200may terminate the process.

FIG.11is a flowchart illustrating the forward searching operation S1003ofFIG.10.

Referring toFIG.11, at step S1101, the memory controller200may set a start address of the plurality of addresses of the map buffer to a selected address.

At step S1103, the memory controller200may read a descriptor corresponding to the selected address.

At step S1105, the memory controller200may determine whether the read descriptor matches the target descriptor. As a result of the determination, if the read descriptor matches the target descriptor, the process may proceed to step S1107. If the read descriptor does not match the target descriptor, the process may proceed to step S1109.

At step S1107, the memory controller200may update the descriptor queue based on the descriptor information stored in the write queue and then may terminate the process.

At step S1109, the memory controller200may reorder the descriptors stored in the descriptor queue.

At step S1111, the memory controller200may determine whether the selected address is a last address of the plurality of addresses of the map buffer. As a result of the determination, if the selected address is the last address, the process may be terminated. If the selected address is not the last address, the process may proceed to step S1113.

At step S1113, the memory controller200may increase the selected address and then return to step S1103.

FIG.12is a flowchart illustrating step S1109ofFIG.11.

Referring toFIG.12, at step S1201, the memory controller200may determine whether the pop-up descriptor has been set. When a forward searching operation is performed, the pop-up descriptor may be set to the maximum value of one or more descriptors read from the descriptor queue. As a result of the determination, if the pop-up descriptor has not been set, the process may proceed to step S1203. If the pop-up descriptor has been set, the process may proceed to step S1205.

At step S1203, the memory controller200may set the read descriptor to the pop-up descriptor and then may terminate the process.

At step S1205, the memory controller200may determine whether the pop-up descriptor is greater than the read descriptor. As a result of the determination, if the pop-up descriptor is greater than the read descriptor, the process may proceed to step S1207. If the pop-up descriptor is less than the read descriptor, the process may proceed to step S1213.

At step S1207, the memory controller200may determine whether the write queue is full. As a result of the determination, if the write queue is full, the process may be terminated. If the write queue is not full, the process may proceed to step S1209.

At step S1209, the memory controller200may update a descriptor corresponding to the selected address in the descriptor queue to the pop-up descriptor.

At step S1211, the memory controller200may store descriptor information including the read descriptor and the previous address in the write queue and then may terminate the process.

At step S1213, the pop-up descriptor may be updated to the read descriptor.

At step S1215, the descriptor queue may be updated based on the descriptor information stored in the write queue and then may terminate the process.

FIG.13is a flowchart illustrating a reverse searching operation S1005ofFIG.10.

Referring toFIG.13, at step S1301, the memory controller200may set a last address of the plurality of addresses of the map buffer to a selected address.

At step S1303, the memory controller200may read a descriptor corresponding to the selected address.

At step S1305, the memory controller200may determine whether the read descriptor matches the target descriptor. As a result of the determination, if the read descriptor matches the target descriptor, the process may proceed to step S1307. If the read descriptor does not match the target descriptor, the process may proceed to step S1309.

At step S1307, the memory controller200may update the descriptor queue based on the descriptor information stored in the write queue and then may terminate the process.

At step S1309, the memory controller200may reorder the descriptors stored in the descriptor queue.

At step S1311, the memory controller200may determine whether the selected address is a start address of the plurality of addresses of the map buffer. As a result of the determination, if the selected address is the start address, the process may be terminated. If the selected address is not the last address, the process may proceed to step S1313.

At step S1313, the memory controller200may decrease the selected address and then return to step S1303.

FIG.14is a flowchart illustrating step S1109ofFIG.13.

Referring toFIG.14, at step S1401, the memory controller200may determine whether the pop-up descriptor has been set. When a reverse searching operation is performed, the pop-up descriptor may be set to the minimum value of one or more descriptors read from the descriptor queue. As a result of the determination, if the pop-up descriptor has not been set, the process may proceed to step S1403. If the pop-up descriptor has been set, the process may proceed to step S1405.

At step S1403, the memory controller200may set the read descriptor to the pop-up descriptor and then may terminate the process.

At step S1405, the memory controller200may determine whether the pop-up descriptor is less than the read descriptor. As a result of the determination, if the pop-up descriptor is less than the read descriptor, the process may proceed to step S1407. If the pop-up descriptor is greater than the read descriptor, the process may proceed to step S1413.

At step S1407, the memory controller200may determine whether the write queue is full. As a result of the determination, if the write queue is full, the process may be terminated. If the write queue is not full, the process may proceed to step S1409.

At step S1409, the memory controller200may update a descriptor corresponding to the selected address in the descriptor queue to the pop-up descriptor.

At step S1411, the memory controller200may store descriptor information including the read descriptor and the previous address in the write queue and then may terminate the process.

At step S1413, the pop-up descriptor may be updated to the read descriptor.

At step S1415, the descriptor queue may be updated based on the descriptor information stored in the write queue and then may terminate the process.

FIG.15is a diagram illustrating an example of the memory controller ofFIG.1.

Referring toFIG.15, a memory controller1000is coupled to a host and a memory device. In response to a request from the host, the memory controller1000may access the memory device. For example, the memory controller1000may control a write operation, a read operation, an erase operation, and a background operation of the memory device. The memory controller1000may provide an interface between the memory device and the host. The memory controller1000may drive firmware for controlling the memory device.

The memory controller1000may include a processor1010, a memory buffer1020, an error correction code (ECC) circuit1030, a host interface1040, a buffer controller1050, a memory interface1060, and a bus1070.

The bus1070may provide a channel between the components of the memory controller1000.

The processor1010may control overall operation of the memory controller1000and perform a logical operation. The processor1010may communicate with the external host through the host interface1040, and communicate with the memory device through the memory interface1060. In addition, the processor1010may communicate with the memory buffer1020through the buffer controller1050. The processor1010may control the operation of the storage device by using the memory buffer1020as an operating memory, a cache memory, or a buffer memory.

The processor1010may perform the function of a flash translation layer (FTL). The processor1010may translate a logical block address (LBA), provided by the host, into a physical block address (PBA) through the FTL. The FTL may receive the LBA and translate the LBA into the PBA using a mapping table. Different address mapping methods using the FTL may be used depending on the unit of mapping. Representative address mapping methods include a page mapping method, a block mapping method, and a hybrid mapping method.

The processor1010may randomize data received from the host. For example, the processor1010may use a randomizing seed to randomize data received from the host. Randomized data may be provided to the memory device as data to be stored, and may be programmed to the memory cell array.

During a read operation, the processor1010may derandomize data received from the memory device100. For example, the processor1010may use a derandomizing seed to derandomize data received from the memory device. Derandomized data may be output to the host.

In an embodiment, the processor1010may drive software or firmware to perform the randomizing operation or the derandomizing operation.

The memory buffer1020may be used as an operating memory, a cache memory, or a buffer memory of the processor1010. The memory buffer1020may store codes and commands to be executed by the processor1010. The memory buffer1020may store data to be processed by the processor1010. The memory buffer1020may include a static RAM (SRAM) or a dynamic RAM (DRAM).

The ECC circuit1030may perform error correction. The ECC circuit1030may perform an ECC encoding operation based on data to be written to the memory device through the memory interface1060. ECC encoded data may be transmitted to the memory device through the memory interface1060. The ECC circuit1030may perform an ECC decoding operation on data received from the memory device through the memory interface1060. For example, the ECC circuit1030may be included in the memory interface1060as a component of the memory interface1060.

The host interface1040may communicate with the external host under control of the processor1010. The host interface1040may perform communication using at least one of various communication methods such as a universal serial bus (USB), a serial AT attachment (SATA), a serial attached SCSI (SAS), a high speed interchip (HSIC), a small computer system interface (SCSI), a peripheral component interconnection (PCI), a PCI express (PCIe), a nonvolatile memory express (NVMe), a universal flash storage (UFS), a secure digital (SD), multiMedia card (MMC), an embedded MMC (eMMC), a dual in-line memory module (DIMM), a registered DIMM (RDIMM), and/or a load reduced DIMM (LRDIMM) communication methods.

The buffer controller1050may control the memory buffer1020under control of the processor1010.

The memory interface1060may communicate with the memory device under control of the processor1010. The memory interface1060may communicate a command, an address, and data with the memory device through the channel.

In another embodiment, the memory controller1000may include neither the memory buffer1020nor the buffer controller1050. Instead, each of these components may be disposed externally to the memory controller1000, or the functions of one or both of these components may be distributed to other component(s) within the memory controller1000.

For example, the processor1010may use codes to control the operation of the memory controller1000. The processor1010may load codes from a nonvolatile memory device (e.g., a read only memory) provided in the memory controller1000. Alternatively, the processor1010may load codes from the memory device through the memory interface1060.

For example, the bus1070of the memory controller1000may be divided into a control bus and a data bus. The data bus may transmit data in the memory controller1000. The control bus may transmit control information such as a command and an address in the memory controller1000. The data bus and the control bus may be separated such that neither interferes with, nor affects, the other. The data bus may be coupled to the host interface1040, the buffer controller1050, the ECC circuit1030, and the memory interface1060. The control bus may be coupled to the host interface1040, the processor1010, the buffer controller1050, the memory buffer1020, and the memory interface1060.

FIG.16is a block diagram illustrating a memory card system2000to which the storage device is applied in accordance with an embodiment of the present disclosure.

ReferringFIG.16, the memory card system2000may include a memory controller2100, a memory device2200, and a connector2300.

The memory controller2100is coupled to the memory device2200. The memory controller2100may access the memory device2200. For example, the memory controller2100may control a read operation, a write operation, an erase operation, and a background operation of the memory device2200. The memory controller2100may provide an interface between the memory device2200and the host. The memory controller2100may drive firmware for controlling the memory device2200. The memory controller2100may be configured in the same manner as that of the memory controller200described with reference toFIG.1.

In an embodiment, the memory controller2100may include components such as a random access memory (RAM), a processor, a host interface, and a memory interface, and an ECC circuit.

The memory controller2100may communicate with an external device through the connector2300. The memory controller2100may communicate with an external device (e.g., a host) based on a specific communication protocol. In an embodiment, the memory controller2100may communicate with the external device through at least one of various communication protocols such as universal serial bus (USB), multimedia card (MMC), embedded MMC (eMMC), peripheral component interconnection (PCI), PCI-express (PCI-e or PCIe), advanced technology attachment (ATA), serial-ATA (SATA), parallel-ATA (PATA), small computer small interface (SCSI), enhanced small disk interface (ESDI), integrated drive electronics (IDE), Firewire, universal flash storage (UFS), Wi-Fi, Bluetooth, and/or nonvolatile memory express (NVMe) protocols. In an embodiment, the connector2300may be defined by at least one of the above-described various communication protocols.

In an embodiment, the memory controller2100and the memory device2200may be integrated into a single semiconductor device to form a memory card, such as a personal computer memory card international association (PCMCIA), a compact flash (CF) card, a smart media card (e.g., SM or SMC), a memory stick, a multimedia card (e.g., MMC, RS-MMC, or MMCmicro), a secure digital (SD) card (e.g., SD, miniSD, microSD, or SDHC), or a universal flash storage (UFS).

FIG.17is a block diagram illustrating a solid state drive (SSD) system3000to which the storage device is applied in accordance with an embodiment of the present disclosure.

Referring toFIG.17, the SSD system3000may include a host3100and an SSD3200. The SSD3200may exchange signals SIG with the host3100through a signal connector3001and may receive power PWR through a power connector3002. The SSD3200may include an SSD controller3210, a plurality of flash memories3221to322n, an auxiliary power supply3230, and a buffer memory3240.

In an embodiment, the SSD controller3210may perform the function of the memory controller200, described above with reference toFIG.1.

The SSD controller3210may control the plurality of flash memories3221to322nin response to the signals SIG received from the host3100. In an embodiment, the signals SIG may be based on an interface between the host3100and the SSD3200. For example, the signals SIG may be defined by at least one of various interfaces such as universal serial bus (USB), multimedia card (MMC), embedded MMC (eMMC), peripheral component interconnection (PCI), PCI-express (PCI-e or PCIe), advanced technology attachment (ATA), serial-ATA (SATA), parallel-ATA (PATA), small computer small interface (SCSI), enhanced small disk interface (ESDI), integrated drive electronics (IDE), Firewire, universal flash storage (UFS), Wi-Fi, Bluetooth, and/or nonvolatile memory express (NVMe) interfaces.

The auxiliary power supply3230may be coupled to the host3100through the power connector3002. The auxiliary power supply3230may be supplied with power PWR from the host3100, and may be charged by the power PWR. The auxiliary power supply3230may supply the power of the SSD3200when power from the host3100is not smoothly supplied. In an embodiment, the auxiliary power supply3230may be disposed within the SSD3200or externally to the SSD3200. For example, the auxiliary power supply3230may be disposed in a main board and may supply auxiliary power to the SSD3200.

The buffer memory3240functions as a buffer memory of the SSD3200. For example, the buffer memory3240may temporarily store data received from the host3100or data received from the plurality of flash memories3221to322nor may temporarily store metadata (e.g., a mapping table) of the flash memories3221to322n. The buffer memory3240may include any of various volatile memories such as a DRAM, an SDRAM, a DDR SDRAM, an LPDDR SDRAM, and a GRAM or nonvolatile memories such as an FRAM, a ReRAM, an STT-MRAM, and/or a PRAM.

FIG.18is a block diagram illustrating a user system4000to which the storage device is applied in accordance with an embodiment of the present disclosure.

Referring toFIG.18, the user system4000may include an application processor4100, a memory module4200, a network module4300, a storage module4400, and a user interface4500.

The application processor4100may run components included in the user system4000, an operating system (OS) or a user program. In an embodiment, the application processor4100may include controllers, interfaces, graphic engines, etc. for controlling the components included in the user system4000. The application processor4100may be provided as a system-on-chip (SoC).

The memory module4200may function as a main memory, a working memory, a buffer memory, or a cache memory of the user system4000. The memory module4200may include a volatile RAM such as a DRAM, an SDRAM, a DDR SDRAM, a DDR2 SDRAM, a DDR3 SDRAM, an LPDDR SDARM, an LPDDR2 SDRAM, and an LPDDR3 SDRAM, or a nonvolatile RAM such as a PRAM, a ReRAM, an MRAM, and/or an FRAM. In an embodiment, the application processor4100and the memory module4200may be packaged based on package-on-package (POP) and may then be provided as a single semiconductor package.

The network module4300may communicate with external devices. For example, the network module4300may support wireless communication, such as code division multiple access (CDMA), global system for mobile communication (GSM), wideband CDMA (WCDMA), CDMA-2000, time division multiple access (TDMA), long term evolution (LTE), WiMAX, WLAN, UWB, Bluetooth, or Wi-Fi communication. In an embodiment, the network module4300may be included in the application processor4100.

The storage module4400may store data therein. For example, the storage module4400may store data received from the application processor4100. Alternatively, the storage module4400may transmit the data stored in the storage module4400to the application processor4100. In an embodiment, the storage module4400may be implemented as a nonvolatile semiconductor memory device, such as a phase-change RAM (PRAM), a magnetic RAM (MRAM), a resistive RAM (RRAM), a NAND flash memory, a NOR flash memory, or a NAND flash memory having a three-dimensional (3D) structure. In an embodiment, the storage module4400may be provided as a removable storage medium (i.e., removable drive), such as a memory card or an external drive of the user system4000.

In an embodiment, the storage module4400may include a plurality of nonvolatile memory devices, each of which may be operated in the same manner as the memory device100described above with reference toFIG.1. The storage module4400may be operated in the same manner as the storage device50described above with reference toFIG.1.

The user interface4500may include interfaces for inputting data or instructions to the application processor4100or outputting data to an external device. In an embodiment, the user interface4500may include any of various user input interfaces such as a keyboard, a keypad, a button, a touch panel, a touch screen, a touch pad, a touch ball, a camera, a microphone, a gyroscope sensor, a vibration sensor, and/or a piezoelectric device. The user interface4500may further include any of various user output interfaces such as a liquid crystal display (LCD), an organic light emitting diode (OLED) display device, an active matrix OLED (AMOLED) display device, an LED, a speaker, and/or a monitor.

As described above, various embodiments of the present disclosure may provide a memory system having improved map search performance, a memory controller, and a method of operating the memory controller.