Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital logic testing
Patent
1997-03-10
1999-09-07
Hafiz, Tariq R.
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital logic testing
395704, 714 38, 712214, 712241, 712233, G06F 9445, G06F 945
Patent
active
059500093
ABSTRACT:
An apparatus and several methods provide for a more optimized computer program that will have a faster execution time than was possible using the prior art reordering technique that adds to a trace until it finds no more predecessors or successors to add. The apparatus and methods disclosed herein use a variety of methods to reorder the program portions in a more intelligent manner that will improve its run-time performance. Each of these methods involves constructing traces in the control flow graph of the computer program. In a first embodiment, a basic block is only added to a trace if it is not negligible within predetermined limits. This negligibility test results in traces that are not extended for infrequently executed basic blocks. In a second embodiment, a basic block is only added to a trace if it is a perfect partner with the last basic block added to the trace. The concept of a "perfect partner" helps to match basic blocks together in a trace that have the greatest affinity for each other. In a third embodiment, a basic block is only added to a trace if it satisfies "should follow" flags and predetermined negligibility criteria. The "should follow" flags and negligibility criteria provide a complex criteria for adding basic blocks to a trace, criteria that create more efficient code in some specific circumstances.
REFERENCES:
patent: 4847755 (1989-07-01), Morrison et al.
patent: 4914590 (1990-04-01), Loatman et al.
patent: 4947315 (1990-08-01), Sokolow et al.
patent: 5014185 (1991-05-01), Saito et al.
patent: 5021945 (1991-06-01), Morrison et al.
patent: 5179703 (1993-01-01), Evans
patent: 5193180 (1993-03-01), Hastings
patent: 5212794 (1993-05-01), Pettis et al.
patent: 5265254 (1993-11-01), Blasciak et al.
patent: 5333304 (1994-07-01), Christensen et al.
patent: 5335344 (1994-08-01), Hastings
patent: 5355487 (1994-10-01), Keller et al.
patent: 5412799 (1995-05-01), Papadopoulos
patent: 5428782 (1995-06-01), White
patent: 5428793 (1995-06-01), Odnert et al.
patent: 5450586 (1995-09-01), Kuzara et al.
patent: 5465258 (1995-11-01), Adams
patent: 5485616 (1996-01-01), Burke et al.
patent: 5517628 (1996-05-01), Morrison et al.
patent: 5522036 (1996-05-01), Shapiro
patent: 5535329 (1996-07-01), Hastings
patent: 5539907 (1996-07-01), Srivastava et al.
patent: 5555417 (1996-09-01), Odnert et al.
patent: 5606698 (1997-02-01), Powell
patent: 5689712 (1997-11-01), Heisch
patent: 5787284 (1998-07-01), Blainey et al.
patent: 5797012 (1998-08-01), Blainey et al.
patent: 5797013 (1998-08-01), Mahadevan et al.
patent: 5812854 (1998-09-01), Steinmetz et al.
Balasa, F., et al., "Transformation of Nested Loops with Modulo Indexing to Affine Recurrences", Parallel Processing Letters, vol. 4, No. 3 (Sep. 1994), pp. 271-280.
Conte, T.M., et al., "Hardware-Based Profiling: An Effective Technique for Profile-Driven Optimization", International Journal of Parallel Programming, vol. 24, No. 2, Apr. 1996, pp. 187-206.
Conte, T.M., et al., "Using Branch Handling Hardware to Support Profile-Driven Optimization", International Symposium on Microarchitecture, 27th, Nov. 30-Dec. 2, 1994, pp. 12-21.
Kishon, A., et al., "Semantics Directed Program Execution Monitoring", J. Functional Programming, vol. 5, No. 4, Oct. 1995, pp. 501-547.
"Program Restructuring Technique for Improving Memory Management Performance", IBM Technical Disclosure Bulletin, vol. 39, No. 03, Mar. 1996, pp. 203-205.
"Statistics Gathering and Analyzing Tool for Open Software Foundation's Distributed Computing Environment", IBM Technical Disclosure Bulletin, vol. 37, No. 02B, Feb. 1994, pp. 215-217.
Youfeng, W, et al., "Static Branch Frequency and Program Profile Analysis", International Symposium on Microarchitecture, 27th, Nov. 30-Dec. 2, 1994, pp. 1-11.
Speer, Steven E., et al., "Improving UNIX Kernel Performance using Profile Based Optimization", 1994 Winter USENIX, Jan. 17-21, 1994, pp. 181-188.
Pettis and Hansen, "Profile Guarded Code Positioning", Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, Jun. 20-22, 1990, pp. 16-27.
Hank et al, "Region-based compilation: an introduction and motivation," MICRO 28, Proceedings of the 28th Annual International Symposium on Microarchitecture, pp. 158-168, Dec. 1995.
Eichenberger et al, "Stage Scheduling: A Technique to Reduce the Register Requirements of a Modulo Schedule," MICRO 28, Proceedings of the 28th Annual International Symposium on Microarchitecture, pp. 338-349, Dec. 1995.
Bortnikov Vita
Mendelson Bilha
Novick Mark
Schmidt William Jon
Shavit-Lottem Inbal
Dam Tuan Q.
Hafiz Tariq R.
International Business Machines Coporation
Martin Derek P.
LandOfFree
Method and apparatus for profile-based reordering of program por 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 apparatus for profile-based reordering of program por, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for profile-based reordering of program por will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1813863