US5931959A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dynamically reconfigurable FPGA apparatus and method for multiprocessing and fault tolerance
Assignee: United States Department of the Air Force
•
Filing: 1997-05-21
•
Granted: 1999-08-03
•
Expires: 2017-05-21
Abstract
Abstract Computing modules can cooperate to tolerate faults among their members. In a preferred embodiment, computing modules couple with dual-ported memories and interface with a dynamically reconfigurable Field-Programmable Gate Array ("FPGA"). The FPGA serves as a computational engine to provide direct hardware support for flexible fault tolerance between unconstrained combinations of the computing modules. In addition to supporting traditional fault tolerance functions that require bit-for-bit exactness, the FPGA engine is programmed to tolerate faults that cannot be detected through direct comparison of module outputs. Combating these faults requires more complex algorithmic or heuristic approaches that check whether outputs meet user-defined reasonableness criteria. For example, forming a majority from outputs that are not identical but may nonetheless be correct requires taking an inexact vote. The FPGA engine's flexibility extends to allowing for multiprocessing among the modules where the FPGA engine supports message passing. Implementing these functions in hardware instead of software makes them execute faster. The FPGA is reprogrammable, and only the functions required immediately need be implemented. Inactive functions are stored externally in a Read-Only Memory (ROM). The dynamically reconfigurable FPGA gives the fault-tolerant system an output stage that offers low gate complexity by storing the unused "gates" as configuration code in ROM. Lower gate complexity translates to a highly reliable output stage, prerequisite to a fault tolerant system.
Inventors
- 👤 Kevin Anthony Kwiat
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 12:11
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/16; G06F11/18; G06F11/187; G06F11/188; G06F11/14; G06F11/1479; G06F11/1487; G06F11/1489; G06F11/1629; G06F11/1641
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
147 words
Apparatus for fault-tolerant multiprocessing, which comprises: a plurality of computing modules; a plurality of memory modules connected to said computing modules; each of said memory modules having at least two ports; said plurality of computing modules being equal in number to said plurality of memory modules; at least one memory interface connected to each of said memory modules; at least one reconfigurable logic and switching device connected to said at least one memory interface; means for storing a plurality of configurations of said at least one logic and switching device; a counter connecting said logic and switching device to said means for storing; and said at least one logic and switching device comprising an array of individually reprogrammable cells configured so that a selected number of said cells can be reprogrammed to cause at least two of said plurality of computing modules to operate in fault-tolerant mode.
Claim 2
Dependent Claim
147 words
Apparatus for fault-tolerant multiprocessing, which comprises: a plurality of computing modules; a plurality of memory modules connected to said computing modules; each of said memory modules having at least two ports; said plurality of computing modules being equal in number to said plurality of memory modules; at least one memory interface connected to each of said memory modules; at least one reconfigurable logic and switching device connected to said at least one memory interface; means for storing a plurality of configurations of said at least one logic and switching device; a counter connecting said logic and switching device to said means for storing; and said at least one logic and switching device comprising an array of individually reprogrammable cells configured so that a selected number of said cells can be reprogrammed to cause at least two of said plurality of computing modules to operate in fault-tolerant mode.
Claim 3
Dependent Claim
20 words
Apparatus as in claim 1, wherein said at least one logic and switching device is a field-programmable gate array (FPGA).
Claim 4
Dependent Claim
15 words
Apparatus as in claim 1, wherein said means for storing is a read-only memory (ROM).
Claim 5
Independent Claim
86 words
A method for multiprocessing in hardware that compensates for faults, comprising the steps of: storing a plurality of configurations for a reconfigurable logic and switching device; partially reconfiguring said logic and switching device to accept at least one computation from at least one computing module; checking said at least one computation to determine whether it satisfies at least one test chosen from the group consisting of reasonableness and inexact voting; and transferring a result from said step of checking to said at least one computing module.
Claim 6
Independent Claim
86 words
A method for multiprocessing in hardware that compensates for faults, comprising the steps of: storing a plurality of configurations for a reconfigurable logic and switching device; partially reconfiguring said logic and switching device to accept at least one computation from at least one computing module; checking said at least one computation to determine whether it satisfies at least one test chosen from the group consisting of reasonableness and inexact voting; and transferring a result from said step of checking to said at least one computing module.
Claim 7
Dependent Claim
22 words
The method of claim 4, further comprising the step of initializing said reconfigurable logic and switching device after said step of storing.
Claim 8
Dependent Claim
26 words
The method of claim 5, wherein said step of initializing includes setting a counter to zero and incrementing said counter automatically to produce successive storage addresses.
Claim 9
Independent Claim
93 words
A method for multiprocessing that compensates for faults in hardware, comprising the steps of: storing a plurality of configurations for a reconfigurable logic and switching device; partially reconfiguring said logic and switching device to accept at least two computations from at least two computing modules; comparing said at least two computations; detecting an error when results from said step of comparing fail to satisfy at least one test chosen from the group consisting of reasonableness and inexact voting; and producing an error detection signal from said step of detecting, thereby indicating a fault.
Claim 10
Independent Claim
93 words
A method for multiprocessing that compensates for faults in hardware, comprising the steps of: storing a plurality of configurations for a reconfigurable logic and switching device; partially reconfiguring said logic and switching device to accept at least two computations from at least two computing modules; comparing said at least two computations; detecting an error when results from said step of comparing fail to satisfy at least one test chosen from the group consisting of reasonableness and inexact voting; and producing an error detection signal from said step of detecting, thereby indicating a fault.
Claim 11
Dependent Claim
22 words
The method of claim 7, further comprising the step of initializing said reconfigurable logic and switching device after said step of storing.
Claim 12
Dependent Claim
25 words
The method of claim 7, wherein said means for initializing includes a counter initially set to zero and incremented automatically to produce successive storage addresses.
Claim 13
Dependent Claim
47 words
The method of claim 7, wherein said step of comparing at least two computations compares at least three computations; and said step of detecting further comprises choosing as said error that at least one computation whose value is in a minority among said at least three computations.
Claim 14
Dependent Claim
48 words
The method of claim 7, wherein said step of comparing at least two computations compares at least three computations; and said step of detecting further comprises choosing as said error that at least one computation whose value is furthest from a majority of said at least three computations.
Claim 15
Dependent Claim
58 words
The method of claim 7, wherein said step of comparing at least two computations compares at least three computations; and said step of detecting further comprises choosing said error by voting, where voting comprises successively matching every pair of said at least three computations and choosing as said error that at least one computation that matches least often.
Claim 16
Dependent Claim
90 words
Apparatus for multiprocessing in hardware that compensates for faults, which comprises: means for storing a plurality of configurations for a reconfigurable logic and switching device; means for partially reconfiguring said logic and switching device to accept at least one computation from at least one computing module; means for checking said at least one computation to determine whether it satisfies at least one test chosen from the group consisting of reasonableness and inexact voting; and means for producing an error detection signal from said step of detecting, thereby indicating a fault.
Claim 17
Dependent Claim
90 words
Apparatus for multiprocessing in hardware that compensates for faults, which comprises: means for storing a plurality of configurations for a reconfigurable logic and switching device; means for partially reconfiguring said logic and switching device to accept at least one computation from at least one computing module; means for checking said at least one computation to determine whether it satisfies at least one test chosen from the group consisting of reasonableness and inexact voting; and means for producing an error detection signal from said step of detecting, thereby indicating a fault.
Claim 18
Dependent Claim
16 words
Apparatus as in claim 13, further comprising means for initializing said reconfigurable logic and switching unit.
Claim 19
Dependent Claim
25 words
Apparatus as in claim 14, wherein said means for initializing includes a counter initially set to zero and incremented automatically to produce successive storage addresses.
Claim 20
Dependent Claim
101 words
Apparatus for multiprocessing that compensates for faults in hardware, which comprises: means for storing a plurality of configurations for a reconfigurable logic and switching unit; means for partially reconfiguring said logic and switching unit to accept at least two computations from at least two computing modules; means for comparing said at least two computations; means for detecting an error when results from said means for comparing fail to satisfy at least one test chosen from the group consisting of reasonableness and inexact voting; and means for producing an error detection signal from said means for detecting, whereby a fault is indicated.
Claim 21
Dependent Claim
101 words
Apparatus for multiprocessing that compensates for faults in hardware, which comprises: means for storing a plurality of configurations for a reconfigurable logic and switching unit; means for partially reconfiguring said logic and switching unit to accept at least two computations from at least two computing modules; means for comparing said at least two computations; means for detecting an error when results from said means for comparing fail to satisfy at least one test chosen from the group consisting of reasonableness and inexact voting; and means for producing an error detection signal from said means for detecting, whereby a fault is indicated.
Claim 22
Dependent Claim
16 words
Apparatus as in claim 16, further comprising means for initializing said reconfigurable logic and switching device.
Claim 23
Dependent Claim
25 words
Apparatus as in claim 17, wherein said means for initializing includes a counter initially set to zero and incremented automatically to produce successive storage addresses.
Claim 24
Dependent Claim
19 words
Apparatus as in claim 16, wherein said means for comparing at least two computations compares at least three computations.
Claim 25
Dependent Claim
35 words
Apparatus as in claim 19, wherein said means for detecting is effective for choosing as said error that at least one computation whose value is furthest from a majority of said at least three computations.
Claim 26
Dependent Claim
45 words
Apparatus as in claim 19, wherein said means for detecting is effective for choosing said error by voting, where voting comprises successively matching every pair of said at least three computations and choosing as said error that at least one computation that matches least often.
Claim 27
Independent Claim
79 words
A method for reducing the duration of partial reconfiguration of a dynamically reconfigurable logic and switching device, which comprises the steps of: selecting, within said logic and switching device, cells that accept n inputs from N computing modules, where n≦N; programming said selected cells to choose a majority from among said n inputs by a one of inexact majority voting and a reasonableness check, whereby only a minimum number of cells in said logic and switching device are reprogrammed.
Claim 28
Independent Claim
79 words
A method for reducing the duration of partial reconfiguration of a dynamically reconfigurable logic and switching device, which comprises the steps of: selecting, within said logic and switching device, cells that accept n inputs from N computing modules, where n≦N; programming said selected cells to choose a majority from among said n inputs by a one of inexact majority voting and a reasonableness check, whereby only a minimum number of cells in said logic and switching device are reprogrammed.
Claim 29
Dependent Claim
46 words
The method of claim 22, comprising the additional steps of: pairwise comparing of said majority with said n inputs; determining from said step of pairwise comparing which ones of said n inputs disagree with said majority by a predetermined amount; and flagging said ones as errors.
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) | 2002-08-02 | 2003-02-01 | 2003-08-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-02 | 2007-02-01 | 2007-08-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-02 | 2011-02-01 | 2011-08-03 | $7700.00 | Window Closed / Lapsed |