Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
1999-03-31
2002-02-12
Iqbal, Nadeem (Department: 2184)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C709S241000
Reexamination Certificate
active
06347383
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to a method and system for data processing and in particular to an improved method and system for address trace compression. Still more particularly, the present invention relates to a method and system for address trace compression utilizing loop detection and reduction techniques.
2. Description of the Related Art
The use of memory address traces has long been established as a technique for studying and predicting the performance of computer systems. The fundamental concepts underlying these techniques are relatively simple, but the engineering involved for constructing, managing and using the address traces is often very complex in practice. Traces must be gathered with minimum perturbation to the system being traced, and information is preferably limited only to the absolute minimum that will be used later in simulating an existing or a future architecture. Also, as processor speeds continue to increase, then for a given period of real time, the size of an address trace increases in proportion to the processor speed.
Additionally, it is becoming clear that to provide acceptable estimates for the system performance, long traces are needed. Such traces include the effects of context switches, inputs and outputs, network traffic etc. Ambitious performance studies would like to observe the system for tens of seconds or minutes if possible. This requirement necessitates long traces and disk speeds are not improving. Extremely long traces consume substantial storage space and cause the simulator to become I/O bound, instead of CPU bound. It may be argued that storage costs and capacities are decreasing at rates comparable or exceeding those of the processor speeds. While this is true, nobody finds the management of terabytes of trace volumes a simple undertaking.
Consequently, it would be desirable to provide an improved method and system for compressing an existing trace during post-mortem through detecting and reducing the loops that manifest in an address trace. The method and system of the present invention relies on the observation that most programs spend their time executing loops, and therefore the trace will follow the structures of such loops. If loops could therefore be detected, then compiler-like techniques could eliminate many of the address references that could later be constructed while the trace is read back. The subject invention herein solves all of these problems in a new and unique manner that has not been part of the art previously.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide an improved method and system for reducing the storage required by the address trace.
It is another object of the present invention to provide an improved method and system for simple reconstruction of the trace during post-mortem simulation.
The foregoing objects are achieved as is now described. A method and system for compressing memory address traces based on detecting and reducing the loops that exist in a trace is disclosed. The method and system consists of two steps. In the first step, the trace is analyzed and loops are detected by determining the control flow among the program basic blocks. In the second step, each loop is analyzed to eliminate constant address references, and to apply compiler-like strength reduction on addresses that differ only by a fixed offset between consecutive loop iterations. Addresses that cannot be eliminated using the method and system of the present invention are kept in the trace.
The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5446876 (1995-08-01), Levine et al.
patent: 5764885 (1998-06-01), Sites et al.
patent: 5802272 (1998-09-01), Sites et al.
patent: 5951623 (1999-09-01), Reynar et al.
patent: 6112319 (2000-08-01), Paulson
IBM Tech. Disclosure, Bull. Automatic loop detector/Eliminator, Aug. 1980, 1 of 2, TDB-ACC-NO: NN8008919.*
IBM Tech. Disclosure, Bull. Trace mechanism with Hang or loop detection, Feb. 1, 1980, 1 of 1, TDB-ACC-NO: NN80024138.*
IBM Tech. Disclosure, Bull, Programmable loop Detector/Eliminator, Aug. 1979, 1 of 3, TDB-ACC-NO: NN79081158.*
IBM Tech. Disclosure Bull, Address trace compressor, Nov. 1972, 1 of 2, TDB-ACC-NO: NN72111866.
Bracewell & Patterson L.L.P.
Iqbal Nadeem
Salys Casimer K.
LandOfFree
Method and system for address trace compression through loop... 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 address trace compression through loop..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for address trace compression through loop... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2975209