Method for creating circuit redundancy in programmable logic devices

• US 6,526,559 B2
• Filed: 04/13/2001
• Issued: 02/25/2003
• Est. Priority Date: 04/13/2001
• Status: Expired due to Fees

• Current Assignee: SRA International, Inc. (General Dynamics Corporation)
• Original Assignee: Interface & Control Systems, Inc. (General Dynamics Corporation)
• Inventors: Krueger, Robert O., Schiefele, Walter P.
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US09/833,712
• Publication Number:
  US 20020157071A1
• Time in Patent Office: 683 Days
• Field of Search: 716/1-18, 326/37-51, 326/101-103, 713/1-100, 710/8-14
• US Class Current: 326/11
• CPC Class Codes: G06F 11/1497 Details of time redundant execution on a single processing unit
• CPC Class Codes: G06F 11/181 Eliminating the failing redundant component
• CPC Class Codes: G06F 11/183 by voting, the voting not being performed by the redundant components
• CPC Class Codes: H03K 19/17748 Structural details of configuration resources
• CPC Class Codes: H03K 19/17752 for hot reconfiguration
• CPC Class Codes: H03K 19/17756 for partial configuration or partial reconfiguration
• CPC Class Codes: H03K 19/17764 for reliability

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.

Claims

1. 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.

2. The method of claim 1, wherein said structural elements include configurable logic units of said programmable logic device.

3. The method of claim 2, wherein said structural elements further include structural elements within each of said configurable logic units.

4. 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.

5. The method of claim 1, wherein said structural elements include interconnections formed on said programmable logic device.

6. The method of claim 1, wherein said structural elements include I/O units of said programmable logic device.

7. 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.

8. 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.

9. 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.

10. 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.

11. The method of claim 10, further comprising the step of:

identifying time margins for said plurality of time slices.

12. 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.

13. 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.

14. 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.

15. 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.

16. The method of claim 1, wherein said programmable logic device includes a field programmable gate array.

17. 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.

18. The method of claim 17, wherein said N≧

1.

19. 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.

20. The claim 17, wherein said time slices have a duration in a range of microseconds.

21. The method of claim 17, wherein said structural elements include configurable logic units of said programmable logic device.

22. The method of claim 21, wherein said structural elements further include structural elements within each said configurable logic unit.

23. 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.

24. The method of claim 22, wherein said structural elements further include interconnections formed on said programmable logic device.

25. The method of claim 17, wherein said structural elements include I/O units of said programmable logic device.

26. 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.

27. 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.

28. 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.

29. The programmable logic device of claim 27, wherein said the least overlap is substantially zero.

30. 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.

31. 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.

32. The programmable logic device of claim 31, wherein said chip further contains a section of non-reconfigurable structural elements.

33. The programmable logic device of claim 27, wherein said configurable structural elements include logic units.

34. The programmable logic device of claim 33, wherein said configurable structural elements further include configurable routing structure.

35. The programmable logic device of claim 33, wherein said configurable structural elements further include structural elements within each of said logic units.

36. 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.

37. 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.

38. The programmable logic device of claim 37, wherein said identifying means are further operationally coupled to said memory means.

39. 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.

40. 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.

41. 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.

42. 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.

43. 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.

44. 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.

45. The programmable logic device of claim 27, including a field programmable gate array.

46. 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.

47. 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.