1372 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMSI: REGULAR PAPERS, VOL. 58, NO.

6, JUNE 2011

In-Place FPGA Retiming for Mitigation of Variational

Single-Event Transient Faults
Wenyao Xu, Student Member, IEEE, Jia Wang, Member, IEEE, Yu Hu, Member, IEEE,
Ju-Yueh Lee, Student Member, IEEE, Fang Gong, Student Member, IEEE, Lei He, Senior Member, IEEE, and
Majid Sarrafzadeh, Fellow, IEEE

AbstractFor anti-fuse or flash-memory-based field-pro- SETs becomes increasingly pronounced for high-performance
grammable gate arrays (FPGAs), single-event transient (SET)-in- FPGA applications [21]. In this paper, we focus on SET mit-
duced faults are significantly more pronounced than single-event igation on anti-fuse or flash-based FPGAs [22] where SEUs
upsets (SEUs). While most existing work studies SEU, this paper
proposes a retiming algorithm for mitigating variational SETs are less significant because the anti-fuse or flash-memory in
(i.e., SETs with different durations and strengths). Considering them have virtually no SEUs for configuration bits, which is
the reshaping effect of an SET pulse caused by broadening and the primary soft error source in SRAM-based FPGAs [23].
attenuation during its propagation, SET-aware retiming (SaR) In the past decade, various SEU mitigation techniques
redistributes combinational paths via postlayout retiming and for FPGAs have been studied [23][34]. [35] uses retiming
minimizes the possibility that an SET pulse is latched. The SaR
problem is formulated as an integer linear programming (ILP) technology to harden the circuit for SEU as well as improve
problem and solved efficiently by a progressive ILP approach. testability. However, because of the inherent difference be-
In contrast to existing SET-mitigation techniques, the proposed tween SEU and SET-induced faults, specific techniques for
SaR does not change the FPGA architecture or the layout of an SET mitigation are needed. For example, one SET may cause
FPGA application. Instead, it reconfigures the connection between multiple consequent faults, which may invalidate triple mod-
a flip-flop and an LUT within a programmable logic block. Ex-
perimental results show that SaR increases mean-time-to-failure ular redundancy (TMR), one of the most popular fault-tolerant
(MTTF) by 78% for variational SETs with a 10-min runtime limit techniques for FPGAs. Most of the existing SET mitiga-
while preserving the clock frequency on ISCAS89 benchmark cir- tion techniquese.g., dual interlocked cells (DICE) [29],
cuits. To the best of our knowledge, this paper is the first in-depth temporally redundant latches [36], and register hardening
study on FPGA retiming for SET mitigation. or selections [37], [38]use modified latching structures to
Index TermsField-programmable gate arrays (FPGAs), re- prevent the propagated SET from being latched. In addition,
timing, single-event transients. device and architecture cooptimization [3] has been studied.
Unfortunately, the above techniques require modification of
FPGA architectures and may introduce area, performance
I. INTRODUCTION
and power overhead. Moreover, strikes by ions with different
energies may result in different signal pulse shapes (called

A GGRESSIVE scaling of CMOS technology makes variational SETs in this paper) and the tolerance of a wide
field-programmable gate arrays (FPGAs) increasingly spectrum of ion strikes therefore requires significantly more
susceptible to single-event effects. Specifically, the heavy ions overhead. For example, to deal with variational SETs using the
in cosmic rays may cause single-event upsets (SEUs) in data transistor sizing technique, nearly the 50% of gates need to be
latches and configuration bits. In addition, these ion strikes sized up, resulting in an overhead of roughly 90%, 77%, and
result in single-event transients (SETs) in both combinational 7% for area, power, and delay, respectively. for ASIC [39].
logic and global clock lines, which can alter the functionality No in-depth techniques for dealing with variational SETs in
of a circuit. The effect of SET-induced faults is frequency-de- FPGAs has been presented.
pendent [1][20], i.e., a higher frequency leads to a higher This paper proposes an SET-mitigation technique, which we
probability of an SET-induced fault. Therefore, the impact of refer to as SET-aware retiming or SaR, that is complementary
to existing methods. Performed in the postlayout CAD stage for
FPGA-based applications, our SaR redistributes combinational
Manuscript received February 03, 2010; revised July 24, 2010 and October
19, 2010; accepted October 23, 2010. Date of publication May 19, 2011; date of paths and minimizes the possibility of an SET-induced pulse
current version May 27, 2011. This paper was partially funded by a UC MICRO being latched. The key enabler of SaR is to build a link between
grant sponsored by Actel. This paper was recommended by Associate Editor D.
the following two factors: a) circuit topology and b) broadening
Chen.
W. Xu, J. Lee, F. Gong, L. He and M. Sarrafzadeh are with Electrical En- and attenuation effects during the propagation of an SET-in-
gineering Department, University of California, Los Angeles, CA 90095 USA duced signal pulse along combinational paths. A necessary and
(e-mail: lhe@ee.ucla.edu).
sufficient condition is presented to characterize the SET-im-
J. Wang is with Electrical and Computer Engineering, Illinois Institute of
Technology, IL 60298 USA. mune circuit topology. Based on this condition, SaR is formu-
Y. Hu is with Electrical and Computer Engineering, University of Alberta, lated as an integer linear programming (ILP) problem solved ef-
Edmonton, AB T6C 2V4, Canada.
ficiently by a progressive ILP approach. We also consider vari-
Color versions of one or more of the figures in this paper are available online
at http://ieeexplore.ieee.org. ational SET pulses with different initial shapes. Note that most
Digital Object Identifier 10.1109/TCSI.2010.2094370 of the existing retiming algorithms only minimize clock period

1549-8328/$26.00 2011 IEEE

XU et al.: IN-PLACE FPGA RETIMING FOR MITIGATION OF VARIATIONAL SINGLE-EVENT TRANSIENT FAULTS 1373

and [40] considers the constraints inside the range of the shortest
and longest paths to satisfy the setup and hold time. These ex-
isting retiming algorithms cannot be applied for variational SET
mitigation, however, since this problem essentially maximizes
the number of paths outside the range defined by the shortest
and longest paths.
Compared with existing SET mitigation techniques, SaR has
a number of unique features. First, it does not require modi-
fication of the FPGA architecture since it is performed at the
compilation time from an FPGA-based design. Also, SaR does
not change the layout except reconfiguring the connection be-
tween LUTs and FFs in a programmable logic block (PLB),
which leads to faster design closure. Moreover, SaR can handle
variational SET-induced pulses and obtain the solution with
the highest yield rate under these pulses. In experiments using
Fig. 1. Programmable logic block in FPGAs.
ISCAS89 benchmarks [41] under 90 nm process technology,
our proposed SaR increases mean-time-to-failure (MTTF) by
78% for variational SETs with a 10-min runtime limit while pre-
serving the minimal clock period.
The remainder of this paper is organized as follows. Section II
presents background and preliminaries. Section III formulates Fig. 2. Physical constraints in the FPGA-based circuit.
the SaR problem. Section IV describes the SaR algorithm, and
Section V extends the algorithm to handle variational pulses re-
sulting from ion strikes with different energies. Experimental the fanout edges of the node to its fanin edges. The number of
results are shown in Section VI, and the paper concludes in FFs after retiming is as follows:
Section VII.

(1)
II. BACKGROUND AND PRELIMINARIES
should be nonnegative, i.e.,

A. FPGA Architecture (2)

Our proposed SaR is performed after placement and routing. With the FPGA architecture in Fig. 1, we can model the
For simplicity of presentation, we assume that our algorithm postlayout circuit as in Fig. 2, where a transmission gate (TG)
targets an FPGA architecture similar to emerging FPGAs [22], models the interconnect between PLBs and has the delay and
[42], [43]. This FPGA is an array of PLBs. A PLB has a combi- reshaping abilities of the interconnect. There are two kinds of
national cell that contains a look-up table (LUT) and a register edges in such a retiming graph. One is the interedge between
cell that contains two multiplexes (MUXes) and one flip-flop PLBs and TGs; weight on interedges is always zero. The
(FF). The configuration bits in the register cell decide if a signal edge between an LUT and an MUX is called an intra-edge,
goes through the FF. Specifically, if the bit is 0, the signal by- the weight of which can be zero or one; is determined
passes FF; if the bit is 1, FF is included in the data path. Note by the value of MUXs configuration bit. Therefore, retiming
that this kind of dual-put PLBs structure enables the case which a sequential circuit under such a retiming graph reassigns the
requires register-output and non register-output simultaneously. configuration values of MUXes to change the weight on the
Therefore, it is not necessary to change the design layout during intraedges without changing the placement and global routing
SaR, and it can be applied to other similar FPGA architectures. (outside an PLB) after retiming.
Let denote a path from node to node . For the
B. In-Place Retiming Graph for FPGAs simplicity of presentation, we refer to the path directly as if
and are irrelevant or obvious from the context. Let be
A sequential circuit is represented by a directed graph the number of FFs along the path . For any pair of nodes and
, in which a node denotes a combinational , let be the minimum number of FFs along any path
cell such as LUT, MUX or transmission gate (TG), and an from to . We have
edge denotes an interconnect from node to node
. Each edge is associated with a nonnegative integer weight (3)
, which represents the number of FFs on the edge.
Using notations similar to Leiserson and Saxe [44], a retiming A path is called a critical path iff .
is a relocation of FFs in circuits, given by a labeling of vertices A path is critical in the retimed circuit iff , the
, which represents the number of FFs moved from number of FFs along after retiming, is equal to , the
1374 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMSI: REGULAR PAPERS, VOL. 58, NO. 6, JUNE 2011

Note that we apply the worst case analysis with respect to

logic as we neglect logic masking effect [47] for SETs in com-
binational circuits.

III. PROBLEM FORMULATION

In this section, we introduce two problem formulations based
on the above FPGA architecture and SET modeling.
Definition 1: Given an SET pulse and a circuit, path ,
which consists of a subpath and an edge , is called
a faulty path iff the following conditions are satisfied.
Fig. 3. Electrical and timing masking. 1) , i.e., there are no FFs in path .
2) Condition (6) is satisfied for path .
minimum number of FFs along any path from to after re- 3) , i.e., there is an FF in edge .
timing. A critical path remains critical after retiming. It is easy to verify that an SET pulse initiated at node can be
Since there is no more than one FF on any edge and there captured at an FF in the fanout of node after its propagation
is always a nonnegative number of FFs along any path after along path , if the three conditions in Definition 1 are
retiming, a retiming is valid iff the following constraint is satisfied.
satisfied: Definition 2: Node is a faulty node iff there is a faulty path
starting from node .
(4) Based on Definition 2, an SET pulse initiated at a faulty node
can be captured by at least one FF.
Also the following lemma holds: Assuming that all SET pulses have the same initial dimen-
Lemma 1: For any pair of nodes and , and any fanout edge sion, the SET-aware retiming problem is formulated as follows:
of , the following condition holds for any valid retiming Formulation 1: (Retiming for Deterministic SET): Given a
: retiming graph , SET pulses all with the same initial du-
ration and same strength , minimum duration and strength
for a pulse to be captured by an FF, and a clock pe-
riod constraint , an SET-aware retiming finds a retiming which
minimizes the number of faulty paths (or the number of faulty
C. SET Modeling
nodes) for a clock period no longer than .
To model the effect of an SET pulse propagating through a In reality, different SET pulses may have various dimensions
circuit cell, each node is associated with a pair of shaping pa- due to the energy difference of the particle strikes. Therefore, the
rameters . Specifically, due to the propagation-in- SET-aware retiming considering variational SET dimensions
duced pulse broadening (PIPB) effect [45] and the electrical at- can be formulated as follows:
tenuation effect [46] in CMOS combinational circuits, an SET Formulation 2: (Retiming for Variational SETs): Given a
pulse with duration and strength is reshaped to the fol- retiming graph , a set of SET pulses with different
lowing duration and strength after passing gate : initial durations, strengths and probabilities of occurrence
, minimum dura-
tion and strength for a pulse to be captured by an FF,
(5) and a clock period constraint , an SET-aware retiming finds
a retiming which minimizes the number of faulty paths (or the
If the duration or strength of SET is smaller than the threshold number of faulty nodes) with a clock period within .
values determined by the electrical characteristics of FFs, then Fig. 4 shows an example to illustrate how retiming can reduce
this pulse is not latched by any FF. For example, as shown in the number of faulty paths. For the simplicity of presentation,
Fig. 3, neither SET1 nor SET2 can be latched since the duration suppose each combinational block has the same
of SET1 is too short (i.e., timing masking [47]) and the strength and the same delay; also, each FF has the same . In
of SET2 is too weak (i.e., electrical masking [47]). addition, suppose SET pulses are identical on each combina-
Suppose an SET pulse occurs at node with initial duration tional block (i.e., the same characteristics and probability of oc-
and strength . Let and be the minimum du- currence) and can be captured iff it is initiated at a node within
ration and strength for a pulse to be captured by an FF. A nec- 3 or 4 logic levels away from a reception FF, i.e., a combina-
essary condition for a pulse to be captured by an FF located at tional path with 3 or 4 logic levels satisfies condition (6). Ini-
the fanout of node is the existence of a path from to tially, in Fig. 4(a), there are two faulty paths ( and ) and
, which has no FFs and satisfies two faulty nodes ( and ). After retiming in Fig. 4(b), only
one faulty path and one faulty node remain. Mean-
while, the clock rate remains the same after the retiming.
Considering SET-induced faults, the full-chip reliability can
(6) be measured by either the number of faulty paths or the number
of faulty nodes. Therefore, we present a uniform algorithm that
XU et al.: IN-PLACE FPGA RETIMING FOR MITIGATION OF VARIATIONAL SINGLE-EVENT TRANSIENT FAULTS 1375

Fig. 6. Potential faulty node .

If is not a faulty path, then either or

. If , then
according to (4). If , then
since is always nonnegative.
Fig. 4. An illustration for SaR. (a) Before retiming. (b) After retiming. If , then or .
In either case, is not a faulty path.
To model a potential faulty path ,
we introduce a binary variable, , where

(8)

The physical meaning of the variable can be inter-

preted as follows. If , condition (7) is satisfied
Fig. 5. Potential faulty path topology. and therefore no FFs are inserted in edge , which indi-
cates that path is not a faulty path after retiming . If
can be used to minimize either of these two metrics in the next , there may be an FF inserted in edge of
section. a potential faulty path because could be 1. If
we minimize the sum of all over all potential critical
paths, indicates that there must be an FF in edge
IV. RETIMING FOR DETERMINISTIC SET
, which can be proved by contradiction.
A. Characteristics of Faulty Paths
B. Characteristics of Faulty Nodes
For a quantitative characterization, we define the potential Similarly, we define a faulty node below.
faulty path as follows: Definition 4: Node is a potential faulty node iff there is at
Definition 3: Path , which consists of a subpath least one potential faulty path starting from node .
and an edge , is a potential faulty path iff Consider the example shown in Fig. 6. If any one of paths
subpath is a critical path from node to node and it , or is a potential faulty path,
satisfies condition (6). node is a potential faulty node. Using the auxiliary variable
Fig. 5 shows an example of the topologies of potential faulty , we can easily model the faulty potential of node
paths. Particularly, there are two critical paths from node to as follows:
node . Suppose that they both satisfy condition (6) and there
are two fanouts of node , i.e., node and node . If any of (9)
these two fanout edges, or , contains an FF (the
shadowed rectangle in Fig. 5), any SET pulses initiated at node
can be captured by the FF. In this example, path is where means path
a faulty path but path is not. is a potential faulty path. Intuitively, (i.e.,
To ensure that a potential faulty path does not form a faulty node is a faulty node after retiming) iff there is at least one
path after retiming, we must guarantee that there are no FFs edge in a potential faulty path which contains an
located at the last edge of this path. The following theorem states FF.
the sufficient and necessary condition that a path is not faulty:
C. Retiming for Faulty Path Minimization
Theorem 1: A potential faulty path
is not a faulty path after a valid retiming iff To minimize the number of faulty paths by retiming, all
potential faulty paths need to be investigated. In Fig. 5,
(7) there are four potential faulty paths, ,
, , and .
Proof: According to (4), for a valid retiming , is In general, suppose there are critical paths from node
either 0 or 1. to node and there are edges in the fanout of node
1376 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMSI: REGULAR PAPERS, VOL. 58, NO. 6, JUNE 2011

, then there are potential faulty

paths, where is the number of nodes in the graph.
With the help of the auxiliary variable , the number
of variables to characterize the potential faulty paths can be re-
duced to by using a weight in front
of each to describe the number of critical paths from
node to node . For example, in Fig. 5, we have
and for and , respec-
tively.
The minimization of the number of faulty paths is equiva-
lent to the minimization of the sum of over all po- Fig. 7. Potential faulty paths under variational SETs.
tential faulty paths. Therefore, the overall SET-aware retiming
problem can be formulated as the following ILP problem: the number of variables because the second constraint is domi-
nant. Formulation in Section IV-D has additional con-
straints for increased complexity. Therefore, a straightforward
solution to the ILP-based formulation presented in and
might be prohibitively expensive. Below, we present a
progressive retiming with improved scalability while preserving
optimality. The proposed progressive retiming is a uniform ap-
proach which deals with both Formulation and For-
mulation . We use to represent any of these two
(10) formulations.
The complexity in Formulation is mainly caused by the
where is the set of all potential faulty paths represented by enormous size of set . We propose a progressive retiming using
the tuples and is the retiming decision variable. Note progressive ILP to solve the above problem. Specifically, we
that we relax the 0-1 integer constraint of variable in use a series of sets to approximate and
ILP (10) because the binarity of is automatically pre- generate a series of retiming . The set is obtained by
served as . Therefore, are all integers, adding to all tuples induced by the faulty paths
and the objective function is to minimize a positive weighted after solving retiming . Then, retiming is obtained by
sum of . solving . Initially, one can choose and to be
any retiming. The algorithm converges based on the following
D. Retiming for Faulty Node Minimization theorem:
Theorem 2: There exists a finite such that .
Using techniques similar to those presented in the previous For such , is the optimal solution of .
subsection, we can minimize the number of faulty nodes by the Proof: We first prove that such exists by contradiction.
following ILP formulation: Assume such does not exist. Then, since for any
, it is straightforward that , which implies
. Since , we have for any .
Minimize However, that is not possible since is a finite set.
Now, suppose . Then there is no new faulty path
induction after retiming , i.e., is a feasible solution of
is a critical path . Therefore, since is the optimal solution of
and , must be the optimal solution of .
All other constraints in (11)
Note that each iteration in the progressive retiming only
takes the constraints from faulty paths generated by all the
Note that the first constraint in Formulation is a linear
previous retiming procedures, instead of those from all the
form of (9). Again, the binarity of the 0-1 integer variable
potential faulty paths. For example, for Fig. 5 contains only
is preserved by the objective function and the binarity of
one tuple, i.e., , since there is only one tuple
.
forming the faulty path under the current retiming.
On the other hand, since there are
E. Speedup by Progressive ILP
two tuples forming potential faulty paths.
In Formulation in Section IV-C, the number of vari- In the first few iterations of the progressive retiming, the
ables is dominated by the number of variables, with number of constraints in can be much fewer than that
complexity where is the in . During the course of the iterations, the number of con-
number of critical paths between two nodes. In the worst case straints accumulates and becomes slower. At the end of
scenario, this number will be exponential to the number of edges the progressive retiming, the number of constraints in is
in the graph, and is the number of fanouts of a node. no more than that in because topology constraints enable
The number of constraints in is in the same order as that certain potential faulty paths will never become a faulty
XU et al.: IN-PLACE FPGA RETIMING FOR MITIGATION OF VARIATIONAL SINGLE-EVENT TRANSIENT FAULTS 1377

TABLE I constraints in by changing the objective function as

CHARACTERISTICS OF SETS follows:

Minimize

TABLE II All constraints from

RESHAPING ABILITIES AND LATCHING WINDOW
where is the set of weighted potential faulty paths.
To handle the faulty node minimization problem, we define
the weighted potential faulty node as follows.
Definition 6: Node is a weighted potential faulty node iff
there is a weighted potential faulty path starting from node .
The weight of this node is

(14)

path. Our experimental results show that progressive retiming where is the set of pulses under which node is a potential
can usually converge in very few iterations. Therefore, we can faulty node and is the faulty potential of node under
terminate the progressive retiming within a limited number of SET pulse which can be calculated as
iterations.

V. RETIMING FOR VARIATIONAL SETs

Using the concept of the weighted potential faulty node, we can
In this section, we extend the proposed retiming to consider minimize the number of faulty paths for variational SET pulses
variational SETs as defined in Formulation 2. For any SET pulse with the following ILP formulation for the the same constraints
with initial duration , strength and probability of the in by changing the objective function as follows:
occurrence , a path is a potential
faulty path iff is a critical path and the below (12) (based Minimize
on (6)) is satisfied:
All constraints from
where is the set of weighted potential faulty paths. The pro-
gressive retiming presented in Section IV-E can be extended in
(12) a straightforward manner to solve the two formulations for vari-
ational SET pulses.

Considering the occurrence of variational pulses defined in For- VI. EXPERIMENTAL RESULTS
mulation 2, we define the weighted potential faulty path as fol-
lows: A. Experimental Settings
Definition 5: Given path and We have implemented the proposed retiming algorithm, SaR,
different pulses , , is a weighted potential for fault path minimization using C++ and solved the ILP using
faulty path iff is a potential faulty path for at least one mosek [48]. All experimental results are collected in a Linux
pulse and the weight of this path is server with an Intel Xeon 3.2 GHz CPU and 2 GB memory.
The algorithms are tested using ISCAS89 benchmarks.1 Each
(13) benchmark is first mapped to 4-LUTs using the Berkeley ABC
synthesis toolset [49]. After that, placement and routing are per-
formed using VPR [50]. In our current experiment, we target the
where is the set of pulses under which path is a poten- nonclustered FPGA architecture, which is similar to the FPGA
tial faulty path. mentioned in Section II. For the simplicity of presentation, we
Consider an example shown in Fig. 7. Suppose there are two assume in this paper that all cells of the same type have the same
pulses, and , with occurrence probability and reshaping abilities and delay.2
, respectively. Additionally, path satisfies According to [51], we consider the two most possible SETs
(12) for both and , and satisfies (12) only for , with duration of 500 ps and 700 ps, respectively, in 90 nm
i.e., can pass both paths while will be eliminated after path process technology, and we summarize their characteristics in
. Therefore, we have and . 1We only list 15 largest ISCAS89 benchmarks in the paper, and more results
Using the concept of the weighted potential faulty path, can refer to our technology report.
we can minimize the number of faulty paths for variational 2It is not difficult to see that our proposed algorithm can also handle the case
SET pulses with the following ILP formulation for the same without this assumption.
1378 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMSI: REGULAR PAPERS, VOL. 58, NO. 6, JUNE 2011

TABLE III
RUNTIME AND PROBLEM MAGNITUDE

Fig. 8. Case study for SaR effectiveness: s444.

Table I. We have tested our proposed SaR under both determin-

istic and variational SETs. is assumed in the experiments
considering deterministic SET. Both and are as-
sumed in the experiments considering variational SETs, and we
assume that and have the same probabilities of
occurrence. We use the PTM 90 nm model [52] to simulate the
characteristics of the SET propagation in our FPGA architec-
ture. We find that the reshaping ability of a given
type of cells is practically independent of the duration and the
strength of the pulses. Note that the reshaping effect is dom-
inated by the LUT cell according to Table II, and the latching
window information of FFs in 90 nm process technology3 is also
shown in Table II.

B. Solution Space Exploration

Retiming is a basic sequential circuit transformation. As
stated in Section I, there are some existing retiming algorithms,
such as retime for min-time, min-are, most forward, and most
backward [21]. To explore the potential solution space for
SET mitigation, we compare the performance among different
retiming strategies. Fig. 8 illustrates faulty path reduction after
min-time, min-area, forward, and backward for benchmark
s444. Similar observations also happen to other benchmarks.
The results clearly show a large optimization room (around
68%) for SET mitigation, where backward retiming seems a
good heuristic to reduce the faulty-path number. However,
there is still a large gap (more than 2X) between backward
retimed circuit and the optimal one (circuit after SaR) in terms
of SET mitigation.

C. Runtime and Quality Trade-Off

To minimize the number of faulty paths, Section IV has
presented two approaches, i.e., the global retiming presented Fig. 9. Case study for optimization convergence: s444.bench. (a) FP number
with iterations. (b) Runtime with iterations. (c) ILP constraint number with it-
in Section IV-C and the progressive retiming presented in erations.
Section IV-E. Both return optimal solutions but with different
runtimes. This subsection experimentally compares these two to 10 000 times) faster than the global onethe latter cannot
approaches in terms of runtime. In addition, we show how to finish most of the benchmark circuits. Furthermore, progressive
trade solution quality for runtime in order to deal with large retiming reduces the problem magnitude drastically (27 times
benchmarks. on average). This observation confirms and approves the run-
Table III compares the runtime of the global retiming and pro- time efficiency brought by progressive ILP solving.
gressive retiming for six benchmarks, where - means the ILP We also study the convergence of the proposed progressive
solver mosek could not finish within 60 h. For the first two small retiming. As an example, Fig. 9 plots the remaining faulty paths
benchmark circuits, the progressive retiming is significantly (up number, runtime and ILP constraint number during the course
3Typically, in the latching window of FFs is equivalent to ; of the progressive retiming for benchmark s444. Clearly, it
in the latching window of FFs is equivalent to the threshold voltage. takes significantly longer to achieve a reduction of a few faulty
XU et al.: IN-PLACE FPGA RETIMING FOR MITIGATION OF VARIATIONAL SINGLE-EVENT TRANSIENT FAULTS 1379

TABLE IV
SaR RESULTS WITH THE MINIMUM CLOCK PERIOD CONSTRAINT

TABLE V
FAULTY PATH REDUCTION WITH DIFFERENT TIMING CONSTRAINTS (W.R.T. CLOCK PERIOD )

paths after the first four iterations due to the enlargement of min) timeout. Meanwhile, the estimated mean-time-to-failure
problem magnitude. Similar observations are made across all (MTTF) is proportional to the area (A) and clock frequency
benchmarks. To achieve the best tradeoff between the runtime and inversely proportional to the fault rate, which in turn is pro-
and quality, we use four iterations for the progressive retiming portional to the number of faulty paths . We get as fol-
in the rest of the experiments. To further control the runtime, we lows:
set the timeout (i.e., time limit) for mosek, the ILP solver. Two
sets of timeouts (10 min and 30 min) are used. When the total MTTF (15)
runtime consumed by mosek exceeds the timeout, the current
best feasible solution obtained by mosek4 will be used as the
Since our retiming preserves the area (in-place retiming) and
final retiming solution.
clock frequency (min-time retiming), MTTF is approximately
D. Faulty Path Reduction for Deterministic SET inversely proportional to the number of faulty paths. The pro-
posed retiming is able to improve MTTF for the minimum clock
Table IV compares the number of faulty paths before (orig-
period by 96% (131%) with a 10-min (30-min) timeout on av-
inal) and after (remaining) optimization. With the minimum
erage.
clock period constraint, our proposed algorithm SaR can reduce
the number of faulty paths by 49% (57%) with a 10-min (30-
E. Faulty Path Reduction for Variational SETs
4Mosek uses an iterative algorithm (the interior point method) for the ILP
solving, and therefore can produce multiple intermediate (suboptimal) solutions In this experiment, we used two kinds of SET pulses with the
during the iterations. characteristics in Table I. As shown in Table IV, our proposed
1380 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMSI: REGULAR PAPERS, VOL. 58, NO. 6, JUNE 2011

SaR algorithm effectively deals with the variational SET mitiga- [8] N. Guan, Z. Gu, Q. Deng, W. Xu, and G. Yu, Schedulability analysis of
tion problem and improves MTTF by 78% (115%) for the min- preemptive and nonpreemptive EDF on partial runtime-reconfigurable
FPGAs, ACM Trans. Design Autom. Electron. Syst., vol. 13, no. 6, pp.
imum clock period constraint with a 10-min (30-min) timeout. 745759, 2008.
Compared to the case with deterministic SET, faulty path reduc- [9] L. Cheng and P. Gupta, A levelized variation modeling scheme, in
tion via retiming for variational SETs slightly decreases caused Proc. IEEE Workshop Design Manufacturability Yield, Los Angeles,
CA, 2010, pp. 1319.
by the increase of the number of ILP formulation constraints. [10] F. He, M. Gu, X. Song, Z. Tang, and L. Cheng, Probabilistic estima-
tion for routing space, Comput. J., vol. 10, no. 4, pp. 667676, 2005.
F. Reliability Versus Performance [11] D. Bhaduri, S. K. Shukla, P. S. Graham, and M. B. Gokhale, Reli-
ability analysis of large circuits using scalable techniques and tools,
The above experiments have already proved the effectiveness IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 4, no. 7, pp. 22472460,
2007.
and efficiency of SaR for SET mitigation. Moreover, we also [12] Y. Jeng and L. Cheng, Digital spectrum of a nonuniformly sampled
investigated the tradeoff between reliability (MFFT) and per- two-dimensional signal and its reconstruction, IEEE Trans. Instrum.
formance (clock frequency). Table V shows faulty path reduc- Meas., vol. 54, no. 3, pp. 11801187, 2005.
[13] F. Ren and D. Markovic, True energy-performance analysis of the
tion with various relaxation of the timing constraints, i.e., al- MTJ-based logic-in-memory architecture (1-bit full adder), IEEE
lowing 0.2X and 0.5X minimal clock period increase after SaR Trans. Electron Devices, vol. 57, no. 5, pp. 10231028, 2010.
respectively. Intuitively, the retiming with a relaxed clock con- [14] F. He, L. Cheng, G. Yang, X. Song, M. Gu, and J. Sun, On theoretical
upper bounds for routing estimation, J. Universal Comput. Sci., vol.
straint searches larger solution space and reduces more faulty 11, no. 5, pp. 117122, 2005.
paths, which is confirmed by Table V. It illustrates that about [15] C. Windstead and S. Howard, A probabilistic LDPC-coded fault com-
70% of more faulty path reduction is obtained when 50% delay pensation technique for reliable nanoscale computing, IEEE Trans.
Circuits Syst. II, Exp. Briefs, vol. 56, no. 7, pp. 484488, 2009.
increase is allowed. Nevertheless, delay will decease clock fre- [16] F. He, X. Song, M. Gu, L. Cheng, G. Yang, Z. Tang, and J. Sun, A com-
quency, to which MTTF is proportional according to (15). Our binatorial congestion estimation approach with generalized detours,
experimental results show that the increasing of system delay Comput. Math. Appl., vol. 51, no. 6, pp. 232241, 2006.
[17] F. He, X. Song, M. Gu, L. Cheng, G. Yang, Z. Tang, and J. Sun, A com-
overwhelms the faulty path reduction and makes MTTF worse binatorial congestion estimation approach with generalized detours, J.
ultimately. Circuits, Syst., Comput., vol. 51, no. 3, pp. 11131126, 2010.
[18] B. Vasic and S. K. Chilappagari, An information theoretical frame-
work for analysis and design of nanoscale fault-tolerant memories
VII. CONCLUSION AND FUTURE WORK based on low-density parity-check codes, IEEE Trans. Circuits Syst.
I, Reg. Papers, vol. 3, no. 7, pp. 24382446, 2007.
We have presented SaR, an SET-aware retiming. The broad- [19] T. B. Chan, A. Pant, L. Cheng, and P. Gupta, Design dependent
ening and attenuation effects during the propagation of an SET- process monitoring for back-end manufacturing cost reduction, in
induced signal are modeled and linked to the topology (i.e., the Proc. Int. Conf. Comput. Aided Design, San Jose, CA, 2010, pp.
116122.
distribution of combinational paths) of a circuit. Based on this [20] W. Robinett et al., Defect tolerance based on coding and series repli-
model, the retiming problem considering variational SETs (i.e., cation in transistor-logic demultiplexer circuits, IEEE Trans. Circuits
SETs with different durations) is formulated as an integer linear Syst. I, Reg. Papers, vol. 54, no. 3, pp. 24102421, 2007.
[21] L. Rockett et al., Radiation hardened FPGA technology for space ap-
programming (ILP) problem and solved by a progressive ILP plications, in Proc. Aerospace Conf., Chicago, IL, 2007, pp. 17.
algorithm. Tested on ISCAS89 benchmarks, our SaR improves [22] [Online]. Available: http://www.actel.com/
MTTF by 78% with a 10-min time limit for variational SETs [23] Y. Hu, Z. Feng, L. He, and R. Majumdar, Robust FPGA resynthesis
based on fault-tolerant Boolean matching, in Proc. ICCAD, San Jose,
without performance and area penalty. In the future, we will CA, Nov. 2008, pp. 706713.
take logic masking [47] into consideration for less conservative [24] Z. Cao, T. Jing, Y. Hu, Y. shi, X. Hong, X. Hu, and G. Yan,
fault models. DraXRouter: Global routing in X-architecture with dynamic resource
assignment, in Proc. Asia South Pacific Design Automation Conf.,
Yokohama, Japan, 2006, pp. 618623.
REFERENCES [25] W. Xu, K. Xu, and X. Xu, A novel placement algorithm for sym-
metrical FPGAs, in Proc. Int. Conf. ASIC, Guilin, China, 2007, pp.
[1] B. Narasimham et al., On-chip characterizaion of single-event tran- 12811284.
sient pulsewidths, IEEE Trans. Device Mater. Rel., vol. 6, no. 3, pp. [26] L. Cheng, W. N. N. Hung, G. Yang, and X. Song, Congestion estima-
542549, 2006. tion for 3D routing, in Proc. Int. Symp. VLSI, San Diego, CA, 2004,
[2] L. Cheng, X. Song, G. Yang, Z. Tang, and S. Gao, A fast congestion pp. 239240.
estimator for routing with bounded detours, in Proc. Asia South Pa- [27] K. Morgan et al., SEU-induced persistent error propagation in
cific Design Automation Conf., Yokohama, Japan, 2004, pp. 666700. FPGAs, IEEE Trans. Nucl. Sci., vol. 52, no. 6, pp. 24382445, 2006.
[3] Y. Lin and L. He, Device and architecture concurrent optimization [28] M. Rofouei, W. Xu, and M. Sarrafzadeh, Computing with uncertainty
for FPGA transient soft error rate, in Proc. IEEE/ACM Int. Conf. in a smart textile surface for object recognition, in Proc. Int. Conf.
Comput.-Aid. Design, San Jose, CA, 2007, pp. 194198. \Multisensor Fusion Integr. Intell. Syst., Salt Lake City, UT, 2010, pp.
[4] K. Xu, W. Xu, J. Shen, and X. Xu, Task scheduling algorithm based 174179.
on dual-Vdd dynamic reconfigurable FPGA, J. Zhejiang Univ., vol. [29] C. Bolchini, D. Quarta, and M. D. Santambrogio, SEU mitigation
2, no. 1, pp. 300304, 2010. for SRAM-based FPGAs through dynamic partial reconfiguration, in
[5] L. Cheng, W. N. N. Hung, G. Yang, and X. Song, Congestion estima- Proc. GLSVLSI, New York, Nov. 2007, pp. 512519.
tion for 3-D circuit architectures, IEEE Trans. Circuits Syst. II, Exp. [30] M. Gu, F. He, L. Cheng, X. Song, and G. Yang, Congestion estima-
Briefs, vol. 51, no. 2, pp. 655659, 2004. tion for hexagonal routing, Int. J. Comput. Math., vol. 16, no. 2, pp.
[6] S. Baeg, S. Wen, and W. Rong, Minimizing soft errors in tcam de- 323331, 2006.
vices: A probabilistic approach to determining scrubbing intervals, [31] L. Cheng, X. Song, G. Yang, W. N. N. Hung, and Z. Tang, A fast
IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 44, no. 7, pp. 814822, congestion estimator for routing with bounded detours, Integr., VLSI
2010. J., vol. 60, no. 11, pp. 25622569, 2008.
[7] W. Hung, X. Song, T. Kam, L. Cheng, and G. Yang, Routability [32] J. Xiong, Y. Shi, V. Zolotov, and C. Visweswariah, Statistical multi-
checking for three-dimensional architectures, IEEE Trans. Very layer process space coverage for at-speed test, in Proc. Design Autom.
Large Scale Integr. (VLSI) Syst., vol. 12, no. 1, pp. 13711374, 2004. Conf, San Jose, CA, 2009, pp. 117122.
XU et al.: IN-PLACE FPGA RETIMING FOR MITIGATION OF VARIATIONAL SINGLE-EVENT TRANSIENT FAULTS 1381

[33] F. He, X. Song, L. Cheng, G. Yang, Z. Tang, M. Gu, and J. Sun, A hier- Yu Hu (M10) received the B.Eng. and M.Eng. de-
archical method for wiring congestion prediction, in Proc. Int. Symp. grees from the Computer Science and Technology
VLSI, Salt Lake City, UT, 2005, pp. 1625. Department, Tsinghua University, Beijing, China, in
[34] Z. Feng, Y. Hu, L. He, and R. Majumdar, IPR: In-place reconfigura- 2002 and 2005, respectively, and the Ph.D. degree
tion for FPGA fault tolerance, in Proc. ICCAD, San Jose, CA, 2009, from the Department of Electrical Engineering, Uni-
pp. 242247. versity of California, Los Angeles (UCLA) in 2009.
[35] S. Krishnaswamy, I. L. Markov, and J. P. Hayes, Improving testability Since 2010, he has been an Assistant Professor
and soft-error resilience through retiming, in Proc. DAC, San Jose, in the Department of Electrical and Computer Engi-
CA, 2009, pp. 6065. neering, University of Alberta, Edmonton, Canada.
[36] D. G. Mavis and P. H. Eaton, Temporally redundant latch for pre- His research interests include general aspects of
venting single event disruptions in sequential integrated circuits, in field-programmable gate arrays (FPGAs).
Proc. Int. Microelectron. Conf., Albuquerque, NM, 2002, pp. 187200. Dr. Hu is the recipient of the Outstanding Graduate Student Award from Ts-
[37] Using Synplify to design in Actel radiation-hardened FPGAs [On- inghua University in 2005, and he is the corecipient of the Best Contribution
line]. Available: www.actel.com/documents/SynplifyRH_AN.pdf Award at International Workshop of Logic and Synthesis 2008. His work has
Technology Report been nominated for the Best Paper Award multiple times at the International
[38] R. R. Rao et al., Soft error reduction in combinational logic using Conference on Computer-Aided Design and Design Automation Conference.
gating resizing and flipflop selection, in Proc. ICCAD, San Jose, CA,
2006, pp. 1825.
Ju-Yueh Lee (S08) received the B.S. degree in
[39] Q. Zhou and M. Kartik, Gate sizing to radiation harden combinational
computer science from National Chiao-Tung Univer-
logic, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol.
sity, Hsinchu, Taiwan, in 2004 and the M.S. degree
25, pp. 155166, Jan. 2006.
in electrical engineering from National Taiwan
[40] C. Lin and H. Zhou, An efficient retiming algorithm under setup and
University, Taipei, Taiwan, in 2006. He is currently
hold constraints, in Proc. DAC, San Francisco, CA, 2006, pp. 7277.
working toward the Ph.D. degree in the Electrical
[41] [Online]. Available: http://www.ece.vt.edu/mhsiao/iscas89.html
Engineering Department, University of California,
[42] [Online]. Available: http://www.xilinx.com/
Los Angeles (UCLA).
[43] [Online]. Available: http://www.altera.com/
His current research interests include com-
[44] C. E. Leiserson and J. B. Saxe, Retiming synthronous circuitry, Al-
puter-aided design for field-programmable gate
gorithmica, vol. 10, no. 2, pp. 535, 1988.
array synthesis and application-specified integrated
[45] V. F. Carrois et al., Investigation of the propagation induced pulse
circuit physical synthesis.
broadening (PIPB) effect on single event transients in SOI and bulk
inverter chains, IEEE Trans. Nucl. Sci., vol. 55, pp. 28422853, Dec.
2008. Fang Gong (S08) received the B.S. degree from the
[46] P. E. Dodd and L. W. Massengill, Basic mechanisms and modeling of Computer Science Department, Beijing University of
single-event upset in digital microelectronics, IEEE Trans. Nucl. Sci., Aeronautics and Astronautics, China, in 2005 and the
vol. 50, pp. 583602, Jun. 2003. M.S. degree from the Computer Science Department,
[47] K. J. Hass, J. W. Gambles, B. Walker, and M. Zampaglione, Miti- Tsinghua University, China, in 2008. He is currently
gating single event upsets from combinational logic, in Proc. NASA working toward the Ph.D. degree in the Electrical En-
Symp. VLSI Design, Chicago, IL, 1998, pp. 1022. gineering Department, University of California, Los
[48] Mosek Optimization Software [Online]. Available: http://www.mosek. Angeles.
com/ His research interests mainly focus on numerical
[49] B. L. Synthesis and V. Group, ABCA system for sequential syn- computing and stochastic techniques for CAD, in-
thesis and verification [Online]. Available: http://www.eecs.berkeley. cluding fast circuit simulation, yield estimation and
edu/alanmi/abc/ optimization. He also works on numerics parallel and distributed computing.
[50] V. Betz, J. Rose, and Alexander, Versatile placement and routing tools
for FPGAs [Online]. Available: http://www.eecg.utoronto.ca/vpr/
Lei He (M99SM08) received the Ph.D. degree in
[51] B. Narasimham, Single-event transient pulse-width measurements in
computer science from the University of California,
advanced technologies Institute for Space and Defense Electronics,
Los Angeles, in 1999.
Vanderbilt Univ., 2008, Tech. Tep..
He has published one book and over 200 technical
[52] Predictive Technology Model (PTM) [Online]. Available: http://www.
papers with 12 best paper nominations. mainly from
eas.asu.edu/ptm/
the Design Automation Conference and International
Conference on Computer-Aided Design. and five
best paper or best contribution awards, including
Wenyao Xu (S08) received the B.S. and M.S. the ACM Transactions on Electronic System Design
degree in electrical engineering from Zhejiang Automation 2010 Best Paper Award. His research
University, Hangzhou, China, in 2006 and 2008, re- interests include modeling and simulation, VLSI
spectively. He is currently working toward the Ph.D. circuits and systems, and cyber physical systems.
degree in the Electrical Engineering Department,
University of California, Los Angeles.
His research interests include computer-aided de- Majid Sarrafzadeh (F96) received the Ph.D. degree
sign for programmable fabrics, wireless health, and in electrical and computer engineering from the Uni-
braincomputer interface. versity of Illinois at Urbana-Champaign in 1987.
He joined Northwestern University as an Assistant
Professor in 1987. In 2000, he joined the Computer
Science Department, University of California at Los
Angeles (UCLA). He is currently a Codirector of the
UCLA Wireless Health Institute, where he has a few
dozen active projects with medical doctors and nurses
Jia Wang (M08) received the B.S. degree in around the world. He has published approximately
electronic engineering from Tsinghua University, 370 papers, coauthored 5 books, and is a named in-
Beijing, China, in 2002 and the Ph.D. degree in com- ventor on many U.S. patents. His recent research interests lie in the area of Em-
puter engineering from Northwestern University, bedded and Reconfigurable Computing with emphasis on healthcare.
Evanston, IL, in 2008. Dr. Sarrafzadeh has served on the technical program committee of numerous
He is an Assistant Professor of electrical and com- conferences and been a general chair of many of them. He has collaborated with
puter engineering at Illinois Institute of Technology, many industries in the past 25 years industries and was the architect of Monterey
Chicago. His research interests are in computer-aided Design SystemsSynopsys acquired the company. He was a cofounder of Hier
design of very large scale integrated circuits and al- Design, Inc. Hier Design was acquired by Xilinx in 2004. He has recently co-
gorithm design. founded Medisens and BioAssyst: both companies in the area of wireless health.