Patent
1996-01-23
1999-08-17
Banankhah, Majid A.
395674, G06F 945
Patent
active
059406216
ABSTRACT:
Compiler performance is improved without compromising program correctness by altering the commonly expected ordering that has been used in the past. A more efficient memory image is provided which results in smaller stack frames (activation records), less required heap space (static data memory storage), improved variable access time due to better spacial locality, and improved cache-hit ratios. An optimal size space storage allocation technique optimizes the run time code, such that fewer instructions are required per each data access. A smaller local area, which is part of the activation record, is provided, such that there is a much greater level of nesting and better cache locality. Improved alignment base sorting is provided such that, based on alignment, the smallest stack frame possible is provided. Profile based optimization, which gathers information about the behavior of the program, is used to determine how best to order and layout storage during the next storage allocation pass, such that items that are accessed more often are allocated further up in the activation record. Temporal locality is used to determine what variables are going to be accessed in what order, where a graph that represents all of the variables is built up. The graph is weighted by the number of times each variable is accessed immediately before or after each other variable. Allocated variables are then laid out in such an order that variables that are accessed temporally close to each other are allocated on the same cache line. Thus, when a cache line hosting a variable is brought into the cache, the variables that are to be accessed next are also automatically brought into the cache because they have been allocated on the same cache line. Therefore, the need to retrieve additional cache lines is greatly reduced. This results in a reduced number of cache misses. Static duration storage is also used to relate to static defined data that is heap allocated.
REFERENCES:
patent: 4310883 (1982-01-01), Clifton et al.
patent: 4542458 (1985-09-01), Kitajima et al.
patent: 5025367 (1991-06-01), Gurd et al.
patent: 5113509 (1992-05-01), Pennings et al.
patent: 5247600 (1993-09-01), Ashcraft et al.
patent: 5347540 (1994-09-01), Karrick
patent: 5367637 (1994-11-01), Wei
patent: 5452440 (1995-09-01), Salsburg
patent: 5530964 (1996-06-01), Alpert et al.
patent: 5537573 (1996-07-01), Ware Ete al.
patent: 5546559 (1996-08-01), Kyushima et al.
Item #351, Derwent WPI Account No. 87-0077601/11.
Eisenbeis et al., Institut National de Recherche en Informatique et en Automatique, Jul. 1990, No. 1262, "A Strategy for Array Management in Local Memory".
Oldehoeft et al., Communications of the ACM, May 1985, vol. 28, No. 5, "Adaptive Exact-Fit Storage Management".
Banankhah Majid A.
Hewlett--Packard Company
LandOfFree
Language independent optimal size-based storage allocation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Language independent optimal size-based storage allocation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Language independent optimal size-based storage allocation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-324354