US 5,136,696 AGranted

High-performance pipelined central processor for predicting the occurrence of executing single-cycle instructions and multicycle instructions

AssigneePrime Computer, Inc.

InventorsRobert F. Beckwith, Neil J. Johnson, Suren Irukulla, Steven Schwartz, Nihar Mohapatra

Life of this patent

Estimating the term…

Loading patent…

Abstract

A pipelined central processor capable of executing both single-cycle instructions and multicycle instructions is provided. An instruction fetch stage of the processor includes an instruction cache memory and a prediction cache memory that are commonly addressed by a program counter register. The instruction cache memory stores instructions of a program being executed and microinstructions of a multicycle instruction interpreter. The prediction cache memory stores interpreter call predictions and interpreter entry addresses at the addresses of the multicycle intructions. When a call prediction occurs, the entry address of the instruction interpreter is loaded into the program counter register on the processing cycle immediately following the call prediction, and a return address is pushed onto a stack. The microinstructions of the interpreter are fetched sequentially from the instruction cache memory. When the interpreter is completed, the prediction cache memory makes a return prediction. The return address is transferred from the stack to the program counter register on the processing cycle immediately following the return prediction, and normal program flow is resumed. The prediction cache memory also stores branch instruction predictions and branch target addresses.

Claims29

Dependent claims

Digital processing apparatus for executing stored program instructions including single-cycle instructions and multicycle instructions during multiple processing cycles, comprising:

instruction memory means for providing said program instructions in response to program addresses and for providing microinstructions of a multicycle instruction interpreter in response to microinstruction addresses;
prediction means responsive to different ones of said program addresses for making predictions of multicycle instructions and predictions of single cycle instructions, said predictions of multicycle instructions including predictions of calls to said instruction interpreter and predictions of returns from said instruction interpreter, said prediction means including a cache memory for storage and readout of said call predictions and instruction interpreter entry addresses respectively associated with each of said call predictions, each of said call predictions and said entry addresses being stored at an address corresponding to the program address for which the call prediction is made, and for storage and readout of each of said return predictions at an address corresponding to the microinstruction address for which the return prediction is made;
control means for providing successive program addresses to said instruction memory means for accessing said program instructions in response to predictions of single-cycle instructions and for providing successive microinstruction addresses to said instruction memory means in response to each prediction of a multicycle instruction until completion of the multicycle instruction interpreter, said control means including
program counter means for holding a current address for accessing said instruction memory means on each processing cycle and for incrementing the current address on successive processing cycles,
stack memory means coupled to said program counter means,
control logic means responsive to each of said call predictions for loading a return program address from said program counter means into said stack memory means, and
selector means responsive to each of said call predictions for loading the entry address into said program counter means and responsive to each of said return predictions for transferring said return program address from said stack memory means to said program counter means;
means responsive to said program instructions and said microinstructions provided by said instruction memory means for executing said program instructions and said microinstructions;
and
means for validating said predictions and for updating said prediction means when said predictions are incorrect.

7 more elements

In pipelined digital processor for executing a stored program including single-cycle instructions and multicycle instructions, instruction addressing apparatus comprising:

control means for providing a program address during a first processing cycle;
prediction means responsive to said program address for predicting a multicycle instruction and making an instruction interpreter entry prediction during said first processing cycle, said prediction means including means responsive to microinstruction addresses for making a prediction of a return from said instruction interpreter, said prediction means including a cache memory for storage and readout of said entry prediction and said entry address at a cache memory address corresponding to the program address for which the entry prediction is made and for storage and readout of said return prediction at a cache memory address corresponding to the microinstruction address or which the return prediction is made;
said control means further including means responsive to said prediction for providing during a second processing cycle an entry address of an instruction interpreter comprising a plurality of microinstructions and for providing successive microinstruction addresses during processing cycles subsequent to said second processing cycle;
and
instruction memory means responsive to said program address for providing said multicycle instruction during said second processing cycle, responsive to said entry address for providing a first microinstruction during a third processing cycle and responsive to said microinstruction addresses for providing microinstructions during processing cycles subsequent to said third processing cycle, said control means comprising
program counter means for holding a current address for accessing said instruction memory means and for incrementing the current address on successive processing cycles,
stack memory means coupled to said program counter means,
control logic means responsive to said entry prediction for loading a return program address from said program counter means into said stack means, and
selector means responsive to said entry prediction for loading said entry address into said program counter means and responsive to said return prediction for transferring said return program address from said stack memory means to said program counter means.

6 more elements

Digital processing apparatus for executing a stored program including single-cycle instructions and multicycle instructions during multiple processing cycles, comprising:

instruction memory means responsive to program addresses for providing program instructions and responsive to microinstruction addresses for providing microinstructions of a multicycle instruction interpreter;
prediction memory means responsive to various ones of said program addresses corresponding to multicycle instructions for readout of instruction interpreter entry predictions and associated entry addresses and responsive to various ones of said microinstruction addresses for making predictions of returns from said instruction interpreter;
program counter means for holding a current address for accessing said instruction memory means and for incrementing the current address on successive processing cycles;
stacking memory means coupled to said program counter means,
control logic means responsive to each of said call predictions for loading a return program address from said program counter means into said stack memory means;
selector means responsive to each of said call predictions for loading the associated entry address into said program counter means and responsive to each of said return predictions for transferring said return program address from stack memory means to said program counter means,
means for executing said program instructions and said microinstructions;
and
means for validating each of said predictions and for updating said prediction memory means when one of said predictions is incorrect, said prediction memory means including a program section for storing interpreter call predictions and branch instruction predictions and an interpreter section for storing interpreter subroutine call predictions, interpreter subroutine return predictions, interpreter branch predictions and interpreter return predictions and wherein said control logic means includes means for providing an interpreter mode bit in said program addresses and said microinstruction addresses for selectively addressing said program section and said interpreter section of said prediction memory means.

6 more elements

A method for executing stored program instructions including single-cycle instructions and multicycle instructions during multiple processing cycles comprising the steps of:

storing program instructions and microinstructions of a multicycle instruction interpreter in an instruction memory;
providing successive program addresses to the instruction memory for accessing the program instructions;
making predictions of multicycle instructions based on the program addresses provided to the instruction memory, the step of making predictions of multicycle instructions including the steps of making call predictions for entering said instruction interpreter in response to multicycle instruction addresses, and making return predictions for returns from said instruction interpreter in response to specified microinstruction addresses, the step of making call predictions including the step of storing said call predictions in a cache memory at addresses corresponding to said multicycle instruction addresses and the step of making return predictions including the step of storing said return predictions in said cache memory at addresses corresponding to said specified microinstruction addresses;
interrupting the program addresses and providing successive microinstruction addresses to the instruction memory for accessing the microinstructions, in response to each prediction of a multicycle instruction;
and
executing the program instructions and the microinstructions, the steps of storing program instructions and microinstructions, and executing the program instructions and the microinstruction being performed in separate stages of a pipelined digital processor.

3 more elements

Digital processing apparatus for executing stored program instructions including single-cycle instructions and multicycle instructions during multiple processing cycles comprising:

an instruction fetching stage comprising
instruction memory means for providing said program instructions in response to program addresses and for providing microinstructions of a multicycle instruction interpreter in response to microinstruction addresses,
prediction means responsive to different ones of said program addresses for making predictions of multicycle instructions and predictions of single cycle instructions, said predictions of multicycle instructions including predictions of calls to said instruction interpreter and predictions of returns from said instruction interpreter, said prediction means including a cache memory for storage and readout of said call predictions and instruction interpreter entry addresses respectively associated with each of said call predictions, each of said call predictions and said entry addresses being stored at an address corresponding to the program address for which the call prediction is made, and for storage and readout of each of said return predictions at an address corresponding to the microinstruction address for which the return prediction is made, and
control means for providing successive program addresses to said instruction memory means for accessing said program instructions in response to predictions of single cycle instructions and for providing successive microinstruction addresses to said instruction memory means in response to each prediction of a multicycle instruction until completion of the multicycle instruction interpreter, said control means including program counter means for holding a current address for accessing said instruction memory means on each processing cycle and for incrementing the current address on successive processing cycles, stack memory means coupled to said program counter means, control logic means responsive to each of said call predictions for loading a return program address from said program counter means into said stack memory means, and selector means responsive to each of said call predictions for loading the entry address into said program counter means and responsive to each of said return predictions for transferring said return program address from said stack memory means to said program counter means;
an instruction decoder stage for decoding said single-cycle instructions, said multicycle instructions and said microinstructions;
an effective address formation stage responsive to outputs of said instruction decoder stage for determining addresses of operands referenced by said single-cycle instructions and said microinstructions;
an operand memory stage responsive to said operand addresses for providing operands referenced by said single-cycle instructions and said microinstructions;
an execute stage responsive to said operands provided by said operand memory stage and the outputs of said decoder stage for executing said single-cycle instructions and said microinstructions;
and
a writer stage for storing the results of said execute stage.

7 more elements

Dependencies are inferred from the claim text.