Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Patent
1994-06-30
1997-09-02
Oberley, Alvin E.
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
711170, G06F 944
Patent
active
056641915
ABSTRACT:
The present invention provides a method and system for determining an optimal placement order for basic blocks within a computer program to improve locality of reference and reduce the working set of the computer program. By reducing the working set, the computer program requires less memory than it normally would require to execute on a computer system. The optimal placement order for basic blocks within a computer program reflects the concurrency of usage for basic blocks during execution of the computer program. The method for determining an optimal placement order includes analyzing the computer program to identify all of the basic blocks, determining how many times each basic block is executed, assigning a placement order to each basic block depending upon how many times each basic block was executed, and reordering the basic blocks according to their assigned placement orders to produce an optimized computer program. The method used to identify all of the basic blocks includes disassembling known instruction addresses to identify the beginning and end of basic blocks and processing jump tables to identify more instruction addresses. Processing jump tables includes processing the first entry of every jump table before processing the second entry of any jump table. The present invention further optimizes a computer program by replacing rarely executed instructions with other instructions that require a smaller amount of storage space.
REFERENCES:
patent: 4047243 (1977-09-01), Dijkstra
patent: 4642765 (1987-02-01), Cocke et al.
patent: 4656583 (1987-04-01), Auslander et al.
patent: 4731740 (1988-03-01), Eguchi
patent: 4763255 (1988-08-01), Hopkins et al.
patent: 4868738 (1989-09-01), Kish et al.
patent: 5212794 (1993-05-01), Pettis et al.
Alan Dain Samples, Dissertation Submitted in Partial Satisfaction of the Requirements for the Degree of Doctor of Philosophy in Computer Science in the Graduate Division of the University of California at Berkeley, 1991. pp. 1-179.
PC Opt Version 1.1 Beta Release User's Guide, 1992, pp. 1, 3-40.
Lee, C-H et al., "Efficient Algorithm for Graph-Partitioning Problem Using a Problem Transformation Method," Computer-Aided Design, vol. 21 No. 10, 1989, pp. 611-618.
Hong Guo et al., "A Fast Algorithm for Simulated Annealing," Physica Scripta, vol. T38, 1991, pp. 40-44.
L.H. Clark et al., "A Linear Time Algorithm for Graph Partition Problems," Information Processing Letters, vol. 42, No. 1, 1992, pp. 19-24.
David E. Van Den Bout et al., "Graph Partitioning Using Annealed Neural Networks," IEEE Transactions on Neural Networks, vol. 1, No. 2, 1990, pp. 192-203.
B.W. Kernighan et al., "An Efficient Heuristic Procedure for Partitioning Graphs," The Bell System Technical Journal, 1970, pp. 291-307.
David S. Johnson et al., "Optimization By Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning," Operations Research, vol. 37, No. 6, Nov.-Dec., 1989, pp. 865-892.
Karl Pettis et al., "Profile Guided Code Positioning," Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, Jun. 20-22, 1990, pp. 16-27.
Robert Sedgewick, "Weighted Graphs," Algorithms in C, Chapter 31, pp. 451-468.
James R. Larus et al., "Rewriting Executable Files to Measure Program Behavior," University of Wisconsin Computer Sciences Technical Report 1083, 1992, pp. 1-17.
Thomas Ball et al., "Optimally Profiling and Tracing Programs," University of Wisconsin Computer Sciences Technical Report 1031, 1991, pp. 1-27.
S.C. Johnson, "Postloading for Fun and Profit," USENIX, Winter, 1990, pp. 325-330.
William Baxter et al., "Code Restructuring for Enhanced Performance on a Pipelined Processer," IEEE COMPCON, 1991, pp. 252-260.
David W. Wall, "Systems for Late Code Modification," WRL Research 92/3, May, 1992, pp. 1-24.
Ralph Grishman, "Assembly Language Programming for the Control Data Series," Algorithmics Press, 2nd Edition, 2nd Printing, Jan., 1972, pp. 45-53 & pp. 176-184.
Apperson Norman Eugene
Davidson Robert I.
Myhrvold Nathan
Shupak Richard
Vogel Keith Randel
Courtenay, III St.-John
Microsoft Corporation
Oberley Alvin E.
LandOfFree
Method and system for improving the locality of memory reference does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for improving the locality of memory reference, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for improving the locality of memory reference will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-316816