Patent US5325495A successfully refreshed from Google Patents.
US5325495A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Reducing stall delay in pipelined computer system using queue between pipeline stages
Assignee: Hewlett Packard Development Co LP
•
Filing: 1993-08-09
•
Granted: 1994-06-28
•
Expires: 2013-08-09
Abstract
Abstract A pipelined computer system employs a queue stage to receive the output of one pipeline stage when a stall occurs in the next stage or downstream of the next stage. This avoids stalling earlier stages of the pipeline. Subsequently, the pipeline advances through the queue, until a bubble occurs. When a bubble is subsequently generated upstream and enters the queue stage, a multiplexer switches the input of the next stage to receive the output of the one stage instead of from the queue stage, and the content of the queue is overwritten. By this mechanism, the delays inherent in processing branches can be reduced.
Inventors
- 👤 Edward J. McLellan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 14:27
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3804; G06F9/3867; G06F9/3869
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
203 words
A pipelined computer system, comprising: a plurality of pipeline stages, each said pipeline stage having an input and an output, said input of each of said pipeline stages receiving information from said output of a preceding one of said pipeline stages in a normal mode of operation; a bypass queue connected to receive said output of one of said pipeline stages, and switch means to route said output of said one of said pipeline stages through said bypass queue instead of to said input of a next one of said pipeline stages and to connect an output of said bypass queue to said input of said next one of said pipeline stages, in a bypass mode initiated in response to a command; control means responsive to a stall occurring in said pipeline downstream of said one of said stages, to generate said command and initiate said bypass mode, said bypass mode being maintained until a bubble enters said bypass queue; said control means being responsive to a bubble entering said queue stage to terminate said bypass mode and initiate said normal mode and cause said next one of said stages to receive the output of said one stage directly via said switch means.
Claim 2
Dependent Claim
203 words
A pipelined computer system, comprising: a plurality of pipeline stages, each said pipeline stage having an input and an output, said input of each of said pipeline stages receiving information from said output of a preceding one of said pipeline stages in a normal mode of operation; a bypass queue connected to receive said output of one of said pipeline stages, and switch means to route said output of said one of said pipeline stages through said bypass queue instead of to said input of a next one of said pipeline stages and to connect an output of said bypass queue to said input of said next one of said pipeline stages, in a bypass mode initiated in response to a command; control means responsive to a stall occurring in said pipeline downstream of said one of said stages, to generate said command and initiate said bypass mode, said bypass mode being maintained until a bubble enters said bypass queue; said control means being responsive to a bubble entering said queue stage to terminate said bypass mode and initiate said normal mode and cause said next one of said stages to receive the output of said one stage directly via said switch means.
Claim 3
Dependent Claim
42 words
A system according to claim 1 wherein said switch means includes a multiplexer having inputs receiving said output of said one stage and said output of said bypass-queue, said multiplexer selecting said input of said next stage in response to said command.
Claim 4
Dependent Claim
22 words
A system according to claim 2 wherein said pipeline stages, said bypass-queue, and said control means are all controlled by a clock.
Claim 5
Dependent Claim
22 words
A system according to claim 3 wherein said control means causes said bubble to be eliminated when said bypass mode is terminated.
Claim 6
Dependent Claim
14 words
A system according to claim 4 wherein said bypass-queue has a depth of one.
Claim 7
Independent Claim
157 words
A method of operating a pipelined computer system, comprising the steps of: performing operations in sequence in a plurality of pipeline stages, each said pipeline stage having an input receiving information from an output of a preceding one of said pipeline stages; bypassing said information from said output of one of said pipeline stages into a bypass-queue instead of allowing said output of said one of said pipeline stages to be coupled to the input of the next one of said pipeline stages, and directing an output of said bypass-queue to said input of said next stage, in response to a command; generating said command in response to a stall occurring in said pipeline downstream of said one of said stages; and in response to a bubble entering said bypass-queue, negating said command and causing said input of said next one of said stages to receive information directly from said output of said one of said stages.
Claim 8
Independent Claim
157 words
A method of operating a pipelined computer system, comprising the steps of: performing operations in sequence in a plurality of pipeline stages, each said pipeline stage having an input receiving information from an output of a preceding one of said pipeline stages; bypassing said information from said output of one of said pipeline stages into a bypass-queue instead of allowing said output of said one of said pipeline stages to be coupled to the input of the next one of said pipeline stages, and directing an output of said bypass-queue to said input of said next stage, in response to a command; generating said command in response to a stall occurring in said pipeline downstream of said one of said stages; and in response to a bubble entering said bypass-queue, negating said command and causing said input of said next one of said stages to receive information directly from said output of said one of said stages.
Claim 9
Dependent Claim
19 words
A method according to claim 6 including synchronizing said steps of performing operations, bypassing, and generating, by a clock.
Claim 10
Dependent Claim
18 words
A method according to claim 7 including eliminating a bubble in said bypass-queue when said command is negated.
Claim 11
Dependent Claim
43 words
A method according to claim 6 including the step of selecting said input to said next stage by a multiplexer responsive to said command, said output of said one stage and said output of said bypass-queue being coupled to inputs of said multiplexer.
Claim 12
Dependent Claim
18 words
A method according to claim 6 including storing said information in said bypass-queue to a depth of one.
Claim 13
Dependent Claim
13 words
A method according to claim 6 wherein said information is decoded program instructions.
Claim 14
Dependent Claim
202 words
A pipelined computer system, comprising: a plurality of pipeline stages, each said pipeline stage having an input and an output, said input of each of said pipeline stages receiving information from said output of a preceding one of said pipeline stages; a queue connected to continuously receive said output of one of said pipeline stages, and switch means to prevent said output of said one of said pipeline stages from going to the next one of said pipeline stages and to connect an output of said queue to said input of said next one of said pipeline stages, in response to a command, so that said input of said next one of said pipeline stages receives information from said output of said queue stage continuously until a bubble enters said queue stage; control means responsive to a stall occurring in said pipeline downstream of said one of said stages, to generate said command; said control means being responsive to a bubble entering said queue stage to negate said command and cause said next one of said stages to receive the output of said one stage via said switch means, rather than from said queue stage , when said queue stage is empty.
Claim 15
Dependent Claim
202 words
A pipelined computer system, comprising: a plurality of pipeline stages, each said pipeline stage having an input and an output, said input of each of said pipeline stages receiving information from said output of a preceding one of said pipeline stages; a queue connected to continuously receive said output of one of said pipeline stages, and switch means to prevent said output of said one of said pipeline stages from going to the next one of said pipeline stages and to connect an output of said queue to said input of said next one of said pipeline stages, in response to a command, so that said input of said next one of said pipeline stages receives information from said output of said queue stage continuously until a bubble enters said queue stage; control means responsive to a stall occurring in said pipeline downstream of said one of said stages, to generate said command; said control means being responsive to a bubble entering said queue stage to negate said command and cause said next one of said stages to receive the output of said one stage via said switch means, rather than from said queue stage , when said queue stage is empty.
Claim 16
Dependent Claim
41 words
A system according to claim 12, said switch means including a multiplexer to receive said output of said one stage and the output of said queue stage to select an input of said next stage, in response to said control means.
Claim 17
Dependent Claim
24 words
A system according to claim 13 wherein said pipeline control stages, said queue stage and said control means are all controlled by a clock.
Claim 18
Dependent Claim
35 words
A system according to claim 12 wherein said control means causes eliminating a bubble in said queue stage when said input to said next stage is switched back to said output of said one stage.
Claim 19
Independent Claim
161 words
A method of operating a pipelined computer system, comprising the steps of: performing operations in sequence in a plurality of pipeline stages, each said pipeline stage having an input receiving information from an output of a preceding one of said pipeline stages; continuously loading a queue stage connected to receive the output of one of said stages, and, in response to a command, instead of allowing said output of said one of said pipeline stages to be coupled to the input of the next one of said pipeline stages, directing an output of said queue stage to said input of said next stage; generating said command in response to a stall occurring in said pipeline downstream of said one of said stages; and in response to a bubble entering said queue stage, negating said command and causing said next one of said stages to receive information from said output of said one of said stages when said queue stage is empty.
Claim 20
Independent Claim
161 words
A method of operating a pipelined computer system, comprising the steps of: performing operations in sequence in a plurality of pipeline stages, each said pipeline stage having an input receiving information from an output of a preceding one of said pipeline stages; continuously loading a queue stage connected to receive the output of one of said stages, and, in response to a command, instead of allowing said output of said one of said pipeline stages to be coupled to the input of the next one of said pipeline stages, directing an output of said queue stage to said input of said next stage; generating said command in response to a stall occurring in said pipeline downstream of said one of said stages; and in response to a bubble entering said queue stage, negating said command and causing said next one of said stages to receive information from said output of said one of said stages when said queue stage is empty.
Claim 21
Dependent Claim
35 words
A method according to claim 16 including selecting said input of said next one of said stages by a multiplexer to receive said output of said one stage or the output of said queue stage.
Claim 22
Dependent Claim
23 words
A method according to claim 16 wherein said pipeline stages, said queue stage and said control means are all controlled by a clock.
Claim 23
Dependent Claim
14 words
A method according to claim 16 including eliminating a bubble in said queue stage.
Claim 24
Dependent Claim
15 words
A method according to claim 16 wherein said queue stage has a depth of one.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-06-27 | 1997-12-27 | 1998-06-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-06-27 | 2001-12-27 | 2002-06-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-06-27 | 2005-12-27 | 2006-06-28 | $7700.00 | Window Closed / Lapsed |