US4943909A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Computational origami
Assignee: NCR Voyix Corp
•
Filing: 1987-07-08
•
Granted: 1990-07-24
•
Expires: 2007-07-08
Abstract
Abstract A processor architecture that permits the realization of any computing function with a regular array of interconnected procssing elements comprising as few as one processing element. The processing element can be as complex as desired. In its minimum form it can be as simple as a NOR gate and switch coupled with some delay elements, with the connectivity and the control signals combining to impart the flexiblity. In use, an algorithm to be implemented is conceptually mapped onto an array of processing elements arranged in rows and columns, where the data dependencies in the columns are unidirectional, and the data dependencies in the rows of processing elements are at most unidirectional. One or more actual processing elements are conceptually scanned over the array through time multiplexed controls to emulate the entire conceptual array and thus perform the algorithm. The scheduling of the processing and communications functions performed by the processing element is dictated by the conceptual array layout of the algorithm.
Inventors
- 👤 Alan Huang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 19:27
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/76; G06F15/80; G06F15/8007; G06F15/8023
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
201 words
Computational apparatus including a processing element having a first and a second input port, a first and a second output port, and a control, characterized by said processing element performing both routing and computation functions; first delay means, connected to said first output port and to a first apparatus output port of said computational apparatus, for storing a preselected number of output signals of said first output port; first combining means responsive to output signals of said first delay means and to signals applied to said computational apparatus at a first apparatus input port for applying a combination of its input signals to said second input port; second delay means, connected to said second output port and to a second output port of said computational apparatus, for storing another preselected number of output signals of said second output port; second combining means responsive to output signals of said second delay means and to signals applied to said computational apparatus at a second apparatus input port for applying a combination of its input signals to said first input port; and means for applying control signals to said control port and causing said processing element to execute preselected processing and signal routing functions.
Claim 2
Dependent Claim
201 words
Computational apparatus including a processing element having a first and a second input port, a first and a second output port, and a control, characterized by said processing element performing both routing and computation functions; first delay means, connected to said first output port and to a first apparatus output port of said computational apparatus, for storing a preselected number of output signals of said first output port; first combining means responsive to output signals of said first delay means and to signals applied to said computational apparatus at a first apparatus input port for applying a combination of its input signals to said second input port; second delay means, connected to said second output port and to a second output port of said computational apparatus, for storing another preselected number of output signals of said second output port; second combining means responsive to output signals of said second delay means and to signals applied to said computational apparatus at a second apparatus input port for applying a combination of its input signals to said first input port; and means for applying control signals to said control port and causing said processing element to execute preselected processing and signal routing functions.
Claim 3
Dependent Claim
56 words
The apparatus of claim 1 wherein said processing element includes a signal processing network connected to said first and second input ports, for performing said computation function; and a signal routing network responsive to input signals at first and second input ports and to output signals of said signal processing network, for performing said routing function.
Claim 4
Dependent Claim
28 words
The apparatus of claim 2 wherein said signal routing network includes the means to switch any of the input signals to one or both of said output ports.
Claim 5
Dependent Claim
189 words
Signal processing apparatus characterized by a plurality of processing elements arranged in an array of rows and columns, with each processing element in a row and a column having one input port connected to one output port of a processing element in a previous row and the same column, and another input port connected to another output port of a processing element in said previous row and another column, where input ports of processing elements in the first row of said array accept input signals to said computational apparatus and output ports of processing elements in the last row of said array comprise output signals of said computational apparatus, said computational apparatus being further characterized by: a plurality of delay means, each connected to an output port of a different one of said processing elements in said last row and each storing its a number of clock-synchronized output signals of said processing element; means for applying output signals of said plurality of delay means to said input ports of said processing elements; and means for controlling, in a clock-synchronized manner, the operational functionality of each of said processing elements.
Claim 6
Dependent Claim
189 words
Signal processing apparatus characterized by a plurality of processing elements arranged in an array of rows and columns, with each processing element in a row and a column having one input port connected to one output port of a processing element in a previous row and the same column, and another input port connected to another output port of a processing element in said previous row and another column, where input ports of processing elements in the first row of said array accept input signals to said computational apparatus and output ports of processing elements in the last row of said array comprise output signals of said computational apparatus, said computational apparatus being further characterized by: a plurality of delay means, each connected to an output port of a different one of said processing elements in said last row and each storing its a number of clock-synchronized output signals of said processing element; means for applying output signals of said plurality of delay means to said input ports of said processing elements; and means for controlling, in a clock-synchronized manner, the operational functionality of each of said processing elements.
Claim 7
Dependent Claim
37 words
The apparatus of claim 4 wherein said means for controlling directs each of said processing elements in said array to perform a selected processing function, independently of the processing function selected for performing by other processing elements.
Claim 8
Dependent Claim
28 words
The apparatus of claim 4 where said delay means provides a signal delay value realizes a selected interconnection pattern in a larger emulated array of interconnected processing elements.
Claim 9
Dependent Claim
21 words
The apparatus of claim 6 wherein said delay means has a delay value that is controlled by an applied control signal.
Claim 10
Dependent Claim
22 words
The apparatus of claim 7 wherein said delay means control signal is dynamically alterable to control the width of said emulated array.
Claim 11
Dependent Claim
192 words
Processing apparatus comprising a plurality of processing elements arranged in rows and columns characterized in that: some of said processing elements are main-stream processing elements, at least one of said processing elements is a feedback-supplying processing element, and at least one of said processing elements is a fedback receiving processing element; each main-stream processing element in a given row and a given column sends output signals to a processing element in a row succeeding said given row and in said given column, and to a processing element in said succeeding row and in a column succeeding said given column; each feedback-supplying processing element sends output signals to one of said feedback-receiving processing elements in a row preceding the row of said feedback-supplying processing element; each of said processing elements in a given row and a given column is, at most, connected to one of said processing elements in subsequent row and said column and to one of said processing elements in an adjacent column; and each of said processing elements performs a selected processing operation independent of the processing operations selected for being performed by other processing elements in said processing apparatus.
Claim 12
Dependent Claim
192 words
Processing apparatus comprising a plurality of processing elements arranged in rows and columns characterized in that: some of said processing elements are main-stream processing elements, at least one of said processing elements is a feedback-supplying processing element, and at least one of said processing elements is a fedback receiving processing element; each main-stream processing element in a given row and a given column sends output signals to a processing element in a row succeeding said given row and in said given column, and to a processing element in said succeeding row and in a column succeeding said given column; each feedback-supplying processing element sends output signals to one of said feedback-receiving processing elements in a row preceding the row of said feedback-supplying processing element; each of said processing elements in a given row and a given column is, at most, connected to one of said processing elements in subsequent row and said column and to one of said processing elements in an adjacent column; and each of said processing elements performs a selected processing operation independent of the processing operations selected for being performed by other processing elements in said processing apparatus.
Claim 13
Dependent Claim
67 words
The processing apparatus of claim 9 wherein each of said main-stream processing element in a row i and column j has one output lead connecting said processing element to a processing element in row i+1 and row j, and one output lead connecting said processing element to a processing element in row i+1 and column j+(-1) i K where K is an integer constant for each row.
Claim 14
Dependent Claim
65 words
The processing apparatus of claim 9 wherein each of said main-stream processing element in row i and column j has one output lead connecting said processing element to a processing element in row i+1 and row j, and one output lead connecting said processing element to a processing element in row i+1 and column j-(-1) i K where K is a constant for each row.
Claim 15
Dependent Claim
60 words
The processing apparatus of claim 9 wherein each of said main-stream processing element in row i and column j has one output lead connecting said processing element to a processing element in row i+1 and one output lead connecting said processing element to a processing element in row i+1 and column j+K where K is a constant for each row.
Claim 16
Dependent Claim
63 words
The processing apparatus of claim 9 wherein each of said main-stream processing element in row i and column j has one output lead connecting said processing element to a processing element in row i+1 and row j, and one output lead connecting said processing element to a processing element in row i+1 and column j-K where K is a constant for each row.
Claim 17
Dependent Claim
19 words
The apparatus of claim 1 wherein said preselected number and said another preselected number are related to each other.
Claim 18
Dependent Claim
29 words
The apparatus of claim 1 wherein said first delay means stores N output signals and said second delay means stores N+1 output signals, where N is a preselected constant.
Claim 19
Dependent Claim
23 words
The apparatus of claim 2 wherein said processing network comprises means to perform a set of computations that constitute a complete boolean cover.
Claim 20
Dependent Claim
12 words
The apparatus of claim 2 wherein said processing network comprises a CPU.
Claim 21
Dependent Claim
12 words
The apparatus of claim 2 wherein said processing network comprises a computer.
Claim 22
Dependent Claim
18 words
The apparatus of claim 4 wherein said signal processing element comprises a NAND gate or a NOR gate.
References Cited (Backward Citations)
US4553203A
Cited
US4740894A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-07-23 | 1994-01-22 | 1994-07-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-07-23 | 1998-01-22 | 1998-07-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-07-23 | 2002-01-22 | 2002-07-24 | $7700.00 | Window Closed / Lapsed |