Solid state drive cache eviction policy by an unsupervised reinforcement learning scheme

Patent metadata

Field	Value
Publication number	US-10977179-B2
Application number	US-201916453179-A
Country	US
Kind code	B2
Filing date	Jun 26, 2019
Priority date	Sep 28, 2018
Publication date	Apr 13, 2021
Grant date	Apr 13, 2021

Abstract

A method and apparatus for cache management and eviction polices using unsupervised reinforcement learning schemes is disclosed.

First claim

What is claimed is:

1. A storage device, comprising:
a memory device;
a logical to physical (L2P) cache comprising a plurality of L2P-units, each of the plurality of L2P-units having a value function;
a controller coupled to the memory device and to the L2P cache, the controller configured to:
initialize each of the plurality of L2P-units at an initial value function of zero;
receive a read command;
determine whether one of the plurality of L2P-units of the L2P cache is related to the read command received;
determine another one of the L2P-units having a lowest value function in the L2P cache;
determine whether a new L2P-unit has a value function higher than the lowest value function of the another one of the L2P-units in the L2P cache;
replace the another one of the L2P-units with the new L2P-unit; and
update the value function of the new L2P-unit to include a reward.

2. The storage device of claim 1 , wherein the controller is further configured to decay the value function of each of the plurality of L2P-units by γ multiplier after the value function of the new L2P-unit is updated to include the reward.

3. The storage device of claim 1 , wherein the controller is further configured to, after determining the one of the plurality of L2P-units of the L2P cache is related to the read command received, update the value function of the one of the plurality of L2P-units of the L2P cache with a second reward.

4. The storage device of claim 1 , wherein the controller is further configured to, after determining that the value function of the new L2P-unit is not higher than the lowest value function of the another one of the L2P-units in the L2P cache, keep the another one of the L2P-units in the L2P cache.

5. A storage device, comprising:
a memory device;
a logical to physical (L2P) cache comprising a plurality of L2P-units, each of the plurality of L2P-units having a value function; and
a controller means for updating the L2P cache to maintain a defined size of the L2P cache, wherein the controller means is configured to:
determine whether there is a cache hit;
evict one of the plurality of L2P-units through reinforcement learning means for determining that the one of the plurality of L2P-units has a lowest value function; and
the one of the plurality of L2P-units with a new L2P-unit for a current host read.

6. The storage device of claim 5 , wherein the controller means is further configured to initiate the value function of each of the plurality of L2P-units to zero.

7. The storage device of claim 5 , wherein the controller means is configured to determine whether there is a cache hit in response to a read command received.

8. The storage device of claim 5 , wherein a value function of the new L2P-unit includes a reward.

9. A method of updating a logical to physical (L2P) cache comprising a plurality of L2P-cache units of a storage device, the method comprising:
initializing an initial value function of each of a plurality of L2P-units to zero;
receiving a read command;
determining whether one of the plurality of L2P-units of the L2P cache is related to the read command received;
determining another one of the L2P-units having a lowest value function in the L2P cache;
determining whether a new L2P-unit has a value function higher than the lowest value function of the another one of the L2P-units in the L2P cache;
replacing the another one of the L2P-units with the new L2P-unit; and
updating the value function of the new L2P-unit to include a reward.

10. The method of claim 9 , further comprising decaying the value function of each of the plurality of L2P-units by γ multiplier after the value function of the new L2P-unit is updated with the reward.

11. The method of claim 9 , further comprising, after determining the one of the plurality of L2P-units of the L2P cache is related to the read command received, updating the value function of the one of the plurality of L2P-units of the L2P cache with a second reward.

12. The method of claim 9 , further comprising, after determining that the value function of the new L2P-unit is not higher than the lowest value function of the another one of the L2P-units in the L2P cache, keeping the another one of the L2P-units in the L2P cache.

Assignees

• Western Digital Tech Inc

Inventors

• Lieber Opher
• Navon Ariel
• Bazarsky Alexander
• Benisty Shay

Classifications

• G06F12/0871 Primary

  Allocation or management of cache space · CPC title

• G06N3/006

  based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO] · CPC title

• G06F2212/214

  Solid state disk · CPC title

• Y02D10/00

  Energy efficient computing, e.g. low power processors, power management or thermal management · CPC title

• G06F2212/7201

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