Connectivity based program partitioning

Details Connectivity based program partitioning Connectivity based program partitioning

1996-10-07

1998-08-18

Cosimano, Edward R.

395707, 395708, 395709, 395710, 395586, 395704, G06F 945

Patent

active

057970122

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.

REFERENCES:
patent: 5107418 (1992-04-01), Cramer et al.
patent: 5161216 (1992-11-01), Reps et al.
patent: 5193190 (1993-03-01), Janczync et al.
patent: 5367683 (1994-11-01), Brett
patent: 5428793 (1995-06-01), Odnert et al.
patent: 5485616 (1996-01-01), Burke et al.
patent: 5555417 (1996-09-01), Odnert et al.
patent: 5579520 (1996-11-01), Bennett
Chow, "Minimizing Register Usage Penalty at Procedure Calls", Proceedings of the SIGPLAN, 'Conf. on Programming Language Design & Implementation, pp. 85-94, Jul. 1988.
Himelstein, et al. "Cross-Module Optimizations: Its Implementation and Benefits", Proceesings of the Summer 87 USENIX Conf., pp. 347-356, Sep. 1987.
Cooper, et al. "The impact of interprocedural analysis & optimization in R.sup.n programming environment" ACM Trans. on Programming Languages & Syst., Oct. 1986.
Crowroft, et al. "Is layering, harmful?" (Remote Procedure Call) IEEE Netw. (USA) vol. 6, No. 1, pp. 20-24, Jan. 1992.
Richardson, et al. "Code Optimization Across Procedures" Computer (USA), vol. 22, No. 2, pp. 42-50, Feb. 1989.
Lomet, "Data flow analysis in the presence of procedure calls" IBM Research & Dev. USA, vol. 21, No. 6, pp. 559-571, Nov. 1977.
K.M. Gilbert, Effective Register Management During Code Generation, IBM Technical Disclosure Bulletin, vol. 15, No. 8, Jan. 1973, pp. 2640-2645.
K. O'Brien et al, Advanced Compiler Technology for the RISC System/6000 Architecture, IBM RISC System/6000 Technology, pp. 154-161, 1990.

Affiliated with

Also associated with

Rating

Connectivity based program partitioning does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Connectivity based program partitioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Connectivity based program partitioning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1125172