Patent US5758112A successfully refreshed from Google Patents.
US5758112A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pipeline processor with enhanced method and apparatus for restoring register-renaming information in the event of a branch misprediction
Assignee: MIPS Tech LLC
•
Filing: 1997-02-07
•
Granted: 1998-05-26
•
Expires: 2017-02-07
Abstract
Abstract Redundant mapping tables for use in processors that rename registers and perform branch prediction is presented. The redundant mapping tables include a plurality of primary RAM cells coupled to a plurality of redundant RAM cells. In the event of a branch instruction, the redundant RAM cells can save the contents of the primary RAM cells in a single clock cycle before the processor decodes and executes subsequent instructions along a predicted branch path. Should the branch instruction be mispredicted, the redundant cells can restore the primary RAM cells in a single clock cycle. A branch stack, coupled to the redundant mapping tables, updates restored mapping tables with changes made for preceding instructions that were decoded in parallel with the branch instruction. A plurality of levels of redundant RAM cells may be used to enable the nesting of a plurality of branch predictions at any one time.
Inventors
- 👤 Kenneth C. Yeager
- 👤 Mazin S. Khurshid
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 10:42
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3842; G06F9/3838; G06F9/384; G06F9/3844; G06F9/3854; G06F9/3858; G06F9/3861; G06F9/3863
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
177 words
A pipeline processor comprising: means for issuing instructions containing logical register numbers; a renaming means, coupled to said issuing means, for renaming logical register numbers to physical register numbers; a storage means, coupled to said renaming means, for storing contents of said renaming means in a first clock cycle in response to a branch instruction; a branch prediction means, coupled to said renaming means, for predicting said branch instruction; a comparator means, coupled to said branch prediction means, for determining whether branch prediction is correct; interconnection means, disposed between said renaming means and said storing means, which enables said storing means to restore said contents of said renaming means in a single clock cycle when a branch misprediction occurs, said contents being restored to a point in time prior to decoding of said branch instruction; and stack means, coupled to said renaming means, for updating said renaming means with changes occurring after said point in time, said changes being caused by instructions decoded simultaneously with said branch instruction and preceding said branch instruction in original program order.
Claim 2
Dependent Claim
177 words
A pipeline processor comprising: means for issuing instructions containing logical register numbers; a renaming means, coupled to said issuing means, for renaming logical register numbers to physical register numbers; a storage means, coupled to said renaming means, for storing contents of said renaming means in a first clock cycle in response to a branch instruction; a branch prediction means, coupled to said renaming means, for predicting said branch instruction; a comparator means, coupled to said branch prediction means, for determining whether branch prediction is correct; interconnection means, disposed between said renaming means and said storing means, which enables said storing means to restore said contents of said renaming means in a single clock cycle when a branch misprediction occurs, said contents being restored to a point in time prior to decoding of said branch instruction; and stack means, coupled to said renaming means, for updating said renaming means with changes occurring after said point in time, said changes being caused by instructions decoded simultaneously with said branch instruction and preceding said branch instruction in original program order.
Claim 3
Dependent Claim
26 words
The pipeline processor of claim 1 further comprising a free list means, coupled to said renaming means, for providing new mapping information to said renaming means.
Claim 4
Dependent Claim
27 words
The pipeline processor of claim 2 further comprising an active list means, coupled to said renaming means, for receiving old mapping information from said first renaming means.
Claim 5
Dependent Claim
36 words
The pipeline processor of claim 3, wherein said storing means includes means for holding a plurality of versions of said contents of said renaming means associated with a plurality of branch instructions at any one time.
Claim 6
Dependent Claim
20 words
The pipeline processor of claim 4 wherein said renaming means includes a floating-point renaming means and an integer renaming means.
Claim 7
Dependent Claim
32 words
The pipeline processor of claim 5 wherein said storage means includes a first storage means coupled to said floating-point renaming means and a second storage means coupled to said integer renaming means.
Claim 8
Dependent Claim
77 words
The pipeline processor of claim 1 wherein said interconnection means includes: a first set of data lines over which a single value held in a primary RAM cell within said renaming means may pass to one of a plurality of redundant RAM cells within said storing means; and a second set of data lines over which one of a plurality of values held in said plurality of redundant RAM cells may pass to said primary RAM cell.
Claim 9
Dependent Claim
133 words
In a pipeline processor capable of renaming registers and speculatively executing instructions, a method for restoring register-renaming information in the event of a branch misprediction comprising the steps of: decoding a plurality of instructions in parallel during a decode cycle, wherein one of said plurality of instructions is a branch instruction; storing contents of a register-renaming mapping table during said decode cycle, said contents being unaffected by said plurality of instructions; saving physical-register information associated with at least one of said plurality of instructions separate from said contents; predicting said branch instruction; verifying said prediction; restoring said contents to said register-renaming mapping table in a single clock cycle when a branch misprediction occurs; and updating said register-renaming mapping table with said physical-register information associated with at least one of said plurality of instructions.
Claim 10
Dependent Claim
133 words
In a pipeline processor capable of renaming registers and speculatively executing instructions, a method for restoring register-renaming information in the event of a branch misprediction comprising the steps of: decoding a plurality of instructions in parallel during a decode cycle, wherein one of said plurality of instructions is a branch instruction; storing contents of a register-renaming mapping table during said decode cycle, said contents being unaffected by said plurality of instructions; saving physical-register information associated with at least one of said plurality of instructions separate from said contents; predicting said branch instruction; verifying said prediction; restoring said contents to said register-renaming mapping table in a single clock cycle when a branch misprediction occurs; and updating said register-renaming mapping table with said physical-register information associated with at least one of said plurality of instructions.
Claim 11
Dependent Claim
23 words
The method of claim 8 wherein said at least one of said plurality of instructions precedes said branch instruction in original program order.
Claim 12
Dependent Claim
28 words
The method of claim 9 wherein said physical register information is characterized by a two-bit validity code indicating whether said physical register information is integer or floating point.
Claim 13
Dependent Claim
77 words
A pipeline processor comprising: a register-renaming mapping table; a redundant mapping table, coupled to said register-renaming mapping table, for storing a complete copy of said register-renaming mapping table in response to a branch instruction; and a branch stack, coupled to said register-renaming mapping table, for storing a portion of said register-renaming mapping table, said portion being associated with an instruction decoded in parallel with said branch instruction, said instruction preceding said branch instruction in original program order.
Claim 14
Dependent Claim
77 words
A pipeline processor comprising: a register-renaming mapping table; a redundant mapping table, coupled to said register-renaming mapping table, for storing a complete copy of said register-renaming mapping table in response to a branch instruction; and a branch stack, coupled to said register-renaming mapping table, for storing a portion of said register-renaming mapping table, said portion being associated with an instruction decoded in parallel with said branch instruction, said instruction preceding said branch instruction in original program order.
Claim 15
Dependent Claim
65 words
The pipeline processor of claim 11 wherein: said redundant mapping table comprises a redundant RAM cell; and said register-renaming mapping table comprises a primary RAM cell, said primary RAM cell being coupled to said redundant RAM cell through a first transistor and a second transistor, said first and second transistors being coupled to a first control line which controls access to said redundant RAM cell.
Claim 16
Dependent Claim
46 words
The pipeline processor of claim 12 further comprising: a third transistor and a fourth transistor disposed between said redundant RAM cell and said primary RAM cell; and a second control line, coupled to said third and fourth transistors, which controls access to said primary RAM cell.
References Cited (Backward Citations)
US5134561A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-25 | 2001-11-24 | 2002-05-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-25 | 2005-11-24 | 2006-05-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-25 | 2009-11-24 | 2010-05-26 | $7700.00 | Window Closed / Lapsed |