US5797012A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Connectivity based program partitioning
Assignee: International Business Machines Corp
•
Filing: 1996-10-07
•
Granted: 1998-08-18
•
Expires: 2016-10-07
Abstract
Abstract A method for partitioning programs into multi-procedure modules for efficient compilation. During interprocedural analysis, a weighted callgraph of the program is constructed in which weights on nodes represent code size of each procedure and weights on edges between the nodes represent execution counts between procedures. A coloured interference graph is built from the analysis information, and is used to induce weighted sub-graphs of the callgraph containing no interferences between procedures in each sub-graph. The procedures from a single sub-graph are combined into one or more modules; procedures with the highest weighted edges between them are combined in a module first until the cumulative node weight of the module reaches a preset limit on memory size.
Inventors
- 👤 Robert James Blainey
- 👤 Christopher Michael Donawa
- 👤 James Lawrence McInnes
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 01:14
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
136 words
A method for partitioning a computer program with multiple procedures into compilation modules on a data processing system having defined constraints, comprising the computer-executed steps of: defining a constraint; determining frequency of execution class as between pairs of all of the procedures in the program; determining instruction size of all of the procedures in the program; dividing the procedures of the program into at least one group, each group having no interferences between procedures; and subdividing each group into compilation units by: i) dividing a remaining pair of procedures having a highest frequency of execution calls into one compilation unit, ii) aggregating the instruction size of the procedures in the one compilation unit, and iii) repeating steps i) and ii) while the aggregate instruction size in the one compilation unit is less than the defined constraint.
Claim 2
Independent Claim
136 words
A method for partitioning a computer program with multiple procedures into compilation modules on a data processing system having defined constraints, comprising the computer-executed steps of: defining a constraint; determining frequency of execution class as between pairs of all of the procedures in the program; determining instruction size of all of the procedures in the program; dividing the procedures of the program into at least one group, each group having no interferences between procedures; and subdividing each group into compilation units by: i) dividing a remaining pair of procedures having a highest frequency of execution calls into one compilation unit, ii) aggregating the instruction size of the procedures in the one compilation unit, and iii) repeating steps i) and ii) while the aggregate instruction size in the one compilation unit is less than the defined constraint.
Claim 3
Dependent Claim
24 words
A method, according to claim 1, wherein the steps of determining frequency of execution calls and determining instruction size comprise constructing a call-weighted multigraph.
Claim 4
Dependent Claim
26 words
A method, according to claim 1, wherein the steps of dividing the procedures of the program into at least one group comprises constructing an interference graph.
Claim 5
Dependent Claim
102 words
A program storage device readable by a machine in a data processing system having preset memory size constraints, tangibly embodying a program of instructions executable by the machine to perform method steps for partitioning a computer program with multiple procedures into compilation modules, said method steps comprising: i) dividing a remaining pair of procedures having a highest frequency of execution calls into one compilation unit, ii) aggregating the instruction size of the procedures in the one compilation unit, and iii) repeating steps i) and ii) while the aggregate instruction size in the one compilation unit is less than the preset memory size.
Claim 6
Dependent Claim
102 words
A program storage device readable by a machine in a data processing system having preset memory size constraints, tangibly embodying a program of instructions executable by the machine to perform method steps for partitioning a computer program with multiple procedures into compilation modules, said method steps comprising: i) dividing a remaining pair of procedures having a highest frequency of execution calls into one compilation unit, ii) aggregating the instruction size of the procedures in the one compilation unit, and iii) repeating steps i) and ii) while the aggregate instruction size in the one compilation unit is less than the preset memory size.
Claim 7
Dependent Claim
173 words
In a computer system having a constraint defined by the computer system or by the user, a method for compiling a computer program into compilation units in a multi-pass compiler capable of generating a call-weighted multigraph having nodes denoting procedures in the computer program, weights on the nodes denoting relative instruction size, edges between the nodes representing execution calls and edge weights representing execution call frequency, the method comprising the computer-executed steps of: i) defining a constraint; ii) sorting the edge weights into a highest to lowest sorted list; iii) selecting an edge having a highest edge weight and any node or nodes connecting to said edge remaining for selection; iv) aggregating the weight of the selected node or nodes; v) dividing the edge and the selected node or nodes into compilation unit having an aggregate node weight not exceeding the constraint when the aggregate weight of the selected node or nodes is added; vi) removing the selected edge from the sorted list; and vii) repeating steps iii) through via for all edges.
Claim 8
Dependent Claim
173 words
In a computer system having a constraint defined by the computer system or by the user, a method for compiling a computer program into compilation units in a multi-pass compiler capable of generating a call-weighted multigraph having nodes denoting procedures in the computer program, weights on the nodes denoting relative instruction size, edges between the nodes representing execution calls and edge weights representing execution call frequency, the method comprising the computer-executed steps of: i) defining a constraint; ii) sorting the edge weights into a highest to lowest sorted list; iii) selecting an edge having a highest edge weight and any node or nodes connecting to said edge remaining for selection; iv) aggregating the weight of the selected node or nodes; v) dividing the edge and the selected node or nodes into compilation unit having an aggregate node weight not exceeding the constraint when the aggregate weight of the selected node or nodes is added; vi) removing the selected edge from the sorted list; and vii) repeating steps iii) through via for all edges.
Claim 9
Dependent Claim
35 words
A method according to claim 5, further comprising the step of sorting the nodes by interference prior to dividing any selected nodes into a compilation unit, whereby to divide nodes into compilation units without interferences.
Claim 10
Dependent Claim
192 words
A program storage device readable by a machine in a data processing system having preset memory size constraints, tangibly embodying a program of instructions executable by the machine to perform method steps for partitioning a computer program with multiple procedures into compilation modules, said method steps comprising: i) defining a graph with nodes, edges, and edge weights, each node representing a respective procedure of said multiple procedures, each edge connecting two respective nodes and representing a call between the two respective nodes, each edge weight representing an execution count between two respective procedures; ii) sorting the edge weights into a highest to lowest sorted list; iii) selecting an edge having a highest edge weight and any node or nodes connecting to said edge remaining for selection; vi) aggregating the weight of the selected node or nodes; v) dividing the edge and the selected node or nodes into compilation unit having an aggregate node weight not exceeding the size constraint on memory when the aggregate weight of the selected node or nodes is added; vi) removing the selected edge from the sorted list; and vii) repeating steps iii) through vi) for all edges.
Claim 11
Dependent Claim
192 words
A program storage device readable by a machine in a data processing system having preset memory size constraints, tangibly embodying a program of instructions executable by the machine to perform method steps for partitioning a computer program with multiple procedures into compilation modules, said method steps comprising: i) defining a graph with nodes, edges, and edge weights, each node representing a respective procedure of said multiple procedures, each edge connecting two respective nodes and representing a call between the two respective nodes, each edge weight representing an execution count between two respective procedures; ii) sorting the edge weights into a highest to lowest sorted list; iii) selecting an edge having a highest edge weight and any node or nodes connecting to said edge remaining for selection; vi) aggregating the weight of the selected node or nodes; v) dividing the edge and the selected node or nodes into compilation unit having an aggregate node weight not exceeding the size constraint on memory when the aggregate weight of the selected node or nodes is added; vi) removing the selected edge from the sorted list; and vii) repeating steps iii) through vi) for all edges.
References Cited (Backward Citations)
US5161216A
Cited
US5193190A
Cited
US5428793A
Cited
US5555417A
Cited
US5107418A
Cited
US5367683A
Cited
US5485616A
Cited
CA2102089A1
Cited
US5579520A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-17 | 2002-02-16 | 2002-08-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-17 | 2006-02-16 | 2006-08-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-17 | 2010-02-16 | 2010-08-18 | $7700.00 | Window Closed / Lapsed |