Automated circuit triplication method and system

Patent metadata

Field	Value
Publication number	US-9244783-B2
Application number	US-201414308471-A
Country	US
Kind code	B2
Filing date	Jun 18, 2014
Priority date	Jun 18, 2013
Publication date	Jan 26, 2016
Grant date	Jan 26, 2016

Abstract

In one general aspect, a non-transitory computer-readable storage medium can be configured to store instructions that when executed cause a processor to perform a process. The process can include defining a plurality of subsets from a representation of a circuit, and rank-ordering each subset from the plurality of subsets. The process can also include selecting at least one of the subsets for triplication based on the rank-ordering and a triplication condition.

First claim

What is claimed is:

1. A non-transitory computer-readable storage medium storing instructions that when executed cause a processor to perform a process, the process comprising:
receiving a representation of a circuit including a plurality of elements and a plurality of relationships;
defining a first subset of the plurality of elements and a second subset of the plurality of elements based on an analysis of the representation of the circuit;
assigning a first rank to the first subset of the plurality of elements, and a second rank to the second subset of the plurality of elements;
receiving a triplication condition for triggering redundancy within the circuit; and
selecting at least one of the first subset of the plurality of elements or the second subset of the plurality of elements for redundancy based on the first rank, the second rank, and based on the triplication condition.

2. The computer-readable storage medium of claim 1 , wherein the analysis is an analysis of a plurality of cycles within the representation of the circuit.

3. The non-transitory computer-readable storage medium of claim 1 , wherein the assigning of the first rank is based on a size of the first subset of the plurality of elements.

4. The non-transitory computer-readable storage medium of claim 1 , wherein the assigning of the first rank and the second rank is based on fan-out.

5. The non-transitory computer-readable storage medium of claim 1 , wherein the assigning of the first rank and the second rank is based on a priority of a component from the first subset of the plurality of elements relative to a priority of a component from the second subset of the plurality of elements.

6. The non-transitory computer-readable storage medium of claim 1 , wherein the triplication condition represents a triplication limit.

7. The non-transitory computer-readable storage medium of claim 1 , wherein the selecting includes selecting the first subset of the plurality of elements,
the process further comprising:
triplicating a portion of the first subset of the plurality of elements based on the triplication condition.

8. The non-transitory computer-readable storage medium of claim 1 , wherein the selecting includes selecting the first subset of the plurality of elements,
the process further comprising:
subdividing the first subset of the plurality of elements into a first portion and a second portion based on the triplication condition; and
excluding the first portion of the first subset of the plurality of elements from redundancy.

9. The non-transitory computer-readable storage medium of claim 1 , wherein the selecting includes selecting the first subset of the plurality of elements,
the process further comprising:
excluding the second subset of the plurality of elements from redundancy based on the first rank having a priority greater than a priority of the second rank.

10. The non-transitory computer-readable storage medium of claim 1 , wherein the first subset of the plurality of elements is mutually exclusive from the second subset of the plurality of elements.

11. The non-transitory computer-readable storage medium of claim 1 , wherein the defining includes defining based on strongly connected component (SCC) decomposition.

12. The non-transitory computer-readable storage medium of claim 1 , wherein the representation of the circuit is derived from a netlist, the plurality of elements correspond with a plurality of components of the circuit, the plurality of relationships represent a plurality of directional connections between the plurality of components of the circuit.

13. The non-transitory computer-readable storage medium of claim 1 , wherein the redundancy includes partial redundancy.

14. The non-transitory computer-readable storage medium of claim 1 , wherein the redundancy includes partial triple modular redundancy.

15. A non-transitory computer-readable storage medium storing instructions that when executed cause a processor to perform a process, the process comprising:
defining a plurality of subsets from a representation of a circuit;
rank-ordering each subset from the plurality of subsets; and
selecting at least one of the subsets for redundancy based on the rank-ordering and a triplication condition, the triplication condition configured to trigger the redundancy within the circuit.

16. The non-transitory computer-readable storage medium of claim 15 , wherein the defining is based on an analysis of a plurality of cycles within the representation of the circuit.

17. The non-transitory computer-readable storage medium of claim 15 , wherein the representation of the circuit includes an element that represents a behavior of a circuit.

18. The non-transitory computer-readable storage medium of claim 15 , wherein the plurality of subsets from the representation of the circuit include a plurality of elements and a plurality of relationships.

19. The non-transitory computer-readable storage medium of claim 15 , wherein the ranking-ordering includes rank-ordering based on a plurality of ranking rules.

20. A non-transitory computer-readable storage medium storing instructions that when executed cause a processor to perform a process, the process comprising:
defining a plurality of subsets from a representation of a circuit including a plurality of elements and a plurality of relationships;
rank-ordering each subset from the plurality of subsets; and
iteratively selecting subsets from the plurality of subsets for redundancy based on the rank-ordering until a triplication condition is satisfied, the triplication condition configured to trigger redundancy within the circuit.

21. The non-transitory computer-readable storage medium of claim 20 , wherein the ranking-ordering includes rank-ordering based on a plurality of ranking rules.

22. The non-transitory computer-readable storage medium of claim 20 , wherein the iteratively selecting subsets includes iteratively selecting a portion of at least one of the subsets to satisfy the triplication condition.

Assignees

• Univ Brigham Young

Inventors

• Wirthlin Michael J

Classifications

• H03K19/00392

  by circuit redundancy (H03K19/0075 takes precedence) · CPC title

• G06F30/34 Primary

  for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD] · CPC title

• G06F11/1608 Primary

  Error detection by comparing the output signals of redundant hardware (G06F11/1629, G06F11/1666 take precedence; error detection or correction in information storage based on relative movement between record carrier and transducer G11B20/18; checking static stores for correct operation G11C29/00; for logic circuits H03K19/003, H03K19/007; for pulse counters or frequency dividers H03K21/40) · CPC title

• H03K19/23

  Majority or minority circuits, i.e. giving output having the state of the majority or the minority of the inputs · CPC title