Reliable State Machines

1.

Reliable State Machines
Dr. Gary R Burke
California Institute of Technology
Jet Propulsion Laboratory
10/14/2005 Caltech
1

2.

outline
• Background
– JPL MER example
• JPL FPGA/ASIC Process
– Procedure
– Guidelines
• State machines
– Traditional
– Highly Reliable
– Comparison
10/14/2005 Caltech
2

3.

10/14/2005 Caltech
3

4.

10/14/2005 Caltech
4

5.

10/14/2005 Caltech
5

6.

MER Mission example
• Large number of FPGAs
• Mostly fuse programmable – but at least
one RAM programmable FPGA
• Several ASICs
• Many standard parts eg Microprocessor,
RAM chips.
10/14/2005 Caltech
6

7.

10/14/2005 Caltech
7

8.

10/14/2005 Caltech
8

9.

10/14/2005 Caltech
9

10.

10/14/2005 Caltech
10

11.

10/14/2005 Caltech
11

12.

10/14/2005 Caltech
12

13.

10/14/2005 Caltech
13

14.

FPGA/ASIC Process
• JPL needs to ensure design process is sound
• A bug in an FPGA/ASIC can halt a billion dollar
mission
• Tight schedules can result in inadequate testing
• Inadequate version control can result in the wrong
code
• First Pass success important for ASIC design
10/14/2005 Caltech
14

15.

FPGA/ASIC Process
To ensure a quality product:
Requirements are correct and do not change
Specification is complete
Design will meet the specification and
requirements
• Testing has covered all possible cases
10/14/2005 Caltech
15

16.

FPGA/ASIC Process
• Peer reviews by experts to check the design
and design approach
• Formal Reviews to ensure design process is
adequate, and to sign off on the design
• Documentation for review and archiving
• Check-lists to ensure all problems are fixed
10/14/2005 Caltech
16

17.

FPGA/ASIC Process
• Configuration Management to ensure
correct versions are used
• Verification Matrix – which documents all
testing
• Checking tools e.g. Lint, DRC; all errors,
and warnings documented
10/14/2005 Caltech
17

18.

ASIC PROCESS
Proto Board
Design
Proto Board
Test
Firmw are Design:
Firmw are
Compilation
ASIC Design Process
GRB - 2/1/04
Specification:
START
IDR
Review
HDL Design:
PDR
Review
Analog Circuit
Design:
Inputs
outputs
process
Level 5
Requirements
Preliminary
Specification
CM plan
Test approach
Create
Specification.
Preliminary
design.
Test Approach.
ASIC/FPGA/
package
selection.
Configuration
management
Review plan
Select Foundry
Partition Design
Specify IPs
FT approach
Structural
Design
sign-off
Physical Design:
Complete Layout::
Physical
Design
sign-off
CDR
Review
Analog Layout
Design:
Preliminary
Specification
CM plan
Test approach
RTL code,
Test Plan
Updated
Specification
Structural code
Test Vectors
Test vectors
Layout
netlist
V-matrix
Structural code
Test Vectors
RTL code,
Test Plan
Updated Specification
Conceptual
RTL Design;
Design
RTL simulation
&
Requiremen DFT;simulation coverage
V test bench & modeling
ts
Trial Synthesis
Review
Trial Timing analysis
Is ASIC
Trial testability anal.
ready to
Test Plan
procede
Initial Firmware design
with
SEU mitigation plan
detailed
Fault tolerant plan
design?
Lint verification
pinout defined
code walkthrough
Structural design:
PDR
Is ASIC
Ready to
procede
with
structural
design?
10/14/2005 Caltech
Synthesis
Timing analysis
testability
Prototype; ATPG
Vendor software
Gate level
verification
Firmware design
Test vectors
TV coverage
Trial P&R
Prototype FPGA
Formal Verification
Structural
Design
Peer
Review
and
Sign-off
Physical Design:
Place and Route
Timing analysis BA
Update Prototype
Test Vectors BA
Vendor software
BA
Gate level
verification BA
Chip layout
Physical
Design
Peer
review
and
sign-off
18
Complete Layout::
Chip integration
DRC
LVS
ERC
CDR
Checklist
CDR
Review: Is
ASIC ready
for
fabrication?
chip
fabrica
tion

19.

FPGA PROCESS
FPGA Design Process
GRB - 2/1/04
Firmw are
Verification
Firmw are Design:
START
Specification:
IDR
Review
HDL Design:
PDR
Review
Prot-board
design
Inputs
outputs
process
Level 5
Requirements
Preliminary
Specification
CM plan
Test approach
Create
Specification.
Implementation
Partition and
Test Approach.
FPGA device
and package
selection.
Configuration
management
Schedule with
Plan for Reviews
Specify IPs
FT approach
RTL code,
Test Plan
Updated Specification
RTL code,
Test Plan
Updated Specification
10/14/2005 Caltech
FPGA Final Build
CDR
Proto-Board
Test
Preliminary
Specification
CM plan
Test approach
Conceptual
HDL Design;
Design
HDL simulation
&
DFT;simulation
coverage
Requiremen
V test bench & modeling
ts
Trial Synthesis
Review
Trial Timing analysis
Is FPGA
Test Plan
ready to
Initial Firmware design
procede
SEU mitigation plan
with
Fault tolerant plan
detailed
Lint verification
design?
pinout defined
code walkthrough
prot-board design
FPGA Prototype
design:
Configuration
code
Test Vectors
Is FPGA
Ready to
procede
with
synthesis?
Synthesis
Timing analysis
testability
Prototype
FPGA software
Gate level
verification
Firmware design
Test vectors
TV coverage
Prototype FPGA
Configuration
code
Test Vectors
Verification
matrix;
Test vectors
Physical Design:
Place and Route
Timing analysis
Update Prototype
Test Vectors
Vendor software
System Test
19
CDR
Checklist
CDR
Review: Is
flight FPGA
ready for
personalizat
ion?
FPGA fuse
programming

20.

Guidelines
• Define set of rules for HDL design
• Reduce ambiguity
• Clarify design to be easily checked and
reviewed
• Implement most reliable design techniques
10/14/2005 Caltech
20

21.

Fault Tolerant State Machines
• The state machine needs to be tolerant of
single event upsets
• State machine should not hang
• State machine should always be in a defined
state
• No asynchronous inputs to state machine
• Default state must be specified
10/14/2005 Caltech
21

22.

State Machines
• A state machine is a sequential machine that when
built into an FPGA or ASIC controls the
sequencing of actions in the digital logic
• The current state of a machine is held in a state
register which is updated on a clock
• The next value of the state register (next state) is
derived from the current state and the inputs
• Outputs from the state machine are decoded from
the state register and can also be combined with
the inputs
10/14/2005 Caltech
22

23.

State-Machine (SM) Encoding
• Each distinct state of the SM is represented
by a unique code
• The allocation of these binary codes to
states is the Encoding
• The simplest encoding is Binary
• In Binary encoding each state is given the
next available binary number in sequence.
10/14/2005 Caltech
23

24.

Other SM Encoding
• 1-hot encoding
– The number of bits in the code is equal to the number of
states. Each encoded state has just 1 bit in the encoded
word set to a 1 (the rest are 0)
– The advantage is that when optimized for non-reliable
use, the amount of logic needed is less than Binary
encoding, and it can be faster. One bit change with a
SEU will result in a bad code which can be detected.
– The disadvantage is the increased number of bits results
in more flip/flops and therefore more targets for SEUs.
The SEU advantage is lost when the 1-hot encoding is
optimized.
10/14/2005 Caltech
24

25.

Other SM Encoding- cont
• Grey-code
– Similar to binary encoding, except the codes are
chosen so that in the main state-machine
sequence only 1 bit changes at a time
– No major advantage over binary with this code.
Decoded outputs from the state register can
make use of the nature of the encoding to
simplify producing a glitch free output.
10/14/2005 Caltech
25

26.

Other SM Encoding- cont
• H2-code
– This variation on Binary encoding uses one
extra bit to ensure all codes are separated by a
Hamming distance of 2. That is, it will take 2
changes in the state register to reach another
known state.
– The advantage is that it has less bits and so less
SEU targets than 1-hot, but retains the fault
tolerance of the un-optimized 1-hot encoding.
10/14/2005 Caltech
26

27.

Other SM Encoding- cont
• H3-code
– This extension on H2 encoding uses additional bits to
ensure all codes are separated by a Hamming distance
of 3. That is, it will take 3 changes in the state register
to reach another known state.
– The advantage is that the SM can be designed such that
a single change in the state register has no effect on the
state.
– The disadvantage is that it requires more logic to
implement
10/14/2005 Caltech
27

28.

Synthesis
• To check the overhead of each of the state
machines, they were individually synthesized
• Finite state machine optimization is turned off
• A clock frequency of 50 MHz is used
• Target device is a Xilinx Spartan 2, speed grade 6
• Error injection circuitry is not included
10/14/2005 Caltech
28

29.

Synthesis Results
State
Machine
Size
# Slice
Flip
Flops
# of 4
input
LUTs
Clock
Max
Minimum
Period Synthesized Period
(ns)
Frequency
(ns)
(MHz)
Binary
4
8
12
16
24
32
One Hot
4
8
32
16
24
32
2
3
4
4
5
5
7
15
25
38
50
96
20
20
20
20
20
20
272.1
178.8
129.6
122.1
109.6
94.5
3.7
5.6
7.7
8.2
9.1
10.6
4
8
12
16
24
32
10
20
31
41
63
237
20
20
20
20
20
20
238.2
194.8
173.0
148.9
148.9
68.6
4.2
5.1
5.8
6.7
6.7
14.6
10/14/2005 Caltech
State # Slice # of 4 Clock
Max
Minimum
Machine Flip input Period Synthesized Period (ns)
Size
Flops LUTs (ns) Frequency
(MHz)
Hamming 2
4
8
12
16
24
32
Hamming 3
4
8
12
16
24
32
3
4
5
5
6
6
8
22
41
49
84
107
20
20
20
20
20
20
226.6
133.5
124.5
117.8
91.5
87.3
4.4
7.5
8.0
8.5
10.9
11.5
5
6
7
7
9
9
15
42
55
71
91
137
20
20
20
20
20
20
162.8
117.4
105.0
102.6
88.7
83.5
6.1
8.5
9.5
9.8
11.3
12.0
29

30.

Four Bit State Encoding
4 Bit State Encoding
16
15
14
12
10
10
# of Slice Flip Flops
8
8
# of Four Input LUTs
7
6.1
6
3.7
4
4
4.4
4.2
5
3
2
2
0
Binary
One Hot
10/14/2005 Caltech
Hamming 2
Hamming 3
30
Clock Period (ns)

31.

Eight Bit State Encoding
8 Bit State Encoding
25
22
20
20
15
15
15
# of Slice Flip Flops
# of Four Input LUTs
Clock Period (ns)
10
8
5.6
5
8.5
7.5
6
5.1
4
3
0
Binary
One Hot
10/14/2005 Caltech
Hamming 2
Hamming 3
31

32.

Twelve Bit State Encoding
12 Bit State Encoding
60
55
50
41
40
# of Slice Flip Flops
31
30
# of Four Input LUTs
25
Clock Period (ns)
20
12
7.7
10
4
5.8
8.0
5
7
9.5
0
Binary States
One Hot
10/14/2005 Caltech
Hamming 2
Hamming 3
32

33.

Sixteen Bit State Encoding
16 Bit State Encoding
80
71
70
60
49
50
# of Slice Flip Flops
41
38
40
# of Four Input LUTs
Clock Period (ns)
30
20
10
16
8.2
4
6.7
8.5
5
7
9.8
0
Binary
One Hot
10/14/2005 Caltech
Hamming 2
Hamming 3
33

34.

Twenty-Four Bit State Encoding
24 Bit State Encoding
100
91
90
84
80
70
63
60
# of Slice Flip Flops
50
50
# of Four Input LUTs
40
Clock Period (ns)
30
24
20
10
5
9.1
6.7
10.9
6
9
11.3
0
Binary
One Hot
10/14/2005 Caltech
Hamming 2
Hamming 3
34

35.

Thirty-Two Bit State Encoding
32 Bit State Encoding
250
237
200
150
137
# of Four Input LUTs
107
96
100
# of Slice Flip Flops
Clock Period (ns)
50
32
5
10.6
14.6
6
11.5
9
12.0
0
Binary
One Hot
10/14/2005 Caltech
Hamming 2
Hamming 3
35

36.

Fault Injection Test
• A test circuit is generated with an example of each
state machine executing the same task, plus a
reference state machine
• The task chosen requires a16-state state machine,
to detect a 16-bit pattern in a serial input stream
• An error generator injects faults into all state
machines except the reference state machine
10/14/2005 Caltech
36

37.

Error Injection Test Continued
• The outputs of each state machine are compared to
the reference output
• A set of counters tallies the comparison outputs
• 2 types of failure are logged for each state
machine:
– Failure to detect pattern
– False detection of pattern (false-positive)
10/14/2005 Caltech
37

38.

Error Injection Test Continued
• Non-key patterns are 1-bit different from the key pattern,
to increase the likelihood of a false match
• Error rate can vary, set to 1:199 clocks in example
• Errors are weighted by distributing them pseudo-randomly
over 16 bits. A state machine with a word size of n,
receives n/16 of the total faults
• Synchronous fault injection is before the state register
• Asynchronous fault injection is after the state register
• All results are from actual implementation of the test
circuits in a Spartan 2 FPGA
10/14/2005 Caltech
38

39.

Error Rate – Synchronous Faults
Synchronous (rate=199)
0.1
0.09
0.08
errors per pattern
0.07
0.06
single
false-pos single
0.05
double
false-pos double
0.04
0.03
0.02
0.01
0
Binary
1-Hot
10/14/2005 Caltech
H2
H3
39

40.

Error Rate – Asynchronous Faults
Asynchronous (rate=199)
0.02
0.018
0.016
errors per pattern
0.014
0.012
single
false-pos single
0.01
double
false-pos double
0.008
0.006
0.004
0.002
0
Binary
1-Hot
10/14/2005 Caltech
H2
H3
40

41.

Error Rate – Asynchronous Pulse Faults
Pulse (rate=199)
0.018
0.016
0.014
errors per pattern
0.012
single
0.01
false-pos single
double
0.008
false-pos double
0.006
0.004
0.002
0
Binary
1-Hot
10/14/2005 Caltech
H2
H3
41

42.

Results: Binary Encoding
• Lowest resources used
• Second fastest speed after One Hot
– Fastest for small number of states
• Second-most sensitive to errors
• Generates false-positive errors i.e. reports
false pattern matches
10/14/2005 Caltech
42

43.

Results: One Hot Encoding
• No false-positive errors (single faults)
• Fastest speed except for small number of states
and large number of states
• Uses more resources than Binary
• Inefficient for large number of states
• Worst fault tolerance of all encoding tested
• Has 2x the error rate of binary encoding
10/14/2005 Caltech
43

44.

Results: Hamming Distance of 2 (H2)
Encoding
• No false-positive errors (single faults)
• Better Fault Tolerance than Binary
• More resources needed than One Hot,
except for large number of states
10/14/2005 Caltech
44

45.

Results: Hamming Distance of 3 (H3)
Encoding
• Zero single-fault errors
– Immune to synchronous and asynchronous
errors
• Lowest double-fault errors
• Most resources used (*)
~2x binary encoding
• Slowest speed (*)
(*) Except for large number of states
10/14/2005 Caltech
45
English     Русский Правила