US4777594A — Data processing apparatus and method employing in…

Claim 1

Independent Claim 196 words

A program instruction flow prediction apparatus for a data processing system having means for prefetching an instruction, said flow prediction apparatus comprising a flow prediction storage element, an instruction storage element containing program instructions to be executed, means coupled with said instruction storage element for addressing an instruction in said instruction storage element, means coupled with said flow prediction storage element and with said addressing means for reading a flow control word in said flow prediction storage element at a location derived from the location of said addressed instruction in said instruction storage element, said flow control word containing at least a branch control portion for predicting the flow of program instructions and a next program instruction address portion containing at least a portion of a next program address if a program branch is predicted, and said addressing means including means for normally employing a next sequential instruction location for use in fetching a next instruction, and for responding to said branch control portion for deriving from said next program instruction address portion a branch location for use in fetching said next instruction, said branch location being used in lieu of said next sequential instruction location.

Claim 2

Dependent Claim 196 words

A program instruction flow prediction apparatus for a data processing system having means for prefetching an instruction, said flow prediction apparatus comprising a flow prediction storage element, an instruction storage element containing program instructions to be executed, means coupled with said instruction storage element for addressing an instruction in said instruction storage element, means coupled with said flow prediction storage element and with said addressing means for reading a flow control word in said flow prediction storage element at a location derived from the location of said addressed instruction in said instruction storage element, said flow control word containing at least a branch control portion for predicting the flow of program instructions and a next program instruction address portion containing at least a portion of a next program address if a program branch is predicted, and said addressing means including means for normally employing a next sequential instruction location for use in fetching a next instruction, and for responding to said branch control portion for deriving from said next program instruction address portion a branch location for use in fetching said next instruction, said branch location being used in lieu of said next sequential instruction location.

Claim 3

Dependent Claim 72 words

The program instruction flow prediction apparatus of claim 1 further comprising means for monitoring instruction flow during instruction prefetching by said instruction prefetching means and means coupled with said monitoring means and responsive thereto for updating at least one of the branch control portion and the next program instruction address portion contained in said flow prediction storage element, said updating being based solely upon a prior history of branching of the instruction.

Claim 4

Dependent Claim 22 words

The program flow instruction prediction apparatus of claim 2 wherein said flow prediction storage element is a random access, high speed memory.

Claim 5

Dependent Claim 25 words

The program flow prediction apparatus of claim 3 further wherein said flow prediction storage element has substantially less storage capacity than a system main memory.

Claim 6

Dependent Claim 24 words

The program flow prediction apparatus of claim 2 further wherein said flow prediction storage element has fewer storage locations than said instruction storage element.

Claim 7

Dependent Claim 74 words

The program instruction flow prediction apparatus of claim 5 wherein said flow control word further includes an index portion, said program instruction flow prediction apparatus further comprising means for comparing said index portion with at least a portion of the address of a current instruction and for inhibiting false prediction of a branch condition for non-branch instructions which map into the same location of said flow prediction storage element as did valid branch instructions.

Claim 8

Dependent Claim 26 words

The program instruction flow prediction apparatus of claim 2 wherein said monitoring means monitors only the branching history of a most recent execution of said instruction.

Claim 9

Dependent Claim 52 words

The program instruction flow prediction apparatus of claim 2, the further improvement wherein said updating means includes means coupled to said monitoring means and responsive thereto for updating said prediction storage element only when actual program instruction flow does not match predicted program instruction flow represented in said flow prediction storage element.

Claim 10

Dependent Claim 47 words

The program instruction flow prediction apparatus of claim 8 further wherein said updating means includes means for removing from said flow prediction storage element a branch control portion when actual program instruction flow does not match predicted program instruction flow represented in said flow prediction storage element.

Claim 11

Dependent Claim 83 words

The program instruction flow prediction apparatus of claim 1 wherein said data processing system has an instruction and execution pipeline means having a plurality of serially operating stages, one of said stages being an instruction fetch stage having a look-ahead program counter, said instruction fetch stage operating normally during a first time duration of said fetch stage, said apparatus further comprising means for loading said program counter with said next program instruction address location during said first time duration of said fetch stage.

Claim 12

Dependent Claim 54 words

The program instruction flow prediction apparatus of claim 1 further wherein said addressing means reads instructions from said instruction storage element as double word instructions aligned on even boundaries of said storage element, and further comprising means for accommodating branching instructions occurring on either an even or an odd boundary of said read instruction.

Claim 13

Dependent Claim 28 words

The program instruction flow prediction apparatus of claim 11 further comprising means for reading a control bit of said flow prediction storage element for identifying said alignment boundary.

Claim 14

Dependent Claim 30 words

The program instruction flow prediction apparatus of claim 12 further comprising means for associating a prediction of program flow with the final word of instructions having more than one word.

Claim 15

Dependent Claim 169 words

A program instruction flow prediction method for a data processing system including the step of prefetching instructions, said flow prediction method comprising the steps of A. addressing an instruction in an instruction storage element, B. addressing a flow control word from a flow prediction storage element at a location derived from the location of said addressed instruction in said instruction storage element, said flow control word containing at least a branch control portion for predicting the flow of program instructions and an instruction address portion containing at least a portion of a next program address if a program branch is predicted, C. deriving from the flow control word a new next program address if a branch is predicted, and D. said instruction addressing step including the step of normally employing a next sequential program instruction address for use in fetching a next instruction, and E. responding to a branch prediction for employing the derived address, in place of the next sequential address, for use in fetching a next instruction.

Claim 16

Dependent Claim 169 words

A program instruction flow prediction method for a data processing system including the step of prefetching instructions, said flow prediction method comprising the steps of A. addressing an instruction in an instruction storage element, B. addressing a flow control word from a flow prediction storage element at a location derived from the location of said addressed instruction in said instruction storage element, said flow control word containing at least a branch control portion for predicting the flow of program instructions and an instruction address portion containing at least a portion of a next program address if a program branch is predicted, C. deriving from the flow control word a new next program address if a branch is predicted, and D. said instruction addressing step including the step of normally employing a next sequential program instruction address for use in fetching a next instruction, and E. responding to a branch prediction for employing the derived address, in place of the next sequential address, for use in fetching a next instruction.

Claim 17

Dependent Claim 37 words

The program instruction flow prediction method of claim 14 further comprising the steps of monitoring instruction flow during said instruction prefetching, and updating said flow prediction storage element based solely a history of a the instruction flow.

Claim 18

Dependent Claim 75 words

The program instruction flow prediction method of claim 15 further comprising the steps of storing as part of said flow control word an index portion, comparing said index portion with the index associated with a current instruction, and inhibiting false prediction of a branch condition for a non-branch instruction which maps into the same location of said flow prediction storage element as the valid branch instructions as a result of said index comparison being invalid.

Claim 19

Dependent Claim 41 words

The program instruction flow prediction method of claim 15 further wherein said updating step comprises the step of updating said prediction storage element only when actual program instruction flow does not match the prediction data stored in said prediction storage element.

Claim 20

Dependent Claim 37 words

The program instruction flow prediction method of claim 14 further comprising the step of combining said instruction address portion with said instruction memory location address for forming the address location of a next instruction to be fetched.

Claim 21

Dependent Claim 50 words

The program instruction flow prediction method of claim 14 further comprising the steps of reading instructions from said instruction storage element as double word instructions aligned on even boundaries of said storage element, and accommodating branching instructions occurring on either an even or an odd boundary of said read instruction.

Claim 22

Dependent Claim 29 words

The program instruction flow prediction method of claim 19 further comprising the step of reading a control bit of said flow prediction storage element for identifying said alignment boundary.

Claim 23

Dependent Claim 31 words

The program instruction flow prediction method of claim 20 further comprising the step of associating a prediction of program flow with the final word of instructions having more than one word.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1991-10-11	1992-04-11	1992-10-11	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1995-10-11	1996-04-11	1996-10-11	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	1999-10-11	2000-04-11	2000-10-11	$7700.00	Window Closed / Lapsed

Data processing apparatus and method employing instruction flow prediction

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag