US6526559B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for creating circuit redundancy in programmable logic devices
Assignee: SRA International Inc
•
Filing: 2001-04-13
•
Granted: 2003-02-25
•
Expires: 2021-04-13
Abstract
Abstract In a field programmable gate array (FPGA) allowing dynamic reconfiguration in time multiplexing fashion, duplicate copies are configured in a time multiplexing manner which are functionally identical to a primary circuit specified for a predetermined FPGA's application. The primary and duplicate circuits are interrogated by a voting circuit which determines the existence of a faulted circuit in order to eliminate the faulted circuit from the operation of the FPGA. In this manner, without physical addition of redundant circuits, fault tolerancy for the FPGA is provided to minimize the cost, weight, volume, heat and energy associated issues of conventional redundance techniques.
Inventors
- 👤 Walter P. Schiefele
- 👤 Robert O. Krueger
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:33
CPC Classifications
H; H03; H03K; H03K19/00; H03K19/02; H03K19/173; H03K19/177; H03K19/17748; G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1497; G06F11/16; G06F11/18; G06F11/181; G06F11/183; H03K19/17752; H03K19/17756; H03K19/17764
Claims Analysis
Total Claims: 51
Claim 1
Independent Claim
122 words
A method for creating circuit redundancy in programmable logic devices, comprising the steps of: (a) establishing a programmable logic device containing a plurality of structural elements, (b) configuring a first portion of said plurality of structural elements at a first time slice into a primary circuit for a predetermined application, (c) identifying at least a second portion of said plurality of structural elements having the least overlap with the structural elements of said first portion thereof, (d) configuring said structural elements at a second time slice of said at least second portion thereof into a duplicate circuit substantially functionally identical with respect to said primary circuit, and (e) comparing performance of said primary circuit and said duplicate circuit in a time-multiplexing fashion.
Claim 2
Independent Claim
122 words
A method for creating circuit redundancy in programmable logic devices, comprising the steps of: (a) establishing a programmable logic device containing a plurality of structural elements, (b) configuring a first portion of said plurality of structural elements at a first time slice into a primary circuit for a predetermined application, (c) identifying at least a second portion of said plurality of structural elements having the least overlap with the structural elements of said first portion thereof, (d) configuring said structural elements at a second time slice of said at least second portion thereof into a duplicate circuit substantially functionally identical with respect to said primary circuit, and (e) comparing performance of said primary circuit and said duplicate circuit in a time-multiplexing fashion.
Claim 3
Dependent Claim
19 words
The method of claim 1 , wherein said structural elements include configurable logic units of said programmable logic device.
Claim 4
Dependent Claim
21 words
The method of claim 2 , wherein said structural elements further include structural elements within each of said configurable logic units.
Claim 5
Dependent Claim
43 words
The method of claim 3 , further comprising the step of: in said step (c), including into said at least one second portion of the structural elements unoccupied, configurable logic units, and, upon exhaustion thereof, unoccupied structural elements within occupied configurable logic units.
Claim 6
Dependent Claim
18 words
The method of claim 1 , wherein said structural elements include interconnections formed on said programmable logic device.
Claim 7
Dependent Claim
18 words
The method of claim 1 , wherein said structural elements include I/O units of said programmable logic device.
Claim 8
Dependent Claim
50 words
The method of claim 1 , wherein said first portion of said plurality of structural elements includes one configurable logic unit, and wherein said at least second portion of said plurality of structural elements includes at least a further configurable logic unit spatially separated from said one configurable logic unit.
Claim 9
Dependent Claim
39 words
The method of claim 1 , further comprising the step of: in said step (c), identifying said at least one second portion of the structural elements as linearly displaced with regard to said first portion of the structural elements.
Claim 10
Dependent Claim
39 words
The method of claim 1 , further comprising the step of: in said step (c), identifying said at least a second portion of the structural elements as spatially rotated with regard to said first portion of the structural elements.
Claim 11
Dependent Claim
62 words
The method of claim 1 , further comprising the steps of: identifying a plurality of time slices, identifying a number of said at least one second portions of unoccupied structural elements, and configuring each of said number of at least one second portions of the unoccupied structural elements into a duplicate circuit at a respective one of said plurality of time slices.
Claim 12
Dependent Claim
20 words
The method of claim 10 , further comprising the step of: identifying time margins for said plurality of time slices.
Claim 13
Dependent Claim
32 words
The method of claim 11 , further comprising the step of determining a feasibility of said number of said second portions and said time margins for said plurality of the time slices.
Claim 14
Dependent Claim
43 words
The method of claim 1 , further comprising the step of: excluding from operation a defective one of said primary circuit and said duplicate circuit, upon detecting in said step (e) a disagreement in performance of said primary circuit and said duplicate circuit.
Claim 15
Dependent Claim
29 words
The method of claim 13 , further comprising the step of: upon completing the steps (a)-(e) for said predetermined application, repeating said steps (a)-(e) for a different predetermined application.
Claim 16
Dependent Claim
31 words
The method of claim 1 , wherein said overlap between the structural elements included into said primary circuit and the structural elements included into said duplicate circuit is substantially zero overlap.
Claim 17
Dependent Claim
17 words
The method of claim 1 , wherein said programmable logic device includes a field programmable gate array.
Claim 18
Independent Claim
133 words
A method for creating fault tolerance in programmable logic devices, comprising the steps of: configuring at a first time slice, a primary group of a plurality of structural elements of a programmable logic device into a primary circuit for a predetermined application; defining a plurality of sequential time slices following said first time slice; identifying in each of said time slices a respective N th duplicate group of said plurality of the structural elements; configuring said respective duplicate group of the structural elements into a duplicate circuit substantially functionally identical to said primary circuit; comparing performance of said primary circuit and said duplicate circuit in time-multiplexing fashion; and excluding at least one of said primary circuit and said duplicate circuit from operation subsequent to disagreement in performance being detected in said comparing step.
Claim 19
Independent Claim
133 words
A method for creating fault tolerance in programmable logic devices, comprising the steps of: configuring at a first time slice, a primary group of a plurality of structural elements of a programmable logic device into a primary circuit for a predetermined application; defining a plurality of sequential time slices following said first time slice; identifying in each of said time slices a respective N th duplicate group of said plurality of the structural elements; configuring said respective duplicate group of the structural elements into a duplicate circuit substantially functionally identical to said primary circuit; comparing performance of said primary circuit and said duplicate circuit in time-multiplexing fashion; and excluding at least one of said primary circuit and said duplicate circuit from operation subsequent to disagreement in performance being detected in said comparing step.
Claim 20
Dependent Claim
9 words
The method of claim 17 , wherein said N≧1.
Claim 21
Dependent Claim
36 words
The method of claim 17 , wherein said N th duplicate group of said plurality of the structural elements has the least spatial overlap with said primary group and with any of (N−1) th duplicate groups.
Claim 22
Dependent Claim
16 words
The claim 17 , wherein said time slices have a duration in a range of microseconds.
Claim 23
Dependent Claim
19 words
The method of claim 17 , wherein said structural elements include configurable logic units of said programmable logic device.
Claim 24
Dependent Claim
20 words
The method of claim 21 , wherein said structural elements further include structural elements within each said configurable logic unit.
Claim 25
Dependent Claim
42 words
The method of claim 22 , further comprising the steps of: identifying said respective duplicate group of the structural elements by a) selecting unoccupied configurable logic units; and upon exhaustion thereof, by b) selecting unoccupied structural elements within occupied configurable logic units.
Claim 26
Dependent Claim
19 words
The method of claim 22 , wherein said structural elements further include interconnections formed on said programmable logic device.
Claim 27
Dependent Claim
18 words
The method of claim 17 , wherein said structural elements include I/O units of said programmable logic device.
Claim 28
Dependent Claim
55 words
The method of claim 17 , further comprising the steps of: defining a plurality of sequential application cycles, each cycle corresponding to a respective application, in each of said application cycles, configuring a respective primary circuit and N duplicate circuits substantially identical functionally to said respective primary circuit, and comparing performance thereof in time-multiplexing fashion.
Claim 29
Dependent Claim
148 words
A programmable logic device with fault tolerance, comprising: a plurality of configurable structural elements; means for defining a plurality of time slices, configuration means containing configuration data and coupled to said configurable structural elements for: (a) configuring a primary group thereof into a primary circuit in a 1 st time slice of said plurality of time slices, and (b) configuring an N th duplicate group of the configurable structural elements into a duplicate circuit substantially functionally identical to said primary circuit in a (N+1) th time slice of said plurality of time slices, wherein N≧1; means for identifying said N th duplicate group of the configurable structural elements having the least overlap with the configurable structural elements occupied in said primary circuit and in any of (N−1) duplicate circuits; and voting means for interrogating said primary circuit and said duplicate circuits in time-multiplexing fashion for comparing performance thereof.
Claim 30
Dependent Claim
148 words
A programmable logic device with fault tolerance, comprising: a plurality of configurable structural elements; means for defining a plurality of time slices, configuration means containing configuration data and coupled to said configurable structural elements for: (a) configuring a primary group thereof into a primary circuit in a 1 st time slice of said plurality of time slices, and (b) configuring an N th duplicate group of the configurable structural elements into a duplicate circuit substantially functionally identical to said primary circuit in a (N+1) th time slice of said plurality of time slices, wherein N≧1; means for identifying said N th duplicate group of the configurable structural elements having the least overlap with the configurable structural elements occupied in said primary circuit and in any of (N−1) duplicate circuits; and voting means for interrogating said primary circuit and said duplicate circuits in time-multiplexing fashion for comparing performance thereof.
Claim 31
Dependent Claim
27 words
The programmable logic device of claim 27 , wherein said identifying means are adapted for off-line searching of said N th duplicate group of the structural elements.
Claim 32
Dependent Claim
16 words
The programmable logic device of claim 27 , wherein said the least overlap is substantially zero.
Claim 33
Dependent Claim
43 words
The programmable logic device of claim 27 , further comprising means for excluding from operation at least one defective of said primary circuit and said duplicate circuits once disagreement in performance thereof has been detected, and said voting means identified the defective circuit.
Claim 34
Dependent Claim
49 words
The programmable logic device of claim 27 , further comprising a chip containing said plurality of configurable structural elements, said time slices defining means, said configuration means, and said means for identifying said duplicate groups of the configurable structural elements, wherein said voting means is located off said chip.
Claim 35
Dependent Claim
19 words
The programmable logic device of claim 31 , wherein said chip further contains a section of non-reconfigurable structural elements.
Claim 36
Dependent Claim
16 words
The programmable logic device of claim 27 , wherein said configurable structural elements include logic units.
Claim 37
Dependent Claim
18 words
The programmable logic device of claim 33 , wherein said configurable structural elements further include configurable routing structure.
Claim 38
Dependent Claim
23 words
The programmable logic device of claim 33 , wherein said configurable structural elements further include structural elements within each of said logic units.
Claim 39
Dependent Claim
37 words
The programmable logic device of claim 35 , wherein said duplicate group identifying means further comprises means for initially searching for unoccupied logic units, and, upon exhaustion thereof, searching for unoccupied structural elements within occupied logic units.
Claim 40
Dependent Claim
44 words
The programmable logic device of claim 27 , wherein said configuration means comprises memory means including a plurality of memory slices, each memory slice containing respective configuration data specifying a function to be performed by said programmable logic device at a predetermined time period.
Claim 41
Dependent Claim
20 words
The programmable logic device of claim 37 , wherein said identifying means are further operationally coupled to said memory means.
Claim 42
Dependent Claim
27 words
The programmable logic device of claim 37 , further comprising sequencer means coupled to said memory means for actuating said memory slices in a predetermined time-multiplexing fashion.
Claim 43
Dependent Claim
48 words
The programmable logic device of claim 39 , wherein said sequencer means actuates in sequence a next memory slice of said memory means upon said primary circuit and said duplicate circuits having been created and interrogated by said voting means during operation of a previous actuated memory slice.
Claim 44
Dependent Claim
70 words
The programmable logic device of claim 39 , wherein during actuation of each of said plurality of the memory slices, said configuration memory means configure a respective primary group of the configurable structural elements into a primary circuit for performing a function specified in said actuated memory slice, and further configure in non-overlapping fashion a plurality of respective duplicate groups into duplicate circuits functionally identical to said respective primary circuit.
Claim 45
Dependent Claim
25 words
The programmable logic device of claim 27 , further comprising means for identifying a number of said duplicate circuits to be configured in time-multiplexing fashion.
Claim 46
Dependent Claim
26 words
The programmable logic device of claim 42 , further comprising means for identifying timing requirements for said programmable logic device for a function to be performed.
Claim 47
Dependent Claim
27 words
The programmable logic device of claim 43 , further comprising means for determining feasibility of said number of said duplicate circuits in view of said timing requirements.
Claim 48
Dependent Claim
14 words
The programmable logic device of claim 27 , including a field programmable gate array.
Claim 49
Independent Claim
72 words
A method for creating circuit redundancy in field programmable gate array (FPGA), comprising the steps of: in a FPGA containing a plurality of configurable structural elements, a) defining a plurality of time slices, and b) configuring, in a time-multiplexing fashion, a plurality of functionally substantially identical circuits from the structural elements of said FPGA having the least overlap with the structural elements occupied in any previous of said plurality of time slices.
Claim 50
Independent Claim
72 words
A method for creating circuit redundancy in field programmable gate array (FPGA), comprising the steps of: in a FPGA containing a plurality of configurable structural elements, a) defining a plurality of time slices, and b) configuring, in a time-multiplexing fashion, a plurality of functionally substantially identical circuits from the structural elements of said FPGA having the least overlap with the structural elements occupied in any previous of said plurality of time slices.
Claim 51
Dependent Claim
31 words
The method of claim 46 , further comprising the steps of: providing voting means, and interrogating and comparing performance of said plurality of functionally identical circuits to detect a defective circuit.
References Cited (Backward Citations)
US5756981A
Cited
US5838584A
Cited
US5745268A
Cited
US5959881A
Cited
US5583450A
Cited
US5701441A
Cited
US5646545A
Cited
US5629637A
Cited
US5761483A
Cited
US5825662A
Cited
US5838954A
Cited
US5600263A
Cited
US6263430B1
Cited
US5978260A
Cited
US6480954B2
Cited
US20020010853A1
Cited
US6072994A
Cited
US5654997A
Cited
US6105105A
Cited
US6102964A
Cited
US6091258A
Cited
US6080204A
Cited
US6034538A
Cited
US5995874A
Cited
US6058330A
Cited
US6009542A
Cited
US6104211A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-02-24 | 2006-08-26 | 2007-02-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-02-24 | 2010-08-26 | 2011-02-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-02-24 | 2014-08-26 | 2015-02-25 | $7700.00 | Window Closed / Lapsed |