Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Scoreboarding – reservation station – or aliasing
Reexamination Certificate
2001-02-16
2004-06-22
Tsai, Henry W. H. (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Scoreboarding, reservation station, or aliasing
C712S214000, C712S024000
Reexamination Certificate
active
06754806
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to circuitry and a method for performing a fast mapping from an input value to an output value. The present invention can be applied to register renaming in pipelined loops in a microprocessor.
2. Description of the Related Art
In high performance computing, the requirement for cyclic register renaming arises in the context of software-pipelined loops, where a high rate of instruction execution is usually required of the target machine (e.g. microprocessor). Execution time is often dominated by loop structures within the application program. To permit a high rate of instruction execution a processor may include a plurality of individual execution units, with each individual unit being capable of executing one or more instructions in parallel with the execution of instructions by the other execution units.
Such a plurality of execution units can be used to provide a so-called software pipeline made up of a plurality of individual stages. Each software pipeline stage has no fixed physical correspondence to particular execution units. Rather, when a loop structure in an application program is compiled the machine instructions which make up an individual iteration of the loop are scheduled for execution by the different execution units in accordance with a software pipeline schedule. This schedule is divided up into successive stages and the instructions are scheduled in such a way as to permit a plurality of iterations to be carried out in overlapping manner by the different execution units with a selected loop initiation interval between the initiations of successive iterations. Thus, when a first stage of an iteration i terminates and that iteration enters a second stage, execution of the next iteration i+1 is initiated in a first stage of the iteration i+1. Thus, instructions in the first stage of iteration i+1 are executed in parallel with execution of instructions in the second stage of iteration i.
In such software-pipelined loops there are typically several iterations of a loop in a partial state of completion at each moment. Hence, there may be several live copies of each value computed within the loop. To distinguish between these values, and to identify them relative to the current iteration, requires that the name of each value held in a register must change at well-defined moments during loop execution. These renaming points are known by the compiler, which also determines the register name required within each instruction to access each value depending on the iteration in which it was computed.
The name of a value held in a register is known to the programmer or compiler in terms of the register identifiers within each assembly-code instruction. The purpose of static register renaming is to define a scheme whereby these identifiers are translated at run-time into actual register numbers based on a translation scheme that can be predicted by the programmer or compiler.
For example, if a value X is assigned to register r
1
in iteration
1
, a typical renaming scheme would make that value available in register r
2
in iteration
2
and in register r
3
in iteration
3
, and so on. It is the responsibility of the compiler or programmer to allocate register identifiers to each value in a way that ensures correct operation of the loop.
In software pipelined loops there are usually loop-variant values, i.e. expressions which must be reevaluated in each different iteration of the loop, that must be communicated between different instructions in the pipeline. To deal with such loop-variant values it is possible to store them in a so-called rotating register file. In this case, each loop-variant value is assigned a logical register number within the rotating register file, and this logical register number does not change from one iteration to the next. Inside the rotating register file each logical register number is mapped to a physical register within the register file and this mapping is rotated each time a new iteration is begun, i.e. each time a pipeline boundary is closed. Accordingly, corresponding instructions in different iterations can all refer to the same logical register number, making the compiled instructions simple, whilst avoiding a value produced by one iteration from being overwritten by a subsequently-executed instruction of a different iteration.
With such a register renaming scheme in operation, before an instruction can be executed by the processor it is first necessary, for each register access within a software-pipelined loop, to perform a register mapping process to translate the register identifiers into actual register numbers. This mapping is done at run time and hence places extra time demands on the processor in a highly time-critical activity. It is therefore desirable that the time taken to perform this mapping is as small as possible.
SUMMARY OF THE INVENTION
The present invention can provide mapping circuitry which maps an input value, within a preselected range of allowable input values, to a corresponding output value within a preselected range of allowable output values. A first candidate output value producing unit is connected for receiving the input value and produces a first candidate output value that differs by a first offset value from the received input value. A second candidate output value producing unit is connected for receiving the input value and produces a second candidate output value that differs by a second offset value from the received input value. The first and second offset values are such that a difference between them is equal to a difference between respective output-range limit values defining the limits of the preselected output-value range and also such that, for any input value within the preselected input-value range, one of the first and second candidate output values is within the preselected output-value range and the other of those two values is outside that range. An in-range value determining unit determines which one of the first and second candidate output values is within the preselected output-value range. An output value selection unit selects as the corresponding output value that one of the first and second candidate output values which is determined to be within the output-value range.
In a first aspect of the present invention the second candidate output value producing unit produces the second candidate output value during operation of the first candidate output value producing unit to produce the first candidate output value.
In a second aspect of the present invention the in-range value determining unit determines which one of the first and second candidate output values is within the preselected output-value range during operation of one or both of the first and second candidate value producing units to produce the first and second candidate output values. The first and second aspects can be used together.
According to another aspect of the present invention there is provided a processor which comprises mapping circuitry embodying the above-described first or second aspect of the present invention, and which also comprises: an instruction issuing unit which issues instructions; at least one instruction executing unit which executes the issued instructions; and a register file, having a plurality of physical registers. The mapping circuitry is connected to receive as its input value a logical register identifier specified by one of the instructions, and the output value of the mapping circuitry is a physical register identifier used for identifying one of the physical registers within the register file that corresponds to the specified logical register identifier.
The present invention can also provide a mapping method for mapping an input value, within a preselected range of allowable input values, to a corresponding output value within a preselected range of allowable output values. A first candidate output value is produced that differs by a first offset value from the received input value.
Greer Burns & Crain Ltd.
PTS Corporation
LandOfFree
Mapping circuitry and method comprising first and second... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mapping circuitry and method comprising first and second..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mapping circuitry and method comprising first and second... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3364255