Source: https://patents.google.com/patent/US20040073764?oq=7%2C603%2C356
Timestamp: 2018-04-20 02:00:30
Document Index: 225538273

Matched Legal Cases: ['arts 262', 'arts 266', 'art 282', 'art 284', 'arts 302', 'arts 306', 'art 322', 'art 324', 'arts 342', 'arts 346', 'art 362', 'art 364', 'art 382', 'art 384', 'art 386', 'art 402', 'art 404']

US20040073764A1 - System and method for reinforcement learning and memory management - Google Patents
System and method for reinforcement learning and memory management Download PDF
US20040073764A1
US20040073764A1 US10630525 US63052503A US2004073764A1 US 20040073764 A1 US20040073764 A1 US 20040073764A1 US 10630525 US10630525 US 10630525 US 63052503 A US63052503 A US 63052503A US 2004073764 A1 US2004073764 A1 US 2004073764A1
US7174354B2 (en )
In accordance with one embodiment, the invention comprises a system for memory management comprising: a computer system or virtual machine having a memory or storage space; and, wherein reinforcement learning logic is used to control the management of the memoryor storage space. Other embodiments and implementations may be developed within the spirit and scope of the invention.
[0014]FIG. 1 shows an illustration of a memory including allocations.
[0015]FIG. 2 shows an illustration of a garbage collection technique.
[0016]FIG. 3 shows an illustration of a generational garbage collector.
[0017]FIG. 4 shows a diagram of a system in accordance with an embodiment of the invention, and illustrates how an RLS garbage collector can be used in an application server environment or system to optimize the application server and the applications running thereon.
[0018]FIG. 5 shows an illustration of various methods of extracting generalized representation of states.
[0019]FIG. 6 shows an illustration of a model of a reinforcement learning system.
[0020]FIG. 7 shows an illustration of a memory showing a good situation with a high freeing rate and much memory left in the unallocated part of the heap is illustrated to the left (1). A worse situation is illustrated to the right (2).
[0021]FIG. 8 shows an illustration of various memory allocation situations.
[0022]FIG. 9 shows a code listing in accordance with an embodiment of the invention, including pseudo code used to address the garbage collection problem.
[0023]FIG. 10 shows performance graphs of an RLS-based system in accordance with an embodiment if the invention compared to a regular JVM for short intervals.
[0024]FIG. 11 shows penalty graphs of an RLS system compared to a regular JVM.
[0025]FIG. 12 shows performance graphs of an RLS-based system in accordance with an embodiment of the invention compared to a regular JVM, for long intervals.
[0026]FIG. 13 shows penalty graphs of an RLS system compared to a regular JVM.
[0027]FIG. 14 shows performance graphs of an RLS-based system in accordance with an embodiment of the invention compared to a regular JVM, for random intervals.
[0028]FIG. 15 shows penalty graphs of an RLS system compared to a regular JVM.
[0029]FIG. 16 shows a graph of Q-function overtime in accordance with an embodiment of the invention.
[0030]FIG. 17 shows a graph of accumulated penalty for two states in accordance with an embodiment of the invention.
[0031]FIG. 18 shows a contour-plot of the Q-function at time step 2500, when the system has not yet run out of memory.
[0032]FIG. 19 shows a contour-plot of the Q-function at time step 10000, when the system has started to occasionally run out of memory.
[0033]FIG. 20 shows a contour-plot of the Q-function at time step 50000, when the system has stopped learning.
[0034]FIG. 21 shows an enlarged contour-plot of the Q-function at time step 50000, to be able to see the detailed decision boundary when s1 and s2<15%.
R=r t +γr t=1+γ2 r t+2
The discount factor γε[0,1] favors immediate rewards over equally large payoffs to be obtained in the future, similar to the notion of an interest rate in economics.
[0114]FIG. 1 shows an illustration of a memory 100 including allocations. At the top an allocated list 102 is shown. In the middle a memory leak 104 is illustrated. At the bottom a memory leak and a dangling reference 106 are illustrated. Memory leaks are memory that is referenced by deallocated memory. A dangling reference is a reference to memory that has been deallocated. These problems cause the computer program to eventually crash, or even worse, to keep running but calculating wrong values.
Incremental Coll ction
Mem ry Blocking
Pr{s (t+1) =s′, r (t+1) =r|s t , a t ,r t ,s (t−1) , a (t−1) , . . . , r 1 ,s 0 ,a 0}
Pr{s t+1 =s′, r t+1 =r|s t , a t}
[0172]FIG. 4 illustrates how the invention can be used in an application server environment or system to optimize the performance of the application server and the applications running thereon. As shown in FIG. 4, the computer system 150 typically includes an operating system 151 upon which a virtual machine 152 (such as a JVM or run time environment) operates. The application server 153 sits upon this JVM run time environment 152. Applications 156, 157, 158 execute within the memory 155 of the system, where they may be accessed by clients. An RLS-based garbage collector 154 in accordance with an embodiment of the invention is used in conjunction with the virtual machine 152 to garbage collect the memory 155 in accordance with the reinforcement learning techniques described herein.
The ε—greedy algorithm chooses the calculated, best action most of the times, but with small probability ε a random action is selected instead. This algorithm satisfies both needs for exploration and exploitation.
The soft-max algorithm works similar to the ε—greedy algorithm but does not choose alternative actions completely at random but according to a weighted probability. The probability of an action is weighted with respect to the estimated Q-value of the current state and that action. The main difference between ε—greedy and the soft-max algorithm is that in the latter case, when a non-optimal action is chosen, it is more likely that the system chooses the next-best action rather than an arbitrary action. The highest probability is always given to the estimated current best action.
The greedy algorithm works best in deterministic environments, while the ε—greedy algorithm works best in stochastic environments. The soft-max algorithm is the most secure algorithm since it has a low probability of choosing inferior actions. The uncertainty about the application environment, the run-time context and the incomplete state information introduces a stochastic component into garbage collection problem. Hence, in accordance with one embodiment the ε—greedy algorithm is chosen.
Q(s, a, θ)=θ1 s 1+. . . +θm s m+θ(m+1)a
[0206]FIG. 6 shows an illustration of a general model of a reinforcement learning system. First the decision process 182 observes the current state and reward 184. Then the decision process performs an action 186 that effects the environment 188. Finally the environment returns a reward and the new state. The reinforcement learning algorithm obtains the information about the current state and the reward from the environment. The reinforcement learning algorithm decides what action to take next and updates its prior belief about the world based on the observed reward and the new state. The process either terminates when a final goal state is reached, (or in the case of an infinite horizon problem continues forever).
If s and a are the vectors representing states and actions, then the estimated state-action value of that state and action is Q(s, a). The linear gradient-descent approximation of the action-value function Q(s, a) will then be Q(s, a, θ), where θ is a vector containing the weight coefficients (θ1−θm+n) below).
Q(s, a)=θ1 s 1+. . . +θm s m+θ(m+1) a 1+. . . +θ(m+n) a n
∇θ(s, a, θ):[d Q(s, a, θ)/d θ i d Q(s, a, θ)/d θ i]
d Q(s, a, θ)/dθ i =s i, for 0≦i<n
d Q(s, a, θ)/dθ i =a i-n, for n≦i<n+m
[0270]FIG. 9 shows a code listing 240 in accordance with an embodiment of the invention, showing pseudo code modified to suit the concrete problem of garbage collection. The pseudo code concerns SARSA with linear, gradient-descent function approximation using a soft-max policy.
Probability to choose a random action P=P0* e−(Timestep2/C)
Where C is between 2000-5000 and P0=0.5. C corresponds to the square number of steps at which the original probability P0 of chosen a random action decreased by a factor e−1.
Probability to choose a random action=0.5*e−(TimeStep/C)
Learning rate=0.1*e−(TimeStep/D)
A non-uniform tiling was chosen, in which the tile resolution is increased for states of low available memory, and a coarser resolution for states in which memory occupancy is still low. The tiles for feature s1 correspond to the intervals [0,4], [4,8], [8,10], [10,12], [12,14], [14,16], [16,18], [18,20], [22,26] and [30,100]. The tiles for feature s2 are the same as for feature s1.
[0290]FIG. 10 shows performance graphs 260 of an RLS-based system in accordance with an embodiment of the invention compared to a regular JVM for short intervals. To the left 262,266 the interval performance of the RLS is compared to the interval performance of JRockit when running the application with short intervals. To the right 264, 268 the accumulated time performance is illustrated. The upper charts 262, 264 show the performances during the first 20 intervals and the lower charts 266, 268 show the performances during 20 intervals after ca 50000 time steps. In the beginning the RLS performs a lot worse than the converted JVM (JRockit) due to the random choices of actions and the fact that the RLS is still learning about the environment. After about 50000 time steps the performance of the RLS compared to JRockit is about the same. This shows the tendency of a decreasing need of time, i.e. decreasing frequency of garbage collections, for the RLS system as it learns.
[0291]FIG. 11 shows penalty graphs 280 of an RLS system compared to a regular JVM. The upper chart 282 shows the accumulated penalty for the RLS compared to the accumulated reward for JRockit when running the application with short intervals. The lower chart 284 shows the average penalty as a function of time. The accumulated penalty for running out of memory becomes constant over time, which demonstrates that the RLS actually learns to avoid running out of memory. After 13000 time steps all future penalties imposed on the RLS are due to garbage collection only. After about 20000 time steps the rate at which JRockit and the RLS are penalized for invoking garbage collections becomes similar.
[0292]FIG. 12 shows performance graphs 300 of an RLS-based system in accordance with an embodiment of the invention compared to a regular JVM, for long intervals. To the left 302, 306 the interval performance of the RLS is compared to the interval performance of JRockit when running the application with long intervals. To the right 304, 308 the accumulated time performance is illustrated. The upper charts 302, 304 show the performances during the first 20 intervals and the lower charts 306, 308 show the performances during 20 intervals after ca 50000 time steps. As may be seen, the RLS performs slightly worse in the beginning than in the short interval application case. This application environment seems to be more difficult for the RLS to learn, due to the fact that it runs out of memory more times than in the previous case during the learning phase (nine times instead of five times).
[0293]FIG. 13 shows penalty graphs 320 of an RLS system compared to a regular JVM. The upper chart 322 shows the accumulated penalty for the RLS compared to the accumulated reward for JRockit when running the application with long intervals. The lower chart 324 shows the average penalty as a function of time. The results are almost the same as for the application with the short intervals, as mentioned above. The accumulated penalty for running out of memory becomes constant overtime in this case too and the accumulated penalty for invoking garbage collections develops in the same way as in the previous case.
[0294]FIG. 14 shows performance graphs 340 of an RLS-based system in accordance with an embodiment of the invention compared to a regular JVM, for random intervals. To the left 342, 346 the interval performance of the RLS is compared to the interval performance of JRockit when running the application with randomly appearing intervals. To the right 344, 348 the accumulated time performance is illustrated. The upper charts 342, 344 show the performances during the first 20 intervals and the lower charts 346, 348 show the performances during 20 intervals after ca 50000 time steps. Due to the random distribution of intervals an interval-to-interval performance comparison of these two different runs is not meaningful. Instead, the accumulated time performances illustrated to the right in FIG. 14 are used for comparison. As can be seen in the lower chart to the right the RLS performs slightly better than JRockit in this dynamic environment. This confirms that the RLS is able to outperform an ordinary JVM in a dynamic environment.
[0295]FIG. 15 shows penalty graphs 340 of an RLS system compared to a regular JVM. The upper chart 362 illustrates the accumulated penalty for the RLS compared to JRockit during a test session with the application with randomly appearing intervals. The lower chart 364 illustrates the average penalty as a function of time. The results show that the RLS runs out of memory a few times more than in the other cases, but learns to avoid it over time, even in this more dynamic case.
[0297]FIG. 16 shows a graph 380 of Q-function overtime in accordance with an embodiment of the invention. The figure shows the development of the state-action value function, the Q-function, overtime. The upper chart 382 shows the Q-function after ca 2500 time steps. The middle chart 384 shows the Q-function after ca 10000 time steps and the lower chart 386 shows the Q-function after ca 50000 time steps and is then constant. Initially, the probability of choosing a random action is still very high and the frequency of choosing the action to garbage collect is high enough to prevent the system from running out of memory. On the other hand the high frequency of random actions during the first 5000 time steps does not require the system to pick a garbage collection action, which means that it will always favor not to garbage collect in order to avoid the penalty. Running out of memory never occurs due to the high value of p0 (0.5) in the probability function for choosing a random action. This can easily be adjusted by choosing a lower value of p0. The only thing the system has learned so far is that it is better to not garbage collect than to garbage collect with a Q-value difference of −10, which is the penalty of invoking a garbage collection.
In some instances, the results from using both the state features s1 and s2 (the current amount of available memory and the previous amount of available memory) may be worse than in the case of only one state feature. One reason for the inferior behavior is that the new feature increases the number of states and that therefore converging to the correct Q-values requires more time. Another reason is that the state feature s2 does not contain the right information as a lot of states that are never visited, e.g. s1=10% and s2=70%. Methods to address this include using the change in available memory s1-s2 as an additional feature at a resolution: [0-2], [3-4], [5-6], [7-8], [9-10]. In any case the probability for choosing a random action the learning rate can be adjusted such that all states at which the system potentially could run out of memory are visited frequently enough. FIG. 17 shows a graph 400 of accumulated penalty for two states in accordance with an embodiment of the invention. The upper chart 402 shows the accumulated penalty for JRockit compared to the accumulated penalty for the RLS using two state features when running the test application with randomly appearing intervals. The lower chart 404 shows that the system still runs out of memory after ca 50000 time steps and hence has not learned all states that lead to running out of memory due to the increased amount of states and to the additional state feature not giving enough information, i.e. has not yet converged to a proper Q-function and policy.
Plots of the Q-function at different stages during the test session are illustrated in FIGS. 18, 19 and 20. In FIG. 18 the Q-function at time step 2500 is illustrated. At time step 2500 the system has not yet run out of memory and hence has not yet learned any state that leads to a penalty of −500. The Q-value for not performing a garbage collection is always better than the alternative action to perform a garbage collection. After about 10000 decisions (i.e. at time step 10000) the system encounters states in which it runs out of memory. This can be seen in FIG. 19 as in states of little memory available the Q-values for performing garbage collections are higher than those for not performing garbage collections. Whereas FIG. 19 illustrates the contour plots of the Q-function after 10000 time steps, FIG. 20 shows the same information after 50000 time steps. At this stage the Q-values did converge. It is interesting to observe that the part of the state space for which garbage collection is preferred is much smaller than in the case of only one state feature, where the decision boundary for s1 was about 12-14%.
[0304]FIG. 21 is an enlarged region to show the details from the contour plots in FIG. 20, where s1 and s2<15%. As may be observed, s2 plays some role, otherwise the decision boundary would be a line parallel to the y-axis. For example, the additional state feature seem to matter in the state s1=10% and s2=15%. This situation represents a high memory allocation rate (about 5%) and the Q-value for performing a garbage collection is higherthan for not performing one. On the other hand, in the state s=10% and s2=12% for which the memory allocation rate is low (about 2%), the action not to garbage collect has higher Q-value than the action garbage collect. Such a behavior is intuitively comprehensible, even though the entire decision boundary for even lower values of s1 and s2 cannot be explained satisfactorily. It might be that these states of very low memory (s1, s2<5%) are not visited at all once garbage collection is invoked for their successor states. Therefore, the Q-values for this part of the state space are not correct.
In all the plots above it can be observed that for high memory available the difference between the Q-values for performing a garbage collection and not performing a garbage collection is about 10, which matches exactly the penalty for performing a garbage collection. This makes sense insofar as the state after performing a garbage collection when the amount of memory available is high is also one of high memory available. It can also be seen that states for which s2 is much smaller than s1 never occur as the memory allocation rate is limited. This observation indicates that the memory allocation rate s2−s1 is a better state feature to use than s2 in some instances.
1 A system for memory management comprising:
a computer system or virtual machine having a memory space; and,
wherein reinforcement learning is used to control the management of the memory space.
2. The system of claim 1 wherein the management of the memory or storage space includes a garbage collection process.
3. The system of claim 1 wherein the virtual machine is a Java Virtual Machine.
4. The system of claim 1 wherein the reinforcement learning uses a temporal difference method.
5. The system of claim 4 wherein the temporal difference method uses on-line SARSA.
6. The system of claim 5 wherein the temporal difference method using SARSA uses tile coding.
7. A system for memory management comprising:
a garbage collector that uses reinforcement learning to control the allocation of memory to applications within said memory space.
8. The system of claim 7 wherein the virtual machine is a Java Virtual Machine.
9. The system of claim 7 wherein the reinforcement learning uses a temporal difference method.
10. The system of claim 9 wherein the temporal difference method uses on-line SARSA.
11. The system of claim 10 wherein the temporal difference method using SARSA uses tile coding.
12. A method for memory management comprising the steps of:
analyzing the memory or storage space of a computer system or virtual machine; and,
using a reinforcement learning technique to control the management of the memory or storage space.
13. The method of claim 12 wherein the management of the memory or storage space includes a garbage collection process.
14. The method of claim 12 wherein the virtual machine is a Java Virtual Machine.
15. The method of claim 12 wherein the reinforcement learning uses a temporal difference method.
16. The method of claim 15 wherein the temporal difference method uses on-line SARSA.
17. The method of claim 16 wherein the temporal difference method using SARSA uses tile coding.
US20040073764A1 true true US20040073764A1 (en) 2004-04-15
US7174354B2 US7174354B2 (en) 2007-02-06
US20170075802A1 (en) * 2004-01-21 2017-03-16 International Business Machines Corporation Determining a benefit of reducing memory footprint of a java application
KR100772871B1 (en) * 2006-02-24 2007-11-02 삼성전자주식회사 Apparatus and method for managing resource on Java environment
US9858183B2 (en) * 2004-01-21 2018-01-02 International Business Machines Corporation Determining a benefit of reducing memory footprint of a Java application
US7461220B2 (en) * 2004-06-04 2008-12-02 International Business Machines Corporation Free item distribution among multiple free lists during garbage collection for more efficient object allocation
US7174354B2 (en) 2007-02-06 grant
Lovejoy 1991 A survey of algorithmic methods for partially observed Markov decision processes
Kulkarni et al. 2004 Fast searches for effective optimization phase sequences
US7624085B2 (en) 2009-11-24 Hierarchical based system for identifying object using spatial and temporal patterns
Hansen et al. 2001 Monitoring and control of anytime algorithms: A dynamic programming approach