US5572690A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cascaded multistage counterflow pipeline processor for carrying distinct data in two opposite directions
Assignee: Sun Microsystems Inc
•
Filing: 1995-06-06
•
Granted: 1996-11-05
•
Expires: 2015-06-06
Abstract
Abstract A counterflow computing pipeline including a series of similar stages is disclosed. In the basic form of the pipeline, the stages are arranged in a linear fashion and each stage in the pipeline communicates with its two adjacent stages. The flow of data elements in the pipeline is bi-directional. A first data stream of data elements flows in a first direction from stage to stage in the pipeline. A second data stream of data elements flows from stage to stage in the pipeline in a second direction counter to the first direction. Circuitry at each stage is provided so that every data element flowing in the first direction meets each and every data element that it passes flowing in the second direction. According to various embodiments of the invention, when two data elements meet at a stage, circuitry may be provided to compare the data elements, copy data from one data element to the other, or otherwise, cause the data elements to interact. The counterflow pipeline may be either synchronous or asynchronous, and may be used for a variety of applications in signal processing, associative memory, and computer architectures.
Inventors
- 👤 Charles E. Molnar
- 👤 Ivan E. Sutherland
- 👤 Robert F. Sproull
- 👤 Ian W. Jones
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 01:09
CPC Classifications
G; G06; G06F; G06F15/00; G06F7/00; G06F7/02; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3867
Claims Analysis
Total Claims: 42
Claim 1
Independent Claim
161 words
A counterflowing data processing system capable of carrying distinct data elements in two directions, comprising: a set of stages interconnected to form a pipeline; circuitry configured to control the flow of a first group of distinct data elements in a first direction through the set of stages forming the pipeline; circuitry configured to control the flow of a second group of distinct data elements in a second direction through the set of stages forming the pipeline; one stage among the set of stages further including: a dynamic selection circuit configured to determine if a first data element from the first group of distinct data elements and a second data element from the second group of distinct data elements are present at the one stage; and interaction circuitry configured to cause the first data element and the second data element to interact in the one stage when the first data element and the second data element are present in the one stage.
Claim 2
Dependent Claim
161 words
A counterflowing data processing system capable of carrying distinct data elements in two directions, comprising: a set of stages interconnected to form a pipeline; circuitry configured to control the flow of a first group of distinct data elements in a first direction through the set of stages forming the pipeline; circuitry configured to control the flow of a second group of distinct data elements in a second direction through the set of stages forming the pipeline; one stage among the set of stages further including: a dynamic selection circuit configured to determine if a first data element from the first group of distinct data elements and a second data element from the second group of distinct data elements are present at the one stage; and interaction circuitry configured to cause the first data element and the second data element to interact in the one stage when the first data element and the second data element are present in the one stage.
Claim 3
Dependent Claim
38 words
The system as set forth in claim 1, further comprising circuitry for assuring that the first data element interacts with each of the distinct data elements of the second group encountered in the pipeline no more than once.
Claim 4
Dependent Claim
44 words
The system as set forth in claim 1, wherein the interaction circuitry comprises compare circuitry to compare the first data element in the one stage with each of the distinct data elements of the second group of data elements encountered in the one stage.
Claim 5
Dependent Claim
55 words
The system as set forth in claim 3, wherein the interaction circuitry further comprises prevention circuitry to prevent the flow of the first data element and the flow of the second data element in the one stage, until the compare circuitry has completed its comparison of the first data element and the second data element.
Claim 6
Dependent Claim
44 words
The system as set forth in claim 1, wherein the dynamic selection circuit further comprises state determination circuitry to determine the state of the one stage, the one stage capable of occupying any one of the following states: Empty; Full; Up; Down; and Complete.
Claim 7
Dependent Claim
35 words
The system of claim 5, wherein the state of the one stage is changed according to the order of crossing boundaries defining the one stage by the first data element and the second data element.
Claim 8
Dependent Claim
26 words
The system as set forth in claim 1, wherein the one stage comprises memory elements to retain the first data element and the second data element.
Claim 9
Dependent Claim
24 words
The system as set forth in claim 1, wherein the one stage comprises modifying circuitry to modify the first and/or second distinct data elements.
Claim 10
Dependent Claim
41 words
The system of claim 8, wherein the one stage includes circuitry to insert a portion of the first data element flowing in the first direction as one of the distinct data elements of the second group flowing in the second direction.
Claim 11
Dependent Claim
23 words
The system as set forth in claim 8, wherein the modifying circuitry comprises circuitry to delete the second data element from the pipeline.
Claim 12
Dependent Claim
25 words
The system as set forth in claim 8, wherein the modifying circuitry comprises circuitry to perform computations involving the first data element in the pipeline.
Claim 13
Dependent Claim
33 words
The system as set forth in claim 11, wherein the circuitry to perform computations permits different computations to be made at different ones of the set of stages interconnected to form the pipeline.
Claim 14
Dependent Claim
34 words
The system as set forth in claim 11, wherein the circuitry to perform computations permits the same computations to be made at different ones of the set of stages interconnected to form the pipeline.
Claim 15
Dependent Claim
20 words
The system as set forth in claim 8, wherein the modifying circuitry comprises circuitry to update the second data element.
Claim 16
Dependent Claim
44 words
The system as set forth in claim 1, wherein the circuitry to control the flow of the first group of distinct data elements and the circuitry to control the flow of the second group of distinct data elements permits elastic operation of the pipeline.
Claim 17
Dependent Claim
47 words
The system as set forth in claim 1, wherein the circuitry to control the flow of the first group of distinct data elements and the circuitry to control the flow of the second group of distinct data elements further comprises circuitry for bi-directional communication between the stages.
Claim 18
Dependent Claim
56 words
The system as set forth in claim 1, wherein the circuitry to control the flow of the first group of distinct data elements and the circuitry to control the flow of the second group of distinct data elements permits asycnchronous movement of the first group and the second group of distinct data elements in the pipeline.
Claim 19
Dependent Claim
56 words
The system as set forth in claim 1, wherein the circuitry to control the flow of the first group of distinct data elements and the circuitry to control the flow of the second group of distinct data elements permits synchronous movement of the first group and the second group of distinct data elements in the pipeline.
Claim 20
Dependent Claim
50 words
The system as set forth in claim 1, wherein the circuitry to control the flow of the first group of distinct data elements and the circuitry to control the flow of the second group of distinct data elements is included in the set of stages interconnected to form the pipeline.
Claim 21
Dependent Claim
29 words
The system as set forth in claim 1, wherein the pipeline further comprises circuitry configured to provide external signals to at least some of the stages of the pipeline.
Claim 22
Dependent Claim
41 words
The system as set forth in claim 1, wherein the pipeline further comprises: circuitry configured to form branches in the pipeline; and circuitry to control the flow of selected ones of the distinct data elements into and out of the branches.
Claim 23
Dependent Claim
40 words
The system as set forth in claim 1, wherein the pipeline further comprises: circuitry configured to form sidings to the pipeline; and circuitry to control the flow of selected ones of the data elements into and out of the sidings.
Claim 24
Dependent Claim
47 words
The system as set forth in claim 1 further comprising a set of the dynamic selection circuits and a set of the interaction circuits, each one of the dynamic selection circuits and the interaction circuits associated with one of the set of stages in the pipeline respectively.
Claim 25
Dependent Claim
43 words
The system of claim 1, further comprising circuitry distributed among the set of stages to ensure that each of the distinct data elements of the first group is compared with each of the distinct data elements of the second group in the pipeline.
Claim 26
Dependent Claim
41 words
The system of claim 1, wherein the dynamic selection circuit is used to determine at which stage in the pipeline a particular first data element from the first group will interact with a particular second data element from the second group.
Claim 27
Independent Claim
173 words
A method of providing a data processing system capable of carrying distinct data elements in two directions, comprising the steps of: providing a set of stages interconnected to form a pipeline; providing circuitry configured to control the flow of a first group of distinct data elements in a first direction through the set of stages forming the pipeline; and providing circuitry configured to control the flow of a second group of distinct data elements in a second direction through the set of stages forming the pipeline; providing one stage among the set of stages further including: a dynamic selection circuit configured to determine if a first data element from the first group of distinct data elements and a second data element from the second group of distinct data elements are present at the one stage; and interaction circuitry configured to cause the first data element and the second data element to interact in the one stage when both the first data element and the second data element are present in the one stage.
Claim 28
Independent Claim
173 words
A method of providing a data processing system capable of carrying distinct data elements in two directions, comprising the steps of: providing a set of stages interconnected to form a pipeline; providing circuitry configured to control the flow of a first group of distinct data elements in a first direction through the set of stages forming the pipeline; and providing circuitry configured to control the flow of a second group of distinct data elements in a second direction through the set of stages forming the pipeline; providing one stage among the set of stages further including: a dynamic selection circuit configured to determine if a first data element from the first group of distinct data elements and a second data element from the second group of distinct data elements are present at the one stage; and interaction circuitry configured to cause the first data element and the second data element to interact in the one stage when both the first data element and the second data element are present in the one stage.
Claim 29
Independent Claim
150 words
A method of managing a data processing system capable of carrying distinct data elements in two directions, comprising the steps of: controlling the flow of a first group of distinct data elements in a first direction through a set of stages forming a pipeline; controlling the flow of a second group of distinct data elements in a second direction through the set of stages forming the pipeline; dynamically selecting one stage among the set of stages in the pipeline, the one stage selected by determining when a first data element from the first group of distinct data elements and a second data element from the second group of distinct data elements are present at the one stage; and causing the first data element and the second data element to interact in the one stage when the first data element and the second data element are present in the one stage.
Claim 30
Independent Claim
150 words
A method of managing a data processing system capable of carrying distinct data elements in two directions, comprising the steps of: controlling the flow of a first group of distinct data elements in a first direction through a set of stages forming a pipeline; controlling the flow of a second group of distinct data elements in a second direction through the set of stages forming the pipeline; dynamically selecting one stage among the set of stages in the pipeline, the one stage selected by determining when a first data element from the first group of distinct data elements and a second data element from the second group of distinct data elements are present at the one stage; and causing the first data element and the second data element to interact in the one stage when the first data element and the second data element are present in the one stage.
Claim 31
Dependent Claim
39 words
The method as set forth in claim 27, further comprising the step of assuring that the first data element interacts with each of the distinct data elements of the second group encountered in the pipeline no more than once.
Claim 32
Dependent Claim
43 words
The method as set forth in claim 27, wherein the dynamic selecting step further comprises the step of determining the state of the one stage, the one stage capable of occupying any one of the following states: Empty; Full; Up; Down; and Complete.
Claim 33
Dependent Claim
37 words
The method of claim 27, wherein the steps of controlling the flow of the first group of distinct data elements and the flow of the second group of distinct data elements permits elastic operation of the pipeline.
Claim 34
Dependent Claim
23 words
The method as set forth in claim 27, further comprising the step of modifying the first data element and/or the second data element.
Claim 35
Dependent Claim
25 words
The method as set forth in claim 31, wherein the modifying step further comprises the step of deleting the second data element from the pipeline.
Claim 36
Dependent Claim
24 words
The method as set forth in claim 31, wherein the modifying step further comprises the step of performing computations involving the first data element.
Claim 37
Dependent Claim
22 words
The method as set forth in claim 31 wherein the modifying step further comprises the step of updating the second data element.
Claim 38
Dependent Claim
39 words
The method of claim 31, further comprising the step of inserting a portion of the first data element flowing in the first direction as one of the distinct data elements of the second group flowing in the second direction.
Claim 39
Dependent Claim
39 words
The method of claim 27, wherein the interaction step further comprises the step of comparing the first data element in the one stage with each of the distinct data elements of the second group encountered in the one stage.
Claim 40
Dependent Claim
29 words
The method of claim 36, further comprising the step of preventing the movement of the first data element from the selected stage until the comparing step has been completed.
Claim 41
Dependent Claim
58 words
The method of claim 27, wherein the step of controlling the flow of the first group of distinct data elements and the step of controlling the flow of the second group of distinct data elements further comprises the step of permitting asynchronous movement of the data elements of the first group and the second group in the pipeline.
Claim 42
Dependent Claim
58 words
The method of claim 27, wherein the step of controlling the flow of the first group of distinct data elements and the step of controlling the flow of the second group of distinct data elements further comprises the step of permitting synchronous movement of the data elements of the first group and the second group in the pipeline.
References Cited (Backward Citations)
US3166715A
Cited
US4112489A
Cited
JPS57139856A
Cited
US4489393A
Cited
US5187800A
Cited
US4885715A
Cited
US4991078A
Cited
EP0365188A2
Cited
US5210750A
Cited
US5107465A
Cited
US5361367A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-11-05 | 2000-05-06 | 2000-11-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-11-05 | 2004-05-06 | 2004-11-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-11-05 | 2008-05-06 | 2008-11-05 | $7700.00 | Window Closed / Lapsed |