Patent US5019967A successfully refreshed from Google Patents.
US5019967A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pipeline bubble compression in a computer system
Assignee: Hewlett Packard Development Co LP
•
Filing: 1988-07-20
•
Granted: 1991-05-28
•
Expires: 2008-07-20
Abstract
Abstract Bubble compression in a pipelined central processing unit (CPU) of a computer system is provided. A bubble represents a stage in the pipeline that cannot perform any useful work due to the lack of data from an earlier pipeline stage. When a particular pipeline stage has stalled, the CPU instructions that have already passed through the stage continue to move ahead and leave behind vacant stages or bubbles. If a bubble is introduced into a pipeline and the pipeline subsequently stalls, the disclosed CPU takes advantage of this stalled condition to compress the previously introduced bubble.
Inventors
- 👤 William R. Wheeler
- 👤 George M. Uhler
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 13:21
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3867; G06F9/3873; G06F9/3802; G06F9/3814; G06F9/3836
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
173 words
A method of operating a pipelined processing unit in a digital computer, said pipelined processing unit having at least a first pipeline segment and a second pipeline segment for processing information, said first pipeline segment processing information in said pipeline upstream of said second pipeline segment; said processing of information in said second pipeline segment being capable of causing a stall condition which results in waiting for processing information and capable of producing a bubble in said first pipeline segment during which said first pipeline segment does no useful processing of information; and control means in said pipelined processing unit for controlling said processing of information and responsive to said stall condition and said bubble; said method comprising the steps of: a) detecting a bubble in the first pipeline segment by said control means; b) detecting a stall condition in the second pipeline segment by said control means; and c) overwriting the bubble in the first pipeline segment by said processing of information, under control by said control means, thereby compressing the bubble.
Claim 2
Independent Claim
173 words
A method of operating a pipelined processing unit in a digital computer, said pipelined processing unit having at least a first pipeline segment and a second pipeline segment for processing information, said first pipeline segment processing information in said pipeline upstream of said second pipeline segment; said processing of information in said second pipeline segment being capable of causing a stall condition which results in waiting for processing information and capable of producing a bubble in said first pipeline segment during which said first pipeline segment does no useful processing of information; and control means in said pipelined processing unit for controlling said processing of information and responsive to said stall condition and said bubble; said method comprising the steps of: a) detecting a bubble in the first pipeline segment by said control means; b) detecting a stall condition in the second pipeline segment by said control means; and c) overwriting the bubble in the first pipeline segment by said processing of information, under control by said control means, thereby compressing the bubble.
Claim 3
Dependent Claim
26 words
A method according to claim 1 wherein said first pipeline segment performs the operations of decoding an instruction and producing control data based upon said instruction.
Claim 4
Dependent Claim
33 words
A method according to claim 2 wherein said second pipeline segment performs the operation of generating sets of control bits in response to the decoding of an instruction in said first pipeline segment.
Claim 5
Dependent Claim
27 words
A method according to claim 3 wherein said bubble in said first segment includes a condition whereby said control data is invalid and thus may be overwritten.
Claim 6
Dependent Claim
39 words
A method according to claim 4 wherein said processor includes a third pipeline segment in which operands are fetched from a register file, an operation is performed on said operands, and a result is stored in said register file.
Claim 7
Dependent Claim
19 words
A method according to claim 5 wherein said control data includes identification of a register in said register file.
Claim 8
Dependent Claim
27 words
A method according to claim 6 wherein said processor is microprogrammed and said second pipeline segment includes fetching said sets of control bits from a microinstruction store.
Claim 9
Dependent Claim
201 words
A processor comprising: a) a plurality of successive operating stages, with operation means in each stage either performing some operation on a set of data or controls received from a preceding stage and passing an output set of data or controls to operation means of a succeeding stage or introducing a stall whereby no operation is performed and no data or controls are passed to operation means of a succeeding stage, wherein said operation means of at least one of said stages alternatively introduces a non-operative set of data or controls to be passed to operation means of a succeeding stage; b) and control means coupled to said operating stages for advancing said sets of data or controls in all of said stages simultaneously when none of said stages has introduced a stall, or in later ones of said stages downstream of said given one of said stages when said given one has introduced a stall; c) said control means including means for overwriting said nonoperative set of data or controls in said operation means of at least one of said stages upstream of said given one of said stages when said given one of said stages has introduced a stall.
Claim 10
Dependent Claim
201 words
A processor comprising: a) a plurality of successive operating stages, with operation means in each stage either performing some operation on a set of data or controls received from a preceding stage and passing an output set of data or controls to operation means of a succeeding stage or introducing a stall whereby no operation is performed and no data or controls are passed to operation means of a succeeding stage, wherein said operation means of at least one of said stages alternatively introduces a non-operative set of data or controls to be passed to operation means of a succeeding stage; b) and control means coupled to said operating stages for advancing said sets of data or controls in all of said stages simultaneously when none of said stages has introduced a stall, or in later ones of said stages downstream of said given one of said stages when said given one has introduced a stall; c) said control means including means for overwriting said nonoperative set of data or controls in said operation means of at least one of said stages upstream of said given one of said stages when said given one of said stages has introduced a stall.
Claim 11
Dependent Claim
27 words
A processor according to claim 8 wherein said operating stages include a first stage for decoding instructions and producing control data for use in a downstream stage.
Claim 12
Dependent Claim
26 words
A processor according to claim 9 wherein said operating stages include a second stage for generating sets of control bits in response to said decoded instructions.
Claim 13
Dependent Claim
25 words
A processor according to claim 10 wherein said processor is microcoded and said second stage fetches said sets of control bits from a microcode store.
Claim 14
Dependent Claim
27 words
A processor according to claim 9 wherein said sets of data or controls are temporarily stored in a latch, and said means for overwriting overwrites said latch.
Claim 15
Dependent Claim
30 words
A processor according to claim 8 wherein said stages include a third stage for fetching an operand from a register in a register file and performing operations on said operand.
Claim 16
Dependent Claim
17 words
A processor according to claim 13 wherein set of data and controls includes identification of said register.
Claim 17
Independent Claim
117 words
A method of operating a pipelined processing unit including a pipeline segment having an input and an output, and said pipeline segment having a first condition indicating a delay downstream of said pipeline segment in said processing unit and a second condition indicating a bubble in which said pipeline segment is receiving useless information on said input from upstream in said processing unit, where the method comprises the steps of: (a) issuing a do-nothing command to said pipeline segment when the first condition does not exit and said second condition exists, and (b) issuing an overwrite command to said pipeline segment when the first condition exists and the second condition exists, whereby said output may be overwritten.
Claim 18
Independent Claim
117 words
A method of operating a pipelined processing unit including a pipeline segment having an input and an output, and said pipeline segment having a first condition indicating a delay downstream of said pipeline segment in said processing unit and a second condition indicating a bubble in which said pipeline segment is receiving useless information on said input from upstream in said processing unit, where the method comprises the steps of: (a) issuing a do-nothing command to said pipeline segment when the first condition does not exit and said second condition exists, and (b) issuing an overwrite command to said pipeline segment when the first condition exists and the second condition exists, whereby said output may be overwritten.
Claim 19
Dependent Claim
14 words
The method of claim 15 where said output issues data representing a microinstruction address.
Claim 20
Dependent Claim
20 words
The method of claim 16 where the do-nothing command causes said pipeline segment to issue useless information on said output.
Claim 21
Dependent Claim
21 words
The method of claim 15 where the overwrite command is an overwrite flag to an output latch of said pipeline segment.
Claim 22
Independent Claim
120 words
A method of operating a pipelined processor having a plurality of pipelined stages, where each stage receives input data from a preceding stage and passes output data to a succeeding stage, and where one of said stages can send a stall control to a preceding stage upstream of said one stage, and wherein said preceding stage can operate in a bubble condition of passing useless output data to a succeeding stage, comprising the steps of: (a) detecting said stall control from said one stage of said pipeline stages; (b) determining that the output data in said preceding stage represents useless output data; and (c) overwriting the output data of said preceding stage with input data received by said preceding stage.
Claim 23
Independent Claim
120 words
A method of operating a pipelined processor having a plurality of pipelined stages, where each stage receives input data from a preceding stage and passes output data to a succeeding stage, and where one of said stages can send a stall control to a preceding stage upstream of said one stage, and wherein said preceding stage can operate in a bubble condition of passing useless output data to a succeeding stage, comprising the steps of: (a) detecting said stall control from said one stage of said pipeline stages; (b) determining that the output data in said preceding stage represents useless output data; and (c) overwriting the output data of said preceding stage with input data received by said preceding stage.
Claim 24
Dependent Claim
36 words
The method of claim 19 where said preceding stage includes a temporary storage element for storing its output data and step (b) comprises the step of detecting an overwrite flag associated with the temporary storage element.
Claim 25
Dependent Claim
21 words
The method of claim 19 where step (c) further comprises the step of advancing all stages preceding said one delayed stage.
References Cited (Backward Citations)
US3248707A
Cited
US4090249A
Cited
US4236206A
Cited
US4794518A
Cited
US4438492A
Cited
US4541047A
Cited
US4534009A
Cited
US4498136A
Cited
US4594655A
Cited
US4670836A
Cited
US4750112A
Cited
US4760519A
Cited
US4636943A
Cited
US4586130A
Cited
US4701915A
Cited
US4794517A
Cited
US4701842A
Cited
US4709324A
Cited
US4794527A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-05-27 | 1994-11-26 | 1995-05-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-05-27 | 1998-11-26 | 1999-05-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-05-27 | 2002-11-26 | 2003-05-28 | $7700.00 | Window Closed / Lapsed |