Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Scoreboarding – reservation station – or aliasing
Reexamination Certificate
2001-02-06
2004-11-30
Kim, Kenneth S. (Department: 2111)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Scoreboarding, reservation station, or aliasing
C712S216000, C712S218000, C712S219000, C717S140000
Reexamination Certificate
active
06826677
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to communicating instruction results in processors and to compiling methods for processors. In particular, the present invention relates to allocating registers for storing instruction results in processors such as microprocessors.
2. Description of the Prior Art
In high-performance computing, 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 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.
For previously-considered processors the task of the compiler in allocating registers within the rotating register file to values produced in a loop computation is complicated, as will be explained in more detail later in the present specification. It is therefore desirable to provide a mechanism for identifying intermediate values, including loop-variant values, within a loop computation that can simplify the compiler task of allocating registers within the rotating register file. It is also desirable to provide an instruction set for a processor in which the instructions are more compact.
BRIEF SUMMARY OF THE INVENTION
A processor according to a first aspect of the present invention has an instruction issuing unit which issues, in a predetermined sequence, instructions to be executed. The sequence of instructions includes preselected value-producing instructions which, when executed, produce respective values. The processor also has at least one instruction executing unit which executes the issued instructions. A register unit, having a plurality of registers, stores values produced by the executed instruction. A sequence number assigning unit assigns the values produced by the value-producing instructions respective sequence numbers according to the order of issuance of their respective value-producing instructions. A register allocating unit allocates each produced value one of the registers, for storing that produced value, in dependence upon the sequence number assigned to that value.
A compilation method according to a second aspect of the present invention converts a sequence of high-level program instructions into a corresponding sequence of low-level instructions to be executed by a processor. The method comprises determining which low-level instructions of the corresponding sequence are preselected value-producing instructions and which are preselected value-requiring instructions. Each value-producing instruction is an instruction which when executed will produce a value. Each said value-requiring instruction is an instruction which when executed will require the value produced by a previously-issued value-producing instruction. The method assigns the produced values respective sequence numbers according to the order in which their respective value-producing instructions will be issued during execution. Each value-requiring instruction is coded with information for use by the processor during execution to identify the produced value required by that instruction. That information is dependent on the said sequence number assigned to that produced value.
Another aspect of the present invention provides a computer program which, when run on a computer, causes the computer to carry out a compilation method embodying the aforesaid second aspect of the present invention. For example, in one embodiment a computer-readable recording medium has stored thereon a computer program which, when run on a computer, causes the computer to carry out a compilation method for converting a sequence of high-level program instructions into a corresponding sequence of low-level instructions to be executed by a processor. The computer program comprises a determining portion that determines which low-level instructions of the corresponding sequence are preselected value-producing instructions and which are preselected value-requiring instructions. Each value-producing instruction is an instruction which when executed will produce a value. Each value-requiring instruction is an instruction which when executed will require the value produced by a previously-issued value-producing instruction. An assigning portion assigns the produced values respective sequence numbers according to the order in which their respective value-producing instructions will be issued during execution. A coding portion codes each value-requiring instruction with information for use by the processor to identify the said produced value required by that instruction. That information is dependent on the sequence number assigned to that produced value.
REFERENCES:
patent: 5826055 (1998-10-01), Wang et al.
patent: 5958043 (1999-09-01), Motomura
patent: 698846 (1996-02-01), None
patent: 2276742 (1994-10-01), None
IBM Technical Disclosure Bulletin; “Multisequencing a single instruction stream identifying dead registers in the common virtual register file”; vol. 36, N. 4, pp. 441-444; Apr. 1, 1993.
Greer Burns & Crain Ltd.
Kim Kenneth S.
PTS Corporation
LandOfFree
Renaming registers to values produced by instructions... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Renaming registers to values produced by instructions..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Renaming registers to values produced by instructions... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3296077