Patent US6076151A successfully refreshed from Google Patents.
US6076151A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dynamic memory allocation suitable for stride-based prefetching
Assignee: Advanced Micro Devices Inc
•
Filing: 1997-10-10
•
Granted: 2000-06-13
•
Expires: 2017-10-10
Abstract
Abstract A dynamic memory allocation routine maintains an allocation size cache which records the address of a most recently allocated memory block for each different size of memory block that has been allocated. Upon receiving a dynamic memory allocation request, the dynamic memory allocation routine determines if the requested size is equal to one of the sizes recorded in the allocation size cache. If a matching size is found, the dynamic memory allocation routine attempts to allocate a memory block contiguous to the most recently allocated memory block of that matching size. If the contiguous memory block has been allocated to another memory block, the dynamic memory allocation routine attempts to reserve a reserved memory block having a size which is a predetermined multiple of the requested size. The requested memory block is then allocated at the beginning of the reserved memory block. By reserving the reserved memory block, the dynamic memory allocation routine may increase the likelihood that subsequent requests for memory blocks having the requested size can be allocated in contiguous memory locations.
Inventors
- 👤 Stephan G. Meier
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 20:44
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0875; G06F9/00; G06F9/06; G06F9/30; G06F9/34; G06F9/345; G06F9/3455; G06F9/38; G06F9/3824; G06F9/383; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99953; Y10S707/99956
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
117 words
A method for dynamic memory allocation in a computer system, comprising: receiving a first request for dynamic allocation of a first memory block including a first number of bytes; allocating said first memory block at a first address succeeding a second address corresponding to a last byte of a previously allocated memory block having said first number of bytes; allocating said first memory block at a third address if said previously allocated memory block has a second number of bytes not equal to said first number of bytes; and reserving a second memory block beginning at said third address and including a third number of bytes equal to a predetermined multiple of said first number of bytes.
Claim 2
Independent Claim
117 words
A method for dynamic memory allocation in a computer system, comprising: receiving a first request for dynamic allocation of a first memory block including a first number of bytes; allocating said first memory block at a first address succeeding a second address corresponding to a last byte of a previously allocated memory block having said first number of bytes; allocating said first memory block at a third address if said previously allocated memory block has a second number of bytes not equal to said first number of bytes; and reserving a second memory block beginning at said third address and including a third number of bytes equal to a predetermined multiple of said first number of bytes.
Claim 3
Dependent Claim
30 words
The method as recited in claim 1 wherein said reserving comprises storing said third address, said first number of bytes, and said third number of bytes in a reserve list.
Claim 4
Dependent Claim
22 words
The method as recited in claim 2 further comprising receiving a second request for a dynamic allocation of a third memory block.
Claim 5
Dependent Claim
42 words
The method as recited in claim 3 further comprising allocating said third memory block at a fourth address succeeding a fifth address corresponding to a last byte of said first block if said third memory block has said first number of bytes.
Claim 6
Dependent Claim
43 words
The method as recited in claim 3 further comprising allocating said third memory block at a sixth address outside of said second memory block if said third memory block has a fourth number of bytes not equal to said first number of bytes.
Claim 7
Dependent Claim
24 words
The method as recited in claim 2 further comprising deallocating said first memory block upon receiving a deallocation request for said first memory block.
Claim 8
Dependent Claim
24 words
The method as recited in claim 6 further comprising releasing a reservation for said second memory block upon said deallocating said first memory block.
Claim 9
Dependent Claim
34 words
The method as recited in claim 7 further comprising deleting said third address, said first number of bytes, and said third number of bytes from said reserve list upon deallocating said first memory block.
Claim 10
Dependent Claim
28 words
The method as recited in claim 1 further comprising maintaining an allocation size cache indicating which addresses were previously allocated for memory blocks having different numbers of bytes.
Claim 11
Dependent Claim
35 words
The method as recited in claim 1 further comprising comparing said first number of bytes to said different numbers of bytes to determine if said previously allocated memory block has said first number of bytes.
Claim 12
Dependent Claim
118 words
A computer storage medium configured to store a dynamic memory management routine which, in response to a first request for a dynamic allocation of a first memory block having a first number of bytes: allocates said first memory block at a first address contiguous to a second memory block having said first number of bytes; allocates said first memory block at a second address discontiguous to said second memory block if said second memory block has a second number of bytes not equal to said first number of bytes; and reserves a third memory block beginning at said second address and having a third number of bytes equal to a predetermined multiple of said first number of bytes.
Claim 13
Dependent Claim
118 words
A computer storage medium configured to store a dynamic memory management routine which, in response to a first request for a dynamic allocation of a first memory block having a first number of bytes: allocates said first memory block at a first address contiguous to a second memory block having said first number of bytes; allocates said first memory block at a second address discontiguous to said second memory block if said second memory block has a second number of bytes not equal to said first number of bytes; and reserves a third memory block beginning at said second address and having a third number of bytes equal to a predetermined multiple of said first number of bytes.
Claim 14
Dependent Claim
35 words
The computer storage medium as recited in claim 11, wherein said dynamic memory management routine reserves said third memory block by storing said second address and said third number of bytes in a reserve list.
Claim 15
Dependent Claim
26 words
The computer storage medium as recited in claim 12, wherein said dynamic memory management routine further stores said first number of bytes in said reserve list.
Claim 16
Dependent Claim
30 words
The computer storage medium as recited in claim 11, wherein said dynamic memory management routine records a third address corresponding to said second memory block in an allocation size cache.
Claim 17
Dependent Claim
24 words
The computer storage medium as recited in claim 14, wherein said dynamic memory management routine records said first address in said allocation size cache.
Claim 18
Dependent Claim
134 words
A computer storage medium configured to store a dynamic memory management routine which, in response to a first request for a dynamic allocation of a first memory block having a first number of bytes: allocates said first memory block at a first address contiguous to a second memory block having said first number of bytes; allocates said first memory block at a second address discontiguous to said second memory block if said second memory block has a second number of bytes not equal to said first number of bytes; records a third address corresponding to said second memory block in an allocation size cache; records said first address in said allocation size cache; and overwrites said third address in said allocation size cache if said second memory block has said first number of bytes.
Claim 19
Dependent Claim
134 words
A computer storage medium configured to store a dynamic memory management routine which, in response to a first request for a dynamic allocation of a first memory block having a first number of bytes: allocates said first memory block at a first address contiguous to a second memory block having said first number of bytes; allocates said first memory block at a second address discontiguous to said second memory block if said second memory block has a second number of bytes not equal to said first number of bytes; records a third address corresponding to said second memory block in an allocation size cache; records said first address in said allocation size cache; and overwrites said third address in said allocation size cache if said second memory block has said first number of bytes.
Claim 20
Dependent Claim
41 words
The computer storage medium as recited in claim 15, wherein said dynamic memory management routine stores said first address in addition to said third address within said allocation size cache if said second memory block has said second number of bytes.
Claim 21
Dependent Claim
52 words
The computer storage medium as recited in claim 15, wherein said dynamic memory management routine further records a number of bytes corresponding to each address in said allocation size cache, whereby said dynamic memory management routine determines if said first memory block and said second memory block comprise equal numbers of bytes.
References Cited (Backward Citations)
US4912629A
Cited
US4989134A
Cited
US5261088A
Cited
US5357618A
Cited
US5561786A
Cited
US5623654A
Cited
US5787447A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-06-13 | 2003-12-13 | 2004-06-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-06-13 | 2007-12-13 | 2008-06-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-06-13 | 2011-12-13 | 2012-06-13 | $7700.00 | Window Closed / Lapsed |