Flash translation layer design using reinforcement learning

Patent metadata

Field	Value
Publication number	US-11630765-B2
Application number	US-202017120908-A
Country	US
Kind code	B2
Filing date	Dec 14, 2020
Priority date	Dec 14, 2020
Publication date	Apr 18, 2023
Grant date	Apr 18, 2023

Abstract

The subject matter described herein provides systems and techniques to counter a high write amplification in physical memory, to ensure the longevity of the physical memory, and to ensure that the physical memory wears in a more uniform manner. In this regard, aspects of this disclosure include the design of a Flash Translation Layer (FTL), which may manage logical to physical mapping of data within the physical memory. In particular, the FTL may be designed with a mapping algorithm, which uses reinforcement learning (RL) to optimize data mapping within the physical memory. The RL technique may use a Bellman equation with q-learning that may rely on a table being updated with entries that take into account at least one of a state, an action, a reward, or a policy. The RL technique may also make use a deep neural network to predict particular values of the table.

First claim

The invention claimed is:

1. A method of writing data to physical memory, the method comprising:
determining a current state based on the physical memory;
executing, using one or more processors, an agent to choose a current action from a plurality of actions based on a corresponding plurality of entries of a table, the plurality of entries of the table each being associated with a write amplification factor based on a location within the physical memory to write data;
writing the data to the physical memory based on the current action;
observing a reward related to a write amplification factor associated with the physical memory based at least in part on the current state and the current action;
updating, using the one or more processors, at least one entry of the plurality of entries of the table based on the observed reward to produce an updated table; and
predicting at least one new entry to add to the updated table using a neural network trained with the updated table.

2. The method of claim 1 , further comprising training the neural network using the updated table by determining or updating a weight for connections of the neural network based on the entries in the updated table.

3. The method of claim 1 , wherein the physical memory is a flash memory, and wherein the agent includes a memory mapping algorithm.

4. The method of claim 1 , wherein each entry of the plurality of entries of the table is a q-score/q-value calculated using reinforcement learning.

5. The method of claim 1 , wherein updating, using the one or more processors, the at least one entry of the plurality of entries of the table includes updating the at least one entry of the plurality of entries of the table using a Bellman equation.

6. The method of claim 1 , wherein the agent chooses the current action based on one of a greedy policy, an ε-greedy policy, or a decaying ε-greedy policy.

7. The method of claim 1 , wherein the reward is a value that is inversely related to the write amplification factor associated with the physical memory.

8. The method of claim 1 , further comprising removing a least recently used entry of the plurality of entries in the table.

9. The method of claim 1 , wherein each node of an input layer of the neural network represents at least one feature of the table, current state, or current action.

10. The method of claim 1 , wherein each node of an output layer of the neural network represents at least one possible entry for the table.

11. A system for writing data to physical memory, the system comprising one or more processors configured to:
determine a current state based on the physical memory;
execute an agent to choose a current action from a plurality of actions based on a corresponding plurality of entries of a table, the plurality of entries of the table each being associated with a write amplification factor based on a location within the physical memory to write data;
write the data to the physical memory based on the current action;
observe a reward related to a write amplification factor associated with the physical memory based at least in part on the current state and the current action;
update at least one entry of the plurality of entries of the table based on the observed reward to produce an updated table; and
predict at least one new entry to add to the updated table using a neural network trained with the updated table.

12. The system of claim 11 , wherein the one or more processors are further configured to train the neural network using the updated table by determining or updating a weight for connections of the neural network based on the entries in the updated table.

13. The system of claim 11 , wherein the physical memory is a flash memory, and wherein the agent includes a memory mapping algorithm.

14. The system of claim 11 , wherein each entry of the plurality of entries of the table is a q-score/q-value calculated using reinforcement learning.

15. The system of claim 11 , wherein the one or more processors are further configured to update the at least one entry of the plurality of entries of the table using a Bellman equation.

16. The system of claim 11 , wherein the agent chooses the current action based on one of a greedy policy, an ε-greedy policy, or a decaying ε-greedy policy.

17. The system of claim 11 , wherein the reward is a value that is inversely related to the write amplification factor associated with the physical memory.

18. The system of claim 11 , wherein the one or more processors are further configured to remove a least recently used entry of the plurality of entries in the table.

19. A non-transitory computer-readable medium storing instructions, that when executed by one or more processors, cause the one or more processors to:
determine a current state based on a physical memory;
execute an agent to choose a current action from a plurality of actions based on a corresponding plurality of entries of a table, the plurality of entries of the table each being associated with a write amplification factor based on a location within the physical memory to write data;
write data to the physical memory based on the current action;
observe a reward related to a write amplification factor associated with the physical memory based at least in part on the current state and the current action;
update at least one entry of the plurality of entries of the table based on the observed reward to produce an updated table; and
predict at least one new entry to add to the updated table using a neural network trained with the updated table.

20. The non-transitory computer-readable medium of claim 19 , wherein the instructions, that when executed by the one or more processors, further cause the one or more processors to train the neural network using the updated table by determining or updating a weight for connections of the neural network based on the entries in the updated table.

21. The non-transitory computer-readable medium of claim 19 , wherein the physical memory is a flash memory, and wherein the agent includes a memory mapping algorithm.

22. The non-transitory computer-readable medium of claim 19 , wherein each entry of the plurality of entries of the table is a q-score/q-value calculated using reinforcement learning.

Assignees

• Google Llc

Inventors

• Silas Shashwat
• Shahidi Narges
• Gong Tao
• Benitez Manuel

Classifications

• G06N3/092

  Reinforcement learning · CPC title

• G06F2212/7207

  management of metadata or control data · CPC title

• G06F3/0679

  Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP] · CPC title

• G06N3/08

  Learning methods · CPC title

• G06F2212/1036

  Life time enhancement · CPC title