Data processing: measuring – calibrating – or testing – Measurement system – Performance or efficiency evaluation
Reexamination Certificate
1997-11-26
2001-01-16
Shah, Kamini (Department: 2857)
Data processing: measuring, calibrating, or testing
Measurement system
Performance or efficiency evaluation
C702S138000, C702S186000, C714S039000
Reexamination Certificate
active
06175814
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to measuring the performance of a computer system, and more particularly measuring average execution rates of executing instructions.
BACKGROUND OF THE INVENTION
Computer processors are getting, faster, yet software application performance is not keeping, pace. For large commercial applications, average processor cycles-per-instruction (CPI) values may be as high as 2.5 or 3. With a four-way instruction issue processor, a CPI of three means that only one issue slot in every twelve is being, put to good rise. It is important to understand why software throughput is not keeping up with hardware improvements.
It is common to blame such problems on memory latencies, in fact, many software applications spend many cycles waiting for data transfers to complete. However, other problems, such as branch mispredicts also waste processor cycles. Independent of the general causes, system architects, and hardware and software engineers need to know which instructions are stalling and why in order to improve the performance of modern computer systems incorporating complex processors.
Typically, this is done by generating a “profile” of the behavior of a system while it is operating. A profile is a record of performance data. Frequently, the profile is presented graphically so that performance bottlenecks can readily be identified.
Profiling can be done by instrumentation and simulation. With instrumentation, additional code is added to a program to monitor specific events during execution of a program. Simulation attempts to emulate the behavior of the entire program in an artificial environment rather than executing the program in the real system.
Each of these two methods has its drawbacks Instrumentation perturbs the program's true behavior due to the added instructions and extra data references. Simulation avoids perturbation at the expense of a substantial performance overhead when compared to executing the program on a real system. Furthermore, with either instrumentation or simulation, it is usually difficult to profile an entire large scale software system, i.e., application, operating system, and device driver code.
Hardware implemented event sampling can also be used to provide profile information of processors. Hardware sampling has a number of advantages over simulation and instrumentation: it does not require modifying software programs to measure their performance. Sampling works on complete systems, with a relatively low overhead. Indeed, recently it has been shown that low-overhead sampling-based profiling can be used to acquire detailed instruction-level information about pipeline stalls and their causes. However, many hardware sampling techniques lack flexibility because they are designed to measure specific events.
Most extant microprocessors, such as the DIGITAL Alpha AXP 21164, the Intel Pentium Pro, and the MIPS R10000 provide event counters that can count a variety of events, such as data cache (D-cache) misses, instruction cache (I-cache) misses, and branch mispredicts. The event counters generate an interrupt when the counters overflow so that the performance data in the counters can be sampled by higher levels of software.
Event counters are useful for capturing aggregate information, such as the number of branch mispredicts that the system incurred while executing a particular program, or part thereof. However, known event counters are less useful for attributing state information to individual instructions, such as which branch instructions are frequently mispredicted. This may be due to the fact that the program counters (PC) of instructions that caused the events may no longer be available when the event count(er overflows and interrupts.
It is a particular problem to deduce the dynamic operation of a processor that can issue instructions out-of-order. Indeed, the behavior of software programs executing in an out-of-order processor can be quite subtle and difficult to understand. Consider the flow of instructions in the out-of-order Alpha 21264 processor as a concrete example.
Superscalar Processor Architecture
Execution Order
An out-of-order processor fetches and retires instructions in order, but processes the instructions according to their data dependencies. Processing instructions can involve register mapping, instruction issuing and executing. An instruction is said to be “in-flight” from the time it is fetched until it retires or aborts.
During each processor cycle, a first stage of the processor pipeline fetches a set of instructions from the instruction cache (I-cache). The set of instructions are decoded. The instruction decoder identifies which instructions in the fetched set are part of the instruction stream.
Because it may take multiple cycles to resolve the PC of a next instruction to fetch, the PC is usually predicted ahead of time by a branch or jump predictor. When the prediction is incorrect, the processor will abort the mispredicted instructions which occupy a “bad” execution path, and will restart fetching instructions on the “good” path.
To allow instructions to execute out-of-order, registers specified in operands of instructions are dynamically renamed to prevent write-after-read and write-after-write conflicts. This renaming is accomplished by mapping architectural or “virtual” registers to physical registers. Thus, two instructions that write the same virtual register cain safely execute out-of-order because they will write to different physical registers, and consumers of the virtual registers will get the proper values.
A register mapped instruction resides in th(e issue queue until its operands have been computed and a functional “execution” unit of the appropriate type is available. The physical registers used by an instruction are read in the cycle that the instruction issues. After instructions have executed, they are marked as ready to retire and will be retired by the processor when all previous ready-to-retire instructions in program order have been retired, i.e., instructions retire in the correct program order. Upon retirement, the processor commits the changes made by the instruction to the architectural “state” of the system, and releases resources consumed by the instruction.
Misprediction
In some cases, such as when a branch is mispredicted, instructions must be trapped or discarded. When this occurs, the current speculative architectural state is rolled back to a point in the execution where the misprediction occurred, and fetching continues at the correct instruction.
Delays
Numerous events may delay the execution of an instruction. At the front of the pipeline, the fetch unit may stall due to an I-cache miss, or the fetch unit may fetch instructions along a bad path due to a misprediction. The mapper may stall due to lack of free physical registers, or lack of free slots in the issue queue. Instructions in the issue queue may wait for their register dependencies to be satisfied, or for the availability of functional execution units.
Instructions may stall due to data cache misses. Instructions may trap because they were speculatively issued down a bod path, or because the processor took an interrupt. Many of these events are difficult to predict statically, e.g, by an examination of the code, and all of them degrade the performance of the system. Simple event counters are inadequate to capture this type of state information. In addition, it is difficult to exactly measure the lengths of the delays to determine which delays deserve special attention.
It is highly desirable to directly attribute events to specific instructions and machine states so that programmers, or optimization tools can improve the performance of software and hardware components of complex computer systems such as super-scalar and out-of-order processors, or for that matter processors of any architectural design.
Problems with Prior Art Event Counters
The main problem with known event counters is that the instruction that caused the event that overflowed the counter was usually fet
Chrysos George Z.
Dean Jeffrey
Hicks, Jr. James E.
Waldspurger Carl A.
Weihl William E.
Compaq Computer Corporation
Oppenheimer Wolff & Donnelly LLP
Shah Kamini
Sherry Leah
LandOfFree
Apparatus for determining the instantaneous average number... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for determining the instantaneous average number..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for determining the instantaneous average number... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2552039