Using reinforcement learning to dynamically tune cache policy parameters

Patent metadata

Field	Value
Publication number	US-11403525-B2
Application number	US-202016889104-A
Country	US
Kind code	B2
Filing date	Jun 1, 2020
Priority date	Jun 1, 2020
Publication date	Aug 2, 2022
Grant date	Aug 2, 2022

Abstract

Reinforcement learning is used to dynamically tune cache policy parameters. The current state of a workload on a cache is provided to a reinforcement learning process. The reinforcement learning process uses the cache workload characterization to select an action to be taken to adjust a value of one of multiple parameterized cache policies used to control operation of a cache. The adjusted value is applied to the cache for an upcoming time interval. At the end of the time interval, a reward associated with the action is determined, which may be computed by comparing the cache hit rate during the interval with a baseline hit rate. The process iterates until the end of an episode, at which point the parameters of the cache control policies are reset. The episode is used to train the reinforcement learning policy so that the reinforcement learning process converges to a trained state.

First claim

What is claimed is:

1. A non-transitory tangible computer readable storage medium having stored thereon a computer program for using reinforcement learning to dynamically tune cache policy parameters, the computer program including a set of instructions which, when executed by a computer, cause the computer to perform a method comprising the steps of:
creating a structured state index characterizing the current state of a workload on a cache;
providing the structured state index to a reinforcement learning process;
using, by the reinforcement learning process, the structured state index to select an action to be taken to adjust a value of a parameterized cache policy used to control operation of a cache;
using the adjusted value of the parameterized cache policy for a time interval;
determining a reward associated with the action; and
iterating the steps of providing the structured state index to the reinforcement process, using the structured state index to select the action, using the adjusted value, and determining the reward to create a training episode for the reinforcement learning process.

2. The non-transitory tangible computer readable storage medium of claim 1 , wherein the step of using, by the reinforcement learning process, the structured state index to select the action to be taken to adjust the value of the parameterized cache policy used to control operation of a cache comprises selecting one of at least two parameterized cache policies and selecting the action to be taken by adjusting the value of the selected one of the parameterized cache policies.

3. The non-transitory tangible computer readable storage medium of claim 2 , wherein the step of using the structured state index to select the action comprises adjusting only one parameter of one of the parameterized cache policies during each iteration.

4. The non-transitory tangible computer readable storage medium of claim 2 , wherein a first of the parameterized cache policies is a prefetch policy specifying a size of a look-ahead window for prefetching blocks of data to the cache, and a second of the parameterized cache policies is a segmentation policy specifying a ratio of the cache that is used for probatory and protected cache items.

5. The non-transitory tangible computer readable storage medium of claim 1 , wherein the step of determining the reward associated with the action comprises comparing a cache hit rate with a baseline cache hit rate.

6. The non-transitory tangible computer readable storage medium of claim 5 , wherein the reward is computed as a difference between the cache hit rate and the baseline cache hit rate.

7. The non-transitory tangible computer readable storage medium of claim 5 , wherein the reward is computed as a ratio between the cache hit rate and the baseline cache hit rate.

8. The non-transitory tangible computer readable storage medium of claim 1 , wherein the structured state index is formed as a vector, in which each element of the vector is formed from a number of accesses in a contiguous region of storage over a predetermined previous window of time.

9. The non-transitory tangible computer readable storage medium of claim 1 , wherein the reinforcement learning process is implemented using a Deep Neural Network.

10. The non-transitory tangible computer readable storage medium of claim 9 , wherein the reinforcement learning process is a Q-learning process.

11. The non-transitory tangible computer readable storage medium of claim 1 , further comprising resetting parameters of the parameterized cache policies at the end of each episode.

12. A method of using reinforcement learning to dynamically tune cache policy parameters, the method comprising the steps of:
creating a structured state index characterizing the current state of a workload on a cache;
providing the structured state index to a reinforcement learning process;
using, by the reinforcement learning process, the structured state index to select an action to be taken to adjust a value of a parameterized cache policy used to control operation of a cache;
using the adjusted value of the parameterized cache policy for a time interval;
determining a reward associated with the action; and
iterating the steps of providing the structured state index to the reinforcement process, using the structured state index to select the action, using the adjusted value, and determining the reward to create a training episode for the reinforcement learning process.

13. The method of claim 12 , wherein the step of using, by the reinforcement learning process, the structured state index to select the action to be taken to adjust the value of the parameterized cache policy used to control operation of a cache comprises selecting one of at least two parameterized cache policies and selecting the action to be taken by adjusting the value of the selected one of the parameterized cache policies.

14. The method of claim 13 , wherein the step of using the structured state index to select the action comprises adjusting only one parameter of one of the parameterized cache policies during each iteration.

15. The method of claim 13 , wherein a first of the parameterized cache policies is a prefetch policy specifying a size of a look-ahead window for prefetching blocks of data to the cache, and a second of the parameterized cache policies is a segmentation policy specifying a ratio of the cache that is used for probatory and protected cache items.

16. The method of claim 12 , wherein the step of determining the reward associated with the action comprises comparing a cache hit rate with a baseline cache hit rate, and computing either a difference between the cache hit rate and the baseline cache hit rate or a ratio between the cache hit rate and the baseline cache hit rate.

17. The method of claim 12 , wherein the structured state index is formed as a vector, in which each element of the vector is formed from a number of accesses in a contiguous region of storage over a predetermined previous window of time.

18. The method of claim 12 , wherein the reinforcement learning process is implemented using a Deep Neural Network.

19. The method of claim 18 , wherein the reinforcement learning process is a Q-learning process.

20. The method of claim 12 , further comprising resetting parameters of the parameterized cache policies at the end of each episode.

Assignees

• Emc Ip Holding Co Llc
• Dell Products Lp

Inventors

• Gottin Vinicius Michel
• Calmon Tiago Salviano
• Dias Jonas Furtado
• Bordignon Alex Laier
• Menasché Daniel Sadoc

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06N3/045

  Combinations of networks · CPC title

• G06N3/0499

  Feedforward networks · CPC title

• G06N3/092

  Reinforcement learning · CPC title

• G06N3/006

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