Granted Patent B2

US 10,289,557 · App. 15/688,095 · Granted May 14, 2019

Abstract

Claims (35)

1. A storage system comprising:

a volatile memory;

a non-volatile memory; and

a controller in communication with the volatile memory and the non-volatile memory, wherein the controller is configured to:

store, in the volatile memory, a data structure representing a compressed version of a logical-to-physical address table stored in the non-volatile memory, wherein each entry in the data structure comprises a start physical address and start and end logical addresses for a sequential run of logical addresses; and

search each entry in the data structure in parallel for a physical address associated with a logical address, wherein:

the searching comprises (i) simultaneously comparing the logical address both to the start logical address and to the end logical address in each entry and (ii) calculating a physical address associated with the logical address, wherein (i) and (ii) are performed in parallel, and

each entry in the data structure is searched in a same amount of time.

2. The storage system of claim 1 , wherein the controller is further configured to calculate the physical address by:

subtracting the start logical address from the logical address;

dividing by a number of entries in the data structure; and

adding the start physical address.

3. The storage system of claim 1 , wherein the non-volatile memory comprises a three-dimensional memory.

4. The storage system of claim 1 , wherein the storage system is embedded in a host.

5. A method for searching a cached, compressed database representing a logical-to-physical address table, the method comprising:

performing the following in a storage system comprising a volatile memory:

caching, in the volatile memory, a compressed database representing a logical-to-physical address table, wherein each entry in the compressed database comprises a start physical address and start and end logical addresses for a sequential run of logical addresses; and

searching each entry in the cached, compressed database in parallel for a logical address, wherein the searching comprises (i) simultaneously comparing the logical address both to the start logical address and to the end logical address in each entry and (ii) calculating a physical address associated with the logical address, wherein (i) and (ii) are performed in parallel, wherein each entry requires a same amount of time to search.

6. The method of claim 5 , wherein the physical address is calculated by:

subtracting the start logical address from the logical address;

dividing by a number of entries in the cached, compressed database; and

adding the start physical address.

7. The method of claim 5 , wherein the storage system further comprises a three-dimensional non-volatile memory.

8. The method of claim 5 , wherein the storage system is removably connectable to a host.

9. A storage system comprising:

a volatile memory;

a non-volatile memory;

means for storing, in the volatile memory, a data structure representing a compressed version of a logical-to-physical address table stored in the non-volatile memory, wherein each entry in the data structure comprises a start physical address and start and end logical addresses for a sequential run of logical addresses; and

means for searching each entry in the data structure in parallel for a physical address associated with a logical address, wherein the searching comprises (i) simultaneously comparing the logical address both to the start logical address and to the end logical address in each entry and (ii) calculating a physical address associated with the logical address, wherein (i) and (ii) are performed in parallel, wherein each entry in the data structure is searched in a same amount of time.

10. The storage system of claim 9 , wherein:

the means for searching comprises a plurality of search circuitry in communication with a decoder and a multiplexor; and

each entry of the data structure is associated with its own search circuitry.

11. The storage system of claim 10 , wherein at least one search circuitry comprises a comparator, an AND gate, a subtractor, a divider, and an adder.

12. The storage system of claim 9 , wherein the non-volatile memory comprises a three-dimensional memory.

13. The storage system of claim 9 , wherein the storage system is embedded in a host.

Assignments (10)