US5850549A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Global variable coalescing
Assignee: International Business Machines Corp
•
Filing: 1996-10-07
•
Granted: 1998-12-15
•
Expires: 2016-10-07
Abstract
Abstract An interprocedural compilation method for aggregating global data variables in external storage to maximize data locality. Using the information displayed in a weighted interference graph in which node weights represent the size of data stored in each global variable and edges between variables represent access relationships between the globals, the global variables can be mapped into aggregates based on this frequency of access, while preventing the cumulative data size in any aggregate from exceeding a memory size restriction.
Inventors
- 👤 Robert James Blainey
- 👤 Christopher Michael Donawa
- 👤 James Lawrence McInnes
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 18:19
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443; G06F8/43; G06F8/433
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
97 words
A method for remapping global data variables during program compilation, comprising the computer-executed steps of: setting a limit; selecting global data variables referenced in the program; assigning a weight value to each selected global data variable representing byte size of data in that variable; dividing the selected global data variables into pairs of variables that are accessed together and re-ordering the pairs from highest to lowest affinity; and beginning from a pair of variables of highest affinity, dividing the selected global data variables into aggregate groupings, each grouping having an aggregate weight value not exceeding the limit.
Claim 2
Independent Claim
97 words
A method for remapping global data variables during program compilation, comprising the computer-executed steps of: setting a limit; selecting global data variables referenced in the program; assigning a weight value to each selected global data variable representing byte size of data in that variable; dividing the selected global data variables into pairs of variables that are accessed together and re-ordering the pairs from highest to lowest affinity; and beginning from a pair of variables of highest affinity, dividing the selected global data variables into aggregate groupings, each grouping having an aggregate weight value not exceeding the limit.
Claim 3
Dependent Claim
17 words
A method, according to claim 1, wherein assigning comprises initially differentiating arrays from non-array global data variables.
Claim 4
Dependent Claim
17 words
A method, according to claim 2, wherein the weight value assigned to a final array is one.
Claim 5
Dependent Claim
70 words
A method, according to claim 1, wherein assigning and dividing comprise building a weighted interference graph of the selected global data variables having: nodes representing the selected global data variables; node weights representing the assigned weight value of each selected global data variable; edges connecting nodes representing access relationships between pairs of selected global data variables; and edge weights representing degree of affinity between pairs of selected global data variables.
Claim 6
Dependent Claim
17 words
A method, according to claim 1, wherein the limit is related to a displacement field size value.
Claim 7
Dependent Claim
126 words
A program storage device readable by a machine in a data processing system, tangibly embodying a program of instructions executable by the machine to perform method steps executable by a computer for remapping global data variables during program compilation, said method steps comprising: setting a limit; selecting global data variables referenced in the program; assigning a weight value to each selected global data variable representing byte size of data in that variable; dividing the selected global data variables into pairs of variables that are accessed together and re-ordering the pairs from highest to lowest affinity; and beginning from a pair of variables of highest affinity, dividing the selected global data variables into aggregate groupings, each grouping having an aggregate weight value not exceeding the limit limit.
Claim 8
Dependent Claim
126 words
A program storage device readable by a machine in a data processing system, tangibly embodying a program of instructions executable by the machine to perform method steps executable by a computer for remapping global data variables during program compilation, said method steps comprising: setting a limit; selecting global data variables referenced in the program; assigning a weight value to each selected global data variable representing byte size of data in that variable; dividing the selected global data variables into pairs of variables that are accessed together and re-ordering the pairs from highest to lowest affinity; and beginning from a pair of variables of highest affinity, dividing the selected global data variables into aggregate groupings, each grouping having an aggregate weight value not exceeding the limit limit.
References Cited (Backward Citations)
US5428793A
Cited
US5555417A
Cited
US5107418A
Cited
US5577253A
Cited
US5367683A
Cited
US5446899A
Cited
US5535392A
Cited
US5625822A
Cited
CA2102089A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-14 | 2002-06-15 | 2002-12-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-14 | 2006-06-15 | 2006-12-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-14 | 2010-06-15 | 2010-12-15 | $7700.00 | Window Closed / Lapsed |