Patent US5715430A successfully refreshed from Google Patents.
US5715430A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multiprocessor computer system and a method for memory allocation to optimize cache coherency within the system
Assignee: Toshiba Corp
•
Filing: 1996-12-18
•
Granted: 1998-02-03
•
Expires: 2016-12-18
Abstract
Abstract A multiprocessor system and method for allocating data into a cachet to minimize the amount of data transaction among the caches for achieving a cache consistency. The system has a plurality of processors, each having a cache. An outside common memory stores data and a bus line is coupled among the respective caches for transferring data among the caches and the common memory for achieving a snooping function among the caches in order to maintain cache consistency. Each processor further includes a memory space allocation controller for controlling a requested data into the cache with a predetermined cache line unit. The memory space allocation controller includes a memory space allocation requestor, a cache line size recognizer and memory space allocator for allocating memory space in accordance with instructions from both the memory space allocation requestor and the cache line size recognizer so as to allocate the requested data within a minimum cache line number.
Inventors
- 👤 Hideaki Hirayama
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 13:19
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/0815
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
262 words
A multiprocessor system comprising: (a) a plurality of processors, each having a cache for storing data; (b) an external common memory for storing data; (c) a bus coupled to the common memory and to each cache for transferring data among the caches and the common memory, and (d) a memory allocation controller for controlling allocation of memory space, wherein the memory allocation controller comprises: (i) means for accepting a memory space allocation request from said processors, (ii) means for recognizing a size of a line of said cache, (iii) means for allocating memory space based on a requested size of memory space allocation obtained from the memory space allocation request obtained from the means for accepting and on the size of the line of said cache obtained from the recognizing means so as to allocate the requested memory space within a minimum possible number of cache lines in said cache during caching data from the memory to the cache, and (iv) means for recognizing the alignment of the cache and for providing the alignment to the memory space allocation means, wherein said means for allocating memory space uses a predetermined cache line occupation ratio in order to determine whether a cache line should be used for an allocation, and wherein the means for requesting memory space allocation requests a minimum allocation size for a requested data, and the memory space allocation means uses the following formula, evaluated by integer computations, to determine the minimum number of cache lines: ((requested minimum allocation size of a memory space+cache line size-1)÷cache line size)×cache line size.
Claim 2
Dependent Claim
262 words
A multiprocessor system comprising: (a) a plurality of processors, each having a cache for storing data; (b) an external common memory for storing data; (c) a bus coupled to the common memory and to each cache for transferring data among the caches and the common memory, and (d) a memory allocation controller for controlling allocation of memory space, wherein the memory allocation controller comprises: (i) means for accepting a memory space allocation request from said processors, (ii) means for recognizing a size of a line of said cache, (iii) means for allocating memory space based on a requested size of memory space allocation obtained from the memory space allocation request obtained from the means for accepting and on the size of the line of said cache obtained from the recognizing means so as to allocate the requested memory space within a minimum possible number of cache lines in said cache during caching data from the memory to the cache, and (iv) means for recognizing the alignment of the cache and for providing the alignment to the memory space allocation means, wherein said means for allocating memory space uses a predetermined cache line occupation ratio in order to determine whether a cache line should be used for an allocation, and wherein the means for requesting memory space allocation requests a minimum allocation size for a requested data, and the memory space allocation means uses the following formula, evaluated by integer computations, to determine the minimum number of cache lines: ((requested minimum allocation size of a memory space+cache line size-1)÷cache line size)×cache line size.
Claim 3
Dependent Claim
267 words
A multiprocessor system comprising: (a) a plurality of processors, each having a cache for storing data; (b) an external common memory for storing data; (c) a bus coupled to the common memory and to each cache for transferring data among the caches and the common memory, and (d) a memory allocation controller for controlling allocation of memory space, wherein the memory allocation controller comprises: (i) means for accepting a memory space allocation request from said processors, (ii) means for recognizing a size of a line of said cache, (iii) means for allocating memory space based on a requested size of memory space allocation obtained from the memory space allocation request obtained from the means for accepting and on the size of the line of said cache obtained from the recognizing means so as to allocate the requested memory space within a minimum possible number of cache lines in said cache during caching data from the memory to the cache, and (iv) means for reporting a start address of said memory allocation being allocated to a memory allocation requesting side, and (v) instruction means for switching a memory allocation method between a method which considers the line size of said cache and a method which does not consider the line size of said cache, wherein the means for requesting memory space allocation requests a minimum allocation size for a requested data, and the memory space allocation means uses the following formula, evaluated by integer computations, to determine the minimum number of cache lines: ((requested minimum allocation size of a memory space+cache line size-1)÷cache line size)×cache line size. 3.
Claim 4
Dependent Claim
267 words
A multiprocessor system comprising: (a) a plurality of processors, each having a cache for storing data; (b) an external common memory for storing data; (c) a bus coupled to the common memory and to each cache for transferring data among the caches and the common memory, and (d) a memory allocation controller for controlling allocation of memory space, wherein the memory allocation controller comprises: (i) means for accepting a memory space allocation request from said processors, (ii) means for recognizing a size of a line of said cache, (iii) means for allocating memory space based on a requested size of memory space allocation obtained from the memory space allocation request obtained from the means for accepting and on the size of the line of said cache obtained from the recognizing means so as to allocate the requested memory space within a minimum possible number of cache lines in said cache during caching data from the memory to the cache, and (iv) means for reporting a start address of said memory allocation being allocated to a memory allocation requesting side, and (v) instruction means for switching a memory allocation method between a method which considers the line size of said cache and a method which does not consider the line size of said cache, wherein the means for requesting memory space allocation requests a minimum allocation size for a requested data, and the memory space allocation means uses the following formula, evaluated by integer computations, to determine the minimum number of cache lines: ((requested minimum allocation size of a memory space+cache line size-1)÷cache line size)×cache line size. 3.
Claim 5
Independent Claim
172 words
A method for allocating memory space using a minimum number of cache lines in a cache of a processor in a multiprocessor system including a memory, the method comprising the steps of: receiving a request for memory space to allocate data in the memory; recognizing a size of a line of the cache; determining a necessary minimum number of cache lines to allocate the memory space to the data based on the size of the cache line, wherein the determining determines the minimum number of cache lines based on the following formula, evaluated by integer computations: (requested size of memory space allocation+cache line size-1)÷cache line size; allocating memory space to the data such that the minimum number of cache lines will be used when caching the data from the memory to the cache, the allocating step further comprising the step of deciding, based on a predetermined cache line occupation ratio, whether remaining space in a cache line which has been used for a previous allocation should be used for a subsequent allocation.
Claim 6
Independent Claim
172 words
A method for allocating memory space using a minimum number of cache lines in a cache of a processor in a multiprocessor system including a memory, the method comprising the steps of: receiving a request for memory space to allocate data in the memory; recognizing a size of a line of the cache; determining a necessary minimum number of cache lines to allocate the memory space to the data based on the size of the cache line, wherein the determining determines the minimum number of cache lines based on the following formula, evaluated by integer computations: (requested size of memory space allocation+cache line size-1)÷cache line size; allocating memory space to the data such that the minimum number of cache lines will be used when caching the data from the memory to the cache, the allocating step further comprising the step of deciding, based on a predetermined cache line occupation ratio, whether remaining space in a cache line which has been used for a previous allocation should be used for a subsequent allocation.
Claim 7
Independent Claim
164 words
A method for allocating memory such that caching of the memory will use a minimum number of cache lines in a cache of a processor of a multiprocessor system, the method comprising the steps of: receiving a request to allocate data in the memory; recognizing a size of a line of the cache; recognizing the alignment of said cache line; determining a minimum number of cache lines for allocating the data based on the size and alignment based on the following formula, evaluated by integer computations: (requested size of memory space allocation+cache line size-1)÷cache line size; allocating the data in the memory such that caching of the data will use the minimum number of cache lines, the allocating step further comprising the step of deciding, based on a predetermined cache line occupation ratio, whether remaining space in a cache line which has been used for a previous allocation should be used for a subsequent allocation; and reporting a start address of the memory allocation.
Claim 8
Independent Claim
164 words
A method for allocating memory such that caching of the memory will use a minimum number of cache lines in a cache of a processor of a multiprocessor system, the method comprising the steps of: receiving a request to allocate data in the memory; recognizing a size of a line of the cache; recognizing the alignment of said cache line; determining a minimum number of cache lines for allocating the data based on the size and alignment based on the following formula, evaluated by integer computations: (requested size of memory space allocation+cache line size-1)÷cache line size; allocating the data in the memory such that caching of the data will use the minimum number of cache lines, the allocating step further comprising the step of deciding, based on a predetermined cache line occupation ratio, whether remaining space in a cache line which has been used for a previous allocation should be used for a subsequent allocation; and reporting a start address of the memory allocation.
Claim 9
Independent Claim
127 words
A method for a compiler/linker to allocate memory for a grouped variable in a cache using a minimum number of cache lines, the method comprising the steps of: receiving a request to allocate the grouped variable in the cache; recognizing a size of a line of the cache; deciding a minimum number of cache lines needed to allocate the variable based on the formula, evaluated by integer computations: (grouped variable space size+cache line size-1) ÷cache line size; and allocating the variable into the minimum number of cache lines, said allocating step further comprising the step of deciding, based on a predetermined cache line occupation ratio, whether remaining space in a cache line which has been used for a previous allocation should be used for a subsequent allocation.
Claim 10
Independent Claim
127 words
A method for a compiler/linker to allocate memory for a grouped variable in a cache using a minimum number of cache lines, the method comprising the steps of: receiving a request to allocate the grouped variable in the cache; recognizing a size of a line of the cache; deciding a minimum number of cache lines needed to allocate the variable based on the formula, evaluated by integer computations: (grouped variable space size+cache line size-1) ÷cache line size; and allocating the variable into the minimum number of cache lines, said allocating step further comprising the step of deciding, based on a predetermined cache line occupation ratio, whether remaining space in a cache line which has been used for a previous allocation should be used for a subsequent allocation.
Claim 11
Independent Claim
145 words
A method for a compiler/linker to allocate memory for a grouped structure of data using a minimum number of cache lines in a cache of a processor, the method comprising the steps of: (a) receiving a request to allocate a grouped structure of data in the cache; (b) recognizing a size of a line of said cache; (c) deciding a necessary minimum number of cache lines needed to allocated the requested data based on the following formula, evaluated by integer calculations: ((grouped variable space size+cache line size-1)÷cache line size)×cache line size; and (d) allocating memory for the requested data using the minimum number of cache lines, said allocating step further comprising the step of deciding, based on a predetermined cache line occupation ratio, whether remaining space in a cache line which has been used for a previous allocation should be used for a subsequent allocation.
Claim 12
Independent Claim
145 words
A method for a compiler/linker to allocate memory for a grouped structure of data using a minimum number of cache lines in a cache of a processor, the method comprising the steps of: (a) receiving a request to allocate a grouped structure of data in the cache; (b) recognizing a size of a line of said cache; (c) deciding a necessary minimum number of cache lines needed to allocated the requested data based on the following formula, evaluated by integer calculations: ((grouped variable space size+cache line size-1)÷cache line size)×cache line size; and (d) allocating memory for the requested data using the minimum number of cache lines, said allocating step further comprising the step of deciding, based on a predetermined cache line occupation ratio, whether remaining space in a cache line which has been used for a previous allocation should be used for a subsequent allocation.
Claim 13
Dependent Claim
257 words
A multiprocessor system comprising: (a) a plurality of processors, each having a cache for storing data; (b) an external common memory for storing data; (c) a bus coupled to the common memory and to each cache for transferring data among the caches and the common memory, and (d) a memory allocation controller for controlling allocation of memory space, wherein the memory allocation controller comprises: (i) means for accepting a memory space allocation request from said processors, (ii) means for recognizing a size of a line of said cache, (iii) means for allocating memory space based on a requested size of memory space allocation obtained from the memory space allocation request obtained from the means for accepting and on the size of the line of said cache obtained from the recognizing means so as to allocate the requested memory space within a minimum possible number of cache lines in said cache during caching data from the memory to the cache, and (iv) means for recognizing the alignment of the cache and for providing the alignment to the memory space allocation means, wherein said means for allocating memory space uses a predetermined cache line occupation ratio in order to determine whether a cache line should be used for an allocation, and wherein the means for requesting memory space allocation requests a minimum allocation size for a requested data, and the memory space allocation means determines the minimum number of cache lines based on (a) the requested minimum allocation size of a memory space and (b) the cache line size.
Claim 14
Dependent Claim
257 words
A multiprocessor system comprising: (a) a plurality of processors, each having a cache for storing data; (b) an external common memory for storing data; (c) a bus coupled to the common memory and to each cache for transferring data among the caches and the common memory, and (d) a memory allocation controller for controlling allocation of memory space, wherein the memory allocation controller comprises: (i) means for accepting a memory space allocation request from said processors, (ii) means for recognizing a size of a line of said cache, (iii) means for allocating memory space based on a requested size of memory space allocation obtained from the memory space allocation request obtained from the means for accepting and on the size of the line of said cache obtained from the recognizing means so as to allocate the requested memory space within a minimum possible number of cache lines in said cache during caching data from the memory to the cache, and (iv) means for recognizing the alignment of the cache and for providing the alignment to the memory space allocation means, wherein said means for allocating memory space uses a predetermined cache line occupation ratio in order to determine whether a cache line should be used for an allocation, and wherein the means for requesting memory space allocation requests a minimum allocation size for a requested data, and the memory space allocation means determines the minimum number of cache lines based on (a) the requested minimum allocation size of a memory space and (b) the cache line size.
Claim 15
Dependent Claim
43 words
A system as in claim 7 wherein the memory space allocation means uses the following formula, evaluated by integer computations, to determine the minimum number of cache line lines: ((requested minimum allocation size of a memory space+cache line size-1)÷cache line size)×cache line size.
Claim 16
Dependent Claim
258 words
A multiprocessor system comprising: (a) a plurality of processors, each having a cache for storing data; (b) an external for storing data; (c) a bus coupled to the common memory and to each cache for transferring data among the caches and the common memory, and (d) a memory allocation controller for controlling allocation of memory space, wherein the memory allocation controller comprises: (i) means for a accepting a memory space allocation request from said processors, (ii) means for recognizing a size of a line of said cache, (iii) means for allocating memory space based on a requested size of memory space allocation obtained from the memory space allocation request obtained from the means for accepting and on the size of the line of said cache obtained from the recognizing means so as to allocate the requested memory space within a minimum possible number of cache lines in said cache during caching data from the memory to the cache, (iv) means for reporting a start address of said memory allocation being allocated to a memory allocation requesting side, and (v) instruction for switching a memory allocation method between a method which considers the line size of said cache and a method which does not consider the line size of said cache, wherein the means for requesting memory space allocation requests a minimum allocating size for a requested data, and the memory space allocation means determines the minimum number of cache lines based on (A) the requested minimum allocation size of a memory space and (B) the cache line size.
Claim 17
Dependent Claim
258 words
A multiprocessor system comprising: (a) a plurality of processors, each having a cache for storing data; (b) an external for storing data; (c) a bus coupled to the common memory and to each cache for transferring data among the caches and the common memory, and (d) a memory allocation controller for controlling allocation of memory space, wherein the memory allocation controller comprises: (i) means for a accepting a memory space allocation request from said processors, (ii) means for recognizing a size of a line of said cache, (iii) means for allocating memory space based on a requested size of memory space allocation obtained from the memory space allocation request obtained from the means for accepting and on the size of the line of said cache obtained from the recognizing means so as to allocate the requested memory space within a minimum possible number of cache lines in said cache during caching data from the memory to the cache, (iv) means for reporting a start address of said memory allocation being allocated to a memory allocation requesting side, and (v) instruction for switching a memory allocation method between a method which considers the line size of said cache and a method which does not consider the line size of said cache, wherein the means for requesting memory space allocation requests a minimum allocating size for a requested data, and the memory space allocation means determines the minimum number of cache lines based on (A) the requested minimum allocation size of a memory space and (B) the cache line size.
Claim 18
Dependent Claim
42 words
A system as in claim 8 wherein the memory space allocation means uses the following formula, evaluated by integer computations, to determine the minimum number of cache lines: ((requested minimum allocation size of a memory space+cache line size-1)÷cache line size)×cache line size.
References Cited (Backward Citations)
US5095424A
Cited
US5222225A
Cited
US5019965A
Cited
US5130922A
Cited
US5113514A
Cited
US5170477A
Cited
US5369753A
Cited
US5317720A
Cited
US5404489A
Cited
US5313609A
Cited
US5335332A
Cited
US5511226A
Cited
US5434993A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-02-02 | 2001-08-04 | 2002-02-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-02-02 | 2005-08-04 | 2006-02-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-02-02 | 2009-08-04 | 2010-02-03 | $7700.00 | Window Closed / Lapsed |