Metastability Tolerant Computing

# Metastability Tolerant Computing

Ghaith Tarawneh.red[*], Matthias Függer, and Christoph Lenzen

---

.footer.venue[Async17 - San Diego, 22<sup>nd</sup> May 2017]

---

## POETS Project Team

---

## Outline

.active.circle[1] .big[Introduction]
.active.vruler[ ]
.active.circle[2] .big[The Model]
.active.vruler[ ]
.active.circle[3] .big[Use Case (NOC Routing)]
.active.vruler[ ]
.active.circle[4] .big[Conclusion]

---

# Introduction

---

## Overview

- We present a method to perform .emph[quasi-reliable computations] in the
presence of metastability.

- The method involves .emph[skipping synchronization] but using a combination of:

* State encoding
  * Control flow design
  * Ordering of data operations

to .emph[constrain circuit behaviour under metastability.]

- .emph.red[Disclaimer :] not a general solution!

---

## Skipping Synchronization

... is usually .emph.red[a very bad idea] because:

1. State bits may become metastable and cause .emph[invalid state transitions].

2. Data bits may become metastable and cause .emph[data corruption].

3. Metastability may .emph[propagate], putting other circuits at risk of (1) and (2).

Can't do much about the above, but can ...

---

# The Model

---

## Metastability in FSMs

Handshake and clock domain crossing logic is usually at some .blue.emph[idle state],
waiting for an asynchronous event (here .emph[req]).

The arrival of .emph[req]
triggers a series of transitions, always ending at the idle state.

---

## Metastability in FSMs

Occasionally, the arrival of .emph[req] may drive state flip-flops into
metastability.

This may cause .underlined-red.emph.red[unintended state transitions] that violate the FSM spec.

---

## Metastability in FSMs

How can we tell which unintended transitions may occur in a certain FSM?

---

## Metastability in FSMs

Consider the idle state and its successor ...

---

## Metastability in FSMs

Assume we choose state encoding as such ...

---

## Metastability in FSMs

Bit distance between 000 and 111 is 3 so all state flip-flops may become
metastable after .emph[req] arrives!

This encoding permits unintended transitions from idle .emph.red[to all other states!]

---

## Metastability in FSMs

Better state encoding can minimize these transitions. In this case choosing
000 and 001 permits only two transitions from .emph[req], both according to spec.

---

## Metastable Closure

* In general, undesired state transitions can be enumerated
as the .emph[metastable closure].red[*] of the state function.

* This is a worst-case consideration of metastability propagation in state
combinational logic.

<p style="font-size: 12pt; position: absolute; bottom: 50pt; width: 80%;">
.red[*] Friedrichs, Stephan, Matthias Függer, and Christoph Lenzen.
"Metastability-Containing Circuits."  arXiv preprint
arXiv:1606.06570  (2016).
</p>

---

## Isolating Unintended Transitions

<table>
	<tr>
		<td style="width: 20%; vertical-align: top;">
			.definition[Unsafe Region]
		</td>
		<td style="width: 2%; vertical-align: top;">
			:
		</td>
		</td>
		<td>
			States in which the FSM may be metastable,
			defined as all states within .emph[k] transitions from the idle state.
		</td>
	</tr>
</table>

<table>
	
	<tr>
		<td style="width: 20%; vertical-align: top;">
			.definition[Safe Region]
		</td>
		<td style="width: 2%; vertical-align: top;">
			:
		</td>
		</td>
		<td>

States that cannot be reached until any metastable events have
			been resolved (i.e. minimum of .emph[k] transitions from idle
			state).

</td>
	</tr>
</table>

---

## Isolating Unintended Transitions

* Unsafe states are .emph[synchronizing states] in which metastable events may
propagate between state flip-flops.

* Synchronization time is .emph[k × propagation delay slack] in state
comb. logic.

---

## Metastability Containment

.definition[Component] : a state machine with associated datapath logic that
serves as a container for metastable states.

---

## Metastability Containment

Components are functional units that:

.check[Follow their nominal spec most of the time]
.check[Fail occasionally, in predictable and benign ways]
.check[Do not allow metastability to propagate beyond]

∴ Components are .emph[synchronizers that compute].

<br/>

When designing components, we can:

.check[Select which control/data operations to .emph[attempt optimistically]]
.check[Select which control/data operations to .emph[perform reliably]]
.check[Select .emph[arbitrary levels of reliability] for optimistic operations]

---

## Failure Types and Rates

#### 1. Synchronization Failure

When metastability .emph[reaches the safe region] (akin to propagating beyond a synchronizer). Its probability is given by

.center[
<img class="equation" src="http://latex.codecogs.com/svg.latex?\text{MTBF}=\frac{e^{t_s/\tau}}{f_c f_d T_w}" border="0"/>
]

where <img class="equation" src="http://latex.codecogs.com/svg.latex?t_s = k\,\,\times" border="0"/> propagation delay slack in .underlined[state combinational logic].

#### 2. Datapath Failures

More frequent events in which .emph[computations are corrupted],
expressed as a probability per handshake

.center[
<img class="equation" src="http://latex.codecogs.com/svg.latex?P=T_w f_c \, e^{-t_s/\tau}" border="0"/>
]

this time taking <img class="equation" src="http://latex.codecogs.com/svg.latex?t_s" border="0"/> as propagation delay slack in .underlined[state and datapath comb. logic].

---

# Use Case

---

## NOC Router

We applied the method to an .underlined[RX transceiver] in a classic 5-port NOC router
(store-and-forward, X-Y routing).

We assume .underlined[asynchronous communication] between the router and its
neighbours.

---

## Transceiver FSM

Unsafe region: .code[ST_IDLE] and .code[ST_LATCHED]

---

## Transceiver Datapath Failures

Caused by the corruption of registers that are write-accessible in unsafe
states:

.spaced-list[
1. .code2[REG_FLIT] (flit register): latches the flit received via the channel interface, written when entering .code[ST_LATCHED]
2. .code2[REG_OUT_CHANNEL] (outgoing channel register): holds the fetched destination of the current packet, written when entering .code[ST_RC]
3. .code2[REG_BUFF_WR_IND] (buffer write index): holds the index of the current flit, written when entering .code[ST_BUF]
4. .code2[MEM_BUFF] (packet buffer): stores current packet, written when entering .code[ST_BUF]
]

---

## Transceiver Failure Rates

We synthesized the router using a commercial 65nm gate library, targetting a
clock frequency of 700 MHz, to obtain realistic estimates of propagation delay
slack and calculate failure rates..red[*]

- State combinational logic had a slack of .emph[1.1ns] corresponding to a synchronization MTBF of .emph[5 × 10<sup>7</sup> years]

- Worst case slack (in state and datapath logic) was .emph[0.32ns] corresponding to a failure probability per handshake .emph[P ≤ 10<sup>-7</sup>]

---

## Simulations

* We ran a .underlined[cycle-accurate simulation] of a NOC consisting of 4 × 4
routers with dummy packets generators and consumers, using:

1. Conventional routers with 2-FF synchronizers
  2. Synchronizer-free metastability-containing routers

---

## Simulations

* For (2), we simulated metastability effects by writing random values to
vulnerable registers at the calculated datapath failure probability (.emph[P = 10<sup>-7</sup>])

* We measured:

* Mean packet delivery time
	* Packet corruption rate
	* Packet loss rate

---

## Results

#### Performance

* Removing synchronizers improved packet delivery time by .emph[17.7 – 26.2%]

---

## Results

#### Packet Transfer Reliability

<center>
<table class="results">
	<tr>
		<td>
		</td>
		<td>
			.emph[2-FF NOC]
		</td>
		<td>
			.emph[Meta NOC]
		</td>
	</tr>
	<tr>
		<td>
			Packet corruption rate
		</td>
		<td>
			0
		</td>
		<td>
			 ≤ 0.0002%
		</td>
	</tr>
	<tr>
		<td style="border-bottom: none;">
			Packet loss rate
		</td>
		<td style="border-bottom: none;">
			0
		</td>
		<td style="border-bottom: none;">
			≤ 0.001%
		</td>
	</tr>
</table>
</center>

<br/>

#### Shifting the Problem of Metastability

- Packet delivery reliability is well studied problem in NOC literature..red[*]

- We managed to "capture" metastability and limit its effects to errors that
we know how to deal with.

---

# Conclusion

---

## Conclusion

* Presented a method to perform quasi-reliable computations in the presence of
metastability in state and data logic

* The method limits control flow and datapath failures to a subset
computations whose failures can be afforded

* Demonstrated the design scheme using NoC routing as a target application

---

## Conclusion

---

## Conclusion

count:false

.big.center[
Thank You
]