Granted Patent B2

US 10,445,232 · App. 15/627,042 · Granted Oct 15, 2019

Abstract

Claims (64)

1. A data storage system for determining a cumulative control state for mapping logical block addresses (LBAs) to physical block addresses (PBAs), the system comprising:

a bitonic network comprising first switches and configured to:

receive a first randomly ordered list and random switch settings;

determine a permutation of the first randomly ordered list using the random switch settings at the first switches, wherein the permutation comprises a second randomly ordered list; and

output the second randomly ordered list;

a bitonic sorter comprising second switches and configured to:

receive the second randomly ordered list;

sort the second randomly ordered list; and

output settings of the second switches used to achieve the sort, wherein the second switch settings define a cumulative control state; and

an access network configured to determine a PBA of a non-volatile memory (NVM) to enable a data access of a corresponding LBA using the cumulative control state.

2. The data storage system of claim 1 , wherein the sort is ascending.

3. The data storage system of claim 1 , wherein the sort is descending.

4. The data storage system of claim 1 , wherein the sort comprises a naturally order sort.

5. The data storage system of claim 1 , wherein the bitonic sorter is configured to output a naturally ordered list.

6. The data storage system of claim 5 , wherein the naturally ordered list comprises the numbers from 0 to M−1 where M is the number of inputs to the bitonic network.

7. The data storage system of claim 1 , wherein the access network is further configured to:

generate a first PBA candidate from a LBA using a first function;

generate a second PBA candidate from the LBA using a second function; and

select either the first PBA candidate or the second PBA candidate for data access based on information related to a background swap of data stored at the first PBA candidate and a background swap of data stored at the second PBA candidate.

8. The data storage system of claim 7 , wherein at least one of the first function or the second function comprises a function performed by at least one of a multi-stage interconnection network or a block cipher.

9. A method for determining a cumulative control state for mapping logical block addresses (LBAs) to physical block addresses (PBAs) of a data storage device, the method comprising:

generating, randomly, first switch settings;

receiving a first randomly ordered list and the first switch settings;

generating a permutation of the first randomly ordered list using the first switch settings, wherein the permutation comprises a second randomly ordered list;

sorting the second randomly ordered list using a bitonic sort;

determining settings of second switches used to achieve the bitonic sort, wherein the second switch settings define a cumulative control state; and

determining a PBA of a non-volatile memory (NVM) to enable a data access of a corresponding LBA using the cumulative control state.

10. The method of claim 9 , further comprising:

generating a bitonic network comprising a plurality of first switches;

generating a bitonic sorter comprising a plurality of second switches;

wherein the receiving the first randomly ordered list and the first switch settings comprises receiving, at the bitonic network, the first randomly ordered list and the first switch settings;

wherein the generating the permutation of the first randomly ordered list using the first switch settings comprises generating the permutation of the first randomly ordered list using the first switch settings at the first switches;

wherein the sorting the second randomly ordered list using the bitonic sort comprises sorting, at the bitonic sorter, the second randomly ordered list; and

wherein the determining the settings of second switches used to achieve the sort comprises determining the settings of the second switches of the bitonic sorter used to achieve the bitonic sort.

11. The method of claim 10 , wherein the bitonic network comprises at least one of a Benes network, an inverse Benes network, an inverse Bitonic network, an Omega network, an inverse Omega network, a Butterfly network, or an inverse Butterfly network.

12. The method of claim 9 , wherein the sort is ascending.

13. The method of claim 9 , wherein the sort is descending.

14. The method of claim 9 , wherein the sort comprises a naturally order sort.

15. The method of claim 9 , wherein the sorting the second randomly ordered list using the bitonic sort comprises generating a naturally ordered list.

16. The method of claim 15 , further comprising:

generating a bitonic network comprising a plurality of first switches;

wherein the receiving the first randomly ordered list and the first switch settings comprises receiving, at the bitonic network, the first randomly ordered list and the first switch settings; and

wherein the naturally ordered list comprises the numbers from 0 to M−1 where M is the number of inputs to the bitonic network.

17. The method of claim 9 , wherein the determining the PBA of the NVM to enable the data access of the corresponding LBA using the cumulative control state comprises:

generating a first PBA candidate from a LBA using a first function;

generating a second PBA candidate from the LBA using a second function; and

selecting either the first PBA candidate or the second PBA candidate for data access based on information related to a background swap of data stored at the first PBA candidate and a background swap of data stored at the second PBA candidate.

18. The method of claim 17 , wherein at least one of the first function or the second function comprises a function performed by at least one of a multi-stage interconnection network or a block cipher.

19. A data storage system for determining a cumulative control state for mapping logical block addresses (LBAs) to physical block addresses (PBAs), the system comprising:

means for randomly generating first switch settings;

means for receiving a first randomly ordered list and the first switch settings;

means for generating a permutation of the first randomly ordered list using the first switch settings, wherein the permutation comprises a second randomly ordered list;

means for sorting the second randomly ordered list using a bitonic sort;

means for determining settings of second switches used to achieve the bitonic sort, wherein the second switch settings define a cumulative control state; and

means for determining a PBA of a non-volatile memory (NVM) to enable a data access of a corresponding LBA using the cumulative control state.

20. The data storage system of claim 19 , wherein the sort is ascending.

21. The data storage system of claim 19 , wherein the sort is descending.

22. The data storage system of claim 19 , wherein the sort comprises a naturally order sort.

23. The data storage system of claim 19 , wherein the means for sorting the second randomly ordered list using the bitonic sort comprises means for generating a naturally ordered list.

24. The data storage system of claim 19 , wherein the means for determining the PBA of the NVM to enable a data access of a corresponding LBA using the cumulative control state comprises:

means for generating a first PBA candidate from a LBA using a first function;

means for generating a second PBA candidate from the LBA using a second function; and

means for selecting either the first PBA candidate or the second PBA candidate for data access based on information related to a background swap of data stored at the first PBA candidate and a background swap of data stored at the second PBA candidate.

25. The data storage system of claim 24 , wherein at least one of the first function or the second function comprises a function performed by at least one of a multi-stage interconnection network or a block cipher.

Assignments (10)