Processor architecture having out-of-order execution, speculative branching, and giving priority to instructions which affect a condition code

• US 5,625,837 A
• Filed: 06/06/1995
• Issued: 04/29/1997
• Est. Priority Date: 12/15/1989
• Status: Expired due to Term

• Current Assignee: Hyundai Electronics America Incorporated (SK Hynix Inc.), SK Hynix Inc.
• Original Assignee: Hyundai Electronics America Incorporated (SK Hynix Inc.)
• Inventors: Gibson, Gary A., Popescu, Valeri, Lightner, Bruce D., Spracklen, John E., Schultz, Merle A.
• Primary Examiner(s): Donaghue, Larry D.
• Application Number:
  US08/471,651
• Time in Patent Office: 693 Days
• Field of Search: 395/800, 395/375
• US Class Current: 712/23
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers
• CPC Class Codes: G06F 9/3865 using deferred exception handling, e.g. exception flags
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units

Abstract

A processor architecture is described which operates with improved computational efficiency using instruction fetching functions that are decoupled from instruction execution functions by a dynamic register file. The instruction fetching function operates in free-running mode which does not stop if a fetched instruction cannot be executed due to data being unavailable or due to other instruction dependencies. Branch instructions are taken in a predicted direction and the results of execution of all instructions are provisionally stored pending validation or invalidation on the basis of the dependencies becoming available later. For branches of executed instructions that are later invalidated, the results of the executed instructions are flushed from provisional storage and the initial instruction which previously executed at the beginning of a branch on predicted dependencies is re-executed on the actual data that subsequently became available, and all subsequent instructions in such branch are also re-executed on the basis of dependencies actually available from execution of previous instructions in such branch.

Claims

1. A data processing system for processing information in response to an ordered series of instructions including instructions that control arithmetic operations on the information and a plurality of branch instructions, each branch instruction accepting input from a stored condition code, the data processing system comprising:

a register unit that stores information;

a fetch unit that continuously fetches instructions from the series of instructions;

a shelver coupled to the fetch unit to receive fetched instructions and to store multiple such instructions, wherein each instruction stored within the shelver is assigned a priority, and wherein such instruction stored within the shelver is stored with a sequential instruction identifier assigned in the order fetched, the sequential instruction identifier being an indicator of seniority within the shelver;

a scheduler coupled to the shelver that continuously selects instructions in the shelver for which all information required for execution is available in the register unit or the shelver for execution and that issues those instructions for execution in an order in accordance with the priority of each instruction and a seniority of each instruction within the shelver as indicated by said sequential instruction identifier;

an arithmetic unit coupled to the scheduler that perform operations on information in the register unit or shelver in response to instructions supplied from the shelver to generate execution results;

a branch predictor that predicts a speculative sequence of instructions following each branch instruction, wherein the fetch unit fetches instructions in accordance with the speculative sequence;

an evaluator that evaluates each branch instruction subsequent to the execution of a last instruction that affects the stored condition code that is the input to the branch instruction;

an incorrect branch repairer that, upon detection of an incorrectly predicted branch instruction by the evaluator, repairs effects of the incorrectly predicted branch instruction and all instructions of the speculative sequence following the branch instruction;

and wherein

the shelver assigns a higher priority to instructions that affect the stored condition code,

whereby the assignment of high priority to instructions that affect the stored condition code accelerates detection and repair of effects of incorrectly predicted branches.

2. The data processing system of claim 1 wherein:

the register unit comprises an array of registers, each register having a unique register number;

each arithmetic instruction in the series of instructions contains a destination comprising a register number and contains at least one operand register number; and

the scheduler determines that all information required for executing an arithmetic instruction is available only when, for each operand register number contained in that instruction, either no instruction in the shelver has a destination register number equal to that operand register number or the results of the most-recently-fetched instruction in the shelver whose destination register number equals that operand register number are available.

3. The data processing system of claim 1 wherein the shelver receives the results of execution of instructions and is capable of storing the result of the execution of every instruction stored within the shelver.

4. The data processing system of claim 3 further comprising:

a retirement unit that copies results of the execution of the oldest instruction in the shelver into the register unit and removing that instruction from the shelving unit.

5. The data processing system of claim 3 in which there are multiple arithmetic units which may supply results to the shelver simultaneously.