\documentclass[12pt]{article}
\usepackage{setspace,fullpage}
\newcommand {\tp}{t_p}
\newcommand {\tf}{t_f}
\newcommand {\toh}{t_{oh}}

\begin{document}
\sloppy

\title{
On the Practicality of Using Intrinsic Reconfiguration for Fault 
Recovery
}

\author{
Garrison W. Greenwood \\
Department of Electrical \& Computer Engineering\\
Portland State University\\
Portland, OR 97207
}

\date{}


\maketitle

\bibliographystyle{unsrt}

\vspace{0.1in}


\noindent Keywords: evolvable hardware, fault recovery, intrinsic evolution, reconfiguration

\vspace{0.1in}

\begin{abstract}
Evolvable hardware combines the powerful search capability of 
evolutionary algorithms with the flexibility of reprogrammable 
devices, thereby providing a natural framework for reconfiguration.  
This framework has generated an interest in using evolvable hardware 
for fault-tolerant systems because reconfiguration can effectively 
deal with hardware faults whenever it is impossible to provide 
spares.  But systems cannot tolerate faults indefinitely, which means 
reconfiguration does have a deadline.  The focus of previous evolvable 
hardware research relating to fault-tolerance has been primarily 
restricted to restoring functionality, with no real consideration of 
time constraints.  In this paper we are concerned with evolvable 
hardware performing reconfiguration under deadline constraints.  
In particular, we investigate reconfigurable hardware that undergoes 
intrinsic evolution.  We show that fault recovery done by intrinsic 
reconfiguration has some restrictions, which designers cannot ignore.
\end{abstract}


\section{Introduction}

Reliable systems can be depended on to provide continual service.  
Unfortunately, faults are inevitable, which leads to disruptions in 
service.  One way of increasing a system's availability is to make it 
fault-tolerant---i.e., capable of detecting and recovering from 
hardware faults.  Exchanging a faulty component with an operating 
spare is the most widely used method for hardware fault 
recovery~\cite{aviz}, but this method is not always practical.
For instance, in some systems mission essential equipment occupies all
of the available space leaving no room for spare hardware.
Another case is when system failure results from an unanticipated
change in the operational environment. For example, high radiation 
environments can induce effects in metal-oxide-semiconductor 
devices~\cite{rads} and high temperatures can lead to failures in 
voltage converters~\cite{temps}. Simply replacing the original system 
with an identical copy accomplishes nothing if the environmental 
conditions haven't changed.

Reconfiguring a faulty system eliminates the need for redundant 
hardware.  Reconfiguration methodically changes the failed system's
architecture until a desired functionality is restored.  There is no
guarantee full functionality can be restored in all cases.  
Nevertheless, reconfiguration is a viable fault recovery 
technique---especially when providing redundant hardware becomes
impractical.

Our work presented in this paper concentrates on those fault tolerant
systems that cannot use redundant hardware for fault recovery and are
therefore forced to use reconfiguration.  Spacecraft or unmanned air 
vehicles are good examples;  both have little room for spare hardware
and they must operate in potentially hostile environments.    

Evolvable hardware (EHW) has emerged as a powerful method for doing 
original hardware design---which naturally suggests it could be 
equally useful for doing hardware reconfiguration.
The idea behind EHW is to combine the biologically-inspired 
search methods of evolutionary algorithms with the flexibility of 
reconfigurable hardware.  The evolutionary algorithm searches 
throughout the space of all possible configurations looking for the 
one that performs the best.  Every configuration the evolutionary 
algorithm finds must be evaluated and there are two accepted 
methods: \textit{extrinsic evolution} where the evaluation is done 
in software, and \textit{intrinsic evolution} where the evaluation is 
done on a hardware implementation.  In many instances intrinsic 
evolution is necessary because the only real way to evaluate a 
configuration is to implement it and have it actually operate in the 
physical environment.  \textit{Intrinsic reconfiguration} refers to any 
search process that uses intrinsic evolution to find new hardware
configurations.

Three types of devices are suitable 
reconfigurable architectures: the {field programmable gate array}
 (FPGA) for digital 
applications; the {field programmable analog array}
 (FPAA) for analog 
applications; and the {field programmable transistor array}
 (FPTA) that 
can be used in either analog or digital applications.  These devices 
represent different levels of granularity.  Both the FPGA and FPAA 
provide configurable blocks of circuitry along with programmable 
routing resources.  Conversely, the FPTA consists of an array of 
MOSFET transistors interconnected via programmable switches.  A small 
number of capacitors are included on-chip, but resistors are 
synthesized using the MOSFET transistors.  FPGAs and FPAAs are 
available as commercial off-the-shelf (COTS) devices (e.g., see 
\cite{fpga} and \cite{fpaa}); the FPTA was fabricated for NASA's 
Jet Propulsion Laboratory and is currently only available for research 
studies \cite{fpta1}.


Some recent work has shown EHW can be quite effective for reconfiguring 
existing hardware to overcome faults \cite{fpta2, mange, lukas}.   
The ability of evolutionary algorithms to find good reconfigurations 
is not at issue in this paper.  We instead are concerned with  the 
issue of time.  Most EHW-based studies rely on device 
simulators rather than physical hardware.  This simulator 
use means the time to download a 
configuration, the time to program the device, and the time to 
conduct a fitness evaluation on the reconfigured  hardware has largely 
been ignored---even though they dramatically affect the evolutionary 
algorithm's running time.  

%This means fault 
%recovery must be completed within specified timeframes or undesirable 
%consequences will occur.  The introduction of a deadline into fault 
%recovery means fault-tolerant systems must be considered real-time 
%systems (RTS).  
%In this paper we derive a formula 
%for estimating intrinsic reconfiguration time.  It will be shown how 
%this estimate impacts the choice of a fault recovery mechanism.

Systems cannot operate indefinitely with faults.  It should be obvious 
that timing constraints must be considered whenever evolutionary fault 
recovery is used.  Why then do researchers ignore them?  EHW 
researchers who study fault tolerant systems almost exclusively focus 
on just restoring functionality~\cite{gree}.  The
evolutionary algorithm running time is usually reported as either
a maximum time or as an average time taken over many runs.  
Average running time doesn't guarantee compliance with a hard recovery 
deadline.  Even the maximum running time is worthless because 
there is no guarantee some future run won't take even longer.
For some reason running times and recovery deadlines aren't
compared.

Designers must contemplate a variety of factors before choosing a 
fault recovery method.  This paper describes the advantages and 
limitations of intrinsic reconfiguration so designers 
can make an informed choice.  In addition, several recommendations
about the best ways to use intrinsic reconfiguration for fault
recovery are included.  No new methods to speed up the evolution are
discussed.  The reader should understand intrinsic reconfiguration 
properties are not application dependent and are not restricted to 
any particular type of evolutionary algorithm. Those properties are 
the central theme of this paper.  Optimization issues are handled more
appropriately within the context of a specific problem.

The paper is organized as follows. Section \ref{s1} compares extrinsic
and intrinsic reconfiguration and explains why the latter is usually
the only option for fault recovery. 
Section \ref{s2} gives a 
brief introduction to RTS and shows why fault-tolerant systems 
are real-time.  Section \ref{s3} derives a formula for estimating 
the intrinsic reconfiguration time and gives some examples to show
reconfiguration time can be surprisingly long.  Section \ref{s5} 
presents guidelines for future development of fault recovery systems 
that employ intrinsic reconfiguration. Finally, some practical issues
involving intrinsic reconfiguration are given in Section \ref{s22}.  

\section{Why Intrinsic Reconfiguration?} \label{s1}

We are concentrating on autonomous fault tolerant systems---i.e.,
systems that can detect, isolate and ultimately recover from a fault
without any human intervention.  Whenever EHW is used for fault 
recovery, the evolution can be done either intrinsically with physical 
hardware or extrinsically with hardware simulations.  
Is one method better than the other?  We believe for truly autonomous 
fault tolerant systems only the intrinsic 
method makes any sense for two reasons: 

\begin{description}

\item{(a)} \textit{lack of in-situ computing resources}

Most EHW research is conducted in laboratories using Pentium 
PCs or UNIX workstations---resources not usually installed on a 
deep-space probe heading towards the planet Neptune!  
The severe lack of space also precludes using pipelined hardware or
multiple processors that could speed up the processing.  
A more likely 
computing environment for reconfiguration operations in
autonomous systems would be a single 
low-end microprocessor. Such a processor is relatively slow and can 
only address small amounts of memory, which
affects the simulation runtime and the accuracy  of the hardware
models.  
Conversely, intrinsic reconfiguration doesn't use
hardware models, so there are no modeling inaccuracies.  Low-end
microprocessors are quite capable of running evolutionary algorithms 
used for EHW.  In fact, compact genetic algorithms 
even run entirely on a single VLSI chip~\cite{gallagher}.  


\item{(b)} \textit{inherent inaccuracies in hardware simulations}

A serious problem for spacecraft is collision with orbital 
debris~\cite{debris}.  Unforeseen failures like 
these are hard to represent accurately in a 
simulation, and even then only if the precise nature of the
failure is known. Unfortunately, getting accurate failure information 
is nearly impossible with truly autonomous systems, especially when
the failure was caused by exogenous events such as collisions.
Evolving a new hardware configuration with an
incomplete or inaccurate simulation is futile.  On the other hand, 
intrinsic reconfiguration never has to make simplifying assumptions
because the evolving hardware is directly interfaced to the damaged
system.  Hence, there is no doubt about how much functionality is
restored in the reconfigured system. 

\end{description}

The above discussion should not imply intrinsic reconfiguration 
has no disadvantages.  Fault recovery is inherently a real time
process---an idea largely ignored by the evolvable hardware community.
We will shortly show that intrinsic reconfiguration can take 
surprisingly long.  In fact, under certain circumstances it may take so 
long that it cannot be used for fault recovery!  Our objective is to
first show designers the limitations of intrinsic reconfiguration 
and second to provide the necessary tools for evaluating its potential 
as a fault recovery method.  However, before discussing those issues 
the reader must understand what makes a system a real-time system.

\section{Real-time systems} \label{s2}

This section provides a brief introduction to real-time systems.  
Interested readers are referred to some of the excellent books on 
this topic for further information (e.g., see \cite{burns}).  We 
begin with a formal definition of a real-time system.

\vspace{3ex}

Definition:  ({real-time system})

\vspace{2ex}

\textit{Any system that is both logically and temporally correct}


\vspace{2ex}


Logical correctness means the system satisfies all functional specifications.  
Temporal correctness means the system is guaranteed to perform these functions 
within explicit timeframes.  Fault-tolerant systems qualify as real-time systems 
because fault detection and fault recovery inherently have deadlines.  That is,
the fault must be detected within a certain period of time after it occurs, and
the fault must be corrected within a certain period of time after it is detected.  
Fault recovery may also have an expected start time.
	
The notion of real-time is often interpreted to mean really fast.  
This interpretation is not correct.  Real-time does not necessarily mean fast---and fast 
does not necessarily mean real-time.  Suppose a document must be sent from 
Chicago to London, and two delivery systems are available: surface mail 
with a guaranteed 3-day delivery time or e-mail with a guaranteed 5 minute 
delivery time.  The e-mail delivery is orders of magnitude faster than surface 
mail, but that does not necessarily mean it qualifies as a real-time delivery 
system.  It is the required delivery deadline that ultimately establishes 
whether the real-time system definition has been met.  For example, both systems are 
real-time systems if the deadline is six days because both are logically 
and temporally correct.  However, neither one is a real-time system if the 
deadline is three minutes because neither one is temporally correct. 

Real-time systems are classified as hard or soft.  Hard systems have 
catastrophic consequences if the temporal requirements are not 
met---up to and including complete system destruction.  In fact, if the hard system is 
safety-critical, failure could lead to injury or even death. Conversely, soft 
systems only have degraded performance if the temporal requirements 
aren't met.  The classification of a fault-tolerant system, in particular, 
depends on the nature of the faults and the consequences for failing to 
detect and correct them in a timely manner.  Suppose a fault results in an 
over-temperature condition.  If the system hardware can survive this 
condition for up to five minutes, then fault recovery must be completed 
within five minutes to prevent further damage.  This would be a hard 
fault-tolerant system.  On the other hand, if the fault only causes a 
minor loss of some sensor data, fault recovery could take considerably 
longer without dire consequences.   This would be a soft fault-tolerant 
system.  

\section{Quantifying Reconfiguration Time} \label{s3}

In this section we derive a formula for estimating the intrinsic reconfiguration
time and describe how the formula is used.   The derivation assumes the hardware environment 
consists of a single processor---i.e., a microprocessor or microcontroller---interfaced 
to a single reconfigurable device.  The processor is responsible
for executing the evolutionary algorithm, converting configurations into a proper
file format, downloading the configuration to the device, and running fitness 
tests to evaluate the configuration.  The processor may or may not be dedicated to
reconfiguration.  That is, the processor may be engaged with other tasks whenever
reconfiguration is not being performed.

\subsection{Formula Derivation}
 
The evolutionary algorithm manipulates a genome that encodes all of the 
information needed to create a hardware configuration.  During each 
generation $\lambda$ offspring are created.  However, with intrinsic evolution 
an offspring's fitness evaluation cannot begin until the configuration 
information is physically downloaded and the device is programmed.  Let $\tp$ 
denote the time it takes to do this.  
Since $\lambda$ downloads take place every generation, the 
download time per generation lasts $\lambda \tp$ seconds.  
If $\tf$ denotes the duration of the fitness test per individual, 
 then $\lambda \tf$ is the fitness evaluation time 
per generation.

The $\tp$ value depends on the type of reconfigurable device---i.e., 
an FPGA, FPAA or FPTA---whereas $\tf$ is application dependent because the 
test duration is determined by the scope of the fitness test.  Every offspring
consumes $\tp + \tf$ time units.  It therefore follows that an
evolutionary algorithm running for $k$ generations, while producing $\lambda$ 
offspring per generation, has an intrinsic reconfiguration time of 

\begin{equation}
T_r(k,\lambda) \; = \; k\lambda(\tp+\tf) 
\label{eqn:1}
\end{equation}





\begin{table*}[ht]
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
\bf{Device} & \bf{Type} & \bf{Size} & \bf{Mfg} & $\mathbf{\tp}$ (ms) & \bf{Ref.} & \bf{Notes}\\ \hline \hline
ispPAC10 & FPAA & 4 & Lattice Semiconductor & 100  & \cite{pac10} & \\ \hline
AN220E04 & FPAA & 4 & Anadigm  & 3.8 & \cite{fpaa0} & 1, 2\\ \hline
XC3020A & FPGA & 64 & Xilinx & 1.5 & \cite{fpga1} & 2\\ \hline
Virtex XCV50 & FPGA & 1728 & Xilinx & 7 & \cite{fpga} & 3 \\ \hline
XC4085XL & FPGA & 3136 & Xilinx & 192 & \cite{fpga1} & 2 \\ \hline
APEX II EP2A70  & FPGA & 6720 & Altera &  12.5 & \cite{fpga4} & 4 \\ \hline
JPL's FPTA2 & FPTA & 64 & fabricated by MOSIS & 0.008 & \cite{jpl22} & 5 \\ \hline
\end{tabular} 
\vspace{1ex} 

(1) All 18 banks are reloaded with 256 bytes/bank \\
(2) Serial transfer with 10 MHz clock \\ 
(3) Byte-wide transfer with 10 MHz clock \\ 
(4) Byte-wide transfers with 66 MHz clock  \\
(5) Byte-wide transfers with 160 MHz clock  
\caption{Programming times for various popular reconfigurable devices.  
All are COTS devices except for the FPTA.  The units for size are 
configurable logic blocks for FPGAs, modules for FPAAs, and cells 
for FPTAs. The references indicate 
where the $\tp$ value is documented.} 
\label{tbl:1}  
\end{table*}

\vspace{1ex}

\subsection{Some Examples} 

Table \ref{tbl:1} shows the programming time ($\tp$) for several 
reconfigurable devices. 
This programming time cannot be ignored, despite being rather 
small in most FPGAs, because EHW algorithms frequently have 
populations sizes in the hundreds and they run for thousands of 
generations.  


\vspace{1ex}

\noindent\textit{Example 1:}

\vspace{1ex}

An EP2A70 FPGA is intrinsically evolved by a generational GA.  
The population size is 200 and 1000 generations are processed. 
From Table \ref{tbl:1}, $\tp = 12.5$ ms.
Then the time spent just reprogramming the FPGA is $\lambda\cdot k\cdot \tp$ or
about 42 minutes.  

\vspace{2ex}

$\tf$ is responsible for
the rather long search times often encountered in analog applications. 
For instance, suppose a proportional-derivative 
controller is implemented in an FPAA.  
A controller's fitness is found by applying a step
input to the control system and then measuring its 
settling time.  The fitness evaluation lasts at least as
long as the settling time does, which can be somewhat lengthy.
Indeed, settling times of two minutes are not unheard of~\cite{ngst}.  
Under these circumstances, it wouldn't 
take a very large population size nor a large number of generations 
to make an intrinsic reconfiguration run for hours or even
days before finishing.

\vspace{1ex}

\noindent\textit{Example 2:}

\vspace{1ex}

An AN220E04 FPAA is used to compensate for aging effects in a 
control system responsible for positioning a satellite's communications 
antenna. The reconfiguration search is done by a generational GA run 
for 500 generations with a population size of 100.  The system's step 
response is measured to determine if the compensation is correct.  This 
step response test takes $\tf = 625$ milliseconds to conduct.  Hence, 
$\lambda = 100$, $k = 500$ and $\tp= 3.8$ ms. Substituting into 
Eq.~(\ref{eqn:1}) yields $T_r(500,100) \approx 8.7$ hours.  



\section{Discussion} \label{s5}

Reconfiguration times are meaningless until they are put into context.
For instance, take Example 2 from the previous section.  
Suppose brief communication sessions with the satellite 
are scheduled at 10 hour intervals.  A session may be skipped, but skipping two 
sessions in a row is not permitted.  If a fault is detected just prior to a 
scheduled session, and if the error results in missing the session, then the 
fault recovery deadline is 10 hours.  This is the worst case scenario\footnotemark.  
An almost 9 hour reconfiguration time may seem quite long, but in this case it is 
perfectly acceptable because $T_r < 10$.  On the other hand, it would 
not be acceptable if communication sessions were scheduled at 6 hour intervals.

\footnotetext{~Missing one session is permitted.  If the fault is detected 
just after a scheduled session, the fault recovery deadline
would be 20 hours.}

The only way to determine if there is a problem is to compare the reconfiguration 
time against the fault recovery deadline.  This latter quantity is system dependent.  
No problem exists so long as the reconfiguration time is less than the recovery deadline.

This time comparison adds a new perspective on intrinsic evolution and, at the same 
time, imposes a new requirement.  Reconfiguration becomes a real-time process whenever
it is used as a fault recovery method.  Consequently, it is no longer sufficient 
to just talk about how an evolutionary algorithm was able to restore a circuit's 
functionality.  These statements may show logical correctness, but without comparing the
reconfiguration time against a deadline there is no proof of temporal correctness.  
Just reporting an algorithm's running time doesn't say anything about temporal correctness either.
The key point is expressed by the following first principle:  

\begin{quote}
\emph{
No fault recovery method can legitimately proclaim 
efficacy until it is proven to be both logically and temporally correct.}
\end{quote}

The validity of this principle is easy to see.  If the recovery 
method isn't logically correct, then the problem can't be fixed.  If it 
isn't temporally correct, then the problem can't be fixed soon enough
to prevent other things from going wrong.  
Without proving logical \underline{and} 
temporal correctness, there is no basis
for claiming a fault recovery method is effective.

It is easy to prove if a fault recovery method is logically 
correct---try it and see if it fixes the problem.  Proving temporal 
correctness, however, is  more complicated because it really depends 
on conducting a thorough failure modes and effects analysis
(FMEA) or fault tree analysis (FTA).  This analysis should identify 
all potential faults and their effects on system 
performance~\cite{fmea}.  One outcome of the failure
analysis is the recovery deadlines.  Temporal correctness is proven 
if a logically correct recovery is guaranteed to finish prior to the 
recovery deadline.  (Unfortunately, no EHW-based fault recovery method
is temporally correct.  See Section \ref{s22} for futher details.) 

No attempt was made in this study to promote one reprogrammable device 
over another.  In fact, the devices we chose to study were picked 
merely to show the broad range of what is available.  There is, 
however, one caveat.  Some reprogrammable devices, such as the 
ispPAC10, are E$^2$PROM based.  Hence, there is a limit to the number 
of times the device can be reconfigured. RAM based devices should be 
used if the population size and/or the number of generations is 
large. 

Up to this point only the programming and fitness evaluation times 
has been considered.  However, the time an evolutionary algorithm takes 
to do all of the other tasks done each generation, such as conducting 
binary tournaments or performing $n$-point crossover, is also 
important.  The genome associated with a particular reprogrammable
device is always the same, so the overhead associated with
running the evolutionary algorithm is roughly constant each generation
regardless of the application.  Let $\toh$ denote the constant overhead 
value.  Then a more accurate formula for the reconfiguration time is

\begin{equation}
T_r(k,\lambda,\toh) \; = \; k\lambda(\tp+\tf) + k\toh
\label{eqn:2}
\end{equation}

The number of generations ($k$) and the evolutionary algorithm
overhead time ($\toh$) can dramatically affect reconfiguration time.  
$k$ depends on the thoroughness of the search and how easily the 
evolutionary algorithm escapes local optima.  The overhead time 
depends on a variety of factors including how parents are chosen, 
the complexity of the reproduction operators, and so on.   Additional 
time must be added to account for the time to convert each genotype 
into the proper file format needed for the download.



Greenwood, et.~al~\cite{gree} suggested evolutionary algorithms 
designed for reconfiguration searches perform best if they have high
selection pressure and if they emphasize mutation for reproduction.
In principle, any type of evolutionary algorithm could be used for 
a reconfiguration search, but from a practical standpoint genetic 
programming algorithms should be avoided.  Genetic programming 
algorithms designed for EHW problems are put on large multiprocessor 
systems to abridge their long running time~\cite{gpsks2,gpsks1}.  
This becomes especially problematic for fault-tolerant systems because, 
if there isn't enough room for redundant hardware, then there isn't 
enough room for a large multiprocessor system either.  It seems 
unlikely a full-fledged genetic programming search,
run on a single processor, could finish quickly enough to meet 
a fault recovery deadline of only a few hours.  



Finally, some devices can be partially reconfigured---i.e., 
configuration changes can be restricted to only small portions of the 
device.  The idea 
is to identify the particular region in the bitstream which requires 
reconfiguration.  A header is then wrapped around this bitstream data 
to identify the address at which to start reconfiguration~\cite{holl}.
Partial reconfiguration reduces $\tp$.  This reduction may be important 
in situations where $\tp$ and $\tf$ are of the same order of magnitude.




\section{Putting Theory Into Practice} \label{s22}

We assume the system is fully designed and it meets all functional specifications.  The objective is now to find out how the system can fail and the resultant effects.   This evaluation can be done in several ways and the interested reader can find more comprehensive information elsewhere (e.g., \cite{dunn} contains an excellent introduction).  

Systems are typically evaluated with one of the following methods:
\begin{itemize}
\item \textit{failure modes and effects analysis (FMEA)}
\begin{quote}
A bottom-up method that looks at each component's failure modes and
how those failures affect system performance.
\end{quote}
\item \textit{fault tree analysis (FTA)}
\begin{quote}
A top-down method that assumes a specific failure has happened and
then analyzes each subsystem to look for the cause.
\end{quote}
\item \textit{failure modes and effects testing (FMET)}
\begin{quote}
Failures are injected into the system to observe their effects.
\end{quote}
\end{itemize}

A designer would use either a FMEA or a FTA to identify
the system's failure modes and their effects. For each effect the
analysis will show what actions (if any)
would prevent the effect from occurring, and if so, how much fault
recovery time is allowed.  

In a perfect world no fault recovery method would ever be used unless 
it is both logically and temporally correct.  In principle
FMET can prove logical correctness---inject the fault and
see if intrinsic reconfiguration prevents the effect from occurring.  
However, proving temporal correctness for intrinsic reconfiguration 
is another story.

In reality temporal correctness cannot be \underline{formally} 
proven for intrinsic reconfiguration because it uses an evolutionary 
algorithm.  Since these algorithms are stochastic, independent runs 
won't always produce repeatable outcomes.  Hence, there is 
no way to guarantee a fixed number of generations will always find 
a desired circuit configuration. 

\textit{This limitation does not, however, mean intrinsic 
reconfiguration cannot be used for fault recovery.}  It is also 
a reality that no system is perfect, always capable of performing 
when called upon.  Systems do fail, so all recovery methods---whether 
or not they use evolutionary algorithms---have a finite probability 
of not executing.  Consequently, the primary concern is to reduce 
the likelihood of failure.  All a designer can do is minimize the 
failure risk to an acceptable level.  There are ways 
to minimize risk when using intrinsic reconfiguration, but that 
depends on whether the fault is anticipated or unanticipated.

 
\subsection{Minimizing Risk With Anticipated Faults}

Anticipated faults are those faults identified while conducting an FMEA 
or FTA.  These faults are precisely known and their effects are 
observed.  Moreover, the fault recovery time is known because the 
analysis tells the time delay between the fault and its effect.

It was stated above that an FMET will verify logical correctness.  
But the first thing---before even conducting the FMET---is to see if 
intrinsic reconfiguration has any chance of meeting a recovery 
deadline.  Here simulation can be useful\footnotemark.  Once the fault 
is identified a designer can envision the type of circuitry needed for 
fault correction.  The designer could construct an evolutionary 
algorithm to search for hardware configurations and the simulator can 
evaluate them.  
It isn't necessary to find the exact desired 
configuration  because the goal is only to approximate the 
evolutionary algorithm running time.  Hence, the search can 
terminate when a sufficiently close enough configuration is found.
Eq.~(\ref{eqn:2}) will 
estimate the physical hardware reconfiguration time which can then
be compared against the fault recovery deadline.  
This procdure will quickly show if intrinsic reconfiguration is
feasible.

\footnotetext{Some COTS device vendors provide simulators for their 
products. Custom FPAAs and FPTAs and some mixed-signal devices can 
use PSpice for simulation.}  

The FMET should be conducted if and only if the reconfiguration time 
is less than the recovery deadline.  The best way to minimize any 
risk is to allow sufficient {slack time}.  In other words, the 
intrinsic reconfiguration should end well short of the recovery 
deadline.  The definition of ``well short'' of course depends on 
the system and the consequences of missing the recovery deadline.  
In safety-critical systems---i.e. systems where failure can lead to 
total system destruction, physical injury 
or even death---the recovery deadline should be several times longer 
than the reconfiguration time.  That requirement can 
be relaxed for systems that aren't safety-critical, but reducing 
the reconfiguration time will always decrease the risk.  \textit{This 
means the designer must know what constitutes an acceptable level of 
risk before specifying the maximum reconfiguration time.}  
  
Another way of reducing risk uses concepts taken from on-board
preventive maintenance programs~\cite{pm}.   The main idea is to do 
fault recovery in stages.  In other words, during each stage, which 
is a fixed time period, intrinsic reconfiguration is only expected 
to find an somewhat improved solution.  
The evolutionary algorithm uses the final population from the
previous stage as the initial population in the current stage.
The (still faulty) system has degraded performance, but it
remains online between stages.  This process continues until full 
recovery is achieved.   

No fault recovery procedure can remove all risk.  This means other
actions may be necessary.  See MIL-STD-882D for some additional risk 
mitigation measures~\cite{mstd}.


\subsection{Minimizing Risk With Unanticipated Faults}


Unanticipated faults are caused by events beyond a designer's control.
Two sources of unanticipated faults are persistent, unexpected 
environmental changes or damage resulting from exogenous events 
such as collision with orbital debris. In many instances the exact
change in the environment or the extent of damage cannot be accurately
determined.  Consequently, unanticipated faults frequently have
unpredictable effects.  Without knowing the effect, it is impossible
to state the recovery time; temporal correctness is no longer relevant.
However, logical correctness may still be important but that
depends on the source of the unanticipated fault.  


\subsubsection {Changed Environment}

Component characteristics can change when the operational environment
changes~\cite{rads,temps}. A new hardware configuration might exploit 
those changed characteristics to restore any lost functions.  For 
example, Stoica et al.~\cite{fpta1} successfully reconfigured a FPTA 
to restore functions lost due to temperature increases.  Logical 
correctness always holds for these type of problems because the 
recovery objective is the same as it was for anticipated faults.  
That is, the goal is to completely restore all original system 
functions.  

\subsubsection {Exogenous Events}

Exogenous events create havoc with an operating system because there
is no way to predict what faults will be induced; there is likewise no
way to predict the ultimate effects.  Consequently, logical correctness 
may be unattainable because there is no guarantee the available 
fault recovery method can deal with an unspecified failure mode. 

Under these circumstances the corrective action switches
from restoring system functions to guaranteeing system survival---which
contradicts the normal interpretation of logical correctness in a
fault tolerant system.  Intrinsic reconfiguration would initially 
just search for a stable system configuration that stops any fault 
migration. For example, compensators can keep a system stabilizable 
even when a sensor or actuator completely fails~\cite{stoustrup}.  Any 
other recovery actions may have to be done after the damaged 
system is taken offline.  

We conclude this section with the following two remarks:
\begin{enumerate}
\item Deterministic recovery methods are designed to handle only a
very specific set of faults.  They therefore have almost no ability to
deal with unanticipated faults---especially faults caused by exogenous
events.  On the other hand intrinsic reconfiguration can evolve novel
circuitry that a designer never considered.  In this realm we believe
intrinsic reconfiguration has the most potential as a fault recovery
method. 
\item  Temporal correctness is ignored under certain 
circumstances.  Does this mean the first principle of fault
recovery is invalid?  Not at all.  \textit{The first principle always 
holds when recovery is from an anticipated fault.}  The reason is an 
anticipated fault can be thoroughly analyzed to determine its effect
and recovery time; temporal correctness requirements are therefore 
clearly defined.  Conversely, unanticipated faults were never analyzed, 
so any discussions about recovery time are meaningless.  Temporal 
correctness cannot be defined in these cases.
\end{enumerate}


\section{Conclusions}

EHW-based reconfiguration is a viable method of performing fault 
recovery in systems without redundant hardware.  Fault-tolerant 
systems are real-time systems.  Consequently, any attempts to 
intrinsically evolve a new hardware configuration must consider 
the device programming time, the fitness evaluation time, and the 
evolutionary algorithm overhead time because they all contribute
to the reconfiguration time.  Eq.~(\ref{eqn:2}) gives a formula 
that estimates the intrinsic reconfiguration time.



It has been shown neither a large population size nor thousands 
of generations are necessary to have reconfiguration searches 
with surprisingly long finishing times.  
However, a long search time by itself  is 
not enough to reject reconfiguration as a fault recovery method. 
Intrinsic reconfiguration can be used for fault recovery so long as
it finishes before the mandatory recovery deadline.

Finally, a first principle for fault recovery was given.
All intrinsic reconfiguration fault recovery methods are stochastic
processes---which means they can never satisfy the first principle 
because temporal correctness cannot be satisfied.  This does not mean 
intrinsic reconfiguration can't be used be fault recovery.  The 
designer just needs to be aware there is some risk involved.
Intrinsic reconfiguration can be used so long as the designer believes
the risk is acceptable.



\bibliography{fault}


\end{document}

