# Burst-Mode Asynchronous Controllers on FPGA

Authors: Duarte L. Oliveira; Marius Strum; Sandro S. Sato
Journal: International Journal of Reconfigurable Computing
 (2008)

---

## Abstract

FPGAs have been mainly used to design synchronous circuits. Asynchronous design on FPGAs is difficult because the resulting circuit may suffer from hazard problems. We propose a method that implements a popular class of asynchronous circuits, known as burst mode, on FPGAs based on look-up table architectures. We present two conditions that, if satisfied, guarantee essential hazard-free implementation on any LUT-based FPGA. By doing that, besides all the intrinsic advantages of asynchronous over synchronous circuits, they also take advantage of the shorter design time and lower cost associated with FPGA designs.


---

## Body

## 1. Introduction

Due to the increasing complexity of
digital systems combined with the market drive for higher performance, there
has been an increased interest about asynchronous circuits [1, 2]. Asynchronous
circuits do not present clock distribution related problems like clock skew.
The circuits have low power consumption, better modularity, robustness toward
variations in temperature, and low emission of electromagnetic radiation [3].
One known weakness of asynchronous circuits has been the difficulty to design
hazard-free circuits and to solve the critical races [3]. Furthermore, asynchronous circuits frequently cannot
benefit from the use of FPGAs due to the extra difficulty imposed by their
fixed architecture to deal with hazards [4].Asynchronous
circuits can be classified according to different criteria like its function
(controller—datapath); delay model (delay insensitive—quasi-delay insensitive—speed independent—generalized fundamental mode (GFM)) [2]; styles
(global asynchronous local synchronous—self-timed systems—micropipeline—speed-independent controllers—burst-mode controllers) [5–9].Burst-mode
asynchronous controllers proposed by Nowick [9, 10] are a popular class of
finite state machines. They allow multiple inputs changes. They operate
according to the GFM, meaning that a new state transition may only start when
the whole circuit (gates and lines) is stable. This paper addresses burst-mode
asynchronous controllers. Their advantages are the use of basic gates,
similarity with synchronous design. These controllers have been adopted in
important industrial and academic designs [11–13].FPGAs are popular
components for prototyping and production of digital circuits due to their low
cost and short design time. Their focus has been on synchronous digital
circuits. There have been some recent efforts to prototype asynchronous
circuits on both commercial [14–17] and academic FPGAs [4, 18–20].Burst-mode
controllers are usually designed using a logic-driven design methodology [21].  There are two reasons why off-the-shelf FPGAs are not fit for
burst-mode asynchronous controllers [4, 14, 22].
(1)
Themapping process
of burst-mode Booleans functions (equations of next state—controllers) to
logic blocks (macrocells) may introduce logic hazards.(2)
Theinternal routing among logic blocks may introduce significant delays
that may result in essential hazards.


### 1.1. Avoiding Logic Hazards in Burst-Mode Controllers

The burst-mode specification proposed by Nowick isfunctional-hazard
free [23]. Nowick also proposed a method to produce logic-hazard free burst-mode Boolean functions [24]. Furthermore, Siegel et al. [25] proposed a technique to decompose large
fan-in burst-mode Boolean functions without
introducing logic-hazards. Finally, Maheswaran and Akella [15] and Hauck et al. [4] showed that
if Booleans functions are functional-hazard free then they can be mapped
on ordinary LUT-based FPGAs without presenting logic hazards [26].


### 1.2. Avoiding Essential Hazards in Burst-Mode Controllers

Yun and Dill [27] and Nowick and Coates [10]
proposed the insertion of delay elements on the feedback wires to avoid
essential hazards in burst-mode controllers.
However, this solution is not adequate for FPGAs because these components are
not designed to ease the insertion of delay elements. Furthermore, delay
elements degrade the circuit cycle time, area, and reliability.In this paper, we demonstrated asufficient
condition that guarantees essential hazard-free operation of any
type of burst-mode controller when mapped on any type of LUT-based FPGA component
without the need of extra delay elements. The proof is based on two new
concepts: (1) essential signals; (2) essential super states. The
essential hazard-free operation is guaranteed if the following conditions are
satisfied:
(1)
essential hazard-free
specification: for all state transitions in a burst-mode specification, if the
label contains a nonempty output burst, it must also contain at least
oneessential input signal;(2)
essential hazard-free
implementation: starting from an essential hazard-free specification, while
building the burst-mode flow map, allsingle
states whose incident state transitions are labeled with nonempty output
bursts must be transformed into essential super states.Furthermore, whenever a burst-mode
specification does not satisfy the first condition, we present twofunctional
transformations that create essential input signals without
altering the original functionality:
(1)
reduction of
input concurrency: transforms concurrent transitions into sequential
transitions whenever acceptable (but there is a latency penalty);(2)
addition of dummy input signals (but
there is an area penalty).This paper is divided in four sections. Section3
briefly explains the burst-mode specifications. Section 2
presents the essential signal and essential super-state concepts and explains
the two functional transformations. Section 4 presents our method and
illustrated with an example. Section 5 shows our experimental results presenting the latency
and area penalties found on nine known and one homemade benchmark. Section 6
presents our conclusions and future work.


## 1.1. Avoiding Logic Hazards in Burst-Mode Controllers

The burst-mode specification proposed by Nowick isfunctional-hazard
free [23]. Nowick also proposed a method to produce logic-hazard free burst-mode Boolean functions [24]. Furthermore, Siegel et al. [25] proposed a technique to decompose large
fan-in burst-mode Boolean functions without
introducing logic-hazards. Finally, Maheswaran and Akella [15] and Hauck et al. [4] showed that
if Booleans functions are functional-hazard free then they can be mapped
on ordinary LUT-based FPGAs without presenting logic hazards [26].


## 1.2. Avoiding Essential Hazards in Burst-Mode Controllers

Yun and Dill [27] and Nowick and Coates [10]
proposed the insertion of delay elements on the feedback wires to avoid
essential hazards in burst-mode controllers.
However, this solution is not adequate for FPGAs because these components are
not designed to ease the insertion of delay elements. Furthermore, delay
elements degrade the circuit cycle time, area, and reliability.In this paper, we demonstrated asufficient
condition that guarantees essential hazard-free operation of any
type of burst-mode controller when mapped on any type of LUT-based FPGA component
without the need of extra delay elements. The proof is based on two new
concepts: (1) essential signals; (2) essential super states. The
essential hazard-free operation is guaranteed if the following conditions are
satisfied:
(1)
essential hazard-free
specification: for all state transitions in a burst-mode specification, if the
label contains a nonempty output burst, it must also contain at least
oneessential input signal;(2)
essential hazard-free
implementation: starting from an essential hazard-free specification, while
building the burst-mode flow map, allsingle
states whose incident state transitions are labeled with nonempty output
bursts must be transformed into essential super states.Furthermore, whenever a burst-mode
specification does not satisfy the first condition, we present twofunctional
transformations that create essential input signals without
altering the original functionality:
(1)
reduction of
input concurrency: transforms concurrent transitions into sequential
transitions whenever acceptable (but there is a latency penalty);(2)
addition of dummy input signals (but
there is an area penalty).This paper is divided in four sections. Section3
briefly explains the burst-mode specifications. Section 2
presents the essential signal and essential super-state concepts and explains
the two functional transformations. Section 4 presents our method and
illustrated with an example. Section 5 shows our experimental results presenting the latency
and area penalties found on nine known and one homemade benchmark. Section 6
presents our conclusions and future work.


## 2. Burst-Mode Specification

The BM specification is
represented as a state transition diagram. Each transition is triggered by an
input burst (single- or multiple-input changes) causing the occurrence of an
output burst (that may be empty or nonempty). It is necessary to define an
initial state. State transitions are represented by arcs, which are labeled
with their corresponding input/output bursts. The signals are always transition
sensitive (0→1, or 1→0). Input bursts may not be empty. The
input signals are monotonic, changing only once during each state transition.
The BM specification has to obey the polarity property, the unique entry point
and the maximal set property [23].Figure1 shows a BM specification. The
input signals are a,b, and c while the output signals are x and y. For example, state transition 7[a+b−/x+]→2 means that if a changes from 0 to 1 and b changes from 1 to 0, the output x will change from 0 to 1. State 0 is
the initial state. Figure 2 shows the corresponding burst-mode flow map (2D map) [27]. Several
tools, like Minimalist [28], 3D [27], and ATACS [29] have been proposed to
synthesize controllers from a textual description of the burst-mode
specification. These tools generate an
independent netlist of the technology
(next-state equations of the type sum of products).Figure 1
BM specification.Figure 2
BM flow map.


## 3. Hazard-Free BM Conditions

BM asynchronous controllers may be
subject to sequential hazards. Essential hazards, like transient essential
hazard or steady-state essential hazard, are inherent to the sequential function
and are not necessarily associated to a particular implementation of the
circuit. The concept of essential hazard has been originally defined by Unger [30]
in connection with fundamental-mode controllers.This concept has been generalized for BM
controllers and may be explained using the total state concept. A total stateA(I,O) is a vector composed of all the input (I) and output (O)
signal values in the specification. A total state corresponds to one single
cube (cell) on a burst-mode flow map (see Figure 2). For
example, the total state 2 of the
Figure 2 is (a,b,c,x,y)=10011. There may be n! paths on the BM flow map
corresponding to the transition from total state A(I1,O1) to total state B(I2,O2) (labeled with an
input/output burst Ib/Ob), n being the number input signals in Ib. These paths cover the set {A,B,C,…,N}, where A is the initial
total state, B is the final total state, and C,…,N are
intermediary total states.


### 3.1. Essential Hazard

Generalized Unger Rule (30) (gur): The Triple Sequential Input Burst
LetA(I1,O1) and B(I2,O2) be two total states in the BM flow map and Ib/Ob the input/output burst that activates the transition A→B. Let N be the number of the input burst
signals. Consider the following transitions sequence:
T1:A[Ib]→B; (transition 1 is A→B activated by Ib)T2:B[Ib_inverted_polarity]→Ci (i=1,…,k are possible final
states);T3:C[Ib]→Dj (i=1,…,n are possible initial
states), (j=1,…,m are possible final states).Definition 1.
There is a potentialsteady-state essential hazard in
the A→ B transition if, applying the GUR rule, any final total state Dj(j=1,…,m)≠B.Definition 2.
There is a potentialtransient essential hazard in the A→B transition if, applying the GUR rule, there is a total state I(≠A and ≠B) on any path of transitions B→Ci or Ci→Dj that produces an output signal different from any
value occurring on any path of transition A→B.
A potential essential hazard can be
detected applying the GUR rule from any initial state. For example, Figures3(a)
and 3(b) show two paths for the 0→1 state transition on the BM flow map of
Figure 2. Consider the 0[b+a+/x+]→1 path on Figure 3(a). According to
the GUR rule we must apply the following activation sequence: T1(b+a+),T2(b−a−),T3(b+a+). The corresponding
paths on the BM flow table are
T1:abcxy={00000→01000→11000→11010},T2:abcxy={11010→10010→10011→00011→00001},T3:abcxy={00001→01001→11001}. As the final total state (11001) after the last activation (T3)
is different from the final total state (11010) after the first
activation (T1), then a steady-state
essential hazard has occurred. Figure 3(a) shows the path T2 and Figure 3(b) shows the path T3.Part of the BM flow map of Figure2: (a) path T2;
(b) path T3 (final total state—FTS).
(a)(b)


### 3.2. BM-EHF Condition

An input signal in a BM specification is acontext signal in an A→B transition if it does not change during this transition (it is not on the
label) while it is a trigger signal if it is labeled during this transition. The input burst of each state
transition can be represented by an input transition cube (ITC). For example,
the ITC for state transition 7→2 on Figure 1 is abc=220 (2 means do not care). In this example a and b are trigger signals
while c is a context signal (whose value is 0).Definition 3.
LetA and B be a
pair of total states in a BM specification and Ib/Ob be the input/output burst for the A→B transition. Let Es be one input signal (Es∈Ib).Es is an essential
signal if it is a context signal on all transitions incident on state A and is a trigger signal on the transition A→B.
For instance (see
Figure1), a,b,c are not essential on transitions 4→0, 1→2, and 2→3 because they are trigger signals on transitions 3→4, 0→1, and 7→2. Signal b is essential on
transition 7→2 because it is a context signal on
transition 6→7. On transition 6→7 both a and c are essential signals.Lemma 1.
A BM specification is essential hazard free (BM-EHF) if and only if for each state transition labeled byIb/Ob, if Ob≠∅, there must
be at least one essential input signal.Proof.
Let T1(A→B) and T2(B→C) be two sequential state transitions of a BM-EHF specification. ITCT1 and ITCT2 are their respective input transition cubes. Suppose that
the transition T2 input burst does not contain as essential
signal. Then ITCT1⊆ITCT2, which means that the C final total state belongs to a path on ITCT1. This fact violates
Definitions 1 or 2.Figure4 shows the HP-mp-for-pkt benchmark [12, 13]. On all transition labels there is at least one essential
signal. Therefore, it is a BM-EHF specification.Figure 4
BM-EHF specification.There are two ways to transform
nonessential hazard-free BM specifications into a BM-EHF specification.


### 3.3. Reduction of Input Burst Concurrency

The transformation consists of decomposing the input burst
labeled on a state transition generating two-state transitions. For example,
Figure5 shows a reduced concurrency BM-EHF specification equivalent to the BM
specification in Figure 1 in which the concurrency has been reduced.  Analyzing the BM specification in Figure 1,
we found state transitions 1→2 and 2→3
without essential signals. Decomposing state transitions
0[b+a+/x+]→1
into 0[b+/]→A[a+/x+]→1 and
decomposing state transition 7[a+b−/x+]→2
into 7[a+/]→B[b−/x+]→2, we obtained
the BM-EHF specification shown in Figure 5. It
is EHF because transitions 4→0 and 7→B
contain empty output bursts while all other transitions contain essential
signals.Figure 5
Concurrency reduction.


### 3.4. Insertion of Essential Signals

This transformation
consists of inserting the smallest number of dummy essential signals in all
state transitions without essential signal. For example, Figure6 shows an
BM-EHF specification 	equivalent to the specification in Figure 1 in which adummy
essential signal
d
has been
added to state transitions 1→2 and 2→3. This transformation has a higher cost
than the previous one because it increases the number of input signals (Ib), modifying the interaction with the external environment.Figure 6
Inserting essential signal.If one observes the 2→3 state transition in Figure 6, the
conclusion is that a is essential on transitions 1→2→3, while d is essential on
transitions 7→2→3.


### 3.5. Super-State Condition

Lemma1 is a necessary
and sufficient condition for an essential hazard free specification but not for hazard-free implementation. The
super-state concept will guarantee the latter condition.Definition 4 (super-state).
Consider an input burstIb(a,b,…,n) and an output burst Ob(x,y,…,m). We call a super-state the set of single total
states defined by all 0/1 combinations of a subset SIb of the
input burst signals, keeping fixed the remaining input signals and all the
output signals.Definition 5 (essential super-state).
Consider a BM-EHF specification in which a total stateF is
reached by a set of N incident transitions {It_i}i=1,…,N.
Each incident transition It_i is activated by an input burst Ib_i. Each input burst is labeled with a subset of the input signals set {Is}. An essential super-state is the super-state defined by the union S∪Ib=∪{Ib_i} of all input signals
active on the incident transitions set {It_i}, labeled with
nonempty output bursts.
An essential super-state BM
flow map is derived from a BM-EHF specification by applying Definition5 to
all total states. Figure 7 is such a map for the specification in Figure 6.
Cells in red are used to compose essential super-states. For example, the 0[a+b+/x+]→1 transition creates essential super-state 1 composed of four total states: abcdxy=[000010,010010,100010,110010]. State 110010 is the final total state. Total
state 2 may be reached from either
state 1 or state 7.  Applying Definition 5, we find that it must be composed of six
total states (essential super-state 2): abcdxy=[000111,010111,100111,110111,100011,110011].  This set of total states can be described by
a cube (super-state transition cube—SSTC). Figure 8 shows the description in states
transition diagram of the BM-ESS flow map.Figure 7
BM flow map with essential super-states (BM-ESS).Figure 8
BM-EHF specification with essential super-states (BM-ESS).Preposition.
If a total stateF in a BM-EHF specification is reached by one or more incident
transitions labeled with empty output bursts, then F is an essential super-state.Proof.
Let T1(A→F) be a state transition with an
empty output burst. SSTCA and SSTCF are super-state transition cubes for final total
states A and F. As A must
be essential, and as SSTCA[output]=SSTCF[output] because
both output bursts are empty, then F is also an essential super-state.Lemma 2.
The BM-EHF specification has an EHF implementation if and only if for∀ total state A∈ BM-EHF it is an essential super-state.Proof.
Let T1(B→A) and T2(A→C) be state transitions with output bursts. SSTCA and SSTCC are the super-state transition cubes of final
total states A and C. Suppose that the
T2(A→C) input burst does not
contain an essential signal. Then SSTCA[input]⊆SSTCC[input] hence SSTCA[output]≠SSTCC[output]. This means that A cannot be an essential
super-state because this would violate Definition 5.


## 3.1. Essential Hazard

Generalized Unger Rule (30) (gur): The Triple Sequential Input Burst
LetA(I1,O1) and B(I2,O2) be two total states in the BM flow map and Ib/Ob the input/output burst that activates the transition A→B. Let N be the number of the input burst
signals. Consider the following transitions sequence:
T1:A[Ib]→B; (transition 1 is A→B activated by Ib)T2:B[Ib_inverted_polarity]→Ci (i=1,…,k are possible final
states);T3:C[Ib]→Dj (i=1,…,n are possible initial
states), (j=1,…,m are possible final states).Definition 1.
There is a potentialsteady-state essential hazard in
the A→ B transition if, applying the GUR rule, any final total state Dj(j=1,…,m)≠B.Definition 2.
There is a potentialtransient essential hazard in the A→B transition if, applying the GUR rule, there is a total state I(≠A and ≠B) on any path of transitions B→Ci or Ci→Dj that produces an output signal different from any
value occurring on any path of transition A→B.
A potential essential hazard can be
detected applying the GUR rule from any initial state. For example, Figures3(a)
and 3(b) show two paths for the 0→1 state transition on the BM flow map of
Figure 2. Consider the 0[b+a+/x+]→1 path on Figure 3(a). According to
the GUR rule we must apply the following activation sequence: T1(b+a+),T2(b−a−),T3(b+a+). The corresponding
paths on the BM flow table are
T1:abcxy={00000→01000→11000→11010},T2:abcxy={11010→10010→10011→00011→00001},T3:abcxy={00001→01001→11001}. As the final total state (11001) after the last activation (T3)
is different from the final total state (11010) after the first
activation (T1), then a steady-state
essential hazard has occurred. Figure 3(a) shows the path T2 and Figure 3(b) shows the path T3.Part of the BM flow map of Figure2: (a) path T2;
(b) path T3 (final total state—FTS).
(a)(b)


## 3.2. BM-EHF Condition

An input signal in a BM specification is acontext signal in an A→B transition if it does not change during this transition (it is not on the
label) while it is a trigger signal if it is labeled during this transition. The input burst of each state
transition can be represented by an input transition cube (ITC). For example,
the ITC for state transition 7→2 on Figure 1 is abc=220 (2 means do not care). In this example a and b are trigger signals
while c is a context signal (whose value is 0).Definition 3.
LetA and B be a
pair of total states in a BM specification and Ib/Ob be the input/output burst for the A→B transition. Let Es be one input signal (Es∈Ib).Es is an essential
signal if it is a context signal on all transitions incident on state A and is a trigger signal on the transition A→B.
For instance (see
Figure1), a,b,c are not essential on transitions 4→0, 1→2, and 2→3 because they are trigger signals on transitions 3→4, 0→1, and 7→2. Signal b is essential on
transition 7→2 because it is a context signal on
transition 6→7. On transition 6→7 both a and c are essential signals.Lemma 1.
A BM specification is essential hazard free (BM-EHF) if and only if for each state transition labeled byIb/Ob, if Ob≠∅, there must
be at least one essential input signal.Proof.
Let T1(A→B) and T2(B→C) be two sequential state transitions of a BM-EHF specification. ITCT1 and ITCT2 are their respective input transition cubes. Suppose that
the transition T2 input burst does not contain as essential
signal. Then ITCT1⊆ITCT2, which means that the C final total state belongs to a path on ITCT1. This fact violates
Definitions 1 or 2.Figure4 shows the HP-mp-for-pkt benchmark [12, 13]. On all transition labels there is at least one essential
signal. Therefore, it is a BM-EHF specification.Figure 4
BM-EHF specification.There are two ways to transform
nonessential hazard-free BM specifications into a BM-EHF specification.


## 3.3. Reduction of Input Burst Concurrency

The transformation consists of decomposing the input burst
labeled on a state transition generating two-state transitions. For example,
Figure5 shows a reduced concurrency BM-EHF specification equivalent to the BM
specification in Figure 1 in which the concurrency has been reduced.  Analyzing the BM specification in Figure 1,
we found state transitions 1→2 and 2→3
without essential signals. Decomposing state transitions
0[b+a+/x+]→1
into 0[b+/]→A[a+/x+]→1 and
decomposing state transition 7[a+b−/x+]→2
into 7[a+/]→B[b−/x+]→2, we obtained
the BM-EHF specification shown in Figure 5. It
is EHF because transitions 4→0 and 7→B
contain empty output bursts while all other transitions contain essential
signals.Figure 5
Concurrency reduction.


## 3.4. Insertion of Essential Signals

This transformation
consists of inserting the smallest number of dummy essential signals in all
state transitions without essential signal. For example, Figure6 shows an
BM-EHF specification 	equivalent to the specification in Figure 1 in which adummy
essential signal
d
has been
added to state transitions 1→2 and 2→3. This transformation has a higher cost
than the previous one because it increases the number of input signals (Ib), modifying the interaction with the external environment.Figure 6
Inserting essential signal.If one observes the 2→3 state transition in Figure 6, the
conclusion is that a is essential on transitions 1→2→3, while d is essential on
transitions 7→2→3.


## 3.5. Super-State Condition

Lemma1 is a necessary
and sufficient condition for an essential hazard free specification but not for hazard-free implementation. The
super-state concept will guarantee the latter condition.Definition 4 (super-state).
Consider an input burstIb(a,b,…,n) and an output burst Ob(x,y,…,m). We call a super-state the set of single total
states defined by all 0/1 combinations of a subset SIb of the
input burst signals, keeping fixed the remaining input signals and all the
output signals.Definition 5 (essential super-state).
Consider a BM-EHF specification in which a total stateF is
reached by a set of N incident transitions {It_i}i=1,…,N.
Each incident transition It_i is activated by an input burst Ib_i. Each input burst is labeled with a subset of the input signals set {Is}. An essential super-state is the super-state defined by the union S∪Ib=∪{Ib_i} of all input signals
active on the incident transitions set {It_i}, labeled with
nonempty output bursts.
An essential super-state BM
flow map is derived from a BM-EHF specification by applying Definition5 to
all total states. Figure 7 is such a map for the specification in Figure 6.
Cells in red are used to compose essential super-states. For example, the 0[a+b+/x+]→1 transition creates essential super-state 1 composed of four total states: abcdxy=[000010,010010,100010,110010]. State 110010 is the final total state. Total
state 2 may be reached from either
state 1 or state 7.  Applying Definition 5, we find that it must be composed of six
total states (essential super-state 2): abcdxy=[000111,010111,100111,110111,100011,110011].  This set of total states can be described by
a cube (super-state transition cube—SSTC). Figure 8 shows the description in states
transition diagram of the BM-ESS flow map.Figure 7
BM flow map with essential super-states (BM-ESS).Figure 8
BM-EHF specification with essential super-states (BM-ESS).Preposition.
If a total stateF in a BM-EHF specification is reached by one or more incident
transitions labeled with empty output bursts, then F is an essential super-state.Proof.
Let T1(A→F) be a state transition with an
empty output burst. SSTCA and SSTCF are super-state transition cubes for final total
states A and F. As A must
be essential, and as SSTCA[output]=SSTCF[output] because
both output bursts are empty, then F is also an essential super-state.Lemma 2.
The BM-EHF specification has an EHF implementation if and only if for∀ total state A∈ BM-EHF it is an essential super-state.Proof.
Let T1(B→A) and T2(A→C) be state transitions with output bursts. SSTCA and SSTCC are the super-state transition cubes of final
total states A and C. Suppose that the
T2(A→C) input burst does not
contain an essential signal. Then SSTCA[input]⊆SSTCC[input] hence SSTCA[output]≠SSTCC[output]. This means that A cannot be an essential
super-state because this would violate Definition 5.


## 4. Metodolology

Our method begins from
the BM specification and implements the asynchronous controllers in the
architecture of Huffman with feedback output. The synthesis procedure has five
steps.(1)
If the BM specification satisfies Lemma1 to go for Step (3), otherwise, Step (2).(2)
Apply in the BM specification the
functional transformations that satisfy Lemma1 (Sections 3.3 and 3.4).(3)
Generate the BM-EHF specification with essential super-states (BM-ESS)
according to Section3.5 (applying Definition 5).(4)
Use the Minimalist tool that starts from
the BM-ESS specification and produces the equations of next-state hazard-free (sum
of products—netlist).(5)
Use the Quartus tool [31] that starts
from the netlist in structural VHDL.The BM specification shown in Figure1
has been used to illustrate our method. Figure 5 shows BM-EHF specification
(Steps (1) and (2)). Figure 9 shows the BM-ESS specification (Step (3)). Steps (4) and (5)
accomplish the automatic synthesis. One-state variable y0 was required to solve the existing conflicts (see Figure 10)
[28]. Figure 11 shows logic circuit (RTL view—Altera). Figure 12 shows result of simulation of
the circuit that was obtained by our method (hazard-free waveforms).Figure 9
BM-ESS specification of Figure5.Figure 10
BM flow map with essential super-states (BM-ESS).Figure 11
Logic circuit: RTL view—Altera.Figure 12
Simulation of the logic circuit of Figure5.


## 5. Discussion & Results

### 5.1. Discussion

Figures13 and 14 show, respectively, the
simulation results and the logic circuit of the mp-for-pkt
benchmark whose specification is shown in Figure 4. The synthesis was performed
using the Minimalist tool followed by the Quartus tool. Figure 13 shows two
glitches, one on the Allocoutbound output and one on the AllocPB output. For example, the glitch on
signal Allocoutbound occurs on state
transition 1[Ackout−Req+/TRS−AllocPB+]→2. Figure
14 shows the behavior in the logic circuit of the state transition 1→2. The
reason of the  glitch:  input signal Req+ acts in the paths 1 and 2, where the change in the path 1 arrives first in LUT-5 (see Figure 14). This glitche can also be identified
in the BM flow map. Thespecification
is EHF (Lemma 1 is satisfied) but the implementation is not (Lemma 2 is not
satisfied), causing a transient essential hazard shown in Figure 15 (to apply
GUR rule—T2: 2[Req−Ackout+]→1−Allocoutbound0→1→0).Figure 13
Simulation of the
mp-for-pkt: with transient essential hazard.Figure 14
Logic circuit of the mp-for-pkt: map view—Altera (behavior 1→2).Figure 15
BM flow map showing a transient essential hazard.The result of simulation of
the circuit that was obtained by our method shows that the glitches have been
eliminated (see Figure16). The area penalty was 8 LUTs against 5 LUTs in the
first solution. The latency penalty was 2,2%.Figure 16
Simulation of the EHF version of the mp-for-pkt.


### 5.2. Results

We applied our theory to 9 known [8, 9, 12, 13] and one homemade benchmark.
Table 1 presents the number of input and output signals, states, and
transitions for each benchmark. Table 2 presents the area and timing results
for these benchmarks synthesized as Huffman machines (with feedback output)
before applying our theory. Syntheses performed using Minimalist followed by Quartus. The area was measured in terms
of the number of LUTs while the latency was derived from simulations of the
circuits already fitted on an EP2C35F672C7 device from Altera (Cyclone II
family).Table 1
BM specifications show data.
BM specificationDesignStates/trans.In/outCall-proc12/153/3Chu1334/43/3Chu1505/53/3Diff-Alu17/93/5Dram-ctrl12/147/6Figure18/93/2Hp-ir-if7/75/5Mp-for-pkt4/43/4QR424/42/2Rcv-setup6/73/2Table 2
Experimental Results to Huffman Machine
The column State vars shows the variables of state.
Huffman machineDesignState varsTotal of LUTsLatency  (ns)Call-proc0810,888Chu1332510,650Chu1500310,017Diff-Alu131711,081Dram-ctrl01011,633Figure10410,675Hp-ir-if0710,900Mp-for-pkt0510,719QR42169,699Rcv-setup0411,104Table3 presents the number
of inputs and output signals, states, transitions, and dummy signals for the
same benchmarks after applying the functional transformations required to
satisfy Lemmas 1 and 2. Table 4 shows the same results for the benchmarks
after adhering to Lemmas 1 and 2.Table 3
BM-ESS specifications lead to the following data.
BM-ESS specificationDesignStates/trans.In/outDummy signalsCall-proc22/403/30Chu1336/83/30Chu15010/153/30Diff-Alu114/233/51Dram-ctrl22/367/60Figure514/193/20Hp-ir-if7/75/50Mp-for-pkt6/83/40QR428/122/21Rcv-setup9/133/21Table 4
Experimental
results show Huffman
machine—EHF (*Minimalist Tool did not complete the synthesis).
Huffman machine—EHFDesignState varsTotal of LUTsLatency (ns)Call-proc0610,898Chu133*———Chu1500711,606Diff-Alu132411,879Dram-ctrl01612,271Figure511110,855Hp-ir-if11411,454Mp-for-pkt0810,948QR421710,769Rcv-setup1610,263As expected we found an area
penalty (average of 54%), a latency penalty (average of 4,8%), and a state
variables penalty (average of 75%). Thecall-proc benchmark showed a
smaller area (less LUTs) and the rev-setup benchmark showed a reduced
latency time. However, the area penalties did not impact significantly the FPGA
usage (≅1%) still leaving
enough free space for a datapath and other components that could be placed on
the same device.


## 5.1. Discussion

Figures13 and 14 show, respectively, the
simulation results and the logic circuit of the mp-for-pkt
benchmark whose specification is shown in Figure 4. The synthesis was performed
using the Minimalist tool followed by the Quartus tool. Figure 13 shows two
glitches, one on the Allocoutbound output and one on the AllocPB output. For example, the glitch on
signal Allocoutbound occurs on state
transition 1[Ackout−Req+/TRS−AllocPB+]→2. Figure
14 shows the behavior in the logic circuit of the state transition 1→2. The
reason of the  glitch:  input signal Req+ acts in the paths 1 and 2, where the change in the path 1 arrives first in LUT-5 (see Figure 14). This glitche can also be identified
in the BM flow map. Thespecification
is EHF (Lemma 1 is satisfied) but the implementation is not (Lemma 2 is not
satisfied), causing a transient essential hazard shown in Figure 15 (to apply
GUR rule—T2: 2[Req−Ackout+]→1−Allocoutbound0→1→0).Figure 13
Simulation of the
mp-for-pkt: with transient essential hazard.Figure 14
Logic circuit of the mp-for-pkt: map view—Altera (behavior 1→2).Figure 15
BM flow map showing a transient essential hazard.The result of simulation of
the circuit that was obtained by our method shows that the glitches have been
eliminated (see Figure16). The area penalty was 8 LUTs against 5 LUTs in the
first solution. The latency penalty was 2,2%.Figure 16
Simulation of the EHF version of the mp-for-pkt.


## 5.2. Results

We applied our theory to 9 known [8, 9, 12, 13] and one homemade benchmark.
Table 1 presents the number of input and output signals, states, and
transitions for each benchmark. Table 2 presents the area and timing results
for these benchmarks synthesized as Huffman machines (with feedback output)
before applying our theory. Syntheses performed using Minimalist followed by Quartus. The area was measured in terms
of the number of LUTs while the latency was derived from simulations of the
circuits already fitted on an EP2C35F672C7 device from Altera (Cyclone II
family).Table 1
BM specifications show data.
BM specificationDesignStates/trans.In/outCall-proc12/153/3Chu1334/43/3Chu1505/53/3Diff-Alu17/93/5Dram-ctrl12/147/6Figure18/93/2Hp-ir-if7/75/5Mp-for-pkt4/43/4QR424/42/2Rcv-setup6/73/2Table 2
Experimental Results to Huffman Machine
The column State vars shows the variables of state.
Huffman machineDesignState varsTotal of LUTsLatency  (ns)Call-proc0810,888Chu1332510,650Chu1500310,017Diff-Alu131711,081Dram-ctrl01011,633Figure10410,675Hp-ir-if0710,900Mp-for-pkt0510,719QR42169,699Rcv-setup0411,104Table3 presents the number
of inputs and output signals, states, transitions, and dummy signals for the
same benchmarks after applying the functional transformations required to
satisfy Lemmas 1 and 2. Table 4 shows the same results for the benchmarks
after adhering to Lemmas 1 and 2.Table 3
BM-ESS specifications lead to the following data.
BM-ESS specificationDesignStates/trans.In/outDummy signalsCall-proc22/403/30Chu1336/83/30Chu15010/153/30Diff-Alu114/233/51Dram-ctrl22/367/60Figure514/193/20Hp-ir-if7/75/50Mp-for-pkt6/83/40QR428/122/21Rcv-setup9/133/21Table 4
Experimental
results show Huffman
machine—EHF (*Minimalist Tool did not complete the synthesis).
Huffman machine—EHFDesignState varsTotal of LUTsLatency (ns)Call-proc0610,898Chu133*———Chu1500711,606Diff-Alu132411,879Dram-ctrl01612,271Figure511110,855Hp-ir-if11411,454Mp-for-pkt0810,948QR421710,769Rcv-setup1610,263As expected we found an area
penalty (average of 54%), a latency penalty (average of 4,8%), and a state
variables penalty (average of 75%). Thecall-proc benchmark showed a
smaller area (less LUTs) and the rev-setup benchmark showed a reduced
latency time. However, the area penalties did not impact significantly the FPGA
usage (≅1%) still leaving
enough free space for a datapath and other components that could be placed on
the same device.


## 6. Conclusions

This work presented two conditions that, if satisfied,
guarantee that burst-mode asynchronous controllers can be mapped on any
commercial LUT-based FPGA without incurring in essential hazards.When these conditions are not satisfied, we
presented functional transformations that may be used to solve the problem. In
this case, there is an area (mainly are added state variables—75%) and
a latency penalty. However, our experimental results on a set of known
benchmark showed low
latency penalty (4,8%) and low FPGA occupation overhead(≅1%). This type
of burst-mode controllers may be combined with a self-timed datapath that have
already been successfully synthesized on commercial FPGAs, in order to create
fully asynchronous processor on FPGAs.



---

*Source: 926851-2009-01-29.xml*