Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2005-01-04
2005-01-04
Nguyen-Ba, Antony (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S144000, C717S156000, C717S160000
Reexamination Certificate
active
06839895
ABSTRACT:
Code restructuring or reordering based on profiling information and memory hierarchy is provided by constructing a Program Execution Graph (PEG) corresponding to a level of the memory hierarchy, partitioning this PEG to reduce estimated memory overhead costs below an upper bound, and constructing a PEG for a next level of the memory hierarchy from the partitioned PEG. The PEG is constructed from control flow and frequency information from a profile of the program to be restructured. The PEG is a weighted undirected graph comprising nodes representing basic blocks and edges representing transfer of control between pairs of basic blocks. The weight of a node is the size of the basic block it represents and the weight of an edge is the frequency of transition between the pair of basic blocs it connects.
REFERENCES:
patent: 5418958 (1995-05-01), Goebel
patent: 5428793 (1995-06-01), Odnert et al.
patent: 5748844 (1998-05-01), Marks
patent: 5797012 (1998-08-01), Blainey et al.
patent: 5828961 (1998-10-01), Subramamian et al.
patent: 5933644 (1999-08-01), Wallace
patent: 5950009 (1999-09-01), Bortnikov et al.
patent: 5999737 (1999-12-01), Srivastava
patent: 6064819 (2000-05-01), Franssen et al.
patent: 6175957 (2001-01-01), Ju et al.
patent: 881568 (1998-12-01), None
Tomko et al, “Profile Driven Weight Decomposition”, ACM, pp. 165-172, 1996.*
Simons B., “Code Positioning for Procedures and Basic Blocks”, IBM Technical Report ADTI-1994,-006; also available as IBM Santa Teresa Laboratory Technical Report TR 03.580.
Heisch R.R., Trace-Directed Program Restructuring for AIX Executables:,IBM Journal of Research and Development, vol. 38, pp. 595-603, Sep. 1994.
Pettis K. et al., “Profile Guided Code Positioning”,Proceedings of the ACM Sigplan '90 Conference on Programming Language Design and Implementation(PLDI), pp. 16-127, Jun. 1990.
Garey M.R. et al.,Computers and Intractability: A Guide to the Theory of NP-Completeness, 124-127, W.H. Freeman & Co., San Francisco, CA, 1979.
Barnard S.T. et al., “Fast Multilevel Implementation of Recursive Spectral Bisection for Partioning Unstructured Problems”,Concurrency: Practice and Experience, vol. 6(2), pp. 101-117, Apr. 1994.
Srivastava A. et al., “A Practical System for Intermodule Code Optimization at Link-Time”,Journal of Programming Languages, vol. 1, pp. 1-18, 1993.
Ju Dz Ching
Muthukumar Kalyan
Ramaswamy Shankar
Simons Barbara Bluestein
Gates & Cooper LLP
Nguyen-Ba Antony
Vo Ted T.
LandOfFree
Method of, system for, and computer program product for... 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 of, system for, and computer program product for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of, system for, and computer program product for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3401496