Parallel memory allocator employing liveness metrics

Patent metadata

Field	Value
Publication number	US-10013348-B2
Application number	US-201514850474-A
Country	US
Kind code	B2
Filing date	Sep 10, 2015
Priority date	Sep 10, 2015
Publication date	Jul 3, 2018
Grant date	Jul 3, 2018

Abstract

A liveness-based memory allocation module operating so that a program thread invoking the memory allocation module is provided with an allocation of memory including a reserve of free heap slots beyond the immediate requirements of the invoking thread. The module receives a parameter representing a thread execution window from an invoking thread; calculates a liveness metric based upon the parameter; calculates a reserve of memory to be passed to the invoking thread based upon the parameter; returns a block of memory corresponding to the calculated reserve of memory. Equations, algorithms, and sampling strategies for calculating liveness metrics are disclosed, as well as a method for adaptive control of the module to achieve a balance between memory efficiency and potential contention as specified by a single control parameter.

First claim

The invention claimed is:

1. A non-transitory, computer readable storage medium encoding a memory allocation module, the memory allocation module including instructions executable by a processor unit to perform:
(1) receiving a parameter representing a length of a thread execution window from an invoking thread;
(2) calculating a liveness metric for the invoking thread, the liveness metric representing heap slot reuse or a number of live data objects within the thread execution window, based upon the parameter;
(3) calculating a reserve of memory to be provided to the invoking thread based upon the parameter and the liveness metric; and
(4) returning a pointer to an allocation of memory corresponding to the calculated reserve of memory, the allocation containing one or more chunks of memory that can be traversed via the pointer,

whereby a program thread invoking the memory allocation module is provided with an allocation of memory including a reserve of free heap slots beyond the immediate requirements of the invoking thread.

2. The storage medium of claim 1 , wherein the liveness metric represents, for a time window with a length specified by the parameter, the average number of times that local heap slots which were holding live objects at the start of the time window were freed and then allocated to hold new objects within the span of the time window, for multiple possible windows of the length.

3. The storage medium of claim 1 , wherein the liveness metric is calculated according to:

reuse
⁡

(
k
)

=

∑

i
=
1

m

⁢

I
⁡

(

e
i

-

s
i

≤
k

)

⁢

(

min
⁡

(

n
-
k

,

s
i

)

-

max
⁡

(

k
,

e
i

)

+
k
+
1

)

n
-
k
+
1

,

where k is the parameter,
where s i and e i are a time interval logical start time and end time, respectively, during an i one of m free intervals in which a thread-local heap slot is free, unallocated, and unoccupied,
where n is the current logical time, and
where function I is a predicate equal to 1 if the condition (e i −s i ≤k) is true or else 0.

4. The storage medium of claim 1 , wherein the liveness metric is calculated according to:
reuse ⁡ ( k ) = X ⁡ ( k ) - Y ⁡ ( k ) + Z ⁡ ( k ) n - k + 1 where X (1)=Σ i=1 m I ( e i −s i =1) s i

X ( k )= X ( k− 1)−Σ i=1 m I ( s i ≥n −( k− 1))+Σ i=1 m I ( e i −s i =k )min( n−k,s i ), for k> 1

Y (1)=Σ i=1 m I ( e i −s i =1) e i

Y ( k )= Y ( k− 1)−Σ i=1 m I ( e i ≤k− 1)+Σ i=1 m I ( e i −s i =k )max( k,e i ), for k> 1

Z (1)=2Σ i=1 m I ( e i −s i =1)

Z ( k )= Z ( k− 1)+Σ i=1 m I ( e i −s i ≤k )+ kΣ i=1 m I ( e i −s i =k ), for k> 1

where k is the parameter,
where s i and e i are a time interval logical start time and end time, respectively, during an i one of m free intervals in which a thread-local heap slot is free, unallocated, and unoccupied,
where n is the current logical time, and
where function I is a predicate equal to 1 if the respective parenthetical condition is true or else 0.

5. The storage medium of claim 4 , wherein the liveness metric is calculated during a plurality of burst periods, each burst period being separated from a next-in-time burst period by a hibernation period.

6. The storage medium of claim 1 , wherein the liveness metric represents, for a time window with a length specified by the parameter, the number of live objects in a local heap existing within the time window plus the number of objects in the local heap newly allocated within the time window, averaged over multiple possible windows of the length.

7. The storage medium of claim 1 , wherein the liveness metric is calculated according to:

live
⁡

(
k
)

=

∑

i
=
1

m

⁢

min
⁡

(

n
-
k
+
1

,

Assignees

• Li Pengcheng
• Ding Chen
• Univ Rochester

Inventors

• Li Pengcheng
• Ding Chen

Classifications

• G06F3/0605

  by facilitating the interaction with a user or administrator · CPC title

• G06F12/0284 Primary

  Multiple user address space allocation, e.g. using different base addresses (interprocessor communication G06F15/163) · CPC title

• G06F3/0631

  by allocating resources to storage systems · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F9/5016

  the resource being the memory · CPC title