. 1
tri‘.

4‘ .

: 7.;
.1. u: 4 01..»

b .9 .
n {F

 

 

 

::
.21 ‘v
.a) :I .
5.43:}

 

 

 

. 5,; .. 5%,”...

«243% L3,,

 

9.3 i

meme»; 8 5 W

I {I Mil/mittNIH/@773" ”Wt

31 9301 [WI/H

W

 

 

 

 

 

 

'li’I/f/

13 7875

 

 

This is to certify that the

thesis entitled

\ HAZARD-FREE TECHNOLOGY MAPPING FOR
LOOK-UP TABLE BASED FIELD PROGRAMMABLE GATE ARRAYS

presented by

Paul T. Barczak

has been accepted towards fulfillment
of the requirements for

Master's degreein Electrical Engineering

flfwgfl

Major professor

Dateflfl/y 5}. /j%

0-7639 MS U is an Affirmative Action/Equal Opportunity Institution

 

LIBRARY

MIChisian State
niversity

 

 

 

PLACE IN RETURN BOX to remove this chookout from your rooord.

TO AVOID FINES Mum on or botoro dd. duo.

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

LA:
RTE—i

MSU IoAn Nflrmotlvo Action/Equal Opportunity Institution

 

 

HAZARD-FREE TECHNOLOGY MAPPING FOR
LOOKUP-TABLE BASED FIELD PROGRAMMABLE GATE ARRAYS

By
Paul T. Barczak

A THESIS

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

MASTER OF SCIENCE

Department of Electrical Engineering

1996

ABSTRACT

HAZARD-FREE TECHNOLOGY MAPPING FOR
LOOKUP-TABLE BASED FIELD PROGRAMMABLE GATE ARRAYS

By

Paul T. Barczak

The Xilinx family of lockup-table based field programmable gate arrays
consists of blocks of hazard-free logic connected with a flexible routing network.
Traditional gated hazard analysis techniques assume that delay can occur between
any boolean elements in the network specification. Since the output of a Xilinx
Configurable Logic Block (CLB) is hazard-free for single input transitions, only
inter-CLB delay can contribute to potential hazards.

This thesis explores the effects of blocks of programmable, hazard-free
logic on network-level hazards. Traditional hazard analysis techniques are revised
for application to these types of networks. Information acquired through the revised
analysis techniques are used to modify an existing F PGA technology mapping

algorithm in order to obtain mappings with fewer logic blocks.

Copyfightby
PAUL THOMAS BARCZAK

1996

TABLE OF CONTENTS

List of Figures .................................. vi
List of Tables .................................. viii
1 Introduction ............................... 1
2 Hazards in Gated Networks ...................... 3
2.1 Hazard Classifications ......................... 5
2.1.1 Function vs Logic Hazards ....................... 5
2.1.2 Static vs Dynamic Hazards ...................... 7
2.2 Network Characteristics Contributing to Logic hazards ....... 9
2.2.1 Terminology and Foundation ..................... 9
2.2.2 Sum-of-Products Internal Signal Analysis ............... 12
2.2.3 Relating Product terms to Logic Hazards ............... 20
2.2.4 Key Observations ............................ 23

3 Hazard Analysis in Networks Composed of Arbitrary HFLEs . . . . 26
3.1 Role of Signal Paths .......................... 27
3.2 Generalizing Unger’s theorems ..................... 30

3.3 Adapting McCluskey’s hazard analysis algorithms for HFLEs . . . . 33

3.3.1 HF LE-marked logic diagrams ..................... 33
3.3.2 Determining BO-sets and Bl-sets ................... 34
3.3.3 Detection of Static HFLE Logic Hazards ............... 40

iv

3.3.4

5.1

5.2

5.3

5.4

5.4.1

5.4.2

5.5

5.5.1

5.5.2

5.6

5.6.1

5.6.2

6.1

7.1

7.2

7.3

Detection of Dynamic HFLE Logic Hazards ............. 43
Xilinx Look-Up Table Based F PGAs ................. 45
Hazard-Free Technology Mapping onto Xilinx LUT FPGAs ..... 48
Algorithm Goals ............................ 50
Algorithm Overview .......................... 50
System Implementation ........................ 53
New SIS Data Structures ........................ 54
Initial Product-term IDs (ipids) .................... 55
Hazard Cover Table .......................... 56
New and Modified SIS Algorithms .................. 58
T.I. Hazard Eliminator ......................... 58
Technology Mapper ........................... 62

Optimizing the Cube Packing Algorithm for HNI Placement . . . . 65

Redundant Cover Eliminator ..................... 70
Merger .................................. 72
Benchmark Results ........................... 74
Performance Analysis .......................... 78
Summary and Conclusions ....................... 83
Summary ................................ 83
Contributions .............................. 85

Future Work . . . .4 .......................... 86

LIST OF FIGURES

2.1 Simple AND-gate Hazard ......................... 6
2.2 Circuit containing a potential logic hazard ............... 6
2.3 Static vs Dynamic Hazards ........................ 8
2.4 Static logic hazard example, demonstrating HISTs and Hle ..... 8
2.5 Internal Signals in a Sum-of-Product Network ............. 15
2.6 Transient literal signals (building blocks) ................ 16
2.7 Tree for possible p-term outputs ..................... 16
2.8 Possible p-term output signals ...................... 17
2.9 Possible Signals at the Network Output, first four p-term BB’s . . . . 17
2.10 All possible S.O.P. general network output waveforms. ........ 19
3.1 Function f = 6d + bd + Ed Implemented with Gates .......... 29
3.2 Function f = 6d + bd + Ed Implemented with Blocks .......... 29
3.3 Bl-set determination example ...................... 39
3.4 Karnaugh map plot of Bl-sets and BO-sets ............... 39
4.1 Xilinx XC3090 CLB ........................... 46
5.1 Block hazard elimination algorithm overview .............. 52
5.2 Finding Adjacent Exposed Product Terms ............... 60
6.1 Eliminated Covers ............................ 79

vi

vii

6.2 Eliminated Nodes ............................. 80

5.1

5.2

5.3

5.4

6.1

6.2

6.3

LIST OF TABLES

Product Term Pairs Exposed States ................... 61
Cover Table (for the Redundant Cover Eliminator) .......... 61
Cover Table C ............................... 67
Cover Table After Extraction ...................... 69
Synthesis Benchmarks mapped onto 3-input blocks .......... 75
Synthesis Benchmarks mapped onto 4-input blocks .......... 76
Synthesis Benchmarks mapped onto 5-input blocks .......... 77

viii

Chapter 1

Introduction

The elimination of combinational hazards from a boolean logic specification can be
a crucial step during circuit synthesis. This requirement is often made of sequential
designs, where output spikes in the combinational portion of the circuit may result
in incorrect states. Spikes are especially troublesome in self-timed circuits, which
give the combinational circuit no opportunity to “settle” before the next state
change.

Techniques for detecting and eliminating hazards in combinational networks
have been described by Huffman [3], McCluskey [6], and Unger [9]. The methods
have focused on the elimination of hazards from the specification using boolean
algebra, and are normally not tied to any particular realization of the logic. These
techniques introduce product terms into the minimized boolean specification which
“cover” the adjacent input states involved in each hazard. The introduction of these
covers result in a new boolean specification, which will be hazard-free regardless of
the technology used to realize the circuit. The characteristics of the implementation
technology are not normally considered during the process of introducing covers.

Attention to the unique delay characteristics of the Xilinx lookup-table (LUT)
based field-programmable gate arrays during hazard elimination will prove

beneficial. LUT-based FPGAs consist of a network of logic blocks, each with a small

fixed number of inputs and outputs. A RAM-based lookup table is used to
determine the combinational outputs of each logic block. The flexibility of the
programmable blocks and a programmable interconnection network allows the
FPGA to realize arbitrary boolean logic functions easily. Because the entire
configuration of the FPGA is stored in RAM, it may be reprogrammed and tested
quickly.

The design of the Xilinx FPGA guarantees that the output of each individual
logic block is hazard-free for single input changes [10]. If traditional hazard-free
synthesis techniques are used to design the boolean specification, the hazard-free
characteristics of the individual blocks are not considered. These hazard-free logic
blocks may “absorb” some hazards that would have been possible in a gated
network. Some covers that would be introduced by the traditional synthesis
techniques may be unnecessary. These additional covers occupy valuable space on
the F PGA.

This paper will explore the effects of hazard-free logic blocks on network
output hazards in multi-level logic implementations. Traditional hazard analysis
techniques will be revised for application to networks composed of blocks of
hazard-free logic. The information acquired through these analysis techniques will
be used to modify an existing LUT-based technology mapping algorithm, which in
many cases produces a mapping with fewer logic blocks than the traditional

approach.

Chapter 2
Hazards in Gated Networks

The effects of spurious delays in combinational networks and the transient behavior
of circuits have been studied by a number of authors [3, 6]. If the transient output
of a circuit depends on both the network inputs and the propagation delay of the
network elements and interconnections, the circuit is said to contain a hazard.
While the circuit is in a transient state, the output may momentarily change to a
value different than what would be expected in steady-state.

The intended use of the combinational Circuit’s outputs determines how
harmful these transient spikes are. Outputs which are supplied to a set of clocked
inputs may always reach steady—state before the next clock pulse. In this case,
spikes may not affect the performance of the network, provided that the clock cycle
is longer than the worst-case settling time of the combinational logic. However,
there are many situations in which it is necessary for the combinational circuit to be
free of all hazards. In a self-timed sequential network, each combinational output
change triggers a machine state change. Incorrect internal states may result in
incorrect network output behavior.

While there are several variations on the classification of hazards, all types of
hazards include the elements shown in the simple and-gate hazard of example 1.

There exists a single fundamental element with two or more input variables v. The

input to the circuit is at some initial state 5,-(v) at time t.-, and changes to a final
state Sf(v) at time t f. The Hamming distance between 55(1)) and Sf('U) is greater
than one, which implies that more than one input variable must change value
between the initial and final state. Since two signals cannot change value
simultaneously, there will always be some finite amount of time At when the logic
element is presented with an input set which differs from both 5,-(v) and Sf(v).
Depending on the properties of the logic element, these transient inputs may result

in an unwanted signal change at the element’s output.

Example 1 - Simple AN D-gate-hazard
Consider a simple AND gate, with inputs 2) = (i1, 2'2), and output 0. If the
initial input state is 5,-(v) = (2'1, i2) = (0, 1) and the final state is
Sf(v) = (1, 0), the timing diagram shown in figure 2.1 is possible. Briefly, at
time t1, the inputs to the AND gate are 5(0) = (1, 1), causing a momentary
spike in the output. At time t2, the input transition is complete. The circuit

reaches steady-state at time t3.

All types of combinational hazards are based on this fundamental example -
the result of two inputs to a logic element changing before the circuit reaches
steady-state. This section will present an overview of the different classifications of
hazards in gated networks. The internal network characteristics which contribute to
a hazard will be analyzed. Traditional hazard analysis and synthesis methods for

gated logic will be discussed.

2.1 Hazard Classifications

Classification of combinational hazards has traditionally concentrated on either the
behavior of the combinational network’s inputs during a hazard, or the behavior its
outputs. Hazards may be classified as either function hazards or logic hazards,
depending on the number of changes that occur at the combinational network’s
inputs during a state change. Additionally, hazards may be classified as either
static hazards or dynamic hazards, depending on the type of changes that occur

at the network’s output during a state change.

2.1.1 IMnction vs Logic Hazards

Hazards may be classified by the type of input changes that are allowed before the
next state transition. Function hazards may be present in circuits in which two or
more network input variables are changed before the next input state transition.
This type of hazard was shown in the simple AND-gate hazard of example 1. To
eliminate function hazards, McCluskey [7J advocates restricting input state changes
to single-input transitions.

If multiple-input transitions are not allowed in the design, a circuit realization
may still contain logic hazards. These hazards are caused by fan-out and
propagation delays within a network of logic elements, when a single variable
transition at the network input may cause multiple signal transitions for an internal

logic element.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

I] | l l
i I l 1
l '2 l l s
[— o 1 l i J
5 o i,’/—l\[ J
J J . . I
to ‘1 [2’3
t >
Figure 2.1: Simple AND-gate Hazard
i l J I
r — z . l
i—TJ>O ' 3‘ 11
i I I
o l |
l l l
l 0 [J’IF—NJ
l A. l
to It, gr,
I >

 

 

 

 

 

 

 

 

 

Figure 2.2: Circuit containirg a potential logic hazard

Example 2 - Logic Hazard
Consider the logic simple network shown in figure 2.2. Though this circuit
has only a single input, the prOpagation delay through the inverter may
cause the signal I to aflect the AND gate some At after the signal 2'. If A, is
positive, the timing diagram for this circuit may be represented by figure 2.2,

where A, = t2 — t1.

Note that in example 2, a spike at the output is possible even though the
network only has a single input (and thus only single input transitions are possible).
Also note the similarities between example 1 and example 2. The inputs and outputs
to the AN D-gate produce the same spike in the output - the only difference is that

the multiple-input transition for the AND-gate is generated internal to the network.

2.1.2 Static vs Dynamic Hazards

In addition to classifying hazards by the behavior of the network input, it is also
possible to classify hazards by the type of transitions that occur in the output. A
static hazard is said to occur if there is a momentary change in the output, but
the steady-state value of the output remains the same before and after the input
transition. A static hazard whose steady-state output value is one is classified as a
static-1 hazard, while a static hazard whose steady-state output value is zero is
classified as a static-0 hazard.

A dynamic hazard is said to occur if the steady-state value of the output
differs from its previous value after an input state change, and the output value

changes more than once before reaching steady-state.

 

 

 

I

J J Static—o hazard Different classifications

J I of hazards by output

l , 1 . behavior. Input state

J Ll Siam-1 hazard change occurs at ti.

J J Circuit output reaches
—“J‘ FJ, steady-state at: .

l -‘ ? dynamic hazard f

l I

ll if

Figure 2.3: Static vs Dinamic Hazards

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8: J

a-m a I J
rad b l

. J L
l l
bi— ! 1 l ' '.
J + | C : J
T‘" ‘ d ——‘_A J
l—t l
J 9 Li

ea & J __l f

a;
J. J .,

(1,1,1)->(1,0,1) Input transition

 

 

 

Figure 2.4: Static logic hazard example, demonstrating HISTs and Hle

2.2 Network Characteristics Contributing to Logic hazards

The root cause of a hazard is tied to multiple signal transitions and the propagation
delay for those signals, regardless of the implementation. It is useful to determine
precisely which network characteristics contribute to potential hazards. This
information will be useful in chapter 3, when the traditional analysis techniques are
modified for application to networks of hazard-free combinational blocks.

In the remainder of this paper function hazards will not be considered. That
is, the output of the network must not depend on the simultaneous change of
multiple input signals. This assumption is acceptable for many designs, and is a

standard constraint for all sequential circuits that operate in fundamental-mode [7].

2.2.1 Terminology and Foundation

To simplify the description of hazard analysis and synthesis algorithms, some new

terminology is introduced.

Definition 1 - Hazard-causing Input State Transition (HIST)
Given two adjacent input states Slanng, if the transition T from one state
to the other may cause any type of hazard, the transition is called a

Hazard-causing Input State Transition.

Definition 2 - Hazard-causing Network Input (HNI)
Given a HIST T, the single input that changed between the two adjacent

input states 5'1 and 52 is called the Hazard-causing Network Input.

Example 3 illustrates the HISTs and HNIs of a simple static-0 logic hazard.

10

Example 3 - Demonstration of HISTs and Hle
The two—level boolean realization of the function f = ab + 5c is shown in
figure 2.4. Consider the two adjacent input states 5'1 = (a, b, c) = (l, 1,1) and
5'2 = (a,b,c) = (1,0,1). Either of the transitions T1 = 51 —» 5'2, or
T2 = 52 —> 31 may cause a static-0 hazard in the output, depending on the
delay characteristics of the implementation’s elements. The timing diagram
illustrates one possible output hazard, caused by the signal 6 changing some
A: after (1. Since hazards are possible for both T1 and T2, both transitions
are HIS Ts.

In this particular example, a hazard is possible between the input

states 5; and $2. The input variable whose value differs between these two

states (the HNI) is 5.

Definition 3 - Hazard-free Fundamental Logic Element (HFLE)
A Hazard-free Fundamental Logic Element is an atomic boolean element that
is hazard-free for single input variable changes. The element is comprised of
a set of inputs, a single output, and a boolean function which relates the

inputs to the output.

HF LEs are the building blocks of a network implementation, as they are the
smallest elements in the network which are guaranteed to be hazard—free. In a gated
network, they are the gates themselves. In a network composed of arbitrary
hazard-free logic blocks (such as the LUT FPGA design), the blocks are HFLEs.

Analysis of hazards in an implementation requires understanding of delay

characteristics between the logic elements. While delay analysis is relatively simple

11

for two-level networks, it becomes considerably more complex with multi-level logic.
Unger [9] provides two valuable theorems that transform multi-level network
implementations into equivalent two-level network implementations. The equivalent

networks, which are less complex, can be analyzed for hazards.

Theorem 1 — multi-level hazard analysis
Given any algebraic expression E, if we transform it into a sum-of-products
form expression F through the use of the associative, distributive, and.
DeMorgan laws (this is, of course, always possible), then circuits
corresponding to E and F, respectively, have precisely the same static

hazards.

Theorem 2 - multi-level hazard synthesis
Given any expression E1, if we generate from it an expression E2 by using
only the generalized DeMorgan law, the associative law, factoring (but not
multiplying out), and transformations of the form AAB —-> A and
A + B -+ A + B, the a circuit corresponding to E2 will have no

combinational hazard not present in circuits corresponding to E1.

It is possible to restrict all further discussion of hazard analysis and synthesis
to 2-level networking, using theorems l and 2. Multi-level equations can simply be
collapsed to an equivalent 2-level network prior to analysis, and 2-level hazard

networks may be constructed and then expanded into multi-level networks.

12
2.2.2 Sum-of-Products Internal Signal Analysis

In order to determine the precise network characteristics which contribute to logic
hazards, a detailed analysis of the internal signals in a S.O.P. circuit will be
performed. By determining the characteristics of the signals which contribute to
hazards, it will be possible to understand how the differences between gated
networks and HFLE networks affect the hazard analysis and hazard-free synthesis
algorithms.

By theorem 1, the hazards in any boolean network may be determined by
analyzing an equivalent sum-of-products representation. Figure 2.5 shows the form
of any S.O.P. implementation. The network shown in figure 2.5 contains two
distinct levels of internal signals. By identifying all waveforms that are possible at
each level, the characteristics of the network output can be classified and related to
boolean combinations of the literals and product terms, and their transition times.

First, all possible literals are identified. All possible combinations of these
literal building blocks can then combined with the boolean AND function to
determine possible product-terms. All combinations of these p-term building blocks,
in conjunction with the boolean OR function will determine waveforms that are

possible at the network output.

13

Literal building blocks
The following general observations are made about the S.O.P. representation:

0 Since the circuit is fundamental mode, only a single input 2' can change

before the circuit reaches steady state.

0 A S.O.P. input literal may be either a network input signal or the inverse of
a network input signal. That is, an inverter may be present in the circuit

before the network input supplies input to an AND gate.

0 Since the circuit is combinational (no feedback), a literal can only change

value only once before the circuit reaches steady-state.

0 Each logic element in the circuit is a HFLE. That is, a spike cannot occur
at the output of an inverter, an AND function, or an OR function when a

single input to the element changes.

It is clear that a literal will either change value once before steady-state or will
retain the same value. There are, then, only four waveforms possible which may

provide input to the AND gates. These building blocks are shown in figure 2.6.
P-term building blocks

By determining all possible combinations of the literal building blocks
combined with an AND function, it is possible to find all of the waveforms that are
possible as product terms. Several general observations can be made about each of

the product terms:

14

0 Each literal may have different delay characteristics before being supplied
as input to the AND function. No two literals may make transitions at

exactly the same time. That is, no two literals have the same to.

0 Any variable that appears in the p-term which has value 0 will force the

p-term’s contribution to 0.

o In order for a product term’s contribution to change, the input variable i
must appear as one of the p-term’s literals. If 2' does not appear as a literal

in the p-term, the contribution will remain constant.

The tree in figure 2.7 represents all possible p-terms. Combinations that are
present in a parent are also present in its two children. Leaves of the tree, then,
include all possible p-terms broken down by waveform. Only the five waveforms
shown in figure 2.8 are possible as product term contributions, or p-term building
blocks. The building blocks are obtained from the tree leaves through the following

observations (note that 2' is the network input that is changing):

1. “Some literal other than 2' appears in the p-term with value 0”. Since the
p-term is an AND function, a constant input variable with value 0 will

drive the value to 0. [p — BB#2]

2. “i does not appear in the p—term and all other literals have value 1.” Since

all literals in the p-term are a constant 1, the p-term output must also be 1.

[P-BB#1l

3. “Either i or i appears in the p-term, not both”, and all other literals in the

15

 

 

 

 

 

 

 

 

 

 

 

 

literal p-term network
signals signals output
0 |
1,: —‘ 81 J
12+— i r J
. J i + J
in ‘p-term #1 i
1,1 &
I2
ln——Jp-term #2 _ f
1,1 & J '
12 ,_J r
l___,
in p-term #n

 

 

 

Figure 2.5: Internal Signals in a Sum-of-Product Network

16

 

Literal BB #1

 

 

 

 

 

 

0

; Literal BB #2
; J Literal BB #3
3 J Literal BB #4

t

C

Figure 2.6: Transient literal signals (building blocks)

 

 

 

l l

 

 

Some variable other All variables other than
than i appears In the i that appear in the
p-term with value 0 p-term have value 1
[pBB#m J
T* l
i appears in the idoes not appear
p—term in the p-term
J [p—BB # 1]
l |
Only 1' or 7 appears Both i and I appear
in the p-term, not in the p-term
UMh
[p—BB # 3, # 4] [p-BB # 2. # 5]

Figure 2.7: Tree for possible p-term outputs

17

 

 

 

 

 

 

J

J
-—————>————————v—————-—————<r———‘-—-————»-Jy-———-
.._.__r

l |
ti ta tb tf

Figure 2.8: Possible p-term output signals

P-term BB #
p—term BB #
p—term BB #

p-term BB #

l
J
J
F—_J J p—term BB #
i
J

 

 

Net. output

J

 

 

 

1 i

o J J

1 J J Net. output

0 4 l

l J J J Net. output

0 J J

L J J J Net. output
‘ r

1—+—fi r—r———

o

 

J J Net. output

 

N___.
~o

N
K...

signal

signal

signal

signal

signal

#1

#2

#3

#4

#5

Figure 2.9: Possible Signals at the Network Output, first four p-term BB’s

18

p-term have value 1. Since the p-term’s contribution will be 1 when all
variables have value 1, and each literal can only change value once, the
p-term’s output will have a single transition. The change can either be a

1 —r 0 transition [p — BB#4] or 0 —> 1 transition [p — BB#3]. Exactly one

transition will occur in the output.

. “Both i and i appear in the p-term and all other literals in the p-term have
value 1”. The waveform in this situation depends on the delay
characteristics of the circuit. Suppose the literal i makes a 0 —> 1 at time t1,
and that i makes a 1 —+ 0 transition at time t2. If delay characteristics
permit t1 > 13;, then a 0 —» 1 —> 0 pulse [p — BB#5] will occur. If t; < t2,
the p-term’s output will retain a constant value of 0 [p — BB#2]. Exactly

one transition can occur in the output.

Possible network output waveforms

Now that all possible signals that may occur as input to the OR gate have

been determined, applying those possible signals to the boolean OR function will

result in all possible network output signals. For the initial combinational analysis,

the fifth p-term building block will be excluded. The fifth p-term will be added back

later. Given these constraints, the resulting possible signals are shown in figure 2.9.

The method used to arrive at these signals is given below:

1. P-term building block #1 has a constant value of 1. This wave form OR’d

with any other waveform will result in a constant value of 1 [Net. output

signal #1].

19

 

 

 

 

 

, J General output waveform #1

. I z

1 J r—j ' J General output waveform #2

‘ l J ‘ J J General output waveform #3

o J L__ L___ J_L__

1 J J J , J General output waveform #4

0% _.' l J

1% —‘ J

0 J J J General output waveform #5
l

 

 

O—n
0—>1->O spikes

Figure 2.10: All possible S.O.P. general network output waveforms.

 

2. P-term building block #2 has a constant value of 0. This wave form OR’d
with any other waveform will result in the other waveform [N et. output

signals #1-4].

3. P-term building block #3 OR’d with p—term building block #4 will result
either in a 1 -» 0 —> 1 transition or a constant 1, depending on timing of
the transitions [Net. output signals #1, #5]. Only a single 1 —» 0 -+ 1

transition can occur at the output.

When the fifth p-term building block is OR’d with the signals in figure 2.9, the
result is the waveforms shown in figure 2.10. The 0 —» 1 -+ 0 spikes of this p-term
will only appear in the network output when all other p-terms have an output of 0.
The resulting waveforms represent all possible signals that may be present at the
output of a S.O.P. network. Note that there may be any number of spikes in these

output waveforms caused by the fifth p-term building block (including 0).

20
2.2.3 Relating Product terms to Logic Hazards

It is relatively straight-forward to relate each of the possible hazard types to the
waveforms shown in figure 2.10. In this section, static and dynamic hazards will be
related to the general waveforms in the previous section. Boolean and delay

characteristics which contributed to the hazard will be isolated.
Static-O Hazard

A static-O hazard occurs when one or more transient spikes occur and the
initial and final state of the network output are zero. This occurs in the general
output waveform #2 in figure 2.10. In order for this output waveform to occur, one
or more product terms must have output signals of the form [p-term BB #5], and
all other product terms must have output signals of the form [p-term BB #2].
Using figure 2.7, the literals possible in each of the p-terms can be determined:

A static-0 logic hazard will occur between two adjacent input states that differ

in i, iff the following conditions are satisfied:

1. At least one p-term exists which includes 2' and i, and the delay
characteristics of the circuit make it possible that i = i at the same time.

All other literals in the p-term have value 1.

2. All other p-terms in the circuit either have some literal v yé 2' whose value is
0, OR include i and i and the delay characteristics of the circuit make it

impossible for i = i at the same time.

Unger [9] has simplified these observations with the following theorem for the

detection of static-0 hazards:

21

Theorem 3 - Unger’s theorem for static-0 hazards
A circuit has a O-hazard between the adjacent input states I] and 12 that
differ only in x,- iff f(Il) = f(12) = 0, there is a p-term pn of the circuit that

includes a:,- and $1., and all other literals of pn have l-values in I] and 12.

Dynamic 1 —+ 0 Hazard

This hazard may be realized by the general output waveform #3, provided one
or more spikes occur. For this hazard to occur, one or more p-terms must have
output signals of the form [p-term BB #5], one or more p-terms must have output
signals of the form [p-term BB #3], and all other p-terms must have output signals
of the form [p-term BB #2].

A dynamic 1 -v 0 hazard will occur between two adjacent input states that

differ in i, iff the following conditions are satisfied:

1. At least one p-term exists which includes i and i, and the delay
characteristics of the circuit make it possible that i = i at the same time.

All other literals in the p-term have value 1.

2. At least one p-term exists which includes the literal i or i (but not both),
and the input signal change causes that literal to make a 1 -+ 0 transition.

All other literals in the p-term have value 1.

3. All other p-terms in the circuit either have some literal v 75 i whose value is
0, OR include i and i and the delay characteristics of the circuit make it

impossible for i = i at the same time.

22

Unger has simplified the network characteristics whiCh lead to dynamic

hazards with the following theorem:

Theorem 4 - Unger’s theorem for dynamic hazards
An AND-to—OR—circuit has a dynamic hazard between the adjacent input
states 11 and 12 that differ only in 2:,- iff f(I1) # f(12), the circuit has a
p-term pf that contains at, and 231-, and all other literals of p; have 1-values in

11 and [2.

Static-1 Hazard

A static-l hazard may be realized by the general output waveform #5. One or
more spikes may occur before the output reaches steady-state. For this hazard to
occur, one or more p-terms must have output signals of the form [p-term BB #3],
one or more p-terms must have output signals of the form [p-term BB #4], zero or
more p-term may have output signals of the form [p-term BB #5], and all other
p-terms must have output signals of the form [p-term BB #2].

A static-1 hazard will occur between two adjacent input states that differ in 2',

iff the following conditions are satisfied:

1. At least one p-term exists which includes 2' and all other literals in the
p-term have value 1. If 2' makes a 0 —+ 1 transition, call the time of the first
occurrence of i to make the transition th. If i makes a 1 -—r 0 transition, call

the time of the first occurrence of 2' to make the transition t1.

2. At least one p-term exists which includei and all other literals in the

p-term have value 1. If i makes a O —) 1 transition, call the time of the first

23

occurrence of i to make the transition th. If i makes a 1 -> 0 transition, call

the time of the first occurrence of i to make the transition t1.
3. t: < t},

4. All other p-terms in the circuit either have some literal v 915 2' whose value is
0, OR include i and i and the delay characteristics of the circuit make it

impossible for i = i at the same time.

Unger [9] has simplified these observations with the following theorem for the

detection of static-0 hazards:

Theorem 5 - Unger’s theorem for static-l hazards
A circuit has a static l-hazard between the 11 and [2 where f(Il) = f(12) = 1

iff there is no p-term that has the value I in both 11 and I2.

2.2.4 Key Observations

This chapter has performed a detailed analysis of a general sum-of-products
equation to isolate the network characteristics which contribute to hazards. By
examining which characteristics the different types of hazards have in common, it is
possible to distill the boolean and delay properties necessary to cause hazards down
to a small set. This set will lead to hazard-free synthesis techniques in gated

networks, as well as analysis and synthesis techniques in networks composed of

HFLEs.

1. A product term which contains a literal and its complement (p-term BB

#5) is essential in order for static-0 and dynamic hazards to occur. If a

24

variable and its complement did not occur in the same product term, the

only hazards possible would be static-1 hazards.

2. A static-l hazard is caused by two p-terms, one which makes a 1 —v 0
transition, and second p-term which later makes a 0 —> 1 transition. The
transition literal (HNI) must occur in the first p-term, and its complement
must occur in the second p—term. This tinting will cause a glitch at the

output unless another p-term has value 1 for the transition.

3. All hazards are caused by the complementation of a network input inside
the circuit. The input and its complement have different paths through the
circuit. Each path causes a transition of the network output. Since the
components in the circuit are not ideal, each path has different propagation

delay and affect the output at a different time before steady-state.

Hazard-free synthesis techniques work by ensuring that several of the above
conditions do not occur in a boolean network. McCluskey [7] and Unger [9]
advocate technology-independent synthesis techniques, which modify the boolean
behavior of the network. Static-0 and Dynamic hazards cannot occur if a variable
and its complement are not allowd to appear in the same product term (a simple
design constraint). Static-1 hazards can be eliminated by introducing a boolean
“cover” which maintains a 1 output for both states of the transition.

Hazards may also be eliminated by controlling the delay properties of the
network. In a static-1 hazard, if the p-term which makes the 0 —+ 1 transition does
so before the p-term which makes the 1 —+ 0 transition, the static-1 hazard cannot

occur. Eichelberger [4] details techniques to control hazards in a gated network by

25

controlling delay. Care must be taken for attempts to control delay in gated
networks, however, since a technology’s delay characteristics may change as the

circuit ages.

Chapter 3

Hazard Analysis in Networks Composed of
Arbitrary HFLEs

Many of the techniques used for hazard detection in gated networks also apply to
networks composed of arbitrary hazard-free logic blocks. In general, logic hazards
are caused by propagation delay along different paths through the circuit. In the
boolean specification of a gated network, the appearance of a literal and its
complement always indicate that the signal has branched. Each of these branches
will affect the network output may be used at differents time before steady-state.

In a network composed of HFLEs, the amount of logic contained in each
HF LE may be different than that in a gated network. Signals which must branch in
a gated network (i.e, a literal and its complement) may not do so in a HFLE
network. Since traditional hazard analysis techniques do not explicitly identify
signal paths, they will often identify potential hazards in an HFLE implementation
where they cannot occur.

This chapter will identify assumptions present in the traditional hazard
analysis techniques which do not apply to hazard-free block logic networks. Unger’s
hazard theorems and McCluskey’s hazard analysis algorithms will be generalized to

identify hazards in networks composed of HFLEs.

26

27

3.1 Role of Signal Paths

Fundamentally, a hazard occurs when two or more signals which provide input to a
logic element change before steady-state. The signals cannot change simultaneously,
There must some finite amount of time in which the element is supplied with inputs
that differ from either the initial state or the final state. If the boolean function of
the logic element is appropriate, the logic element’s output may change more than
once before steady state.

Example 4 shows “equivalent” gated and block-HFLE logic implementations
of the same boolean function, and demonstrates the impact that signal path has on

possible hazards.

28

Example 4 - Signal Path Impact
Figure 3.1 represents a two-level gate implementation of the function
f = dd + bd + 2d. If the inputs to the circuit are initially (at time to) set to
all zeros, the initial inputs to the OR-gate are then (A, B, C) = (0, 0,1),
which results in a steady-state value of l at the network output.

If the network input d makes a 0 —) 1 transition, a static-1 logic hazard
is possible, as shown in the timing diagram. After the signal (1 changes, two
internal signals, A and C, must make transitions due to the fan-out of the d
signal. Depending on delays in the internal circuit, it is possible that the
internal signal C makes the 1 —) 0 transition before the signal A makes the
0 —> 1 transition. This causes the input at the OR-gate to momentarily drop
to (A, B, C) = (O, 0, 0), resulting in a static-1 hazard at the output.

Consider now figure 3.2, which is a implementation of the same
function using larger HFLEs. Given the same set of input states and the
same 0 -> 1 transition in the d input, a hazard is not possible hazard at the
output. The internal network signals at the output logic block (A, B, C) only
make a single transition (1, 0, 0) -—+ (1, 1, 0). Since individual blocks are
hazard-free, a single input signal change at the output logic block cannot

cause a hazard at the network output.

The above example demonstrates the role that signal fan-out plays in hazards.
The potential static—1 logic hazard in the gated network is caused by the fan-out
and recombination of the HNI d. The network input must branch in order to supply

input for the two p—terms dd and cd. Since both branches cannot change at precisely

29

 

 

a———o&

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

aJ ’

J J

__J b' ?'

cJ I]

A l ?%J

+ d.—e:..

b & B J Jll
d J _C_J Bl TlJ
’— CI llJ

LG rJ JJ_J

8‘ l Ill
C‘——C to'1t2f3

 

 

 

Figure 3.1: Function f = 6d + bd + Ed Implemented with Gates

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a J J l
b J J l
c J J T
a———+a £83056 | d J______ J
l
—“" if A Al I l
L____lc I a f=a+bc J T
B b fr— f BJ J J
0 CL l l
b c
J J l
f J J J
l l l
t0 t1 t2

Figure 3.2: Function f = ad + bd + Ed Implemented with Blocks

30

the same time, a hazard is possible in the circuit if t; — t1 > 0.

In the block-logic implementation, the signal d that appears in the two
product terms 5d and Ed does not branch. Both p-terms are contained in a single
logic block. Since the signal does not branch, only a single internal signal changed
during this state transition. The potential hazard in the gated network has been

effectively absorbed by the HFLE implementation.

Definition 4 - Signal Path of a Literal
Given a network realization, the signal path of a input literal is defined as the
set of hazard-free fundamental logic elements that the input literal must

propagate through before affecting a change in the network output.

The signal path of a literal provides a mechanism to identify fan-out of a
signal in arbitrary HF LE networks. In the S.O.P. equation, two different literals

have branched in the network if and only if they have different signal paths.

3.2 Generalizing Unger’s theorems

Unger’s theorems for identifying potential logic hazards in a circuit assume that the
appearance of a variable and its complement are the result of fan-out in the circuit.
In a network composed of arbitrary HFLEs, this is not always the case.

The following three theorems are based upon Unger’s hazard analysis
theorems for gated networks, but eliminate the assumption that a literal and its
complement must follow different signal paths. Note that these theorems still apply

to traditional gated networks, where the gates themselves are HF LEs.

31

Theorem 6 - HFLE-Logic Static-0 Hazards
A HF LE network implementation has a O-hazard between the adjacent input
states I; and I; that differ only in I iff f(Il) = f(12) = 0 there is a p-term pn
of the circuit that includes I and I, which have different signal paths, and all

other literals of pn have l-values in II and 12.

Theorem 7 - HFLE-Logic Dynamic Hazards
A HF LE network implementation has a dynamic hazard between the
adjacent input states I] and 12 that differ only in I iff f(Il) # f(12), the
circuit has a p-term pf that contains I and I with different signal paths, and

all other literals of pf have 1-values in 11 and [2.

PROOF. Recall from chapter 2 that in order for either a static-0 or a
dynamic hazard to occur, a product term in the network must contain a
literal and its complement. This product term can produce a 0 —» 1 —+ 0
spike as shown in figure 2.8.

Let 12(1), and p(I) represent the signal paths of the literal and its
complement from the network input to the network output. Let d(p(l)) be
the propagation delay through the circuit along a signal path p(l). In order
to produce a spike at the output, there must be some finite amount of time
after a transition that a signal affects the network’s output before its
complement makes the opposite transition. That is, d(p(l)) 75 d(p(l)) so that
the literal and its complement can be “on” simultaneously.

Because each HF LE has only one network output and the circuit is

32

both combinational and fundamental-mode, the literal and its complement
which have the same signal path will travel through the same components
and interconnects. Since the signal paths are identical, the delay along the
paths are identical. That is, p(l) = p(I) —> d(p(l)) = d(p(l)).

A product term with a literal and its complement can produce a spike

iff the signal paths differ.

Theorem 8 - HFLE-Logic Static-1 Hazards
A HFLE network implementation has a l-hazard between the adjacent input
states I; and I; that differ only in I where f(I;) = f(12) = 1 iff there is no
p-term that has the value 1 in both I; and 12. Additionally, there must be no
set of p-terms p; active for I; and p2 active for 12, in which I appears in p;

with the same signal path as I in p2.

PROOF. Recall from chapter 2 that in order for either a static-1 or a
dynamic hazard to occur, a product term p; in the network must contain a
literal I and another product term p2 must contain its complement I. It must
be possible for these two product terms to be alternately “on” during this
transition. That is, p; makes a 1 —t 0 transition and p2 makes a 0 —> 1
transition. In order to produce a spike at the output, d(p(l)) < d(p(I)).

As was shown in the prrofs of theorems 6 and 7, a literal and its
complement which have the same signal path through the network have the
same delay. That is, p(l) = p(l) —) d(p(l)) = d(p(I)).

If I and I share the same signal path, there can be no spike at the

network output.

33

3.3 Adapting McCluskey’s hazard analysis algorithms for HFLEs

The same techniques that were used to modify Unger’s theorems for networks of
HFLEs will be used to adapt McCluskey’s hazard analysis algorithms. The
algorithms will be modified so that they do not make assumptions about the signal
paths of a literal and its complement. McCluskey uses the following steps to develop

algorithms for identifying hazards:

1. Reduce a multi-level circuit into a two-level S.O.P. representation. Identify
the unique signal paths of all input signals from their network input to the

output of the network.

2. Identify all static logic hazards by finding l-sets which satisfy Unger’s static

hazard theorems (theorems 3 and 5).

3. Identify all dynamic logic hazards by finding all P-sets which satisfy

Unger’s dynamic hazard theorem (theorem 4).

The reader is referred to McCluskey’s text on logic design [7] for full
descriptions of algorithms in a gated networks. For the sake of brevity, only to

modified algorithms for HFLE networks will be presented here.

3.3.1 HFLE-marked logic diagrams

The signal path of all literals must be determined to identify any hazard in a
network composed of arbitrary HFLE blocks. Recall that in gated networks, a literal
and its complement can not share the same signal path. This assumption can not be
made in a network of HF LES. Additional information is introduced into the logic

diagram to explicitly identify the signal paths of HNI literals and their complements.

34

Definition 5 - HFLE-marked logic diagram
A HF LE-marked logic diagram is one in which each hazard-free fundamental

logic element is uniquely labeled (usually, with a number).

HF LE-marked logic diagrams are similar to the marked logic diagrams
McCluskey uses for dynamic hazard analysis in gated networks. McCluskey’s
marked logic diagrams only captures signal fan-out information of signals within the
circuit, and not fan-out due to complementation of an input. In order to analyze a
HFLE network, the complete signal path of each literal is needed for both static and
dynamic hazard analysis.

The following modifications are made to McCluskey’s hazard analysis

algorithms, which will allow them to used for networks of arbitrary HF LEs:

1. A HFLE-marked network is used to determine the signal paths of the

inputs during analysis.

2. Bl-sets are used instead of l-sets and P-sets. Bl-sets resemble P-sets in
that they are derived from a marked logic network, but they allow the use
of several simplification techniques not permitted when deriving l-sets and

P-sets.

3. Additional signal path criteria are added to the signal and dynamic logic

hazard algorithms.

3.3.2 Determining BO-sets and Bl-sets

The first step in analysis is reduction of the multi-level network realization to a

two-level S.O.P. equation and constructing a signal path for each literal in the

35

equation. A list of HF LEs that the signal “passes through” is maintained on each
literal, which is constructed as the multi-level equation is multiplied out. This list is
recorded as a subscript ot the literal in the S.O.P. equation, and represents the
signal path of that literal.

When forming the S.O.P. expression for the network, several logic theorems

may be used to simplify analysis:
1. X, + XbYc = X (a).(b) may be used to eliminate redundant product terms.

2. Xa(X;> + YC) = X(a),(b) may be used to eliminate redundant sums.

3. Unlike traditional hazard analysis, X0)?“ = O and X, + X“ = 1 may be

used, provided the signal paths of the complementary terms are identical.

Note that for the first two items, the signal path of both X elements must be
carried along with the reduced term. It is necessary to represent all signal paths of
literals which can cause a transition at the output.

It is now possible to define Bl-sets and BO-sets, which are similar to

McCluskey’s P-Sets and S-sets.

Definition 6 - A set of literals is a Bl-set of a network N iff:

1. A HF LE—marked network logic diagram is used, which labels each
fundamental logic element uniquely. The label of the HFLE is appended to

the signal label as the signal passes through it.
2. Whenever all of the literals are equal to l, the network output is equal to l.

3. If any literal is removed, condition (a) no longer holds.

36

Definition 7 - A set of literals is a BO-set of a network N iff:

1. A HFLE-marked network logic diagram is used, which labels each
fundamental logic element uniquely. The label of the HF LE is appended to

the signal label as the signal passes through it.
2. Whenever all of the literals are equal to 0, the network output is equal to 0.

3. If any literal is removed, condition (a) no longer holds.

Example 5 illustrates the method used to determine the Bl-sets and BO-sets of

a HFLE network.

Example 5 - Bl-set determination
Consider the marked-F LE diagram shown in figure 3.3. “Multiplying” out

the network yields the following expressions:
f = ((9); + $;)393)4 + (312 + 9222).; (1)

f = ((w;,3:r;,3)y3)4 + 312,4(3/2,4 + E“)
f = w1,3,4$1,3,4y3,4 + 372,4y2,4 + 92,422.41 (2)
f = w1,3.4$1,3,4y3,4 + 372,4;2,4 (3)

Note that the term @2434“ was eliminated between equations 2 and 3.
While traditional analysis does not allow the use of this elimination, it may
be used here when determining BO-sets and Bl-sets, provided the signal path

is identical for both terms.

37

The Bl-sets for this network are:

[wl 3,4, It 1 3,4, 93,4] , [372.4, 2'2,4l (4)

By taking the dual of equation 1, the BO-sets of this network can be

determined. The dual of equation one is:

 

fD =(((w1$1)3 'J' y3)4)(y2(I/2 + 22))4

“multiplying” this equation out gives:

 

ID = (wm + 331.3 + y3)4(y2i—/2 + y222)4

f0 = (1013.4 + $1.3,4 + y3.4)(312,422.4)
f0 = (1013.4 + 31.3.4 + 313,4)(372'4 + 22,4)
f0 = 1013.437“ + 31.3.1437“ + 313,437“ + 1013.422", + 31.3.42“ + 313,432,,

Taking the dual again gives:

f = (w;,3,4 + 92,4)(1’13A + 92,4)(93A + 92,4)(w1,3,4 + g2,4)(1'1,3,4 + 2'2,4)(3.l3,41v:2,4)

The BO-sets for this network are:

[w1,3,4;3-/2,4l, [$1,3,4, 92,4]; [93.4, 372,4]; [w;,3,4, 22,4] , [$1.33, 22,4], [313,4a 22.4] (5)

By selective use of the boolean complement theorems, product terms and sum
factors which contain both a variable and its complement may remain. If the
variable and its complement have exactly the same delay path, the terms may be
eliminated. If the literal and its complement have different delay paths, the

corresponding set is called unstable.

38

Definition 8 - Unstable B0 and B1 sets
A Bl-set or BO-set is called unstable if it contains at least one pair of

complementary literals with differing signal paths.

Definition 9 - Stable B0 and B1 sets
A Bl-set or BO-set is called stable if it contains no pairs of complementary

literals with differing signal paths.

Definition 10 - Stable and Unstable variables
Those variables which appear with their complement in an unstable set are
called unstable variables. Variables which do not appear with their

complement in a set are called stable variables.

Sets are said to be active or inactive in precisely the same manner as in

traditional hazard analysis:

Definition 11 - Active Stable Bl-set
A (stable) Bl-set is said to be active for an input state iff all the literals of

the set are equal to 1 for that state.

Definition 12 - Active Stable BO-set
A (stable) BO-set is said to be active for an input state iff all the literals of

the set are equal to 0 for that state.

39

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

W , £=£+S
f L———J _
x J J f=a&b
(j) '———— a f
l_—"— b (3 J r f=a+B J
y J a fJ f
J f=a+§b I b AJ
f
Z b (3;
Figure 3.3: Bl-set determination example
WX wx
yz 00 01111) yz_oo o_1 1_1__1(L
00 ( 1 1 1J’ 1) 00 J J
! J a“ I _L!\—
01 . o1 (OJ 07 o [04)
//\\J —-J+———. —— 7':
‘1 r1 J 11 33] Q.
J l
10 LLJJJ J 10 __e>-(lJ_—_—O:_J _J )8:

 

 

Figure 3.4: Karnaugh map plot of Bl-sets and BO-sets

 

 

40

Definition 13 - Active Unstable Bl-set
An unstable Bl-set is said to be active for the transition between a pair of
input states iff all stable literals are 1 for both states of the transition and all
its unstable variables have different values for the two states of the

transition.

Definition 14 - Active Unstable BO-set
An unstable BO-set is said to be active for the transition between a pair of
input states iff all stable literals are 0 for both states of the transition and all
its unstable variables have different values for the two states of the

transition.

Definition 15 - Inactive Sets

Sets that are not active are inactive.

3.3.3 Detection of Static HFLE Logic Hazards

Now that all of the definitions are in place, modifications to McCluskey’s static logic
theorems may be made. Theorems 9 and 10 will identify static-1 hazards in
networks of arbitrary HF LEs using Bl-sets and BO-sets, respectively. Theorems 11

and 12 will identify static-0 hazards with Bl-sets and BO-sets, respectively.

41

Theorem 9 - HFLE Logic Static-l Hazard Theorem (using Bl-sets)

A static logic l-hazard exists in a block-logic network iff:

1. There is a pair of adjacent input states that both produce 1 outputs. That
is, each of the input states has a Bl-set active for it. Call the variable

which differs in value between the two adjacent states v (the HNI).

2. There is no (stable) Bl-set of the network that is active for both input

states of the pair.

3. There is no pair of Bl-sets, each active for one of the input states, in which

0 has the same signal path.

Theorem 10 - HFLE Logic Static-l Hazard Theorem (using BO-sets)

A static logic l-hazard exists in a block-logic network iff:

1. There is a pair of adjacent input states with the network output equal to 0

for both states.

2. There is an (unstable) BO-set that is active for the transition between the

pair of input states.

42

Theorem 11 - HFLE Logic Static-0 Hazard Theorem(using Bl-sets)

A static logic O-hazard exists in a block-logic network iff:

1. There is a pair of adjacent input states with the network output equal to 0

for both states.

2. There is an (unstable) Bl-set that is active for the transition between the

pair of input states.

Theorem 12 - HFLE Logic Static-0 Hazard Theorem (using BO-sets)

A static logic O-hazard exists in a block-logic network iff:

1. There is a pair of adjacent input states that both produce 0 outputs. Call

the variable which differs in value between the two adjacent states v (the

HNI).

2. There is no (stable) BO-set of the network that is active for both input

states of the pair.

3. There is no pair of BO-sets, each active for one of the input states, in which

v has the same signal path.

Note that the theorems 11 and 10 appear nearly identical to those McCluskey
uses in traditional hazard analysis. This is not entirely as it appears; an expanded
definition would include the condition that the variable and its complement, which
appear in the unstable sets do not have the same signal path. This condition is

guaranteed already, since all such unstable sets have already been eliminated while

43
“multiplying out” the equation.

Example 6 - Static hazard determination

Figure 3.4 shows a Karnaugh map of the Bl-sets and B0-sets for example 5.
Examination of the Bl-sets shows a transition between the two stable sets
with no stable sets covering the transition. The HIST for this hazard is the
transition (w, 1',y,z) = (1,1,1,0) —+ (1,1,0, 0), and the HNI is y. The signal
path for y and 3; differs between the two stable Bl-sets.

Examination of the B0-sets reveals a unstable set [3134, 3.1“], and the
network output equal to 0 for the (w, z,y, z) = (1,1,1, 0) ——» (1, 1,0,0)

transition. This constitutes the static-1 hazard.

3.3.4 Detection of Dynamic HFLE Logic Hazards

Since McCluskey already explicitly takes signal fan-out into account for dynamic
hazard detection, McCluskey’s Dynamic Hazard Theorem applys to HFLE networks
with only a change in terminology. Bl-sets must be used in place of McCluskey’s
P-sets, and B0-sets must be substituted for S-sets. Again, this is not exactly as it
would appear. The determination of Bl-sets and BO-sets will eliminate all unstable

sets which have a variable and its complement with the same signal path.

44

Theorem 13 - Dynamic Block Logic Hazard Theorem
A dynamic logic hazard exists in a block logic network for a transition T

between a pair of adjacent input states I and J iff:

1. There is an unstable Bl(B0)-set which is active for T. Denote this unstable

set by U and the unstable variable by X.

2. There is a stable Bl(BO)-set which is active for I and inactive for J.
Denote this stable set by B. There is in B a literal X " with a different

subscript from any of the subscripts on X "‘ in U.

3. All other Bl(B0)-sets are inactive for J.

4. All other B1(BO)-sets are either inactive for I or all Bl-sets which are
active for I have a literal X " with a different subscript from any of the

subscripts on X‘ in U.

Chapter 4
Xilinx Look-Up Table Based FPGAS

Xilinx F PGAs provide the benefits of custom components without the usual time
and testing disadvantages of custom 105. The XC3000 and XC4000 families consist
of repeated arrays of programmable Configurable Logic Blocks (CLBs) connected by
a flexible routing network. Input / Output Blocks (1035) are also provided, which
are integrated into the circuit via the flexible routing network.

The devices are programmed by loading configuration data into internal
memory cells. They can be reprogrammed an unlimited number of times, making
hardware updates as easy as changing software.

The Configurable Logic Blocks (CLBs) use memory m-input look-up tables to
realize a CLB’s output function. The look-up tables (LUTs) are made from RAM
cells, which derive the function output based on the CLB’s truth table and the
inputs supplied. Because the CLB function is implemented in RAM, the
propagation delay is independent of the function realized.

The CLB of a XC3090 is shown in figure 4.1. The XC3090 consists of a single
TLU. The TLU may be either used to realize a single function f from 5 inputs, or
two functions f and g of four inputs each. If the TLU is used to implement f and g,
the inputs must meet certain criteria (they must share a common literal and meet

other restrictions). The CLB also contains two D flip-flops, which may provide

feedback to the TLU.

45

 

 

 

 

 

 

 

 

 

 

 

 

 

 

DIN J ——————————————————— J
J A __—1 JQX
Jf ii a ; r—‘I
H“ . J
J' *1 D ' J I
I! a H a .
a : = F l J _JJ—" X
b J J TLU : J; J
2 L: : I i
6 J J GJA J; J. J Y
J__1 J IL—JJ r——J J "J .
J J—J rJ DY J . J

 

Figure 4.1: Xilinx XC3090 CLB

The XC4000 series provides three TLUs. Four independant external inputs
(Fl-F 4 and G1-G4) are provided to each of two TLUs. These function generators
are capable of implementing any arbitrary boolean function based on their inputs,
producing outputs labelled F’ and G’. Additionally, a third TLB H can implement
any boolean function from its three inputs. Two of these inputs may either come
from F’ and G’ or from outside the CLB. The third input must come from outside
the CLB.

Xilinx has designed each of the TLUs to be hazard-free for single—input
transitions [21]. Maheswaran and Akella [16] have exploted this characteristic for
the design of a hazard-free cell set for micro-piplined architectures. They provide

the following list of properties for the XC3000 and XC4000 series TLUs:

1. All of its inputs can change independent of each other and at any time.

47

2. The block delay is transport and not inertial. An input pulse, however
small, will propagate through to the output after the block delay and would

not be “swallowed” by the logic block.

3. There can never be a decoding glitch when one input changes. Even a
non-overlapping decoder (equivalent to a static logic hazard) cannot
generate a glitch, since the node capacitance will retain the previous logic

level until the new transfer gate is activated about a nanosecond later.

4. For more than one “simultaneous” input change, glitches are possible in the
presence of intermediate code which produces a different result (same as a

function hazard).

In the XC4000 series, delay may be introduced between the TLUs if F’ and G’
are used as inputs to H, resulting in output spikes. However, each TLU has been
designed to be hazard-free by Xilinx, and may be treated as a Hazard-free
Fundamental Logic Element, as defined in definition 3. The HFLE hazard analysis
techniques developed in chapter 2 may be used for Xilinx logic mappings, provided

each TLU is treated as an independent HFLE.

Chapter 5

Hazard-Free Technology Mapping onto Xilinx
LUT FPGAs

The reusability of FPGAs and their convenience for rapid prototyping have made
them useful for both synchronous and asynchronous finite state machine designs.
Because the majority of commercially feasible F SM designs are synchronous, there
has been a good deal of effort into optimizing the efforts of synchronous F SMs onto
F PGAs. Very little research has been done, in contrast, into techniques to optimize
the mapping of asynchronous FSMs onto FPGAs.

For asynchronous FSMs which use the Huffman model, making the next-state
combinational logic hazard-free is a necessity. Any glitches which occur in the
next-state logic may cause the system to enter an incorrect state and may result in
improper network outputs.

The hazard-free characteristics of the XILINX CLB suggest that some savings
are possible if the logic hazards present in the boolean description can be absorbed
by the logic blocks. Any boolean function mapped into a single CLB is guaranteed
to be hazard-free. Unfortunately, many state machines must implement more
combinational logic than can be incorporated into a single CLB.

When the combinational logic requires more than a single CLB, the common
method is to fall back to technology-independent techniques. McCluskey’s method

is used to synthesize a hazard-free boolean equation, including covers, which is then

48

ar

5P

CO

CC

dc

SE

49

mapped. This method will produce a hazard-free implementation which can be
mapped onto any target technology.

Introduction of covers does not take advantage the hazard-free nature of the
CLB; more covers may be introduced than are necessary for the XILINX
architecture. These covers require additional logic, which may occupy valuable CLB
space when mapped onto the FPGA.

Recall from chapter 2 that a hazard can only occur if literal and its
complement which “cause” the hazard have different signal paths. The approach
that will be taken for this algorithm will be to attempt to map Hle and their
complement so that both literals share the same signal path. When this can be
done, the hazard that would be possible in a gated network cannot occur.

Recall from definition 4 that the signal path of a literal is the list of all of the
logic elements that literal must propagate through. If the technology mapping
algorithm maps the HN I and its complement into the same CLB, they share the
same signal path and the hazard cannot occur. The HNI gathering technique, then,
is to eliminate hazards by gathering the HN I and its complement into the same
CLB.

In this chapter, a new algorithm is proposed which integrates hazard
elimination with technology mapping for arbitrary amounts of combinational logic.
HNI gathering is used to augment traditional hazard-elimination techniques for the
cube packing technology mapping algorithm. This results in a hazard-free design

with fewer covers than technology-independant synthesis methods.

50

5.1 Algorithm Goals

The following goals are defined for the new hazard-free technology mapping

algorithm:

0 The algorithm can take as input any combinational logic boolean

specification, regardless of number of inputs.

0 The resulting mapping must be free of both static and dynamic block

hazards.

o The hazard-free nature of the mapping should not be dependent on the
delay characteristics of the routing network connecting the CLBs. That is,
a change in the delay properties of the network should not make a hazard

possible.

0 The technique should take advantage of existing technology mapping
algorithms. Efficient technology mapping is in itself a complex problem.

Leveraging as much existing work in this area as possible is desirable.

5.2 Algorithm Overview

In network equations whose product terms contain many literals, one literal may be
involved in many possible hazards. The limited number of inputs in a single CLB
may make it impossible to group all of these HNI pairings into a single logic block.
In cases where HNI pairing cannot eliminate all hazards from the circuit, HNI

pairing will be used to augment McCluskey’s method of using boolean covers.

51

Introducing the boolean covers once the HN I pairings are known poses a
dependency problem. In order to know which hazards are eliminated by HN I pair
gathering, the network must have already been mapped. Integrating additional logic
into an existing mapping is likely to be an inefficient use of the CLBs. By nature,
covers share almost all of the same input variables as the product terms that they
cover. It is likely that literals from the cover would have been mapped into existing
logic blocks had they been included in the specification prior to technology
mapping. Unfortunately, once the circuit has been mapped, it becomes very difficult
to “shoehorn” new product terms into existing CLBs.

To overcome this problem, McCluskey’s method will be used to introduce
covers for all hazards in the combinational logic prior to technology mapping. The
resulting technology-independent hazard-free equation is mapped onto logic blocks,
which is then analyzed to eliminate any unnecessary cover logic. Elimination of
these covers may result in underfull logic blocks; these may be collapsed onto their
fan-ins to reduce the number of CLBs.

An outline of the algorithm which produces a minimized, hazard-free mapped

network is given below and shown in figure 5.1.

1. Traditional combinational logic minimization methods are used to reduce

the supplied boolean logic network into a minimized SOP equation.

2. A technology independent hazard elimination algorithm is used to

produce a minimized set of covers which will eliminate all hazards.

3. A technology mapper is used to map the infeasible boolean specification

into feasible nodes which may be directly mapped onto logic blocks. The

52

 

Minimized, Infeasible Node 3

 

 

J T.I. Hazard Eliminator :——\ Cover Table

 

 

T.I Hazard Free, Infeasible, Marked Node

 

 

T

 

Hazard-Free, Feasible, Marked Node

 

 

 

 

 

Redundant Cover Eliminator Jx__ Cover Table

 

Block Hazard-Free, Feasible, Marked Node

 

 

 

 

 

 

 

Minimized, Block Hazard-free
Feasible Node /

Figure 5.1: Block hazard elimination algorithm overview

53

resulting multi-level network is feasible and hazard-free.

4. If the HNI pair which contributes to a hazard has been mapped into a
single logic block, the hazard cannot occur. When this happens, a cover
that was produced to eliminate that hazard is unnecessary. The
redundant cover eliminator identifies unnecessary covers and eliminates

them from the network specification.

5. When redundant covers are eliminated, some logic block inputs may
become unused. A standard block merging algorithm is used to merge

logic onto these underfull blocks without disturbing the HNI pairing.

6. The preceding three steps are repeated until no further covers may be

eliminated.

5.3 System Implementation

Several of the modules in figure 5.1 are complex algorithms in themselves,
particularly the technology mapping algorithm. In order to simplify the prototype,
an existing FPGA synthesis system was modified rather than developing the
modules from scratch. The SIS system, developed and distributed by theUniversity
of California at Berkeley, already provides combinational logic minimization and
FPGA technology mapping. The presence of these algorithms along with the
modular nature of the SIS user interface provide a good framework to modify for
the new algorithm.

To implement the hazard-free mapping algorithm, the following modifications

were made to SIS:

54

1. The existing hazard elimination code in SIS was modified to generate a
marked network and a cover table. These are needed by the redundant

cover eliminator to identify unnecessary covers.

2. The redundant cover eliminator did not previously exist in SIS. This

module was added.

3. The technology mapper and merger were modified to propagate
product-term markings as they process the network so that the cover
eliminator can identify the initial product terms. Improvements to the

mapping algorithm itself were also made to promote HNI pairing.

5.4 New SIS Data Structures

The cover eliminator must be able to find covers and HNI literals after the network
has been mapped in order to identify redundant logic. This may be a difficult task,
since the technology mapper may divde and recombine product terms for optimal
block placement. Separation of the original literals may cause the terms in the
mapped network to bear little resemblence to the initial SOP equation’s product
terms.

To assist the cover eliminator in relating product terms in the mapped
network to product terms in the initial network, The hazard eliminator will mark
the initial product terms after it produces covers. The covers, along with the
product terms which they cover, are recorded in the cover table for later use by
the cover eliminator. These markings must be propagated through the technology

mapper and the merger as they manipulate the network specification.

55
5.4.1 Initial Product-term IDs (ipids)

The network is marked with product-term IDs after the covers have been introduced
and before it is supplied to the technology mapper. Product term IDs may then be
used to relate initial product terms to product terms once the network has been

mapped.

Definition 16 - Initial product-term ID (ipid)
Given a boolean equation E = 101 + p2 + 192 + ..., the initial product-term ID,
or ipid is a unique integer associated with product term before the equation
is mapped onto logic blocks. The ipid may be denoted by i(p,,) = ipid or

may be written in the equation E as 175:9“).

After the network is mapped, each product term in the mapped network will
have an associated contribution set which matches the mapped product term

with the initial product terms.

Definition 17 - Contribution Set
Given a boolean equation E = pill + p?) + pg” + ..., let P be the set of all
ipids in E. When E is mapped into the m-feasible multi-level equation F ,~
then let fn be a product term in one of equations of F. The contribution set
of f" is denoted by C(fn) = {ipid1,ipid2, .}.., where C(fn) Q P is the set of

initial p-terms which fn is derived from. C ( fn) is written in the equation F

as f'Eipid1,ipid2,...].
Example 7 demonstrates these two definitions.

Example 7 - Ipids and Contribution Sets

56

Consider the following boolean equation:
f=abcd+acde (1)

The boolean equation is labeled with ipids prior to technology mapping,

resulting in the following marked equation:
f = abcdm + code(2) (2)

The ipids in equation 2 are i(abcd) = 1 and i(acde) = 2. After technology
mapping the equation onto 3-input logic blocks, f is represented by the

following network of equations:
f = 1,411+ at.” (3)
t1 = achm] (4)

It is clear that the product term acd in equation 4 contributes to the
realization of both product terms in equation 2. The contribution set of acd
is C (acd) = {1, 2}. The product term btl in equation 3 only contributes to

one initial product term, abcd; thus, C(btl) = 1.

The propagation of ipids through the technology mapper requires a specific set
of rules to be used as the product terms are divided and combined. These rules are

outlined later, in the section which details the technology mapper modifications.

5.4.2 Hazard Cover Table

Marking the boolean network with ipids allows the cover eliminator to relate
mapped product terms back to initial product terms. The cover elminator must also

be able to determine which which initial product terms contributed to a potential

57

hazard and the cover that was introduced to eliminate that hazard. The hazard
eliminator constructs the cover table with this information and saves it for later
use by the cover eliminator. Each entry in the table contains the ipids of the two
product terms involved in a hazard, the HNI variable, and the ipid of the cover

introduced to eliminate the hazard.

58

5.5 New and Modified SIS Algorithms

The details of the changes needed in the SIS modules to accommodate the
hazard-free technology mapping algorithm are given in this section. A single
example will be used throughout the various algorithms, which will illustrate the
progression from an infeasible network which contains possible hazards to the final
hazard-free feasible network. For the sake of illustration, the function

0 = 562a + bode + 2258:: + abef + acef + abEf will be mapped onto 3—input logic

blocks.

5.5.1 T.I. Hazard Eliminator

McCluskey’s Hazard-Free Synthesis Theorem [7] specifies that two conditions must

be met in order to make a boolean equation hazard-free for any implementation:
1. No product term can contain a complementary pair of literals.

2. For any pair of adjacent input states that both produce a one output, there

must be a product term that includes both states.

The first requirement is easily met by using the boolean complements theorem. In
the specification, any product term that contains both a literal and its complement
will be eliminated, since it has a logical value of zero.

To fulfill the second requirement, covers are introduced for any exposed
states. An exposed state occurs when there are two product terms which are
alternately “on” for adjacent input states, and there does not exist a product term
that is “on” for both states. The hazard eliminator detects these exposed states and

introduces a product term to cover them. Whenever a cover is introduced, the

59

hazard eliminator records it in the cover table for later use by the redundant cover
eliminator.
Finding Adjacent Exposed States

In order to satisfy McCluskey’s second requirement for a hazard-free network,
the hazard elminator must detect product terms which are alternately “on” for a set
of adjacent input states. That is, it must detect any two product terms pl, 172 and
adjacent input states i1, i; such that at state i1, p1 has a one value and p2 has a zero
value, and at state i2, p2 has a one value and p1 has a zero value. Additionally, there
must be no product term 123 which has a one value for both i1 and i2.

A variation of McCluskey’s tabular technique is used to detect adjacent
product terms with an exposed input state transition. If two product terms contain
exactly one complementary literal (.1: appears in p; and if: appears in p2) then the
product terms are alternately “on”. If no product term exists which covers both
input states, the input states are exposed and the product term pairs may
potentially cause a hazard. A cover must be introduced to eliminate that potential
hazard.

A demonstration of this technique is shown in example 8.

Example 8 - Finding Exposed States

The product terms of the initial minimized boolean specification:
0 = 832:: + bode +£1de + abef+ acef+ abt—Bf

are placed into a table (shown in figure 5.2). Each product term is compared
to every other term. If exactly one complementary literal exists between the

two product terms ( p1 has a 0 in the column for the literal, 122 has a 1), the

60

 

 

 

a b c d e f
5669 I o o o - 1 —
5669 o o - o 1 —
abef 0 1 — - 0 1
bcde - 1 0 1 1 -
abef 1 1 - - 1 1

 

 

Figure 5.2: Finding Adjacent Exposed Product Terms

product terms are alternately “on” for a pair of adjacent input states.

Once a pair of alternately “on” product terms are found, all other
product terms are examined to determine if the two input states are both
“on” in another product term. If a product term 1);», exists such that a
complementary literal does not exist (i.e., no 0 - 1 conflicts) between p3 and
p1 and p3 and 192, then [)3 provides a cover for the input states. If no such 1);;
exists, the adjacent input states are exposed and have the potential for
causing a hazard.

The variable that is complementary between the exposed input states is
the HNI - when this variable make a transition it alternates which product
term contributes a one to the network output.

Examining all possible product term pairs for exactly one
complementary literal reveals the three pairs shown in table 5.1. Only one

set of the input states, abde f , already has a cover and is not exposed.

61

 

P-term Pair Transition Signal Exposed States Cover Already Exists?

abde ace f a bcde f No
bgde acef c abdef Yes - abef
12946 are; e «:11ch No
abce bcde b acde N 0

Table 5.1: Product Term Pairs Exposed States

 

Cover (ipid) P-term Pair{ipids) HNI

7 1,2 I)
8 2,6 e
9 3,5 a

Table 5.2: Cover Table (for the Redundant Cover Eliminator)

 

Introducing and Minimizing the Covers

Introduction of covers is done directly from the exposed states. Given two
product terms, p1 and 1);, with exactly one complementary literal I, the cover can be
found by constructing a product term c which contains all of the literals in p1 and
all of the literals in p2 except for the complementary literal I.

New covers are introduced into the equation and tagged with ipids. For the

example, this results in the following equation:

0 = 832.2“) + bcdem + dbdeJaJ + abefm + acestJ + abEstl

+52deJ7J + abEde‘” + bode f (9’

The ipids of the product term pairs and cover, as well as the HNI, are placed in a
cover table (shown in table 5.2) to be later used by the redundant cover eliminator
and the technology mapper.

The hazard eliminator’s technique differs from McCluskey’s hazard free
synthesis in several key ways. McCluskey combines logic minimization of the

equation with hazard elimination. This method imposes an additional condition on

62

the selection of essential prime implicants. In standard logic minimization, prime
implicants are chosen such that all states are covered. In hazard-free logic
minimization, prime implicants must not only cover all states, but must also cover
all adjacent states.

In contrast, the input to the hazard eliminator is already minimal. All cover
logic that the hazard eliminator introduces is redundant to the minimized equation.
Each cover may be eliminated without changing the boolean function of the
network. This technique is not always as efficient as McCluskey’s technique, but

redundant logic may easily be disposed of after the network is mapped.

5.5.2 Technology Mapper

Once the hazard eliminator produces a hazard-free infeasible network, the
technology mapper will take that network as input and construct a hazard-free
n-feasible network. Any of the standard technology mapping algorithms could be
modified for this stage; the standard SIS cube packing algorithm was chosen for its
simplicity and its performance in grouping HN I pairs. Adaptation of other
technology mapping algorithms for this technique is left for future work.

Only one change is necessary for the technology mapping algorithm. The
technology mapper must be able to propagate ipids through the mapping process. It
must be possible for the cover eliminator to relate the mapped product terms to
initial product terms. Tuning the algorithm to group more complementary HIST
literals also proves useful, and is covered in a subsequent section.

The cube packing algorithm has two phases. The first phase is to make the

product terms feasible by extracting literals into new blocks from product terms

63

which have more than n literals. This leaves a sum-of-products equation where each
product term has at most 72 literals. The second phase is to pack sum terms from
the SOP equation into blocks such that the block has at most n inputs.
Extraction

In order to map a network onto n-input blocks, product terms which have
more than n literals must be made n-feasible. To do this, intermediate product
terms of n literals are extracted into a separate block. The output of this new block
is AN Ded to what remains of the original product term. This process reduces the
number of inputs required for any single product term without changing the boolean
function of the network.

Example 9 illustrates cube extraction.

Example 9 - Cube Extraction
Perform cube extraction for a 2-input blocks on the following ipid-marked
equation:

f = abcm + bchzJ + bcgJ3) (1)

If be is chosen as a intermediate product term, the result is:
f 2 cell] + Edlzl + €gJ3] (2)
e = balm] (3)

Which results in product terms which are all 2-feasible.
Note that if there are enough literals in a product term, it may take

more levels of intermediate product terms in order to make it feasible. When:

f = abcdefm (4)

64

is mapped onto 2-input blocks, the result is:

f = 53511] (5)
51 = abJIJ (6)
52 = chl] (7)
53 = efm (8)
54 = 515‘,” (9)

The rule for ipid propagation is demonstrated in equations 1, 2, and 3 in
example 9. When a cube is extracted from a set of p-terms, the contribution set of
the cube is the union of all ipids of the p-terms. The contribution sets of the
original p-terms remain unchanged.

Packing

Once all of the product terms are decomposed so that they are n-feasible, the
sum terms must also be decomposed so that each S.O.P. equation has at most n
inputs. The method used is similar to extraction - intermediate sum terms with at
most 72 inputs are introduced to draw literals out of the original equation, until

there are n or fewer inputs remaining. Example 10 illustrates cube packing.

65

Example 10 - Cube Packing
Equation 2 in example 9 is a S.O.P. equation with 3 inputs, which does not
map onto a 2-input node. To pack this equation into 2-input nodes, as, Eg,
and ed are both separated into intermediate nodes. The resulting set of

equations are 2-feasible:

f = pi” + p123]

p4 = 9J3] + p.53]
P3 = 59m
P2 = Edm
P1 = 05m

6 = ch1’2'3J

The rule for ipid propagation in packing is similar to extraction. When a
subset of a S.O.P term is removed into a intermediate variable, the contribution set
of the intermediate variable is the union of the contribution sets of all of the

product terms it replaces.

5.6 Optimizing the Cube Packing Algorithm for HNI Placement

There are decisions about which literals will be extracted and which product term
prodcted that can influence the effectiveness of HN I gathering. The standard SIS
cube packing algorithm always extracts the first 12 from any infeasible product term
and always packs the first n product terms into a cube. The addition of some

heuristic decisions about which product terms and literals will be selected can

66

greatly enhance the algorithm’s ability to group HN I pairs.

To eliminate a hazard, HNI literals from two different product terms must be
mapped into the same block. Two HNI literals can only be grouped together if the
cubes that they were extracted into could be packed into a single block. Since full
cubes cannot be packed, HNIs that are extracted into full cubes have no possibility
of participating in HNI pairing.

The modified extraction algorithm for arriving at n-feasible cubes is divided
into two phases. During the first phase, product terms which contain HNI matched
pairs are decomposed so that they leave as many matched Hle in underfull cubes
as possible. Once all potential HNI product terms are decomposed, the standard

extraction algorithm is applied to decompose the remaining product terms.

0 A copy of the cover table is constructed (which will be referred to as C).

This table will be modified during extraction and packing.

o For each HN I pair in the cover table, the product containing the HN I literal
and labeled with the ipid numbers are located. Call these product terms
(p1, p2). Let ll be the number of literals in p], and 12 be the number of

literals in 192.

1. Only “full” cubes (cubes with n literals) are extracted from
infeasible product terms. If 11 mod n = 0 or 12 mod n = 0, none of
the cubes derived from p1 and 1); will be underfull. HN I pairs with

these product terms are eliminated from C.

2. If ll mod n # 0 and 12 mod n # 0, the HNI literal can be left in an

underfull cube when both product terms are decomposed. Extract

67

 

Cover (ipid) P—term Pair(ipids) HNI

7 l, 2 b
8 2, 6 e
9 3, 5 a
TWble C

 

 

other literals from p1 and p2 first, leaving the HNI literals in the

underfull remainder.

0 Once all HNI pairs in C have been processed, the remaining infeasible

product terms are decomposed using the standard extraction algorithm.

After extraction is complete, what remains in C is only the HNI pairs that are

in underfull cubes. These HNI literals are grouped first during cube packing.

Example 11 - Technology Mapping

o = cilia“) + bide“) + 838.2(3) + abe f J” + ace fJ5J + ab; f J6)
+£12.14” + new» + bode f J9)

When this equation is mapped onto 3 input nodes, given the cover
table shown in table 5.3, the product term pair 532w), bcdem is examined.
Since neither product term is a multiple of 3, the product terms may be

decomposed leaving the HN I literal b in the underfull cube:
0 = 515(1) + €2b(2) + 552133) + abefJ“) + acefJ5) + abEfJGJ
+51dl7) + abcdesl + bedefJg)

81 = (1680’?)

52 =3 Eden)

68

The next pair of product terms in the cover table are Ede”), abe f J6).
Since one of the product terms has three literals, it is not possible to extract
the HNI into an underfull cube.

Neither of the final pair of product terms in the cover table, obi-163),
and ace f J5), has a number of literals that is a multiple of 3. The HNI may be

extracted into underfull blocks for this HNI pair:
0 = 51b“) + €2bJ2) + 535(3) + abefJ“) + 54am + c-zbefJe’>

+eldJ7) + abédf<8> + e3ch9)

E3 = deJB’g)

54 = cest)

Now that all products in the cover table have been processed, the

following cubes are extracted:

55 = abem
56 = (.1026)
E7 = C-leJBJ

When these cubes are extracted, the following S.O.P equation is left:
0 = 61311] + 5212”] + 53813” 55f“) + 54051+ 56f[6] + 51dm+ €7dfl8] + escfp]

The last two product terms in the above equation still have three literals.

These are extracted as separate cubes:
58 = 57de8J
59 = E.'3Cf[9l

Leaving the following equation:

69

 

Cover (ipid) P-term Pair(ipids) HNI

7 1,2 b
9 3,5 a

IMWWEn

 

[

0 = E:IEJI] + 52b[2] ‘1' 53531‘1' €5fl4] + 5405] + €5fJ6] + €1dJ7] + EJ881+ Egg]

The above S.O.P. equation is ready for cube packing. Product term

pairs which remain in the cover table (table 5.4) are addressed first:

[1

P1 = 5181 + 51pr

P2 = 535”] + 540”]

Any remaining terms which share common inputs are factored out:
P3 = €5fJ4J + 56f[6]
Leaving the following equation:
0 = meJ + pig’s] + py’sl + 51dJ7J + £98] + 5&9]

Since none of the product terms in the above equation share inputs, the

product terms are grouped into 3-input blocks:

A: = pin] + $351+ 95“]
p5 = 51,117] + 6178]

Leaving the following feasible set of equations:

0 = pL1,2,3,4,5,6] + p[57,s] + €[89]

70

P1 = 813“] + Eibm

P2 = 53:1[31 + 540”]

p3 = €5f[4] + EefJ6J

p4 = pl1 ’2] + 105’” + I)?”
p5 = eldm + elf]

81 = acell’n

52 = cdem
53 = bdel3'91
E4 - ce f [5]
£5 - abem
e = 5122"”
57 = achSJ
es - e7de81
69 - 53c f J9]

5.6.1 Redundant Cover Eliminator

Once the network is mapped onto logic blocks, the Redundant Cover Eliminator
analyzes the ipid-marked mapping to determine which HNI pairs were mapped into
the same logic block. Since a HN I literal and complement that were mapped into
the same block have the same signal path, the potential hazard can not occur. The
cover that was introduced to for the hazard is unnecessary and can safely be
eliminated.

For each entry in the cover table, the set of block equations in the mapped
network is examined for HNI literals and complements which share the same block.

The cover may be eliminated iff:

71

o The HN I literal in the cover table entry appears in two product terms p1

and 10;» in a single block in the equation.

0 For the two ipid pairs i1 and i; in the cover table entry, one occurs in the
contribution set of the first product term, and the other ipid occurs in the
contribution set of the second product term. That is, i1 6 C (p1) and

i2 6 C(Pz).

Covers that are identified as redundant may be eliminated from the network.
The following rules are used to adjust the contribution sets and product terms in

the mapped network:

1. If the ipid of the cover appears in contribution set of a product term, the

ipid is eliminated from the contribution set.

2. If the contribution set of a product term is empty, the product term is

eliminated.

3. If all product terms in a block have been eliminated, the block is retained

with a “0” function. “0” function blocks will be eliminated by the merger.

Example 12 - Redundant Cover Elimination

Given the feasible set of equations in example 11 and the cover table

3] .
, aJ5J occur in the same

found in example 8, we see that the pair of Hle 8‘
logic block, as well as the pair 5111+ 1,12], Covers 8 and 9 may be eliminated

from the contribution sets of the product term, leaving the following

72

equations:

0 = p51,2,3,4,5,6] + pJSSJ
p1 = 613"] + elbm

P2 = 5333] + 5405]

P3 = Esfm + 56fl6]

p4 = elm] + 9951+ pl?”
P5 = 5?]
51 = aéelll
52 = Eden]
53 = bdem
54 = ce f J5]
55 = abem
56 = 81,36]
57 = fiberl
53 = e7de8]
59 = 0

5.6.2 Merger

Covers eliminated by the redundant cover eliminator may result in some of the
block being “underfull”. That is, it may be possible to collapse some of the blocks
into their fanouts while retaining the HN I groupings and the feasibility of the
network. In example 12, p5 could be eliminated by collapsing it back into its fanout.
The existing SIS command “xl-cover” is used to collapse the nodes into their

fanouts. This command sets up a binate covering formulation to enumerate all sets

73

of nodes which can be realized as a single block. Mathony’s algorithm is used to
solve the formulation.

This method will not separate any sum or product terms that have already
been mapped, but will simply collapse a node into its outputs if it is possible. This
ensures that all HN I pairs that have been mapped into the same logic block will
remain mapped to the same logic block. Merging the blocks will not cause any

hazard to be re-introduced.

Example 13 - Merger

Given the feasible set of equations in example 12, the merger is able to
collapse several underfull blocks onto their inputs. This elimates two

unnecessary blocks (59 and p5), leaving the following set of equations:

0 = pL1,2,3,4,5,6] + 698]

P1 = 515“] + 515”]
P2 = 83513] + €40J5J

P3 = Esfm + €6fJ6J

p4 = elm] + pi3'51+ pl?”
51 = aéelll
52 = Eden]
53 = bdem
64 - ce f [5]
55 - abeJ‘q
66 = 3526’
57 = 3122‘”

Chapter 6

Benchmark Results

Synthesis benchmarks for combinational logic were used to evaluate the effectiveness
of the new algorithm at reducing the number of CLBs needed. The benchmarks
used were the Logic Synthesis and Optimization Benchmarks (version 2.0), available
from the the Microelectronics Center of North Carolina. Comparisons were done on
a random sample of two-level and multi-level benchmarks which contained possible
hazards.

Table 6.1 through 6.3 compare the results of McCluskey’s
technology-independant hazard-free technology mapping technique against the new
technique using HNI gathering. These tables show results of mapping the
benchmark equations onto CLBs consisting of 3, 4, and 5 inputs.

The benchmark equations were first collapsed into two-level boolean
equations. The Quine-McCluskey minimization algorithm (available within SIS) was
used to arrive at a minimal sum—of-products equation. McCluskey’s
hazard-elimination algorithm was then used to introduce covers for any potential
hazards. The table shows that the number of covers required to make the equation
hazard-free before mapping.

The cube-packing technology mapper was used to arrive at an initial mapping;

the number of CLBs necessary is shown in the table. The mappings were analyzed

74

75

 

name

5xpl
93ynn
93ynunl
(317
alu2
alu4
apexl
apex3
apex5
apex6
apex7

b12

b9

c8

cc

cht
clip
cm150a
cm15la
cm152a
cm162a
cnn163a
conl
count
cps
dalu
daio
misexl
misex2
Inux
ttt2

x2

covers original mapping eliminated covers merged mapping

26
862
867

1
316
939
3250

1711
2292
775
97

32
12
105
19
46
189

32
12
12
26
18
6
152
505

6495
2

7

1

32
67

3

123
1020
1014

5
682
1668
6262

3556
5283
2489
397

89
123
212
89
174
408

99
33
32
68
52
14
440
2763

13913
8

42

75

99
265
26

118
1019
1013

5
672
1645
6195

3451
5208
2396
384

87
119
208
82
138
402

98
29
28
68
52
14
440
2708

9383
7

36
66
94
254
24

Table 6.1: Synthesis Benchmarks mapped onto 3-input blocks

76

 

name

5pr
9syn1
95ynnnl
(317
alu2
alu4
apexl
apex3
apex5
apex6
apex7
b12

b9

c8

cc

cht
clip
cm150a
cnnl51a
cm152a
cm162a
cn0163a
conl
count
cps
dalu
daio
misexl
misex2
nnux
ttt2

x1
x2

covers original mapping eliminated covers merged mapping

26
862
867

1
316
939
3250

1711
2292
775
97

32
12
105
19
46
189

32
12
12
26
18
6
152
505

6495
2

7

1

32
67
199
3

78
718
720

2
498
1187
4717

2585
3901
1751
259

55
91
149
58
66
295

57
25
24
48
36
11
297
1935

9942
4

21
55
78
171
297
18

9
3

7

1
13
39
102

18
12
1

76
711
714

2
485
1165
4682

2547
3884
1705
247

54
87
143
56
65
291

57
25
24
48
36
11
295
1896

9623
3

16
47
73
167
283
18

Table 6.2: Synthesis Benchmarks mapped onto 4-input blocks

77

 

name covers original mapping eliminated covers merged mapping
5xp1 26 58 8 55
9sym 862 506 3 506
9symml 867 513 6 513
C17 1 2 1 2
alu2 316 370 9 361
alu4 939 975 41 963
apexl 3250 3403 108 3375
apex3 1711 2321 57 2293
apex5 2292 3901 86 3884
apex6 775 1251 128 1227
apex7 97 192 14 167
b12 32 45 13 44
b9 12 64 7 61
CS 105 119 29 113
cc 19 43 7 35
cht 46 41 43 39
clip 189 216 12 210
cm150a 32 50 2 50
cm151a 12 21 4 21
cm152a 12 20 4 20
cm162a 26 41 10 33
cm163a 18 31 12 24
conl 6 7 2 6
count 152 248 47 241
cps 505 1621 82 1603
dalu 6495 7885 921 7603
daio 2 4 2 3
misexl 7 19 6 11
misex2 1 18 1 18
mux 32 55 5 54
ttt2 67 131 19 117
x1 199 245 19 227
x2 3 15 l 11

Table 6.3: Synthesis Benchmarks mapped onto 5-input blocks

78

to determine which covers were redundant based on HNI pair gathering. The table
shows the number of covers which were redundant based on HNI pair gathering.
These covers were identified and removed by the redundant cover eliminator.

Finally, the SIS command “xl-oover” was used to collapse any underfull CLBs
into their fanouts. The final column in the table shows the number of CLBs needed
to realize the benchmark specification.

To prove that the HNI-gathering algorithm retained boolean equivalency, the
final hazard-free, feasible equation was collapsed, minimized, and compared with the
original equation. To prove that the HN I-gathering algorithm eliminated all
hazards, the results of the new algorithm were analyzed with the HFLE hazard

detection algorithm of chapter 3.

6.1 Performance Analysis

On average, the new mapping hazard-free mapping algorithm outperforms
traditional technology-independent techniques, particularly when mapping onto
small block sizes. Of the 32 benchmarks which were run, the HN I gathering
technique eliminated more than twenty covers in 9 of them. The number of
eliminated covers for these benchmarks for n = 3, n = 4, and n = 5, is shown in
figure 6.1.

As is expected, the number of covers that can be eliminated increases as the
size of the block increases. Larger blocks allow more literals to be grouped into a
single block and provide a greater opportunity for mapping pairs of Hle into the
same block.

The elimination of a cover does not always result in the elimination of a CLB.

79

9.52 5.56588

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2% mac Eu mo mxoam mxoam mxoam Fxoam van

" m. m . n ._ u 4d " #q m 1: ".-.P.IT_ ”inn—IE m —_—I._
- W M n a
- M a

...... m" W W
I ..... v" m n ..

l 0" - .

_ . _ _ L _ r _ —

 

 

 

or

ON

on

ow

om

om

on

om

om

cop

peieugwua SJSAOQ 10 mowed

Figure 6.1: Eliminated Covers

 

80

20

0:52 {acacocom

 

 

 

 

m
V
m

H:

0..--.--q

I —.
l

 

 

mo mxmam mxmam mxmam Fxoam was

.: L: 5.: an: ...m.:

 

.
._
_||_

 

 

 

0..

m_.

cm

mm

on

mm

ow

paieugwgla sepoN lo iueoied

Figure 6.2: Eliminated Nodes

 

81

Frequently, the cover will have the same inputs as the product terms that it covers.
When mapping onto a n-input CLB, a product term and its cover will frequently be
mapped into the same CLB if the number of literals in the product term are less
than 12. When the cover is eliminated, the product term must remain and the CLB
cannot be eliminated.

For this sample, the new algorithm used an average of 7.53 percent fewer
CLBs than the traditional mapping algorithm when n = 3. For n = 4, the new
algorithm uses an average of 2.71 percent fewer CLBs. For n = 5, HNI pairing uses
an average of 2.22 percent fewer CLBs.

A trade-off exists between two different characteristics of logic mapping. In
order to eliminate covers, the Hle must be mapped to the same block. As the
number of inputs to a CLB increases, the more likely it is that HNIs can be mapped
to the same block. In order to reduce blocks due to cover elimination, the cover
must be mapped to a different block than the product terms which caused the
hazard. As the number of inputs to the CLB increase, the more likely that the cover
and product terms are mapped to the same block.

For most of the above examples, the best cell reduction occurred when n = 3.
Any block which contains a HNI literal and its complement must have one input
occupied by the HNI literal. In a 3-input block, the remaining two inputs are likely
to be occupied by a literal from each of the covered product terms. If this occurs,
there is no room left for the cover, which must be mapped into a separate CLB.

From figure 6.2, it is clear that the algorithm does provide some reduction for
logic blocks with more than 3 inputs. In general, however, the algorithm is most

effective for 3-input blocks. As the size of the CLB increases, hazard covers are

82

more easily mapped into the same logic blocks as the product terms they cover.

Chapter 7

Summary and Conclusions

7.1 Summary

LUT-based FPGAs offer the advantages of rapid prototyping and experimentation
with a minimum of engineering cost. The commercial success of these types of
FPGAs has spurred a new area of research focused on the efficient mapping of
boolean logic onto these devices. Until recently, however, this research has largely
been limited to the synchronous uses of these devices. Implementing self-timed
circuits using FPGAs poses a unique set of challenges, and is emerging as a new
area of research.

Self-timed sequential circuits offer several advantages over synchronous
sequential systems. A self-timed circuit is potentially faster, may take up less space,
and does not have problems with clock skew. However, the synthesis of self-timed
circuits is considerably more complex. Self-timed sequential circuits are particularly
prone to hazards in next-state combinational logic, since the circuits are given no
opportunity to “settle” before the next state transition. Any glitch that occurs in
the combinational logic may manifest itself as an incorrect next-state.

Implementing asynchronous circuits in a technology demands a careful
characterization of the hazard behavior of the technology. The implementation of

the Xilinx LUT FPGA is a particularly interesting case. Maheswaran and Akella

83

84

[16] have shown that logic mapped into a single logic block is guaranteed to be
hazard-free.

This paper has explored the effects of hazard-free CLBs on hazard analysis
and synthesis methods. A traditional hazard analysis algorithm is modified to
properly detect hazards in a network composed of these hazard-free logic blocks. A
technology mapping algorithm is also modified to produce a hazard-free mapping of
the network using the hazard-free nature of the individual logic blocks.

Traditional hazard analysis and synthesis techniques are reviewed in chapter 2
to show the relationship between hazards, delay, and signal path. The delay
characteristics of a network of simple gates are very different from a network of
Xilinx CLBS. The differences between these two implementations are explored in
chapter 2, and a generalized Hazard-free Logic Element (HFLE) was defined, which
may be used to model both simple gates and CLBs.

The role of delay and signal fan-out with respect to static and dynamic
hazards are also explored in chapter 2. A boolean sum-of-products equation is
analyzed in detail to relate hazards to boolean and delay characteristics in product
terms.

Chapter 3 applies signal-path analysis to Ungers’s hazard theorems and
extends them to networks composed of arbitrary HFLEs. HFLE-marked logic
diagrams are introduced, which are used to identify HNI complement pairs which
share the same signal path. Theorems 9 - 12 are extensions of McCluskey’s
techniques to detect hazards in networks composed of HFLEs.

The knowledge of hazard absorption gained through these new hazard analysis

techniques is used to modify an existing technology technique in chapter 6. A new

85

hazard-free synthesis algorithm is introduced, which consists of a
technology-independent hazard—eliminator, a technology mapper, a redundant cover
eliminator, and a merger. The hazard eliminator introduces covers in the network to
assure that no spikes will occur in the network in a technology-independent manner.
The hazard-eliminator also produces a marked network so that the literals in the
original equation may be related to the literals in the mapped equation.

The cube packing technology mapping algorithm was modified in order to
propagate the literal markings, and modifications were also made to better group
complementary pairs of HNIs. A HNI literal and complement which are mapped
into the same CLB share the same signal path. When this occurs, the potential
hazard can no longer occur. Covers that were introduced to eliminate these hazards
are unnecessary, and the redundant cover eliminator removes those covers from the
circuit.

When redundant covers are removed, the resulting mapping may have
underfull blocks, which occupy valuable CLB space. The merger attempts to reduce
the number of blocks by merging underfull blocks onto their fanouts.

The performance of the new synthesis algorithm was tested in chapter 7, by

applying the new algorithm to a set of standard logic synthesis benchmarks [1].

7.2 Contributions

This paper has the following salient contributions:

0 This paper has presented a new way of modeling circuits, based on
hazard-free logic elements. This model may be applied to many

implementations whose network components are hazard-free, from simple

86

gates to memory-based F PGAs.

o It has been shown that a hazard cannot accur if the complementary pair of
literals which “cause” the hazard have the same signal path. Sharing of
signal paths is possible in networks of HFLEs, and this observation leads to

analysis and synthesis methods for HFLE networks.

0 This paper has provided a new analysis method for networks composed of
hazard-free logic elements. These analytical results lay a foundation for

future hazard research, particularly involving LUT-based FPGAs.

o This paper has successfully adapted an existing technology mapping
technique using the hazard characteristics of LUT-based F PGAs. The new
techniques in many cases produces hazard-free mappings with fewer blocks
than traditional techniques. This mapping technique directly impacts the

efficiency of mapping asynchronous sequential circuits onto Xilinx FPGAs.

7 .3 Future Work

The analysis and synthesis techniques in this paper assumed single-input change
constraints on the combinational logic. Further work is necessary to extend the
ideas in this paper to circuits in which multiple inputs are permitted to change
simultaneously.

The synthesis technique introduced in this paper used a modified cube packing
algorithm. Cube packing was chosen because of its simplicity; more efficient
technology mapping algorithms exist. Using one of the more complex algorithms,

such as one of the other SIS algorithms, may produce mapping with fewer blocks.

87

Modifications to these algorithms to propagate the signal path information would
need to be completed, and the algorithms may also need to be modified to
encourage HNI grouping.

The technology mapper, redundant cover eliminator, and merger made an
assumption that each logic block contained only a single output. The Xilinx CLBs
allow multiple outputs per CLB, though both outputs must be derived from the
same equation. In a network where CLBs with two outputs and three inputs are

permitted, the equation f = ab + bed could be mapped as follows:

f = [11+ [21d
[1] = ab
[2] = be

If these are mapped into two CLBs, one with inputs a, b, and c and one with
inputs [1], [2], and d, the complementary static-1 hazard would be eliminated
because the the HN I pair (2, I) would be mapped into the same logic block. These
types of mappings may make possible many more opportunities for HNI grouping

and elimination of hazards.

Bibliography

[1] R. Lisanke, “Logic Synthesis and Optimization Benchmarks User Guide”,

Microelectronics Center of North Carolina.

[2] “SIS: A System for Sequential Circuit Synthesis”, Electronics Research

Laboratory Memorandum No. UCM/ERL M92 / 41

[3] D. A. Huffman, “The Design and Use of Hazard-Free Switching Networks,”

Journal of the ACM, pp 4-47, 1957.

[4] E. B. Eichelberger, “Hazard Detection in Combinational and Sequential
Switching Circuits,” Fifth Annual Symposium on Switching Circuit Theory and

Logical Design, Princeton, N.J. 1964.

[5] K. Karplus, “Xmap: a Technology Mapper for Table-lookup Field

Programmable Gate Arrays,” ACM/IEEE Proceedings of the Design

Automation Conference, pp. 240-243, 1991.

[6] E. J. McCluskey, Introduction to the Theory of Switching Circuits,

McGraw-Hill, 1965.
[7] E. J. McCluskey, Logic Design Principles, Prentice-Hall, 1986.

[8] H. C. Torng, Switching Circuits, Theory and Logic Design, Addison-Wesley,

1972.

88

89

[9] S. H. Unger, Asynchronous Sequential Switching Circuits, Wiley-Interscience,

1969.

[10] Xilinx, Technical Data, XC3100 Logic Cell Array Family, Xilinx Corporation,

1992.

[11] K. Chung and .1. Rose, “TEMPT: Technology Mapping for the Exploration of
FPGA Architectures with Hard-Wired Connections,” ACM/IEEE Proceedings

of the Design Automation Conference, pp. 361-367, 1992.

[12] P. Sawkar and D. Thomas, “Area and Delay Mapping for Table-Look-Up Based
field Programmable Gate Arrays,” ACM/IEEE Proceedings of the Design

Automation Conference, pp. 368-373, 1992.

[13] P. K. Chan and S. Mourad, Digital Design Using Field Programmable Gate

Arrays, Prentic—Hall, 1994.

[14] R. J. Francis, J. Rose, and Z. Vranesic, “Chortle-crf: Fast Technology Mapping
for Lookup Table-Based F PGAs,” ACM/IEEE Proceedings of the Design

Automation Conference, June 1991.

[15] J. P. Roth and R. M. Karp, “Minimization over Boolean Graphs,” IBM Journal

of Research and Development, April 1982.

[16] H. Maheswaran and V. Akella, “Hazard-Free Implementation of the Self-Timed
Cell Set for the Xilinx 4000 Series FPGA, ” Electrical Engineering Technical

Report, University of California at Davis, 1994.

90

[17] M. Yu and RA. Subrahmanyam, “A Path-Oriented Approach for Reducing
Hazards in Asynchronous Designs, ” ACM/IEEE Proceedings of the Design

Automation Conference, pp. 239-244, 1992.

[18] P. Sawkar and D. Thomas, “Performance Directed Technology Mapping for

Look-Up Table Based FPGAs, ” ACM/IEEE Proceedings of the Design

Automation Conference, pp. 208-212, 1993.

[19] R.J. Francis, J. Rose, Z. Vranesic, “Technology Mapping for Delay
Optimization of Lookup Table-Based F PGAs,” International Workshop on

Logic Synthesis, 1991.

[20] R. Murgai, R. K. Brayton, A. Sangiovanni-Vincentelli, “Sequential Synthesis

for Table Look Up Programmable Gate Arrays,” ACM/IEE Proceedings of the

Design Automation Conference, pp. 224-229, 1993.

[21] Xilinx, Xilinx XC4000 Series Product Specification, Xilinx Corporation, 1995.

nICHIcaN STATE UNIV. LIBRARIES
JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ
31293014137875