Storage device for performing map scheduling and electronic device including the same

Patent metadata

Field	Value
Publication number	US-11016904-B2
Application number	US-201916543531-A
Country	US
Kind code	B2
Filing date	Aug 17, 2019
Priority date	Nov 14, 2018
Publication date	May 25, 2021
Grant date	May 25, 2021

Abstract

A storage device includes a controller and a memory. In response to a request of a host, the controller generates: (A) a first list as a result of counting: (1) the number of first page numbers included in a first range among page numbers included in a logical address received from the host and (2) the number of second page numbers included in a second range not overlapping the first range, (B) generates a second list as a result of respectively grouping the first page numbers and the second page numbers based on the first list, and (C) translates the logical address to a physical address based on the second list and the first map data. The memory stores the first map data to be provided to the controller. The first map data matches the first page numbers and the second page numbers with respective physical addresses.

First claim

What is claimed is:

1. A storage device comprising:
a controller configured to:
in response to a request of a host, generate a first list identifying a count of first page numbers and second page numbers, wherein the first page numbers are included in a first range among page numbers included in a logical address received from the host and the second page numbers are included in a second range not overlapping the first range,
generate a second list that groups the first page numbers and the second page numbers, based on the first list, and
translate the logical address to a physical address based on the second list and first map data; and

a memory configured to store the first map data to be provided to the controller, wherein
the first map data match the first page numbers and the second page numbers with the physical address.

2. The storage device of claim 1 , wherein the controller is further configured to access a host memory to communicate with the host memory, for requesting the first map data.

3. The storage device of claim 1 , wherein the controller is further configured to:
request second map data from a host memory based on the second list, and
translate the logical address further based on the second map data.

4. The storage device of claim 3 , wherein:
the memory is further configured to store a data table that matches the physical address with the logical address, and
the first map data are included in the data table.

5. The storage device of claim 4 , wherein the second map data are associated with the first map data loaded from the data table to the host memory.

6. The storage device of claim 4 , wherein the controller is further configured to obtain physical page numbers corresponding to the first page numbers, based on the first map data loaded onto the host memory at one time.

7. The storage device of claim 1 , wherein the controller is further configured to generate the second list based on a number of the page numbers included in the logical address.

8. The storage device of claim 1 , wherein:
the controller is further configured to generate the second list during a reference time, and
a length of the reference time is not associated with an order in which the page numbers included in the logical address are received by the controller.

9. The storage device of claim 1 , wherein:
the first list includes a first index associated with the first range and a first count indicating the count of the first page numbers, and
the first count is matched with the first index.

10. The storage device of claim 9 , wherein when the first count is not smaller than “2”, the controller is further configured to:
include one of the first page numbers in a first item of the second list, and decrease the first count as much as “1”.

11. The storage device of claim 10 , wherein the controller is further configured to include another of the first page numbers in a second item to be grouped with the first item.

12. A storage device comprising:
a controller configured to:
in response to a request of a host, for translating a logical address received from the host to a physical address, access a host memory to obtain first map data, and
perform a scheduling, during a reference time, for generating a first list including grouped first page numbers and grouped second page numbers, based on the logical address including the first page numbers of a first range and the second page numbers of a second range,

wherein:
the first map data match the first page numbers and the second page numbers with the physical address, and
a length of the reference time is not associated with an order in which the first page numbers and the second page numbers are received by the controller.

13. The storage device of claim 12 , wherein:
the controller is further configured to:
match a first count, indicating a number of the first page numbers, with a first index indicating the first range, and
match a second count, indicating a number of the second page numbers, with a second index indicating the second range, and

the first list includes the first index, the first count, the second index, and the second count.

14. The storage device of claim 12 , further comprising:
a memory configured to store second map data to be loaded onto the host memory, wherein
the second map data include the first map data.

15. The storage device of claim 14 , wherein:
the second map data are loaded onto the host memory in a loading data unit, and
a size of the loading data unit is associated with a capacity of the host memory.

16. The storage device of claim 15 , wherein a size of the first range and a size of the second range are associated with the loading data unit.

17. The storage device of claim 15 , wherein:
the first page numbers are respectively included in items of the first list, and
the items including the first page numbers are grouped.

18. The storage device of claim 12 , further comprising:
a memory configured to store second map data to be loaded onto the host memory, wherein
the controller is further configured to obtain physical page numbers corresponding to the first page numbers, based on the second map data loaded onto the memory at one time.

19. An electronic device comprising:
a storage device configured to:
in response to a request of a host, generate a first list identifying a count of first page numbers and second page numbers, wherein the first page numbers are included in a first range among page numbers included in a logical address received from the host and the second page numbers are included in a second range not overlapping the first range,
generate a second list that groups the first page numbers and the second page numbers based on the first list, and
request map data based on the second list; and

a host memory positioned outside the storage device and configured to provide the map data to the storage device in response to a request of the storage device.

20. The electronic device of claim 19 , wherein:
the storage device includes a controller configured to translate the logical address to a physical address based on the requested map data, and
the map data match the logical address with the physical address.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Cho Yongwon
• Kim Hyeonwu
• Ahn Seok-Won

Classifications

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title

• G06F3/0658

  Controller construction arrangements · CPC title

• G06F3/0656

  Data buffering arrangements · CPC title

• G06F2212/7201

  Logical to physical mapping or translation of blocks or pages · CPC title

• G06F2212/7203

  Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks · CPC title