AI.\.h a .5; i

it?

WW-

ru.§.i..§»ma.
.nrafia.

a

e. .
A . .%..

,.V b. :l .,
nmyz...‘ mar:
Wm» why
.: .

.

o.

I.

ha.
y

n...
man.” 5.4m}

.. imfimfiflfih

 

THE818

SUTATE UN

IIIIIIIIIIIIIIII IIIIII IIIIII IIIIIIIIIIII

1293 01688 5265

 

 

 

 

 

 

This is to certify that the
thesis entitled

REDESIGN PROCESS OF DIGITAL VLSI CIRCUITS WITH
INCOMPLETE IMPLEMENTATION INFORMATION

presented by

Mohammad Athar Khalil

has been accepted towards fulfillment
of the requirements for

Master's degree in_E]_e_C_1'.Li_Cfll Eng

Mfiyé/or

Major professor

Date Oé/Og/Qg/

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

 

 

LIBRARY

Michigan State
Unlverslty

 

 

 

PLACE IN RETURN BOX
to remove this checkout from your record.
TO AVOID FINES return on or before date due.

 

DATE DUE MTE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

use mmmu

 

REDESIGN PROCESS OF DIGITAL VLSI CIRCUITS WITH INCOMPLETE
IMPLEMENTATION INFORMATION

By

Mohammad Athar Khalil

A THESIS
Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of
MASTER OF SCIENCE
Department of Electrical Engineering

1998

ABSTRACT

REDESIGN PROCESS OF DIGITAL VLSI CIRCUITS WITH INCOMPLETE
IMPLEMENTATION INFORMATION

By

Mohammad Athar Khalil

This thesis deals with the problem of redesigning digital VLSI circuits with incom-
plete implementation information. Given a digital circuit with incomplete implementation
information, the developed redesign process recovers functionality of the missing parts in
original design using test generation techniques. A circuit is redesignable if the transfer
functions of the portion with incomplete implementation information can be derived. The
derived transfer functions are then used to re-implement the missing portions. We do not
intend to discover the exact circuit schematic and components that were present in the cir-
cuit originally implemented. Rather, the functions originally intended to be present will be
identical. The developed redesign process is comprised of three steps: Redesignability
check, Feasibility check and Re-implementation. A set of simple rules have been devel-
oped to quickly analyze whether redesigning the missing parts of a target circuit is cost
effective or not. A number of circuit partitioning schemes have also been developed to
decrease the computational complexity and to improve the quality of the redesign process.

Several benchmark circuits have been tested and satisfactory results are obtained.

To my mother and father.

iii

ACKNOWLEDGEMENTS

I would like to express my sincere gratitude to my advisor, Dr. Chin-Long Wey, for
all his assistance with my research and the development of this thesis. His guidance, care,
patience and constant encouragement not only kept me motivated but also were crucial for
keeping the research objectives in perspective. Thanks are also due to the members of my
committee, Dr. James A. Resh and Dr. Anthony S. Wojcik, for all their help and support.

I am very grateful to my family for encouraging me to pursue higher studies, espe-
cially to my parents for the encouragement and support they have given me every day of

my life. I also wish to thank all my friends for their moral support.

iv

TABLE OF CONTENTS

LIST OF TABLES ............................................................................................................. vi
LIST OF FIGURES .......................................................................................................... vii
Chapter 1
INTRODUCTION ............................................................................................................... 1
Chapter 2
BACKGROUND ................................................................................................................. 8
2.1 Boolean Difference ........................................................................................... 8
2.1 D-Algorithm ................................................................................................... 12
Chapter 3
PROBLEM STATEMENT ............................................................................................... 19
Chapter 4
DEVELOPMENT ............................................................................................................. 30
4.1 Redesign Methodologies ....................................................................................... 30
4.1.1 Redesignability Check ................................................................................. 31
4.1.2 Feasibility Check ......................................................................................... 46
4.1.3 Re-implementation ...................................................................................... 55
4.2 Improvement ......................................................................................................... 59
4.2.1 BO-Augmentation ........................................................................................ 61
4.2.2 BI-Augmentation ......................................................................................... 64
4.2.3 Multiple B-Groups ....................................................................................... 66
Chapter 5
EXPERIMENTAL RESULTS .......................................................................................... 70
5.1 Redesign Process ................................................................................................... 70
5.2 Results ................................................................................................................... 72
Chapter 6
CONCLUSIONS ............................................................................................................... 82
APPENDIX A
BENCHMARK CIRCUITS PARTITIONING DETAILS ................................................. 86
REFERENCES .................................................................................................................. 91

Table 2.1:

Table 2.2:

Table 2.3:

Table 3.1:

Table 4.1:

Table 5.1:

Table 5.2:

Table 5.3:

LIST OF TABLES

Truth Table, 2-input NOR gate ........................................................................ l4
Singular Cover, 2-input NOR gate ................................................................... l4
Propagation D-Cubes, 2-input NOR gate ......................................................... 15
Simulation Results of Example Circuit 1 .......................................................... 27
Truth Table for B-group of Example Circuit III ............................................... 57
Benchmark Circuits ......................................................................................... 74
Benchmark Circuits Partitioning Parameters ................................................... 76
Experimental Results of Benchmark Circuits .................................................. 78

vi

Figure 1.1:
Figure 1.2:

Figure 1.3:

Figure 2.1:
Figure 2.2:

Figure 3.1:

Figure 3.2:

Figure 4.1:

Figure 4.2:

Figure 4.3:

Figure 4.4:

Figure 4.5:

Figure 4.6:

Figure 4.7:

Figure 4.8:

Figure 4.9:

LIST OF FIGURES

Process Model of Re-engineering .................................................................. 3
Example Circuit, 24ml: (a) Netlist; and (b) Schematic ................................... 6

Example Circuit 1, with Incomplete Implementation Information: (a) Netlist;

and (b) Schematic .......................................................................................... 7
Example Circuit for Boolean Difference ...................................................... 11
Example Circuit for D-Algorithm ................................................................ 18
System Model: (a) CCM; and (b)-(d) Redesign Modeling ........................... 20

Circuit Partitioning Scheme: (a) Example Circuit I Partitioning; (b) and (0)
Schematic of the Example Circuit I Partitions ............................................. 23

Example circuit 11, with Incomplete Implementation Information: (a) netlist;

(b) schematic; and (c) B-group .................................................................... 32
CI-Partitioning: (a) Blocks; (b) Block Ci ..................................................... 34
Example Circuit HI: (a) B-group; (b) C—group; (c) Partitioned Blocks
C1,C2,C3; and ((1) Circuit Schematics for C1, C2, C3 .................................. 37
(a) Example Circuit IV: (b) B-group; (c) C-group; and (d) Partitioned Blocks
C1,C2 ............................................................................................................ 39
CO-Partitioning: (a) Blocks; (b) Block Ci .................................................... 41

Example Circuit V: (a) B-group; (b) C-group; (c) Partitioned Blocks
C1,C2,C3;and (d) Circuit Schematics for C1, C2, and C3 ............................. 43

(a) Example Circuit VI: (b) B-group; (c) C-group; and (d) CO-Partitioned
BIOCkS C1,C2,C3 .......................................................................................... 44

A-group Partitioning: (a) First Step; Example Circuit 1: (b) Before Partition-
ing; and (c) After Partitioning ...................................................................... 49

A-group Partitioning: (a) Second Step, Block Ai; Example Circuit HI: (b) A-
group; (c) Block A1; and (d) Block A2 ........................................................ 51

vii

Figure 4.10:

Figure 4.11:

Figure 4.12:

Figure 4.13:

Figure 4.14:

Figure 5.1:
Figure 5.2:

Figure 5.3:

Augmented Partitioning: (a) Concept; (b) Augmented B-group; (c) BO-Aug-

mented C- group; and (d) BI-Augmented A- group ...................................... 6O
BO-Augmentation: Example Circuit VI; (a) Block C1; (b) Block C1,; (b)
Augmented B’-group; and (c) C’—group ...................................................... 63
BI-Augmentation: (a) Example Circuit 1; (b) Original B-group; (c) Aug-
mented B’-group; and (d) A’ -group ............................................................. 65
Multiple B-Groups: (a) Example Circuit VII; (b) Example Circuit VIII ...... 67
Multiple B-Groups: Example Circuit IX (a) B1 and B2 groups, and (b) Aug-
mented B1 - group ........................................................................................ 69
Redesign Process .......................................................................................... 71

Benchmark Circuit: (a) Script File; (b) cml38a.b1if; and (c) cml38a.gate...73

Circuit cml38a Partitioning: (a) B-Group; (b) C-Group; (c) A-Group; and ((1)
Inputs and Outputs of Each Group ............................................................... 77

viii

Chapter 1

INTRODUCTION

Industry and military community increasingly rely on the use of "smart" systems for
intelligent manufacturing control systems and weapon systems. The components that make
these systems "smart" are the complex microelectronics devices that form their "brain."
Microelectronics technologies are extremely dynamic and now become obsolete every 18
months. This makes microelectronics the main factor driving the "smart" systems obsoles-
cence and defence missions degradation. The life of these "smart" systems can be generally
extended by improving their reliability and maintainability using advanced technologies.

Replacement methods have been effectively used to resolve the microelectronics
obsolescence problem to enhance maintainability. However, the methods are effective only
if the digital designs are well documented. Unfortunately, the present methodologies per-
form poorly and many designs are undocumented [1]. Many existing designs have been
developed without the assistance of a comprehensive CAD process, which means that the
detailed information about the design at various intermediate levels is not available. The
netlist, HDL (Hardware Description Language), or design data is not present, and system
interfaces and functional requirements are not documented. As a result, one may either use

the exact replacement parts from sources that were not on the original documentation, or

take a similar part that is not a direct replacement. Further, one may develop a re-engineer-
ing process for a form, fit, and function replacement based on initial specification.

Consider a process model of re-engineering shown in Figure 1.1 [2]. The process
model is captured by two sectioned triangles. The higher levels are concepts and require-
ments, while the lower levels include designs and implementations. Forward engineering
is the process of developing a system by moving from high level abstract specification to
detailed, implementation-specific manifestations [3]. Conversely, reverse engineering is
the process of analyzing a system in order to identify system components, component rela-
tionships, and intended behavior. In other words, reverse engineering is the process of con-
structing high level representation from lower level instantiations of an existing system.

Reverse engineering process for digital circuits verifies schematics and perfor-

mance specification against actual hardware and provides a method of identifying internal
structures down to a device level to determine an optimal design approach [1]. The individ-
ual devices are identified and characterized and a working schematic is developed through
the use of various instruments and design tools. Reverse engineering has been an effective
method that enhances the maintainability of the existing undocumented designs. However,
manual reverse engineering methods won’t work for complex devices. Hence, new meth-
odologies are needed to deal with complex digital microcircuits.

Even though today’s CAD tools provide a sophisticated design process from behav-
ioral level description to detailed physical implementation, redesigning a circuit due to a
minor change or technology change requires a design time equal to that of the entire circuit,
or achieves a performance worse than the original one. The new methodologies can also be

employed to reduce the redesign time of existing circuits for minor changes while still

Altemation

 

Concept

Requirement

 

Design

 

 

 

Implementation

 

V

 

 

 

 

e-design

Figure 1.1: Process Model of Re-engineering.

maintaining or improving the original performance, that is, such techniques can be used for
safe replacement of modules, blocks of logic gates, in the gate level design of entire circuit.
Safe replacement refers to substitution of a module in the existing design with a redesigned
module, in order to achieve area reduction and/or timing improvement of gate level design
while preserving the overall functionality of the existing circuit.

This study deals with a challenging problem for enhancing maintainability of
undocumented complex digital designs. Consider the flow describing the redesign process
illustrated in Figure 1.1, the original implementation information in System A is either
missing or incomplete. Redesign starts with only partial knowledge in the implementation
level [4]. One of the most difficult aspects of redesign is the recognition of the functionality
of existing implementation [5]. Two problems involving the recognition of the functional-
ity can be identified:

1. The implementations of the missing or incomplete parts are given, but their

functionality are unknown; and

2. The implementations of the missing or incomplete parts are unknown, but the

functionality of the entire digital circuit is known.

The former problem is to recognize the functionality of each missing part from the
possible design styles and/or known libraries. The later problem is to recover the function-
ality of the missing or incomplete parts and to re-implement these parts [6,7]. This study
deals with the later problem and develops a redesign methodology to support undocu-
mented complex digital designs using the die and test vectors as data sources.

More specifically, given a digital VLSI circuit, the original implementation infor-

mation is either missing or incomplete. Consider the example circuit, 24ml [8], which is a

three bit adder. Figure 1.2(a) shows the circuit netlist generated by sis [9], while Figure
1.2(b) illustrates the schematic circuit diagram. It is assumed that the implementation of
Block B is missing or incomplete. The masked portion, of the netlist and schematic for
example circuit I shown in Figure 1.3(a) and (b) respectively, represents the missing or
incomplete implementation information. With the partial knowledge in the implementation
and the functionality of the digital circuit, an efficient redesign process is developed to rec-
ognize the functionality of the missing/incomplete parts and to recover the original design
from the existing implementation. A circuit is redesignable [4] if the transfer function, i.e.,
inputs/outputs relationship, of each missing part can be derived. Therefore, the missing
parts can be re-implemented from the derived transfer functions. Note that we do not intend
to discover the exact circuit schematic and components that were present in the circuit orig-
inally implemented. Rather, the functions originally intended to be present will be identical.
In this study, the redesign problem is resolved by using some test generation tech-
niques. Chapter 2 will briefly review the test generation schemes used in this study. In
Chapter 3, the redesign problem is stated formally and the problem is formulated with a sys-
tem model. Chapter 4 describes the development of redesign process and also presents
schemes to improve its quality. Chapter 5 presents the redesign process and also reports our
experimental results. Finally, Chapter 6 gives the conclusions and presents some ideas for

future research.

 

model 24ml

 

.inputs 1 234567
.outputs 24 25 26 27
.default_input_arrival 0.00 0.00
.default_output_required 0.00 0.00
.default_input_drive 0.07 0.07
.default_output_load 3.00
.gate or2 a=2 b=5 O=[386]
.gate nor2 a=3 b=6 O=[10]
.gate invl a=4 O=[390]
.gate invl a=7 O=[391]

.gate nand2 a=[390] b=[391] O=[458]

.gate aoi22 a=[458] b=1 c=4 d=7 O=[28 7]
.gate nand2 a=3 b=6 O=[46 0]

.gate oai21 a=[10] b=[287] c=[460] O=[465]

.gate ao22 a=[386] b=[465] c=2 d=5 0:24
.gate xor a=l b=4 O=[13]

.gate xor a=[13] b=7 O=27

.gate invl a=1 O=[38 9]

.gate oai22 a=27 b=[389] c=[390] d=[391] O=[393]
.gate invl a=[393] O=[44 9]

.gate or2 a=3 b=6 O=[45 2]

.gate nand2 a=[452] b=[460] O=[394]
.gate nand2 a=[393] b=[394] O=[486]
.gate oai21 a=[393] b=[394] c=[486] 0:26
.gate oai21 a=[449] b=26 c=[460] O=[396]
.gate nor2 a=[386] b=[396] O=[289]

.gate nand3 a=[396] b=2 c=5 O=[476]
.gate oai21 a=[289] b=24 c=[476] 0:25
.end

 

 

lgolszsl

 

 

 

3
6 E'
458
90 _
4 v
+
7—{3‘3’91 L
1 +
I__

 

 

 
 

465 I

(a)

E

 

    

 

 

 

 

 

 

 

 

 

 

 

 

III

Input nodes: 12 3, 4, 5, 6, 7
Output nodes: 24,25,26,27

Figure 1.2: Example Circuit, z4ml: (a) Netlist; and (b) Schematic.

 

.model 14ml

.input512345 67

.outputs 24 25 26 27
.default_input_arrival 0.00 0.00
.default_output_required 0.00 0.00
.default_input_drive 0.07 0.07
.default_output_load 3.00

.gate or2 a=2 b=5 O=[386]

.gate nor2 a=3 b=6 O=[10]

.gate invl a=4 O=[390]

.gate invl a=7 O=[391]

.gate 11de a=[390] b=[39l] O=[458]
.gate a0122 a=[458] b=1 c=4 d=7 O=[28 7]
.gate 11de a=3 b=6 O=[4 60]

.gate oa121 a=[10] b=[287] c=[460] O=[465]

 

.gate a022 a=[386] b=[465] c=2 d:5 0:24

.gate xor a=1 - 0:13]

.gate xor a=[l3] b=78 0:27

.gate invl a=1 O=[38 9]

.gate oa122 a=27 b=[389] c=[390] d=[391] O=[393]
.gate invl a=[393]0-

.gate or2 a=3 b=6 O=[45 29]

.gate nand2 a=[452] b=[460] O=[394]

.gate nand2 a=[393] b=[394] O=[486]

.gate oaiZl a=[393] b=[394] c=[486] 0:26

 

 

.gate nand3 a=[396] a=2 c=5 O=[476]
.gate oa121 a=[289] b=24 c=[476] 0:25
.end

 

 

<3me

   

(a)

25

26

Input nodes: l,2,3,4,5,6,7
Output nodes: 24,25,26,27

Figure 1.3: Example Circuit I, with Incomplete Implementation Information:
(a) Netlist; and (b) Schematic.

Chapter 2

BACKGROUND

This chapter reviews the test generation methods that can be used to resolve the
redesign problem. There are various algorithmic automatic test pattern generation systems
(ATPG systems) currently in use for combinational logic circuits. Some ATPG systems
generate algebraic equations for the circuit and then perform symbolic manipulation on
these equations to generate all possible test patterns for a particular fault. Other ATPG sys-
tems find the test vectors in a topological, or structural, manner. Such ATPG’s frequently
use a data structure representing the circuit to be tested. The test vector is generated by
assigning the values corresponding to the discrepancy at the line with a fault and then
searching for consistent values for all circuit lines such that the discrepancy becomes
observable at a circuit primary output [10]. A brief discussion of one algebraic manipula-
tion method (Boolean Difference) and one structural search method (D-Algorithm) fol-

lows:

2.1 Boolean Difference

The basic principle involved in Boolean Difference is to derive two Boolean

expressions, one of which represents the fault free behavior of the circuit and the other rep-

resents the logical behavior under an assumed single stuck at fault condition. These two
equations are then exclusive-ORed; a fault is indicated if the result is 1 [11].

Let F (X ) = F (x1, ..., x") be a logic function of 11 variables. If one of the inputs to
the logic function, e.g. input x,- , is faulty, then the output would be F (x1, ..., ii, ..., x") .
The Boolean difference of F (X) with respect to x,- is defined as:

d -
Z;I?'(X) = F(x1,...,xi, ...,xn)€BF(x1,...,x,-,...,xn)
I

It can also be represented as [12]:
iF(X) = Fi(0) 6 Fi(1)
dxi

where

171(0) : F(xl, ...,x 0, xi“, ,xn)

i-l’

F(1)= F(x1,...,xi_ 1,1,x,.,1,..., xn)

The function ZJ71" (X ) is called the Boolean difference of F (X) with respect to xi .
i

It can be seen that when F(xl, ...,xi, ...,xn)¢F(x1,...,x,-,...,x ), d F(X) = 1 and

d—

thatwhen F(x], ...,xi, ...,xn) : F(xl, .. —F(X) : 0. Todetectafaulton

or X', -: x9") ,xid

xi , it is required to find input combinations so that whenever x,- changes to x; , (due to a
fault), F (x1, .. ,xn ) will be different from F (x1, ,x n). In other words the

aim is to find input combinations for each fault occurring on xi such that a‘é-HX) = 1 .
1'

Some useful properties of the Boolean Difference are as follows [13]:

finx) = %F(X); F (X) denotes the complement of F (X). (2.1)
i 1'

—F(X) = —_F(X)

dxi dxi (2-2)
51% <F<X»)= §g(—<F<X») (2.3)

d d d d d

memm = F(X)F£(G(X)) e C(X)3;i(F(X)) 6» IZZ‘F‘X”XHZG(X))
(2.4)

d —- d — d d d

Emir) + G(X)| = F(X)a—£(G(X)) ea G(X)d—xi(F(X)) 63 (3171(F(X»)(7;.~G(X))

(2.5)

d _ d d
52mm 69 G(X)| .. EHX) Gad—ham (2.6)

A Boolean function F (X) is said to be independent of x,- if and only if F (X) is log-
ically invariant under complementation of x,- , that is if F (x1, ..., xi, ..., x") =
F(x1,...,x,~,...,xn).

This implies that a fault in x,- will not affect the final output F (X) and

:gr—F (X) = 0. Based on this, some additional properties can be added [11]:
i

H‘émr) = o; if F(X) is independent of x,.

%F(X) = 1; if F(X) depends only on xi.
1'

£IF(X)G(X)I = F(X)2d;(G(X)) ; if F (X) is independent of xi.
(Iii—IF (X) + G(X)| = F—‘(_X-);;(G(X)) ; if F (X) is independent of xi.

The effect of two faults at the input of a logic circuit on its output can be analyzed

by defining the double Boolean difference as follows [14]:

IO

d2 _ d L _ d .5’.
WW) _ 5(dxj(F(X))) - afldfo‘X”)

t j 1

2
—¥d——F(X) : F(0,0)$F(O, l)63F(1,0)$F(1, 1)
dxidxj

Thus test generation for multiple stuck at faults can be generalized by using Multi-

ple Boolean Differences.

 

dP d d(P - 1)
____.. = _ F
dxi. . . dxip F(X) dxldxi. . .dxip _ I (X)

The Boolean difference method generates all tests for every fault in a circuit. It is a
complete algorithm and does not require any trial and error. However, the method is costly
in terms of computation time and memory requirements. For large circuits, a great amount
of algebraic manipulation may be required to derive test for a given fault [15]. This is the
reason, that we have used efficient partitioning schemes, (discussed in chapter 4), to reduce
the size of target circuit, so that usage of Boolean difference method for our problem
becomes feasible.

Consider example circuit given below in Figure 2.1, which is a part of the circuit

 

[12-

“2 : N386 — +—

1.15 — 81
N46

 

 

 

 

 

 

 

 

 

Figure 2.1: Example Circuit for Boolean Difference.

shown in Figure 1.2. Using Boolean difference for the node N465, we can write

11

F = N24 = N465(“5+“2)+“5“2

dF

 

 

dN465 = F465(0)€BF465(1)

The above expression shows that the node N 465 will be sensitized to primary output
N24 when inputs u2 and us are not equal. Considering that the node N465 is not accessible,
the logic value of this node can be observed at the output node N24 by setting u2 and us to
be complement of each other. The Boolean difference expression gives all possible sensi-
tized paths for the node, that is, in this example the possible ways to sensitize N465 to N24

are to have either 132 : us or u2 : 55.

2.2 D-Algorithm

Before going into the details of D-Algorithm, the main concepts of structural test
generation methods for stuck at faults are discussed briefly. There are three following fun-

damental operations involved in generating a test for a stuck at fault:

Fault Sensitization

It is the process of generating a discrepancy at the fault site.

12

Fault Propagation

It is the process of moving a discrepancy closer to a circuit output.

Line Justification
It is the process of assigning consistent values to all of the lines in the circuit that

were not assigned values through fault sensitization or fault propagation.

The D-algorithm [16] uses sensitized paths to find a test vector for a fault if one
exists. It has been specified formally, and is appropriate for computer implementation. The

notations and certain new terms that will be used are first described before going in to the

details of D-Algorithm [17].

D-Notation

To keep track of error propagation values must be considered in both the fault free
circuit N, and the faulty circuit N f defined by the target fault f. For this we define composite
logic values of the form v/vf, where v and Vf are the values of the same signal in N and Nf.
The composite logic values that represent errors, 1/0 and 0/1, are denoted by symbols D and
D respectively. This is a compact way of specifying how faults propagate through a circuit.
D implies that in the good machine a 1 is to be found at the node holding D, whereas in the
faulted machine a 0 is to be found at that node. D is defined analogously. The other two
composite values, 0/0 and III, are denoted by 0 and 1. Any logic operation between two

composite values can be done by separately processing the fault free and faulty values, then

13

composing the results. For example, D + 0 = O/ 1 + 0/0 = 0 +0/ 1+0 = 0/1 = D. To these four
binary composite values a fifth value (X) is added to denote an unspecified composite
value, that is, any value in the set {O,1,D,D}. It can be verified that D behaves consistently

with the rules of the Boolean algebra.

Singular Cover

The Singular Cover of a logic gate is a compact representation of its truth table. For
example, the truth table and singular cover of a 2-input NOR gate, with inputs a, b and out-

put c, are given in Table 2.1 and Table 2.2 respectively.
Table 2.1: Truth Table, 2-input NOR gate

 

 

 

 

 

a b c
O 0 1
0 1 0
1 0 0
1 1 0

 

 

 

 

 

Table 2.2: Singular Cover, 2—input NOR gate

 

 

 

 

 

 

 

 

a b c
0 0 1
X 1 0
l X 0

 

Each row of the singular cover is called a CUBE. The set of cubes, which contains

0 as the output value, is called the P0 set. The set of cubes containing 1 as the output value

14

is called the P1 set.

Propagation D-Cubes

The propagation D-Cubes of a gate are those which cause the output of a gate to
depend solely on one or more of its inputs (usually one). This allows a fault on this input to
be propagated through the gate. For example, the propagation D-cubes for a 2-input NOR

gate are given in Table 2.3.

Table 2.3: Propagation D-Cubes, 2-input NOR gate

 

 

 

 

b
D
O
D

UGO»
Odd”

 

 

 

 

 

Propagation D-cubes can be derived from the singular cover, or by inspection. To
generate the propagation D-cubes, intersect region P0 of a gate’s cover with region P1
according to the following algebraic rules:

OnO=OnX=XnO=O
InlzlnX=an=l
XnX=X
1nO=D
On1=D
In general, it is possible to have up to 2(2N-1) propagation D-cubes for an N -input

gate, so normally only those cubes with a single D in the inputs are stored.

15

Primitive D-Cubes of Fault (P.D.C.F.)

A Primitive D-Cube of Fault for a fault in a circuit is used to specify the existence
of a given fault. It is a set of inputs to the circuit which bring the fault to the circuit output.
The P.D.C.F. for a fault are generated in the following manner:

1. Generate singular covers for the circuit in both its faulted and fault-free states.

2. Intersect the P0 cubes of the fault free cover with the F1 cubes of the faulted

cover and intersect the P1 cubes with the F0 cubes. F1 and F0 play analogous
roles in the faulted cover to P1 and P0 in the fault-free cover. Intersection is
defined by intersecting each element of the cubes in the same manner as

already defined for propagation D—cubes.

D-Intersection

The D-Intersection is the method used for building sensitized paths. It is a set of
rules which show how D signals at the outputs of gates intersect with the propagation D-
cubes of other gates, allowing a sensitized path to be constructed. Following are the set of
rules, for the D-cube intersection:
Let A : (a1,a2, ...,an) and B = (b1,b2,...,bn) be D-cubes where ai and bj e
{0,1,D,D,X} for i,j = 1,2,. . .,n. The D-intersection, denoted by A n B is given by:
L an=q
2. IfaiatXandbiaéXthen
ambi=as ifbi=ai

= 0; otherwise.

16

 

Finally A ('1 B : Q, i.e. the empty cube, if for any i, ai n bi = Q; otherwise

AnB=a,-nbi,...,annbn

The Full D-Algorithm

1. Choose a P.D.C.F. for the fault under consideration.

2. Sensitize all possible paths from the faulty gate to a primary output of the cir-
cuit. This is done by successively intersecting the P.D.C.F. of the fault with
the propagation D-cubes of successor gates. The process is called the “D-
Drive”.

3. Justify the net assignments made during the D-drive by intersecting the singular
covers of gates in the justification path with the expanding D-cube. This is

called the “Consistency Operation”.

The D-algorithm is applied in solution of our redesign problem with the following

modification.

1. Choose D as the value for the unknown node in the circuit.

2. Sensitize paths from this node to a primary output of the circuit. This is using
the propagation D—cubes of gates. The process is similar to the “D-Drive”.

3. Justify the net assignments made during the D-drive by intersecting the singular
covers of gates in the justification path with the expanding D-cube. This is the
“Consistency Operation” of the D-Algorithm.

Consider the example circuit shown in Figure 2.2. Assume that the node 396 is not

accessible and we want to find the logic value at this node. Value D is selected for this node.

17

This node can be observed at primary output 25. So a sensitized path is found first to this
output. Using NAND3 gate for sensitizing 396 to 25, we set nodes 2 and 5 equal to 1, so
that the output of the gate 476 is D. Now consider NOR2 gate with output 289, setting 2
and 5 equal to 1 makes one of its inputs (386) equal to 1 whereas the other input (396) is
D. So the output of this gate will be D. So, in order to make D observable at the primary
output node 25, the logic value needed at node 24 is 1. Since setting 2 and 5 equal to 1
forces the output of node 24 to 1, thus, the node 396 can be observed at node 25 with nodes
2 and 5 set equal to l. The next step is to find the appropriate values of the inputs of the
gates which have been assigned logic values for sensitizing the path. There must not be any
conflict of logic value at a single node of the circuit. The final values for each node of the
example circuit are shown in parenthesis in Figure 2.2. So, if we set inputs 2 and 5 equal to
1 the logic value at output 25 will be the same as that at node 396. Hence observing logic
value at node 25, with the above condition satisfied the value at node 396 can be found

without accessing it.

 

(1
(1)2 ‘
(1)5 386 ‘

 

 

Figure 2.2: Example Circuit for D-Algorithm.

18

Chapter 3

PROBLEM STATEMENT

Basically, a circuit can be described by a system model, Component Connection
Model (CCM) [18,19], as shown in Figure 3.1(a) where a and b are the component input
and output variables, respectively, and u and y are the primary inputs and outputs, respec-
tively. A digital circuit can also be described by CCM model, where each component may
represent a block of logic gates. For the redesign problem, as illustrated in Figure 3.1(b),
the target circuit is comprised of Missing Parts as indicated by shaded blocks, and the
Known Parts. Without loss of generality, the blocks can be re-arranged as in Figure 3.1(c),
where B-group contains all unknown blocks, while both A-group and C-group contain the
remaining known blocks. For the redesign problem, the following assumptions are made:

1. The functionality of the target circuit is given; and

2. The functionality and internal structure of B-group are unknown, but its input!

output nodes are given.

Assumption 1 implies that, for any input vector u, the corresponding output vector
y is attainable. Based on Assumption 2, B-group is equivalent to a black-box, where the
external nodes are known. One trivial solution is to apply all possible combinations to the

inputs of B-group and probe the outputs. Here, it is assumed that the inputs and outputs of

19

 

Components

   

u: System Inputs {:1 Known Parts

y: System Responses _ Missing Parts
(at) (b)

 

Figure 3.1: System Model: (a) CCM; and (b)-(d) Redesign Modeling.

20

B- group may not be all accessible except the primary inputs and outputs.

Based on the assumptions, the target circuit can be partitioned into three groups, as
shown in Figure 3.1(d), where pB={p1,p2,...,pw} and qB={q1, q2,...,q,} are the inputs and
outputs of B- group, respectively. Some primary outputs, yB, of the target circuit may result
from B-group. A-group takes the primary inputs, uPIA, and produces the outputs, p A, and
primary outputs, y A. Note that the inputs pB are comprised of all elements in p A, possibly
some elements in y A, and some primary inputs. On the other hand, the inputs of C-group
include all elements in qB, possibly some of the primary inputs, uPIC’ and some primary
outputs, yI C’ resulted from both A-group and B-group. The outputs of C-group are the pri-
mary outputs, y C' The primary inputs to these three groups may have some in common. The
major task is to find the inputs/outputs relationship of the Missing Parts in B-group. There-
fore, the redesign process is to derive the functions Fj’s, j=1,2,...,r, where q]: j(p1,
p2,...,pw), and to re-implement the functions Fj’s for the Missing Parts in B-group.

For simplicity of presenting the material, the example circuit, 24ml, is employed,
where its netlist generated by sis and schematic circuit diagram are shown in Figure 1.2(a)
and (b) respectively. It is a three bit full adder. The circuit has 22 gates, 7 primary inputs
(nodes 1, 2, 3, 4, 5, 6, and 7 are denoted as u], uz, u3, u4, u5, u6, and u7 respectively) and 4
primary outputs (24, 25, 26, and 27, denoted as yl , y2, y3, and y4 respectively). The masked
portion, of the netlist and schematic for example circuit I shown in Figure 1.3(a) and (b)
respectively, represents the missing or incomplete implementation information.

The redesign process first starts with partitioning the target circuit into three groups,
where B-group includes all unknown blocks, while A-group and C-group contain the

remaining known blocks. In this implementation, A-group and C-group are partitioned in

21

such a way that C-group contains those gates which takes qj’s as their inputs, and their fan-
in and fan-out gates, while the remaining known blocks are included in A-group. Figure
3.2(a) shows that B—group for example circuit I has pB:{ 393,394,449,460,486 } , qB={ 396} ,
and yB= {26}. For C-group, the gates associated with qB, or node 396, as shown in Figure
3.2(b), are the NOR2 gate "289" (denoted as the gate with the output node 289), and the
NAND3 gate "476". The gate "289" has a fan-in gate, OR gate "386", and a fan-out gate,
0A121 gate "25". Therefore, C-group has up1C={2,5}, yIC={24}, and yC={25}. Further-
more, A-group includes the remaining gates and it has upm:{ 1,2,3,4,5,6,7},
p A={ 393,394,449,460,486} and y A: { 24,27 } .

After partitioning the target circuit into three groups, the next step is to check if the
outputs, qB={q1,q2,...,q,}, of B-group are all observable from the primary outputs yC. In
Figure 3.1(d), the primary output vector yC is a function of Uplc, qB, and YIC, i.e.,

yC = Gc<Up1cz {q1,q2,...,q,}; Yrc) (3.1)

For example circuit 1, in Figure 3.2(b) we have,

N25 = Gc({2.5 }; {396}; {24})= N24[(u2+us)+N3961 + “205N396 (3.2)

The observability of an input qi of C-group, i.e., an output of B-group, can be
checked if there exists an input vector which sensitizes qi to any primary outputs in yC. Oth-
erwise, the outputs of B-group are not observable. For example, in Figure 3.2(a), {396} is
observable from the primary output {25}. By (3.2), one can generate a set of input vectors
as follows:

N25=N396 if [(uz=us=0) & N24=01 or [(U2=us=1)] (3.3)

Since the gates in A-group are known and thus the outputs, p A, of A-group can be

22

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 1 —
460 — 2 — — 393
449 — 396 L 3 q _ 394
393 4 B — 396 25 4 — — 449
394 j C 5 —. — 460
| 26 7 -—
| 24
27
(a)
24
2 -— 386
1, 289
5 " +
I [I . 25
396 &o—
24 & O—
C 5 476
(b)

460
449

393
394

486

 

(C)

Figure 3.2: Circuit Partitioning Scheme: (a) Example Circuit I Partitioning;
(b) and (c) Schematic of the Example Circuit I Partitions.

23

resulted from the primary inputs in “PIA- Note that the inputs pB={p1,p2,...,pw} of B-group
include all elements in p A, and may include some elements in y A and some primary inputs.
Therefore, when an input vector is applied to A-group, the corresponding output vector
including p A and y A results. This implies that an input vector, p33, of B-group results when
the input vector ua is applied to A-group. For simplicity, we refer that p13a is reachable by
11“. An input vector of B-group is unreachable if it can not be resulted from primary inputs.

The following property concludes:

Property 3.1

The outputs, q1, q2,..., q,, and y3, of B-group are "don’t cares" if the corresponding

input vector is unreachable from primary inputs.

Consider a reachable input vector p13a of B-group. Let qBa=(q1a,q2a,...,q,a) denote
the corresponding output vector of B-group for pBa. By (3.1), qi is observable if there exists
an input vector of C-group which can sensitize qi along with a sensitized path to primary
output(s), where the input vector of C-group is comprised of {uplc; {q1,q2,...,q,}; yIC]. By
Assumption 1, primary outputs, y C, can be obtained from the primary inputs which can
reach p33 and observe qi. Thus, qia is determined by derived primary outputs and known
primary inputs. On the other hand, if there exist no such sensitized input vectors, then qi is
not observable, resulting qia is a "don’t care", i.e., qia ="x". Therefore, the following prop-

erty results:

24

Property 3.2

Let qBa=(qla,qza,...,qra) denote the corresponding output vector of B—group for a
reachable input vector pBa. If ‘11 is not observable, then qia is a "don’t care."

Let RB be the collection of primary input vectors, which can reach to pBa, an input
vector of B-group. Suppose that there exists an input vector in RB such that

Yc = GCOIPIC? {Cil’q2’W’Qr}; Yrc) = Gcmptc; {(11}; VIC) (3-4)

This means that qi is observable and ye is function of the inputs uplc and yIC and
the only unknown parameter qi. By Assumption 1, the primary outputs, yC, can be obtained
from the primary inputs which can reach p13a and observe qi. Thus, the only unknown
parameter qi in (3.4) can be resolved from the simulated yC and the primary input vectors.

Thus, the following property concludes:

Property 3.3

Let qBa=(qla,qza,...,q,a) denote the corresponding output vector of B-group for a
reachable input vector p33. If qi is observable and the sensitized input vector is independent
of q] , q2, ..., q“, qm, .., qr, then qia can be determined by the derived primary outputs and
the known primary inputs.

Consider the case that there exists an input vector in RB such that

Yc = Gc(uprc3 {<11 ’q2’°'°’qr}; Yrc) = Gc(uplc; {(1%th Yrc); Where Qi¢qj~ (3.5)

Since yC can be obtained from the primary input vectors in RB, qi can be observable
and qia is determined by yC, Uplc, and YIC’ if qj has been pre-determined. However, in gen-

eral, both qi and qj are unknowns unless both qi and qj in (3.5) can be determined indepen-

25

dently. Therefore, qia is said to be undefined and denoted as qia="U".

Property 3.4

Let qBa=(qla,q2a,...,qra) denote the corresponding output vector of B-group for a
reachable input vector p33. If q, is observable and the sensitized input vector depends on
q1, q2, q“, qm, ..., q,, where there exists at least one of qj’s which cannot be pre-deter-

mined, then qia is undefined.

Consider an input vector uo=(u1,u2,u3,u4,u5,u6,u7):(0,0,0,0,0,0,0). When it is
applied to the target circuit, the corresponding output y:(N24,N25,N26,N27)=(0,0,0,0). Here
110 satisfies the condition in (3.3), and thus, by Property 3.3, N396=N25=0. When the input
vector is applied to A-group, we obtain (393,394,449,460,486)=(0,l,1,1,1). This implies
that, when the inputs (0,1,1,1,1) is applied to B-group, the output N396=0 and N26:0.

It can be easily verified that (393,394,449,460,486)=(0,0,0,0,0) is unreachable, by
Property 3.1, both N396 and N26 are don’t cares. Table 3.1 shows all input combinations
of (393,394,449,460,486) and their corresponding outputs (396,26), where all possible
27:128 primary input combinations are simulated and the resultant inputs and outputs of
B-group are tabulated. Results show that only six combinations are reachable. Therefore,

the Boolean expressions of B-group can be derived from Table l as follows:

N396 = N394N393 + N460

N26 = N393N394 + N393N394

26

Table 3.1: Simulation Results of Example Circuit I

 

26

XXXXXXXlXXXXXOXOXXXOXXXXleXXXXX

 

 

 

 

 

 

 

 

6
w XXXXXXXOXXXXXIXOXXX1XXXX1X0XXXXX
6

w 01010101010101010101010101

0

% 00110011001100110011001100

9

M 00001111000011110000111100

4

” 00000000111111110000000011

3

” 00000000000000001111111111

 

 

 

27

Apparently, the developed B-group may not have exactly the same topological
structure as the original one. However, it can be easily verified that the circuit with the
developed B- group has the same functionality as the original one. In fact, it is not necessary
for the developed B-group to have the same functionality as the original B-group as long
as the functionality of the circuit with the developed B-group and the original circuit are the
same. This leads to a way of identifying redundant nodes and gates. For example, the above
expressions require only three inputs, i.e., 393,394,460. Thus, nodes 486 and 449 are redun-

dant, so are the corresponding NAND2 and INV l gates.

Discussion:

Properties 3.1 and 3.2 determine don’t care outputs of B-group, while Property 3.3
defines the corresponding output values. If the inputs/outputs of B-group can be completely
determined by Properties 3.1, 3.2, and 3.3, as in the example circuit I shown in Figure 3.2,
then the target circuit is redesignable. By Assumption 1, the functionality of the target cir-
cuit is given. This implies that the target circuit is always redesignable. The worst case is
to redesign the target circuit based on the given functionality. We suppose that this redesign
solution is costly. Therefore, by the term "redesignable" we mean that the circuit can be
redesigned at a reasonably low cost. In other words, the redesign solution can be found
from the partitioned groups. On the other hand, the term "unredesignable" implies that the
redesign solution cannot be generated from the current partitioned groups.

The redesign problem can be solved using the digital test generation techniques
such as Boolean difference, path sensitization, backtracking methods [11]. More specifi-

cally, the primary input vectors of A-group that reach an input vector of B-group are called

28

controllable primary input vectors, for short, and the reachable input vectors of B-group
are referred to as reachable input vectors. In this implementation, all reachable and
unreachable input vectors must be derived. For those reachable input vectors, by Property
3.2, we must check if their corresponding outputs of B-group are observable from the con-
trollable primary input vectors. Thus, the redesign problem involves checking the observ-
ability of B-group and deriving its reachable and unreachable input vectors. Therefore, one
may use exhaustive simulation, Boolean difference, path sensitization, or backtracking
method to generate all controllable primary input vectors and all reachable input vectors.
Which method is more effective depends upon the number of inputs/outputs in each group
and the computation complexity for performing those methods. Hence, in order to simplify
the redesign process, it has been developed in various steps, so that the decision whether
the target circuit is “redesignable” or not is made as early as possible and with the minimum
amount of computation. The different steps of redesign process are discussed in the next

chapter.

29

Chapter 4

DEVELOPMENT

This chapter presents the details of the developed redesign process. First section
describes our initial development. Various steps involved in the redesign process are
explained using examples. The second section gives the improvements made to different

steps in order to improve the overall quality of the redesign process.

4.1 Redesign Methodologies

In this development, the redesign process is comprised of the following three major
steps:

1. Redesignability Check

2. Feasibility Check

3. Re-implementation

The first step checks if the circuit is redesignable. If so, the second step determines
the cost of finding the functionality of the missing parts. In case it is cost effective to extract
the functionality of missing parts, the cost associated with the re-implementation of missing
parts is estimated. If it is feasible to re-implement the missing parts the third step extracts

the functionality and re-implement them.

30

4.1.1 Redesignability Check

Consider a reachable input vector p133 of B-group and its corresponding output vec-
tor qBar-(qla,q2a,...,q,a). By Property 3.3, an output value qia of B-group can be determined
from the derived primary outputs and the known primary inputs if the output qi is observ-
able and the sensitized input vector is independent of q1, q2, ..., q“, qm, qr. Otherwise,
by Property 3.4, qia is undefined. Consider C-group in Figure 3.1(d), the inputs of C-group
include all elements in qB, and possibly some primary inputs, uPIC, and some primary out-
puts, yIC, that resulted from both A-group and B-group. The outputs of C-group are the pri-

mary outputs, yC. Without loss of generality, say yC={yCl,yC2,...,yCm}.

Property 4.1

The target circuit is redesignable if yC = Q or r = 0.

Consider the circuit in Figure 1.2, with B-group now including the CAD] gate with
output node 25, as shown in Figure 4.1(a) and (b). Let the circuit be denoted as example
circuit H. Then the B-group, as illustrated in Figure 4.1(c), has the input nodes p3 =
{24,289,476} and the output nodes yB = {25} and ye = 0. By Property 4.1, this circuit is

redesignable.

To simplify the redesignability check process, C-group is partitioned into v blocks
where v _<_ m. Two different partitioning schemes are developed: One partitions the C- group
based on the input qj, referred to as CI-Partitioning Scheme, while the other is based on the
output yC, referred to as CO-Partitioning Scheme. These two schemes are discussed below

in detail:

31

 

.model 24111]

.inputs 1234567

.outputs 24 25 26 27
.default_input_arrival 0.00 0.00
.default_output_required 0.00 0.00
.default_input_drive 0.07 0.07
.default__output_load 3.00

.gate 012 a=2 b=5 O=[386]

.gate nor2 a=3 b=6 O=[10]

.gate invl a=4 O=[390]

.gate invl a=7 O=[391]

.gate nand2 a=[390] b=[391] O=[458]
.gate aoi22 a=[458] b=l c=4 d=7 O=[287]
.gate 11de 8:3 b=6 O=[4 60]

.gate oai21 a=[10] b=[287] c=[460] O=[465]

 

.gate a022 a=[386] b=[465] c=2 d: 5 0:24
.gate xor a=1 b=4 O=[l3

.gate xor a=[l3] b=78 O: 27

.gate invl a=1 O=[38 9]

.gate oai22 a=27 b=[389] c=[390] d=[39l] O: [393]
.gate invl a=[393] O=[44

.gate or2 a=3 b=6 O=[4529]]

.gate 11de a=[452] b=[460] O=[394]
.gate 11de a=[393] b=[394] O=[486]
.gate oai21 a=[393] b=[394] c=[486] 0:26
.gate oai21 a=[449] b=26 c=[460] O=[396]
.gate nor2 a=[386] b=[396] O=[289]

.gate nand3 a=[396] b=2 c=5 O=[476]

 

 

.end

 

 

(a)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   

 

 

Input nodes: 1,2,3,4,5,6,7
Output nodes: 24,25,26,27

 

(b)
24 _
289 — B
476 —

 

 

 

|__25

(C)

Figure 4.1: Example circuit 11, with Incomplete Implementation Information:
(a) netlist; (b) schematic; and (c) B-group.

32

CI-Partitioning Scheme

In this scheme, C-group is partitioned into v blocks, as illustrated in Figure 4.2(a).
Each block Ci, as shown in Figure 4.2(b), may contain Si primary inputs, say uPICi={UPICij,
j=1,2,...,si} : Uplc, where S, 2 O; zi primary outputs produced from A-group and B-group,
YICi=IYICij’ j=1,2,...,zi), where 1i 2 0; and ti outputs of qB, QCi={inj, j=1,2,...,ti} c;
qB={q1,q2,..., q,}, where ti 2 l and ti 5 r. YCi ; yc, where nyCi is the number of primary
outputs in yC and nyCi 2 1.

After partitioning, all blocks Cj’s are sorted in an ascending order with tj. For ti=l,
i-e» YCi=GCi(uCi;{CII’92’---"Ir} 3YICi)=GCi(uCi;{CIi};YICi), if 91 is mt Observable, by Property
3.2, q,“ is a "don’t care"; otherwise, by Property 3.3, qia can be determined from the derived
primary outputs and the known primary inputs. Therefore, combining Properties 3.2 and
3.3, qia can be determined if qi is the only unknown parameter in QCi- The following lem-

mas and property result:

Lemma 4.1

(a) If qi is the only unknown parameter in QCi, then q,“ can be determined.

(b) If QCi={qj}, i.e., ti=1, then qia can be determined.

Property 4.2
Let C:{C1,C2,..., Cm} and qB={q1.Q2,...,q,}. If m = r, the target circuit is redesign-

able.

33

 

(a)

 

uPICi nyCi

ti Ci ‘7é'P YCi
QCI +>
YICi J—J

 

 

 

Figure 4.2: CI-Partitioning: (a) Blocks; (b) Block Ci.

34

Proof

m = r implies that ti = 1 for all blocks Ci’s. By Lemma 4.1(b), qia can be determined
and thus the circuit is redesignable.

Consider a block cj with tj=2, and let ch=ICle1tC1Cjzl=lC1j1,qk}. If qk e QCk and
tk=1, i.e., QCk:{qk}, by Lemma 4.1(b), qka can be determined. Thus, qjl is the only
unknown parameter qjl in ch. By Lemma 4.1(a), qja can be determined. Lemma 4.1 can
be generalized as follows. Let ti* be the number of undetermined qia’s. Initially, ti*=ti. If
QCi={qi}, i.e., ti=1, by Lemma 4.1(b), qia can be determined. Once qia is determined, tj* is
updated for all j, i.e., t-* decrements by 1 if qi e ch- The updating process is summarized

in Algorithm 1, and Property 4.3 results:

Property 4.3

Let tf" be the number of undetermined qia’s in QCi with the updating process in
Algorithm 1, if ti*=l for all i, then the target circuit is redesignable.

To describe the above redesignability check, the target circuit in Figure 1.2 is again
considered, but B-group is changed to include the OAI21 gate with output node 465, the
INVl gate with output node 449, and the AND2 gate with the output node 486. Thus, the
B-group for this example circuit III, as illustrated in Figure 4.3(a), has the input nodes
{10,287,460,393,394} and the output nodes {465,449,486}. As shown in Figure 4.3(b), C-
group includes the inputs up1C={u1,u2,u3,u4,u5,u6,u7}, QC={465,449,486}, and y1C={27},
and the outputs yc={24,25,26}. C-group is partitioned into three sub-groups, C1, C2, and
C3, as shown in Figure 4.3(c), with the schematic circuit diagrams in Figure 4.3(d), each

has ti=1. Therefore, by Property 4.2, the circuit is redesignable.

35

 

 

Step 0:

Step 1:

1.1:
1.2:

1.3:

Step 2:

Algorithm 1

Let C={C1,C2, .., Cm} and qB={q1,q2,...,q,};
Initialize TS[i] : ti, for i=1,2,...,r.
(Updating)
count := 0;
FOR j=l TO r

IF TS[j]:1 THEN {count++; param[count]=j;}
IF (count = 0) GOTO Step 2;
FOR k=1 TO count

TS[ParamUll--;
GOTO Step 1.1;
ti* = TS[i], for i=1,2,...,r.

 

36

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 __
— _24
10 — I i—
287—— I449 4—
393— B I—465 g: C ”‘25
394— 486 7_
460— 449— 26
465—
486—
(a) 27 I
(b)
1— 2
3—
2 _ 24 4 _ 26 3 _I 25
5— C — 6— C2 — 5 — C —
465— 1 7— 6 — 3
486— 449-
27_I 26 I 24
(C)

 

4%
C1

 

Figure 4.3: Example Circuit III: (a) B-group; (b) C-group; (c) Partitioned Blocks C1,C2,C3
and (d) Circuit Schematics for C1, C2, C3.

37

Consider another example circuit IV obtained from the target circuit in Figure 1.2.
Here the B-group is changed to include the A0122 gate with output node 287 and the
0A122 gate with the output node 393. Therefore, B-group has the input nodes
{l,4,7,389,390,391,458,27} and the output nodes {287,393} as shown in Figure 4.4(a). C-
group, illustrated in Figure 4.4(b), includes the inputs upIC:{u2,u3,u5,u6}, QC={287,393},
and the outputs yC={ 24,25 ,26}. Using CI-partitioning, C-group is partitioned into two sub-
groups, C1, and C2, as shown in Figure 4.4(c). Since each block has ti=1, therefore, by
Property 4.2, the circuit is redesignable.

Property 4.3 shows that the circuit is redesignable if ti*=1 for all i, after performing
the updating process in Algorithm 1. On the other hand, if ti* > 1 for some i, the circuit is
unredesignable with the present circuit partitioning scheme. Since a circuit may be parti-
tioned in many different ways, the circuit is unredesignable in the present partitioning
scheme, but it may be redesignable with other partitioning schemes. As mentioned previ-
ously, all circuits are redesignable if the redesign cost is acceptable. With the present circuit

partitioning scheme, the following unredesignability checks result:

Property 4.4

Let ti* be the number of undetermined qia’s in QCi with the updating process in

Algorithml, if there exists at least one ti*>l , then the target circuit is unredesignable.

Property 4.5

Let C={C1,C2,...,Cm} and qB={q1,q2,...,q,}. If m < r, the target circuit is unredes-

ignable.

38

389
390
391
458
27

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

llll

 

llll

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2—
3— _ 24
_ 5—
B 287 6— C —— 25
— 393 287— _. 26
393—
(b) (c)
2—
2— 3_ __ 25
3— 5__ C
2— C1 _24 6— 2 — 26
287— 393-—
2.1—J

(d)

Figure 4.4: (a) Example Circuit IV: (b) B-group; (c) C-group;

and (d) Partitioned Blocks C1,C2.

39

Proof

If m < r, then there exists at least one ti*>1, by Property 4.4, the circuit is unredes—

ignable.

CO-Partitioning Scheme

In this scheme, C-group is partitioned into In blocks, based on outputs of the C-
group, yC. Again considering the C-group in Figure 3.1(d), the CO-partitioning is illus-
trated in Figure 4.5(a). Each block C,, as shown in Figure 4.5(b), may contain 8, primary
inputs, say uPICi={up1CiJ-, j=1,2,...,si} c; um, where s, 2 0; 2, primary outputs produced from
A-group and B-group, ylc,={y1C,,-, j=1,2,...,zi}, where z, 2 0, and t, outputs of
qB=Iqlvq2v~9quv QCi=ICICijv j=1,2w-Jt} ; qB, where 0 S t, S r. Another set QC*=
{QC],Q02,...,QCm} is also defined that is used to keep information about the redesignability
of each QCi and will also be used later in section 4.2 to improve redesignability of a target
circuit.

To describe CO-partitioning scheme, the target circuit in Figure 1.2 is again consid-
ered, but B-group is changed to include different gates, so that various cases can be consid-
ered that are possible during partitioning. As already mentioned, the first step is to partition
C-group into m blocks based on its outputs. The partitioned m blocks are then divided into

following three categories:

(a) Blocks with t.:0

Consider the target circuit in Figure 1.2, but for this example circuit V, B-group

now includes the 0A121 gate with output node 465, and the AND2 gate with output node

40

 

 

 

 

 

Yer
<12 YC2
qr YCm
YIC

(a)
Si
“FIG .74.
ti Ci ‘—" YCI
QCi #4.”
Zi
YICi _/__:L
(b)

Figure 4.5: CO-Partitioning: (a) Blocks; (b) Block Ci-

41

486. Thus, Figure 4.6(a) shows that the B-group has the input nodes PB =
{ 10,287,460,393,394} and the output nodes qB = {465,486 }. As shown in Figure 4.6(b), C-
group includes the inputs uplc={u1,u2,u3,u4,u5,u6,u-, } , QC={465,486}, and y1C={27}, and the
outputs yc={24,25,26}. According to the partitioning scheme, C-group is partitioned into

3 blocks, C1, C2, and C3, as shown in Figure 4.6(c). Block C3 has t3: 0.

(b) Blocks with ti=l

Blocks C], and C2 of Figure 4.6(c) have t]: 1 and t2: 1.

(c) Blocks with ti>l

Again consider the target circuit in Figure 1.2. The B-group now includes the
A0122 gate with output node 287, the 0A122 gate with output node 393, the NAND2 gate
with output node 458, the INVl gate with output node 390, the INVl gate with output node
391, and the NOR2 gate with output node 10. Figure 4.7(a) shows that the B-group has
input nodes {u1,u3,u4,u6,u7,27} and the output nodes {10,287,393}. As shown in Figure
4.7(b), C-group includes the inputs uplc={u2,u3,u5,u6}, QC={ 10,287,393}, and y1C={27},
and the outputs yc={24,25,26}. C-group is then partitioned into 3 blocks, C1, C2, and C3,

as shown in Figure 4.7(c). Block C, has t.=2.

In the first step of this scheme of redesignability check, the blocks with ti=0 are con-

sidered. Since such blocks do not provide useful information for the redesign process,

therefore these are eliminated from 05" resulting in Qc*= { QC, ,QC2,...,QCm-} where m*S m.

42

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

l—
_n __24
10 — §__
287—1 _465 4._
393— B 4 6 5— C —25
394.4 " 8 9,:
460: 465— —26
486-—
(a) 27_j
(b)
H
1— 2—
2—n 4— 3“ 3 I—
5~ C1 —-24 6— C2 —26 6—
465-4 42:6: 7—
27__] 22:4
27

 

 

(c)

 

 

 

 

 

 

 

 

 

 

 

2
is: 24
2—+ 386 -—+—
5-
465
C1

 

    
 

449 25
26

 
   

C3
((1)

Figure 4.6: Example Circuit V: (a) B-group; (b) C-group; (c) Partitioned Blocks C],C2,C3:
and ((1) Circuit Schematics for C1, C2, and C3.

43

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 — 3: — 24
3 —— — 10 5 __
4 _ B _ 287 13— C —— 25
6 ~ _ 393 237 __
7 — 393 — — 2‘
27___I
(b) (C)
. 2
2_ 3__ 34
— C
5— 3
6—— Cl 24 6-— C2 _26 6—
393—
10:
287— 393fi 24 I
26

((1)

Figure 4.7: (a) Example Circuit VI: (b) B-group; (c) C-group;
and (d) CO—Partitioned Blocks C1,C2,C3.

Property 4.6

The target circuit is not redesignable if r > m*.

In the second step, blocks with ti:1 are used. The rules for such blocks are as fol-

lows:

1.

If the unknown QCi={ qx } , where 1 S x Sr, appears in only one of the ‘m’ blocks

then it can be observed at ya and therefore can be determined from the avail-
able information. Hence QC, is eliminated from Qc*.

If the unknown Qc,:{qx}, where 1 S x Sr, appears in more than one of the ‘m’
blocks and each block ch containing qx has ti = 1, then qx can be observed at

ya and ycj’s. This implies that the unknown can be determined and the corre-
sponding QC, and ch’s are removed from QC“.

If the unknown Q(;i={qx } , where 1 S x S r, appears in more than one of the ‘m’
blocks and ch’s containing qx has tj>1, then all sensitized paths 0,, for

qxe QC, and ij for q, e ch are found. If U,“ 2 mg, this means thath can be
determined from block QC, by observing it at ya. Hence qx becomes a known
for ch and therefore tj is decremented for corresponding ch's and QC, is elim-

inated from QC*.

The above two steps of redesignability check are performed successively and the

45

circuit is redesignable if QC* = O is obtained.

Property 4.7

The target circuit is not redesignable with the available information if 03% after

applying the redesignability check.

Corollary 4.7.1:

The target circuit is not redesignable with the available information if all the parti-
tioned C, where 1 S i .<_ m have t, > 1.

This redesignability check is summarized in Algorithm 2.

Discussion:

The two schemes presented above provide simple rules for redesignability check
and determine whether the circuit is unredesignable in the present partitioning scheme. So
after partitioning the target circuit, the redesignability check will be performed. If the cir-
cuit passes the check, the next step will be the feasibility check. However, if the circuit fails

the check alternative partitioning schemes will be tried as discussed later in this chapter.

4.1.2 Feasibility Check

Once a target circuit passes the redesignability check, this implies that the outputs
of B-group, qB:(q1,q2,...,qr), are observable. In feasibility check, we determine whether it
is cost effective to determine the inputs/outputs relationship of B-group and then to re-
implement it. In this part of the redesign process, first reachability of the inputs of B- group,

p3 = (p1,p2,...,pw), is determined using A-group. In the example circuit 1, given in Chapter

46

 

 

Step 0:
Step 1:

Step 2:
Step 3:
3.1:
3.2:
3.3:
3.4:
Step 4:

Step 5:

Step 6:

Algorithm 2

Set QC*={QCI¢QC29---9QCmI

Set count : 0 (Used for # of QC, with ti > 1)

Select QC, with t, = 0;

Qc*=Qc*-{QCt |t=01

m=m-#of{Qc. |t1=0}

Ifr>m,gotoStep6

Sai=1

Ifti :1 go to Step 5

If QCichj=Z, Vj at i, go to Step 4

If t,- = 1, for j’s with QCichj-atO, go to Step 4

1r { U,,- I for j’s with QC,erCj 1: e & tj > 1} e U,,, go to Step 5
r=r—1

tj=tj-l forjwitthichjatQ

If r = 0, circuit is redesignable [STOP] else go to Step 1
count = count + l

Ifcount at: m, i = i + 1, go to Step 3.1
The circuit is not redesignable [STOP]

 

47

 

3, all reachable input vectors of B-group were derived using exhaustive simulations, i.e.,
simulate the circuit in A-group with all possible combinations of the primary inputs. As the
number of inputs and outputs of A—group increase computational complexity becomes a
critical issue. Therefore, a cost function has been defined associated with functionality
extraction based on the number of inputs and outputs of A-group. The redesign process is
continued only if it is cost effective, otherwise we say that it is not feasible to redesign the
circuit.

To reduce the computational complexity, a simple circuit partitioning scheme is
proposed in this implementation. As illustrated in Figure 3.1(d), A-group takes some pri-
mary inputs uplA and produces the outputs {p1,p2,...,pw} as the inputs of B-group and some
primary outputs y A. If we assume that the number of primary inputs in up“ is k, then 2k
logic simulations on A-group are needed. Thus the number of simulations can be reduced
if A-group can be partitioned into many smaller blocks.

The partitioning of A-group is performed in two steps. In the first step A-group is
partitioned to contain only those gates which contribute to the inputs of B-group
{p1,p2,...,pw}, as shown in Figure 4.8(a). The number of primary inputs in A-group will now
be ‘h’ where h S k.

Consider the A-group, shown in Figure 4.8(b), for the example circuit I discussed
in Chapter 3. The A-group can be partitioned as described above. Figure 4.8(c) shows that
A-group will contain only {393,394,449,460,486} as outputs, which will result in
uplA:{u1 ,u3,u4,u6,u7 }. The number of simulations has decreased from 27(=128) to 25(=32),
resulting in significant reduction of computational complexity.

In the second step, let A-group, obtained after first step, be partitioned into g blocks,

48

 

(a)

 

 

 

 

 

 

 

 

1—
2— —393
3-— ——394
4— A ~449
5— ~460
6— —486
7—.
l 24
27
(b)
1 — —— 449
3 — —— 460
4 —— A — 486
6 — — 393
7 — — 394
(C)

Figure 4.8: A-group Partitioning: (a) First Step;
Example Circuit I: (b) Before Partitioning;
and (c) After Partitioning.

49

denoted by A1,A2,...,Ag. Each block A,, as shown in Figure 4.9(a), may take or, primary
inputs, say uA,={uA,,-, j=l,2,..., ori}e up“, where 1 Soc, _<. h, and produce some outputs
pAie {p1,p2,...,pw}. If mummy-=0, for any i and j, then h=0t1+a2+...+0tg. Thus the number
of simulations required is reduced from 2h to (2a1+2a2+...+2a8). Practically, however, we
may partition the A-group into many smaller groups such that (a1+a2+...+0tg) is minimum.

Consider the A-group, shown in Figure 4.9(b), for the example circuit III given in
Figure 4.2. It takes the inputs up1A={u1,u3,u4,u6,u—,} and produces the outputs
pA={10,287,460,393,394}. According to the partitioning scheme, A-group is partitioned
into two blocks, A, and A; as shown in Figure 4.9(c) and ((1) respectively, where
uA1={u3,u6} and uA2={u1,u4,u-,}. The number of simulations is reduced from 25(:32) to
23+22(=12). Thus, the computational complexity has reduced considerably.

A number nuplA(MAX) has been defined that determines the maximum allowable
number of inputs in any of the partitioned block of A-group. The choice of nupIA(MAX) is
variable depending upon the available computing facilities and will be decided by the
designers. If the number of inputs in a single A-group partition exceeds nupIAaVIAX), we
say that the solution is not cost effective. However, it should be noted here that we can also
apply backtracking technique used in ATPG’s to find reachable vectors of the B-group.
Since simulation is faster compared to backtracking process, the criterion used here
assumes backtracking to be fifty percent efficient compared to the simulation. Hence, back-
tracking can also make the solution cost effective in a case where the number of inputs of
a partitioned block exceed nuPIA(MAX), but the number of outputs of that block is less than
nupIA(MAX)/2. Let nuAj be the number of inputs and “(FM + yAi) be the number of outputs

of each block Ai, then we have the following property:

50

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1— —— 10
“i 3- 14:2.
uAi fl Ai ~—> PAi g: A 393
7 -— — 394
YAi
(a) (b)
’2: + big
3— —10
__394 3‘ 452
3‘ &o—l—

 

 

 

(C)

 

 

 

1‘1 — 287
4'fl A2
7—( — 393

 

'AHQ-pt

 

((1)

Figure 4.9: A-group Partitioning: (a) Second Step, Block At;
Example Circuit HI: (b) A-group; (c) Block A]; and ((1) Block A2.

51

Property 4.8

The redesign solution is not cost effective if there exists a single partitioned block

AI With nuAi > nupIA(MAX) and 11(p A1 + yAi) > (nupIA(MAX)/2).

After it is determined that redesign solution is cost effective, the next step is to find
the reachable input vectors of B-group. In order to efficiently find the reachable vectors
both simulation and backtracking are employed. Consider the two blocks, A, and A2 as
shown in Figure 4.9(c) and (d) respectively, we have already seen that partitioning has
reduced number of simulations from 32 to 12. Since the number of outputs in block A2 are
2, we shall require 22 backtrackings. So, by using simulation for block A1 and backtracking
for block A2, the reachable input vectors can be found using 4 simulations and 4 backtrack-
ings.

The choice of using either simulation or backtracking for a partitioned block of A-
group depends on the number of its inputs and outputs. As discussed earlier, simulation is
faster compared to backtracking process, the criterion used specifies that if the number of
outputs in block Ai is less than half the number of its inputs, then use of backtracking is
more efficient compared to simulation. So for each partitioned block of A-group, either
simulation or backtracking is employed which ever is efficient in that particular case.

Algorithm 3 summarizes the procedure for finding reachable input vectors of B-
group.

After finding the reachable input vectors, feasibility check determines the cost of

re-implementing the circuit. The critical issue involved in the re-implementation of missing

52

 

 

Step 1:
Step 2:

Step 3:

3.1:

Step 4:

Step 5:
Step 6:

Algorithm 3

Partition A-group to contain only {p1,p2,...,pw} as outputs

Partition A-group obtained in Step 1 into many smaller groups

such that (011+0t2+...+0tg) is minimum

IF nupIAi S nuPIA(MAX) for all 1 THEN go to Step 4

IF 11(p Ai-I-y Ai) > (nupm(MAX)/2) for I With nupIAi > nupIA(MAX)
THEN go to Step 6

FOR i=1 TO g
IF nupw S 2*n(pAi+yAi) simulate partitioned block

ELSE backtrack partitioned block

Find reachable input vectors pB=(p1,p2,...,pw) [STOP]

Redesign solution is not cost effective [STOP]

 

 

 

Step 1:

Step 2:
Step 3:

Step 4:

Algorithm 4

If QCinQCj=®a VI 3* i. where QCiOQCj E Qc*. QCi’=QCi.

else merge blocks i and j for those j’s where QCinQCJ-ICQ to get QCi’.

Rearrange blocks of C-group based on the QCi’s obtained in Step 1

Partition each block Cit, so that it contains only one element
in each QCiv

Modify the B-group and C-group accordingly,

the circuit now becomes redesignable

 

53

 

 

parts is the number of reachable input vectors of B-group. Whether one can efficiently han-
dle implementation of a large circuit primarily depends on the available design tools and
computing resources. Another factor of consideration will be the necessity of the task. If
there are no alternatives one will have to do it. So keeping these points in mind, the design-
ers will decide whether it is feasible to re-implement the missing parts or not. A number
INPUT_VECTORMAX has been defined that determines the maximum number of reach-
able input vectors in order to have the re-implementation feasible. If the reachable input
vectors of B-group exceed INPUT_VECI’ORMAX, we say that re-implementation is not

feasible. The following property concludes:

Property 4.9

If the reachable input vectors of B-group exceed INPUT_VECTORMAX, then re-

implementation of the target circuit is not feasible.

Discussion

In the feasibility check, we have introduced partitioning scheme for A-group and
the use of backtracking technique in order to efficiently determine the reachable input vec-
tors of B-group. Feasibility check first determines whether finding the reachable input vec-
tors is cost effective. If so it determines the reachable vectors and checks the feasibility of
re-implementing the circuit. This check halts the redesign process if finding reachable vec-
tors is not cost effective or re-implementation is not feasible. However, if the target circuit

passes the feasibility check, we proceed to the next step of re-implementation.

54

4.1.3 Re-implementation

Once a circuit passes the redesignability and feasibility check, it is determined that
the outputs of B- group are observable and functionality extraction along with re-implemen-
tation is cost effective. We can find the relation between inputs and outputs of B-group
using different approaches. Here, two such approaches are presented that can be used to
derive the transfer function of B-group. The selection of approach depends on the number
of inputs and outputs of A, B and C-groups of the target circuit. After deriving the transfer
function, the B-group can be re-implemented using appropriate minimization and synthesis
tools. This implementation uses VLSI design tools, espresso and sis. The two approaches

to determine the transfer function of B-group are summarized below:

Approach 1

In this approach, first A-group is solved to find all reachable combinations of inputs
of B-group. For each reachable combination, the outputs of B-group are then sensitized to
be observed at the primary outputs. This approach is suitable for circuits in which the func-
tion for the primary output vectors yC is complex. The following steps are followed:

1. Simulate/Backtrack A-group, to find the reachable combinations of p3 :
{p1,p2,...,pw}. Find all the primary input vectors that generate each reachable
input of B-group.

2. Find sensitized path for each qie qB={q1,q2,...,q,}, in C-group for each reach-
able combination of p3 = {p1,p2,...,pw}.

3. Redesign B-group.

55

Consider example circuit [[1 shown in Figure 4.3. We shall use this approach to re-
implement the missing parts. The first step gives us only 6 reachable vectors out of the 32
possible combinations of the inputs of B-group. So the outputs of B-group for these 26
combinations will be don’t care i.e. ‘X’. In the second step, using the modified D-algorithm
discussed in Chapter 2, we find out that B-group output node 465 is observable for all the
6 reachable input vectors while node 486 and 449 are observable only for 5 and 2 reachable
input vectors respectively. The results obtained are given in the form of a truth table for B-

group in Table 4.1. Using this truth table the B-group is re-implemented and the results are

as follows:
465 : W5)
486 = (393x394)
449 = 393

The netlist, generated by sis, for this redesigned B-group is exactly the same as that
of the original B-group and replacing the missing block with this netlist results in the orig-

inal entire circuit without missing information.

Approach 2

In this approach, first C-group is solved to find all sensitized paths for outputs of B-
group. A- group is then simulated/backtracked under the conditions obtained for sensitized
paths. This approach is suitable for circuits in which the function for the primary output
vector yc is simple and the number of inputs and outputs of A-group are large compared to
the number of outputs of B-group. The steps involved are outlined below:

1. Find all sensitized paths for each qie q3={q1,q2,...,q,}, in C-group.

56

Table 4.1: Truth Table for B-group of Example Circuit HI

 

486

XXXOXXlXXlXXXXXXXXXXXXXOXXXXXlXX

 

 

 

 

 

 

 

 

m XXXlXXlXXlXXOXXXXXXXXXXOXXXXXOXX
m XXXXXXOXXXXXXXXXXXXXXXXXXXXXXIXX
m 01010101010101010101010 101
m 00110011001100110011001 011
m 00001111000011110000111 000
m 00000000111111110000000 111
m 00000000000000001111111 111

 

 

 

57

2. Simulate/Backtrack A-group for ue up“, which satisfy the condition of sensi-
tized paths, found in 1.

3. Redesign B-group.

Consider example circuit I given in Figure 1.3. We shall use the above approach to
re-implement the missing parts. The first step is to find all sensitized paths for outputs of
B-group. We shall use Boolean difference for this purpose. Considering the C-group of the
circuit and using the expression describing N24, we can write

F = N25 =—fi3fi6 (N396 (I15 + 62) + u2 135 + 32 u5) + N396 (52 55 + u2 115)

'1' (66 + U3) (N396 (Us + 62) + U2 US '1' Hz 115) (67 (U4 '1' El) '1' 61 U4)

F396(0) = 3366 ( 1.12 Us '1' Hz 115) ‘1' (U6 '1' E3) ( ‘12 65 + 62 1.15) (67 (E4 '1" 61) + 61 U4)

F396(I) = 3366 (Us + 62) '1' (U6 ‘1' U3) (Us + 62) (U7 (U4 ‘1" Til) ‘1' El 64) + 62 Us + 112 [Is

dF/dN396 = F396(0) 69 F396“)
: 52 65 + u2 u5
The above result shows that node 396 is observable at primary output node 25
when u2 = us. After this step, the reachable input vectors are determined by simulating A-
group for those primary input vectors for which u2 = 115- The results obtained are the same

as already given in Table 3.1. The re-implemented B-group is given below:

N396 = N394N393 + N460
N26 = N393N394 + N393N394
The netlist, generated by sis, for this redesigned B-group is not the same as that of

the original B-group but replacing the missing block with this netlist results in a circuit that

58

is functionally equivalent to the original entire circuit in all respects.

Discussion

The approaches given above require finding sensitized paths which can be accom-
plished by using the digital test generation techniques such as Boolean difference, path sen-
sitization, backtracking methods [11]. For approach 1, we have used D-algorithm with
modification as already described in Chapter 2. The problem of finding all possible sensi—
tized paths is handled using Boolean difference. The partitioning of C-group into smaller
blocks makes it effective to use Boolean difference for finding all possible sensitized paths.
In our implementation we are using sis and espresso to find the boolean difference.

Therefore, one may use exhaustive simulation, Boolean difference, path sensitiza-
tion, or backtracking method to generate all controllable primary input vectors and all
reachable input vectors. Which method is more effective depends upon the number of
inputs/outputs in each group and the computation complexity for performing these meth-

ods.

4.2 Improvement

In this section, various improvements made to the initial development are
described. These improvements are related to the circuits which either fail the redesigna-
bility check or the feasibility check. In order to handle these problems an augmented par-
titioning scheme for B-group is proposed. The B-group is augmented to B’-group, as
shown in Figure 4.10(a). B’-group may cover some gates in A-group, and/or some gates in

C-group. The augmented partitioning is classified as BO-Augmentation when gates from

59

 

BI-A tat' <————— .
ugmen ron —————>BO-Augmentatron

(a)

 

Figure 4.10: Augmented Partitioning: (a) Concept; (b) Augmented B-group;
(c) BO-Augmented C-group; and (d) BI—Augmented A-group.

C-group are included in B-group and as BI-Augmentation when gates from A-group are
included in B-group. BO-augmentation is used when a target circuit fails the redesignabil-
ity check while BI-augmentation is employed to make functionality extraction of B—group

cost effective. The two partitioning schemes are discussed below:

4.2.1 BO-Augmentation

This partitioning scheme is used when target circuit fails the redesignability check,
discussed in section 4.1.1. The basic concept of this partitioning is to reduce the number
of qi’s in the circuit, so that each qi can be determined independent of other qj’s for all j at
i. This is accomplished by finding the points of minimum connectivity in C-group. In case
of failure of the redesignability check, the set QC“ contains QCi’s that cannot be deter-
mined from the current partitioning, on termination of Algorithm 2. In other words, the
unknowns that can be resolved under current partitioning have been eliminated from QC*.
So in order to make the circuit redesignable, we need to focus our attention to QCi’s that are
contained in 05" when the redesignability check halts. Thus instead of dealing with all
QCi’s, we work only with those which are essential to make the circuit redesignable.

Once the QCi’s have been found as described above, we consider only those blocks
from the partitioned ‘m’ blocks that contain these QCi’s as their input. These blocks are
regrouped such that QC}. and QC,» are disjoint for all i at j. By such partitioning we have con-
fined the unknowns, qi’s, that depend on each other in separate blocks. The next step is to
partition each individual block C,-, so that it contains only one unknown. In other words,
we find the node in the group where all the unknowns in Qcy converge. While doing this

the worst case would be to go up to the primary outputs, which supports the fact that with

61

Assumption 1 taken in our problem, every circuit is redesignable. Since now each block
contains only one unknown it can be redesigned but in order to make it redesignable, we
have not only modified the B-group, as shown in Figure 4.10(b), but the C-group has also
been altered, as illustrated in Figure 4.10(c). The number of outputs in th will be less than
that in qB while the number of primary outputs in th will be greater than or equal to that
in YB-

The above partitioning scheme to improve redesignability properties of the target
circuit can be best described by an example. Consider the circuit given in Figure 1.2 with
B-group for example circuit VI including the A0122 gate with output node 287, the 0A122
gate with output node 393, the NAND2 gate with output node 458, the lNVl gate with out-
put node 390, the INVl gate with output node 391, and the NOR2 gate with output node
10. The CO-partitioning for C-group of this circuit into 3 blocks, C1, C2, and C3, is shown
in Figure 4.7(c). We can see that for block C1, we have upm = {u2,u3,u5,u6},
QCI={10,287}’ )’1C1=g 311d YCI={24}’ for bIOCk C2, u1>1C2 = {112.113.05.116}, QC2={393}.
ylcz={24,26} and yC2={ 25} and similarly for block C3, upm: {u3,u6}, QC3={ 393 } , ”(33:0
and yC3={26}. This circuit fails the redesignability check because QC1={ 10,287} can not
be resolved with the current partitioning of the circuit. Algorithm 2 for the redesignability
check will terminate with Qc*={Qc1}- Since the unknowns 10 and 287 are contained only
in QC], we do not need to merge any other block with this. The regrouping will result in a
block identical to the block C1. The block C], as shown in Figure 4.11(a) contains “no
={u2,u3,u5,u6}, QC,={10,287}, ym=® and yc1:{24}. Then we partition block to get C1»
such that QC]. contains only one element. It can be seen that the two unknowns 10 and 287

converge at 0A121 gate with output node 465. By making Qcp={465 } , as illustrated in Fig-

62

 

5— C1 __24

10—
287—

 

 

 

 

 

5— C1. I—24

 

 

 

(b)

465

393

 

 

:4 —24
51
6— C’ —25
10
287
393— —25

 

 

 

(d)

Figure 4.11: BO-Augmentation: Example Circuit VI; (a) Block C1; (b) Block C11;
(b) Augmented B’-group; and (c) C’-group.

63

ure 4.11(b), we have met the condition of single unknown qi in each block Cy. Hence the
circuit is redesignable with the new B’-group and C’-group which are shown in Figure
4.1 1(c) and (d) respectively. B’-group now contains th ={465,393}. With this modified,
B’-group, the target circuit will pass the redesignability check.

BO-augmentation is summarized in Algorithm 4.

4.2.2 BI-Augmentation

This partitioning scheme is used to make functionality extraction of the target cir-
cuit cost effective. The basic goal of this partitioning is to reduce the computational com-
plexity of finding the reachable input vectors of B- group. Computational complexity
generally, but not absolutely, increases with the number of inputs and outputs of B-group.
Thus, if we augment B-group, as illustrated in Figure 4.12(a), for the example circuit I in
Figure 1.3. It shows that the original B-group, shown in Figure 4.12(b), has 5 inputs and
now the B’-group, illustrated in Figure 4.12(c), has only 3 inputs. Hence, the computational
complexity for deriving the redesign solution can be reduced significantly. The number of
inputs p3, will be less than that in p13. While altering the B-group, this partitioning also
modifies the A-group, as shown in Figure 4.10(d). The A’-group for example circuit I is

illustrated in Figure 4.12(d).

Discussion
The augmented circuit concept not only makes the redesignability check and func-

tionality extraction simpler, but also reduces the circuit size. More specifically, when a

practical large circuit is considered, since the majority parts are known and only a small

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

394_ 396

 

 

 

 

 

 

 

 

 

449..
393— B
26
460— —-
486‘
(b)
1 —
3 — — 460
4 — A’ —— 393
6 — —— 394
7 __
(d)

Figure 4.12: BI-Augmentation: (a) Example Circuit I; (b) Original B-group;
(c) Augmented B’-group; and (d) A’-group.

65

portions of the circuit is missing, we may apply the circuit augmentation to find the func-
tionality of a relatively smaller circuit compared to the entire circuit which still includes the
missing parts. Thus, the circuit complexity can be reduced and this makes the proposed par-

titioning schemes for redesign process more feasible.

4.2.3 Multiple B-Groups

In this section, the case of multiple B-groups is discussed, that is, the parts with
missing implementation are spread wide apart in the entire circuit. Again the assumption
made is that the input and output nodes of each B-group are known. Let the number of B—
groups in the circuit be ‘p’, so that we have B1, Bz, ...,Bp. In case of multiple B-groups, we
can have three possible cases.

In the first case, the groups Bi are independent, that is, outputs of none of the
groups are the inputs to any other group directly or indirectly. Consider the example circuit
VII shown in Figure 4.13(a) for such a case. The output of Bl-group, YBl = {465} is
observable at primary output node 24 whereas output of Bz-group, sz = {486} is observ-
able at primary output node 26. The reachable input vectors of each group can be found
independently. So both the groups BI and B2 can be redesigned using our developed rede-
sign process.

The second case is when the outputs of one or more B-groups are the input of other
B- groups, but such outputs are observable at one or more primary outputs. Consider exam-
ple circuit VIII as illustrated in Figure 4.13(b). The output of Bl-group, YBI = {393} is in
the input path to B 2-group via node 449 but node 393 is observable at primary output node

26. So, in this case we shall have to redesign Bl-group first using our developed process.

66

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(b)

Figure 4.13: Multiple B-Groups: (a) Example Circuit VII; (b) Example Circuit VIII.

67

After the re-implementation of B l-group is introduced in the circuit BZ-group can be rede-
signed with the developed redesign process.

In the third case, we consider that the outputs of one or more B-groups are the input
of other B-groups, but such outputs are not observable at any primary output. For this case,
consider example circuit IX, as given in Figure 4.l4(a). The output of Bl-group, YBl =
{458} is in the input path to Bz-group via node 287 and node 458 is not observable at any
primary output. In order to deal with such a situation, we augment the Bi-group so that all
the unknowns become observable at the primary outputs. The augmentation of Bl-group
to Blt-group is illustrated in Figure 4.l4(b). The augmented Blt-group can now be rede-

signed using the developed redesign process.

Discussion

In this section, it is shown that the developed redesign process can also handle mul-
tiple B- groups. If the multiple B-groups do not depend on each other, then each group will
be resolved independently. When multiple B-groups depend on each other, we first rede-
sign those groups which are independent of others and then check whether remaining B-
groups become redesignable. Using this procedure successively, if we are unable to rede-

sign certain B-groups then we augment so that a redesignable B-group is obtained.

68

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 4.14: Multiple B-Groups: Example Circuit IX (a) B1 and B2 groups ;
and (b) Augmented Bln-group.

69

Chapter 5

EXPERIMENTAL RESULTS

Different approaches that can be used to solve the redesign problem and various
ways to handle the computational complexity have been described in the previous chapters.
This chapter summarizes the developed redesign process to solve the redesign problem and

presents the experimental results of some benchmark circuits.

5.1 Redesign Process

Figure 5.1 shows the flow chart of the developed redesign process. Given a circuit
with incomplete implementation information in B-group, the circuit is initially partitioned
to get the C-group. If the circuit passes the redesignability check then the feasibility check,
as discussed in Section 4.1.1., is processed, otherwise BO—augmentation, described in Sec-
tion 4.2.1, is performed. In the feasibility check, initially A-group is considered and the cost
associated with determining the reachable input vectors of B-group, in terms of number of
simulations and/or backtrackings, is evaluated. In case it is not cost effective to find the
reachable input vectors of B-group with initial partitioning as described in Section 4.1.2,
BI-augmentation, discussed in Section 4.2.2, is applied to make redesign solution cost
effective. The criterion used in the redesign process is the one given in Property 4.8. The

maximum allowable number of inputs in any partitioned block of A-group, nupIA(MAX) =

70

 

 

 

C-Group Partitioning

 

     
 

Redesignability
Check

 

BO-Augmentation

I

 

 

 

 

 

 

 

 

A-Group Partitioning

 

      
 
      
 

Feasibility
Check

 

 

BI-Augmentation

 

 

Feasibility
Check

Gedesign not Feasib9 (Re-implementatioD

Figure 5.1: Redesign Process

Fail

 

 

 

 

 

71

10, is assumed for these benchmark circuits. That is, if there exists a single partitioned
block of A-group which has number of inputs and outputs more than 10 and 5 respectively,
it is not cost effective to find the reachable vectors. If the reachable input vectors of B- group
can be found in a cost effective manner, we then proceed to check the feasibility of re-
irnplementation. The criterion for feasible re-implementation is based on Property 4.9. The

212, is assumed,

maximum number of reachable input vectors, INPUT_VECTORMAX =
i.e., if the number of reachable input vectors of B-group exceed the number 4096, the re-
implementation is not feasible with the available resources. When a circuit passes both the
redesignability and feasibility check, the input/output relationship is determined using the
approaches given in Chapter 4. After deriving the transfer function, the missing parts are

re-implemented using existing VLSI design tools, where espresso and sis are used in this

implementation.

5.2 Results

In order to demonstrate the effectiveness of the developed redesign process, a set of
benchmark circuits has been tested. The benchmark circuits were generated using sis with
the script file in Figure 5.2(a). for MCNC benchmark circuits in the path Isis/ex/comb/
mcnc9l/mlexl. More specifically, this implementation first read the blif file of a circuit,
where Figure 5.2(b) shows the blif file of the benchmark circuit “cml38a”. The circuit is
then optimized using only one cycle of the suggested script “script.rugged” in sis. However,
better results may be obtained by repeating the script file for several time. Here, the cell
library “scmos.genlib” is employed. The circuit is mapped using this library to obtain the

netlist, as shown in Figure 5.2(c). Table 5.1 lists the number of primary inputs, the number

72

 

www.mawe amazes-651 ”5:..fi. Kawm

sis> read_blif filenameblif

   

 

 

 

 

 

 

 

sis> source script.rugged

sis> read_library scmos.genlib

sis> map -W

sis> write_blif -n filenarne. gate

(a)
.model CM138 --1- 1 ---l 1
.inputsabcdef ---l l .namesabchm
.outputsghijklmn .namesabcjoi 1---1
.names a b c j0 g 0'“ 1 '0“ 1
1--- 1 -O—- l --0- 1
-1--1 --l-1 ---1 1
--1-1 ---1 1 .namesabchn
---1 1 .names a b c jO k 0--- 1
.names a b c jO h 1'" 1 '0“ 1
o.-- 1 -1-- 1 --0- l
-1--1 --0-1 --—1 1
--1- 1 ---1 1 .names fe djO
---] 1 .namesabchl 1--1
.namesabchi 0'" 1 '1'1
1--- 1 -1--1 --01
-0.- 1 --0- 1 .end
0))

.model CM138 .gate invl a=a O=[327]
.inputs a b c d e f .gate or2 a=[327] b=[330] O=[335]
.outputs g h i j k l m n .gate or3 a=[335] b=b c=c O=h

.default_input_an’ival 0.00 0.00
.default_output_required 0.00 0.00
.default_input_drive 0.07 0.07
.default_output_load 3.00
.default_max_input_load 999.00
.gate nor2 a=e b=f O=[326]

.gate 11de a=d b=[326] O=[330]
.gate or2 a=a b=[330] O=[331]
.gate or3 a=[331] b=b c=c O=g

.gate invl a=b O=[332]
.gate or3 a=[331] b=c c=[332] O=i
.gate or3 a=[335] b=c c=[332] O=j

.gate invl a=e O=[333]

.gate or3 a=[33l] b=b c=[333] O=k
.gate or3 a=[335] b=b c=[333] O=l

.gate or3 a=[33l] b=[332] c=[333] O=m
.gate or3 a=[335] b=[332] c=[333] 0=n
.end

 

(C)

73

Figure 5.2: Benchmark Circuit: (a) Script File; (b) cm138a.blif; and (c) cm138a.gate.

 

 

Table 5.1: Benchmark Circuits

 

No. of Primary

No. of Primary

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Circuit Inputs Outputs N o. of Gates
alu2 10 6 202
apex6 135 99 417
bl 3 4 5
C17 5 2 3
cm138a 6 8 15
cm42a 4 10 17
cm82a 5 3 l 1
cmb l6 4 28
count 35 16 80
decod 5 16 30
example2 85 66 174
13 132 6 46
i5 133 66 66
i7 199 67 407
majority 5 1 8

 

 

 

 

74

 

of primary outputs, and the gate count for each benchmark circuit generated from the above
procedure. For example, the resultant benchmark circuit for “cml38a” has 6 primary inputs
(a, b, c, d, e, t), 8 primary outputs (g, h, i, j, k, l, m, n) and 15 gates (l NOR2, 1 NAND2, 2
0R2, 8 0R3, 3 INVl).

Based on the resultant benchmark circuits in Table 5.1, a set of benchmark circuits
for redesign process are generated and listed in Table 5.2. The table shows the number of
inputs and outputs in each group. For example, consider the unknown B-group of the
benchmark circuit “cm138a”, as shown in Figure 5.3(a). The partitioned C-group and A-
group are illustrated in Figures 5.3(b) and 5.3(c), respectively. The inputs and outputs of
each group are listed in Figure 5.3(d). For B-group, the number of inputs an:2, the number
of outputs excluding the primary outputs an=1, the number of primary outputs nyB=0, and
the number of gates #3:]. The numbers are listed in the Columns 2 to 4 in Table 5.2. Sim-
ilarly, for C-group, nuc=2, nyIC=0, nyc=4, and #C=6; and for A-group, nuA=4, 11p A=2,
r1y A=0, and #A:3. The detailed input and output nodes of the partitioned groups for each
benchmark circuit in Table 5.2 are given in APPENDD( A.

Based on the redesign process illustrated in Figure 5.1, Table 5.3 summarizes the
experimental results for all benchmark circuits in Table 5.1. Consider the benchmark cir-
cuit “cml38a”, as shown in Figure 5.3. The redesignability check was first performed on
the C-group shown in Figure 5.3(b). Since the unknown qB = {[335]} can be observed at
the primary outputs of the circuit, so the circuit passed the redesignability check without
BO-augmentation, i.e., BO-augmentation is not required to pass the test. It is followed by
the feasibility check. Since the number of inputs of A-group, nuPIA:4, is less than

nup1A(MAX):10, finding reachable vectors is cost effective and thus the circuit passes the

75

Table 5.2: Partitioning Parameters for Benchmark Circuits

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Circuit an BqB Bye #11 11he nyIC Bye #C BuA BpA ByA #A
alu2 6 l 0 2 10 2 3 199 5 6 0 12
apex6 11 2 2 4 1 0 2 2 l9 8 0 36
b1 4 1 0 l 0 1 1 l 2 1 1 2
C 17 4 0 l l 0 0 0 O 2 l 0 1
cm138a 2 1 0 1 2 0 4 6 4 2 0 3
cm42a 2 2 O 2 2 0 4 7 2 2 0 2
cm82a 4 l O 1 2 0 2 6 3 2 0 2
cmb 4 2 O 2 13 0 2 8 0 0 0 0
count 13 3 0 8 3 0 3 5 14 7 0 13
decod 3 4 0 5 3 0 16 24 l l 0 1
example2 l6 5 1 6 41 1 16 77 l 1 0 13
i3 16 1 0 5 16 0 1 0 0 0
i5 26 0 10 10 0 0 0 0 19 6
i7 52 25 0 27 28 0 25 54 53 25 O 82
majority 3 1 l 5 0 l 4 3 3 0 3

an : Number of inputs in B-group.
an : Number of outputs in B-group excluding those outputs that are primary outputs.
nyB : Number of primary outputs which are the outputs of B-group.

#B : Number of gates in B-group.

nuC
nyIC
nyC

#C : Number of gates in C-group.

nuA
up A
Dy A
#A

: Number of primary inputs in C-group.
: Number of primary outputs which act as an input to C-group.
: Number of primary outputs in C-group.

: Number of primary inputs in A-group.
: Number of outputs of A-group which are not a primary output.
: Number of primary outputs in A-group.
: Number of gates in A-group.

76

 

 

 

.model CM138B

.inputs [327] [330]

.out uts [335]

.de ault_input_arrival 0.00 0.00
.default_output_required 0.00 0.00
.default_input_drive 0.07 0.07
.default_ou ut_load 3.00

.gatie or2 a: 327] b=[330] O=[335]
.en

 

330:

327— + ”335

 

 

 

 

 

(a)

 

 

.model CM138C

.inputs [335] c b

.outputs n l j h
.default_input_arrival 0.00 0.00
.default_output_required 0.00 0.00
.default_input_drive 0.07 0.07
.default_output_load 3.00

.gate or3 a=[335] b=b c=c O=h
.gate or3 a=[335] b=c c=[332] O=j
.gate or3 a=[335] b=b c=[333] 0:1
.gate or3 a=[335] b=[332] c=[333] O=n
.gate invl a=b O=[332]

.gate invl a=e O=[333]

.end

 

 

 

 

 

.model CM138A

.inputs (1 e f a

.outputs [327] [330]

.de ault_input_arrival 0.00 0.00
.default_output_required 0.00 0.
.default_input_drive 0.07 0.07
.default_output_load 3.00

.gate invl a=a O=[327]

. gate 11de a=d b=[326] O=[330]
.gatie nor2 a=e b=f O=[326]

.en

00

 

 

 

 

 

 

 

 

 

 

 

 

(b)
e 4 0326
r 4 + d_ & p—33o
a {jg 327
(C)

 

 

p3 = {[327}. [330]}; q]; = {[3351}; ya = Q
uPIC = lb, C};)'1C = 3: YC = {11,131, n}
use. = (a. d. e. f}; n. = {1327]. [3301}; YA: B

 

 

((1)

Figure 5.3: Circuit cm138a Partitioning: (a) B-Group; (b) C-Group; (c) A-Group.
and ((1) Inputs and Outputs of Each Group.

77

(2

Table 5 .3: Experimental Results of Benchmark Circuits

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Circuit Redesignability Check Feasibility Check
Without BO- With BO-Aug- Functionality Re-implementa-
Augmentation mentation Extraction tion

alu2 Fail Pass Pass Pass
apex6 Pass N/R Pass Pass
b1 Pass N/R Pass Pass
C17 Pass N/R Pass Pass
cml38a Pass N/R Pass Pass
cm42a Pass N/R Pass Pass
cm82a Pass N/R Pass Pass
cmb Pass N/R Pass Pass
count Pass N/R Pass Pass
decod Pass N/R Pass Pass
example2 Pass N/R Pass Pass
13 Pass N/R Pass Pass
i5 Pass N/R Pass Pass
i7 Pass N/R Pass Fail
majority Pass N/R Pass Pass

 

 

 

 

 

N/R : Not Required.

78

 

feasibility check without the need of BI-augmentation. Finally, the feasibility of implemen-
tation is checked after finding the reachable input vectors. The number of reachable input
vectors, in this case is 4 which is less than INPUT_VECTORMAX:4096, so re-implemen-
tation is feasible. The transfer function was determined and the re-implemented B-group
was identical to the unknown B-group. Therefore, the circuit passes all the tests listed in
Table 5.3.

For the circuit “alu2”, the B-group is comprised of two NOR gates with the output
nodes [465] and [466], respectively. When the redesignability check is applied to C-group,
both unknowns [465] and [466] cannot be observed without the involvement of each other
using either CI-partitioning or CO-partitioning schemes discussed in Section 4.1.1. Thus,
the redesignability check failed and BO-augmentation was performed. This augmentation
resulted in B-group including the NOR2 gate [993] from C-group in addition to the NOR3
gate [465] and NOR3 gate [466]. With this BO-augmentation the circuit passes the redes-
ignability check. The feasibility check was processed next, since the number of inputs of
A-group, nuA=5, does not exceed nupIA(MAX)=10, finding reachable vectors is cost effec-
tive and we proceed to check the feasibility of implementation after finding the reachable
input vectors. The total number of reachable input vectors for B-group is 21 which is less
than INPUT_VECTORMAX:4096, so re-implementation is feasible and the circuit has
passed the feasibility check. The transfer function for B-group was determined and the cir-
cuit can be re-implemented.

For the circuit “apex6”, the circuit passes the redesignability check as shown in
Table 5.3. For the feasibility check, as shown in Table 5.2 and in Appendix A, the number

of inputs and outputs of A-group are 19 and 8, respectively, and they exceed

79

nuPIA(MAX)=10 and nupIA(MAX)/2=5, respectively. Therefore, as discussed in Section
4.1.2, the A-group was partitioned into two blocks A1 and A2 where the number of inputs
and outputs of A, were 9 and 5, respectively, and those of A2 were 10 and 3, respectively.
Thus, this partitioned A-group passes the criterion of Property 4.8 and hence finding reach-
able vectors is cost effective. The circuit passed the feasibility check and the redesigned B-
group can be re-implemented.

For the circuit “count”, it is similar to the case of “apex6”,where the number of
inputs and outputs of A- group exceed nupIA(MAX) and nupIA(MAX)/2, respectively.
Therefore, the A-group was partitioned into two blocks A] and A2, where the number of
inputs and outputs of block A1 were 13 and 6, respectively. Here, block A2 passed the test
but block A] failed the criterion of Property 4.8. So, BI-augmentation was performed
resulting in inclusion of gate [669] in B-group. With this BI-augmentation the number of
outputs of block A, reduced from 6 to 5=nupIA(MAX)/2, meeting the criterion of Property
4.8 and hence finding reachable vectors is cost effective. The circuit passed the feasibility
check and the redesigned B-group can be re-implemented.

For the circuit “cmb”, the B-group is chosen as all its inputs are the primary inputs
of the original circuit, where no A-group is included. Results show that the C-group passes
the redesignability check. Since the total number of reachable input vectors for B-group is
16 which is less than INPUT_VECTORMAX, re-implementation is feasible.

For the circuit “15”, the B-group is chosen as all its outputs are the primary outputs
of the original circuit, where no C-group is included. The circuit passes all tests and can be
re-implemented.

For the circuit “17”. Redesignability check performed on the C-group obtained for

80

this circuit was successful. In the feasibility check, the first criterion of cost effectiveness
of finding the reachable input vectors was satisfied but the number of reachable input vec-
tors was 252, which is greater than INPUT_VECTORMAX, so re-implementation is not fea-
sible according to Property 4.9. Hence, the circuit has failed the feasibility check, as

indicated in Table 5.3, and the redesign process is halted.

81

Chapter 6

CONCLUSIONS

This thesis describes a new problem of redesigning digital VLSI circuits with
incomplete implementation information. Given a digital circuit with incomplete implemen-
tation information, the proposed redesign process is to recover the original design from the
partial known implementation information. In this study, the developed redesign process is
comprised of three steps: redesignability check, feasibility check and re-implementation.
Computational complexity is of major concern in this problem. A number of properties
have been developed to determine whether the target circuit is redesignable or not, without
involving excessive computation. As mentioned earlier, based on the assumptions, all tar-
get circuits are redesignable. However, some redesign solutions may end-up with redesign-
ing the entire circuit which is costly. Therefore, by "redesignable" in this study it is meant
that the circuit can be redesigned at a reasonably low cost. The cost factor is considered at
the second stage of the redesign process, that is the feasibility check. In this check, the cost
associated with determination of reachable input vectors of B-group is first considered. If
it is cost effective to find the reachable vectors, feasibility of re-implementation of the miss-
ing parts is evaluated. The decision whether to re-implement the missing parts or not is

made taking various cost factors into account which include factors like complexity of the

82

transfer function of missing parts and the need of the task in hand. A number of efficient
partitioning schemes for the target circuit have also been developed in order to make the
redesign process cost effective both in terms of time and money. In our developed redesign
process, the system with incomplete implementation information is redesigned using con-
cepts of test generation techniques. This redesign process was used to redesign the missing
parts of various benchmark circuits and satisfactory results were obtained.

The developed redesign process can be applied to efficiently deal with microelec-
tronics obsolence problem. It can be very helpful in configuration management by gener-
ating documentation for undocumented designs. The process can also be effective in cases
where safe replacement of some functional blocks in an existing implementation of the cir-
cuit is required. Safe replacement may be needed due to reasons such as performance
improvement, obsolete parts. This developed redesign process can also be extended to be

used for correction of single design errors .

This study also outlined a number of interesting research topics for future research:

1. Based on the proposed partitioning schemes, how to efficiently and effectively
generate the reachable input vectors of B-group.

2. How to efficiently and effectively determine the observability of the outputs of
B-group.

3. How to efficiently and effectively find the minimum number of primary input
vectors that generate all reachable input vectors of B-group while making the
corresponding outputs of B-group observable.

4. Develop new partitioning schemes which can efficiently and effectively deter-

83

mine unredesignability within a constrained cost defined by the designers.

5. How to take into account the timing constraints, such as wire and propagation
delays, hold times, of the original implementation of missing parts.

6. How to determine whether the missing parts included some redundant elements
or not. Redundant elements might have been used for the purpose of hazard
removal.

7. How to efficiently and effectively apply this technique for sequential circuits

with missing or incomplete implementation.

84

APPENDIX A

85

APPENDIX A

BENCHMARK CIRCUITS PARTITIONING DETAILS

alu2

p3 = {[1083], [1080], [1107], [1628], [1079], [1090113113 = {[465], [466]}; YB = O
UPIC = {a, b, c, d, e, f, g, h, i,j}; yIC : {m, n}; yC = {k, l, 0}
up“ = {e, f, g, h,j}; pA = {[1083}, [10801,[1107],[1628], [1079], [1090]};YA = 0

am

133 = {AX20, AXZI, X2161, [116], [431], [597], [2187], [3791], [2325], [2210],
[3773]}; qB = { [428], [429]}; yB = {X2323_P, X2161_P}

uPIC = {RYZ};Y1C = O; YC = {M20}. AXZI_P}

um = {CBT2, PSYNC, ICLR, TXMESS_N, A, B, QPRO, QPRI, QPR2, QPR3, QPR4,
AXZO, X2320, X2321, X2322, X2323, X2324, X2160_N, X2161}; pA = [[2210],
[597], [116], [431], [2187], [3791], [2325], [3773]}; YA = g

111

PB= {b,c, g, [293]};q3={[273]};y3=0
uPIC = g; Yrc = {e}; YC = {f}
upm= {a,Cl;PA = {[2931}; YA :18}

£11

pB = {lGAT(0), ZGAT(1), 3GAT(2), [307]}; ya = {22GAT(10)}
“PIC = Q: m = 3: yC = 3:
upn = {20AT(1). 3643(2)); 1);, = {[3071}; YA = Q

unflfla

P3 = {13271, [3301};913 = {[335]}; YB = Q
uPIC ={b,C}:Y1C = g; Yc = {11,13 1. 11}
um. = (a. d. e. f); pi = {13271. 13301}; YA = z

86

unAZa

= {[337] [338]}'q3= {[339], [397]};yB=®
uPIC= {a d} Y1c= O; YC= {e, f, 111, Mg
“PIA — {b.c); pA- — {[337}, [338]}; yA- _

unBZa

PB: {a C [3261 [3501}'QB={[3271};YB=@
uPIC={d. 6}, YIC= O YC= {g,h}
“PIA‘ - 1 b C} PA= {13261, [3501}; YA:

cmb

={j.k l m};qn= {[296] [397]};yt3=
upIC-{abcdefg,h11,nop}ylc gQ;yc={q,t}
“PIA=Q’ PA= z'3’A= O

mum

p3 = {e, g, q, a0, d0, f0, [663], [660], [654], [651], [669], [666], [633]}; qB : {[303],
[664] [67011' YB=

“PIC: {j q. 8}; ytc= gig rc={c10 t0 v0}

111)“: {q, r, u, v, w, x, y, 2, a0, b0, c0, d0, e0, f0}; pA = {[663], [660], [654], [651],
[669]. [666]. [633]}; YA = g

decod

= {a C [348]};qB= {[351] [352] [357] [358]}'YB=
upm: {b, c, (1}; VIC: Q; yC={f, g,h, i, j,k, l, m, n, o, p,q,r, s, t, u}

u1>1A= {(1}; PA - {[348]}; YA=

examplrz

pB : {b, b1, a2, c2, r0, [989], [1000], [1042], [994], [988], [1039], [1756], [1130], [78],
[993], [985]}; qB : {[356], [382], [1081], [1772], [1780]}; yB = {m2}
upm:{bfg,ij,klmnop,q,rstuvwxp0r080blq1,r1, s1,t1,ul,vl,
W], X], yl, a2, b2, c2, d2, e2, f2, g2, h2}; yIC: {m2}; ye: {g3, d4, e4, f4, g4, h4, i4, j4,
k4, 04, p4, r4, 54, t4, u4, v4}

upIA = {b, f, p0, a2, b2, c2, e2, h2}; pA = {[989], [1000], [1042], [994], [988], [1039],
[1756], [1130], [78], [993], [985]}; yA = Q

87

.13

pB = {V56(26),V28(26),V56(27),V28(27),V120(0),V88(O),V120(l),V88(l),V120(2),
V88(2),V120(3),V88(3),V120(4),V88(4),V120(5),V88(5)}; qB = {[439]}

um = {V56(18),V28(18),V56(19),V28(19),V56(20),V28(20),V56(21),V28(21),
V56(22),V28(22),V56(23),v28(23),V56(24),V28(24),V56(25),V28(25) }; yIC = Q;
YC={V133(1)}

Um=@:pn=®:yA=®

15

p3 = {V183(15), V76(14), V64(14), V76(11), V64(11), V183(12), V118(2), V115(2),
V199(14),V100(13),V88(13),V199(8),Vl24(1),V121(1),V100(7),V88(7),V199(11),
V100(10), V88(10), V183(0), V132(1), v128(1), V112(3), V109(3), V52(15), V40(15)}
qB =2; yB = {V183(14), V183(1 1), V199(13), V167(0), v167(12), V183(8), V167(15),
V199(4), V199(10), V199(7)}

uPIC = @; YIC = 9: YC = O

uPIA = {V64(15), V76(15), V88(11), V100(11), V88(14), V100(14), V88(15), V133(0),

V100(15), V115(3), V118(3), V121(2), V124(2), V121(3), V124(3), V128(2), V132(2),
V128(3), V132(3)}; yA:{V183(15), V183(12), V199(14), V199(8), V199(11), V183(O)}

11

p3 = {V199(l), V199(O), V160(16),[1941], V160(24),[1893], Vl60(23), [1899],
V160(22),[1905], V160(21),[1911], Vl60(20), [1917], V160(26),[1881], Vl60(19),
[1923], Vl60(18), [1929], V160(l3),[1959], V160(17),[1935], Vl60(11), [1971],
Vl60(10), [1977], Vl60(25), [1887], Vl60(15), [1947], Vl60(8), [1989], Vl60(27),
[1875], Vl60(14), [1953], V160(5), [2007], Vl60(12), [1965], Vl60(4), [2013],
Vl60(3), [2019], Vl60(9), [1983], Vl60(6), [2001], Vl60(7), [1995]}

QB = {[1132], [1260], [1244], [1228], [1212], [1196], [1292], [1180], [1164], [1084],

[1148], [1052], [1036], [1276], [1116], [1004], [1308], [1100], [956], [1068], [940],
[924], [1020], [972], [988]}; YB = Q

“PIC = {V199(1), V199(O), V199(4), V192(27), Vl92(26), V192(25), Vl92(24),
Vl92(23), V192(22), V192(21), V192(20), Vl92(19), Vl92(l8), V192(l7), Vl92(16),
Vl92(15), Vl92(14), V192(13), V192(l2), Vl92(l 1), V192(lO), V192(9), Vl92(8),
V192(7), V192(6), V192(5), V192(4), Vl92(3)}; YIC = 3;

ye = {V259(31), V259(30), V259(29), V259(28), V259(27), V259(26), V259(25),
V259(24), V259(23), V259(22), V259(21), V259(20), V259(19), V259(18), V259(17),
V259(16), V259(15), V259(14), V259(l3), V259(12), V259(1 l), V259(10), V259(9),
V259(8), V259(7)}

upIA = {V199(1) V199(O) V128(27) V199(4) V128(26) V128(25) V128(24) V128(23)
V128(22)V128(21)V128(20)V128(19)V128(18)V128(17)V128(16)V128(15)
V128(14) V128(l3) V128(12) V128(11) V128(lO) V128(9) V128(8) V128(7) V128(6)

88

V128(5) V128(4) V128(3) Vl92(27) V192(26) Vl92(25) Vl92(24) V192(23) V192(22)
V192(21) V192(20) V192(19) V192(18) V192(17) Vl92(16) V192(15) V192(14)
V192(l3)V192(12)V192(11)V192(10)Vl92(9)Vl92(8)V192(7)Vl92(6)V192(5)
V192(4) V192(3)}

pA = {[1941] [1893] [1899] [1905] [1911] [1917] [1881] [1923] [1929] [1959]

[1935] [1971] [1977] [1887] [1947] [1989] [1875] [1953] [2007] [1965] [2013]
[2019] [1983] [2001][1995]};yA=Q

. '|
Pa = {[299}, [300]. [330]}; C13 = {[322]}; YB = Q

“PIC = {a, b. C. d. C}; ytc = g: YC = If}
11pm = {a. b. C}; p», = ([299]. [3001.[330]};YA = 3

89

REFERENCES

90

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[3]

[9]

[10]

[11]

[12]

REFERENCES

Defense Microelectronics Activity [Online] Available http://www.dmea.osd.mil, J an-
uary 3, 1998.

E.J. Byme, “A Conceptual Foundation for Software Re-engineering,” Proc. IEEE
Conf. on Software Maintenance, pp. 226-235, 1992.

E.J. Chikofsky and J .H. Cross 11, "Reverse Engineering and Design Recovery: A
Taxonomy," IEEE Software, Vol. 7, pp.l3-l7, January 1990.

CL. Wey, “Development of Redesign Process for Digital VLSI System,” Proc. of
40th Midwest Symp. on Circuits and Systems, pp. 1001-1004, August 1997.

A. Wojcik, C.L. Wey, T. Doom, and J. Samarziya, “An approach to the redesign of
digital circuits from partial information,” Tech. Rep. MSUCPS:TR97-47, Depart-
ment of Computer Science, Michigan State University, Dec, 1997.[Online] Available
http://web.cps.msu.edu/’I‘R/MSUCPS:TR97-47.

C.L. Wey and MA. Khalil, “Redesignability Analysis of Digital VLSI Circuits with
Incomplete Implementation Information,” to appear in Proc. of IEEE International
Symp. on Circuits and Systems, May 1998.

MA. Khalil and CL. Wey, “Using Test Generation Techniques for Redesigning Dig-
ital VLSI Circuits with Incomplete Implementation Information,” Proc. International
Conference on Chip Technology, Hsinchu, Taiwan, pp. 146-152, April 1998.

MCN C Library from the 1989 International Work-shop on Logic Synthesis, [Online]
Available http://www.cbl.ncsu.edu/pub/Benchmark_dirs/LGSynth89/DOCUMEN-
TATION/ doc.txt.

Sentovich et al., “SIS: A system for Sequential Circuit synthesis,” Department of
Electrical Engineering and Computer Science, University of California, Berkeley,
CA 94720, May, 1992.

M. Abrarnovici, M.A. Breuer, and AD. Friedman, Digital Systems testing and Test-
able Design, Computer Science Press, 1990.

P.K. Lala, Fault-tolerant and Fault-Testable Hardware Design, Prentice-Hall Intema-
tional, London, 1985.

H. Fujiwara, Logic Testing and Design for Testability, 1985.

91

[13] SB. Akers, In, “On tthe theory of Boolean functions,” Journal of the society for
Industrial and Applied Mathematics, vol. 7, pp. 487-498, 1959.

[14] Ku, C.T., G. M. Masson, “The Boolean difference and Multiple Fault Analysis,”
IEEE transactions on computers, vol. c-24(1): pp. 62-71.

[15] E.J. McCluskey, Logic Design Principles, Prentice Hall, Englewood Cliffs, NJ,
1986.

[16] J .P. Roth, “Diagnosis of automata failures: A calculus and a method,” IBM Journal
of Research and Development, pp. 278-291, July, 1966.

[17] B. Strunz, C. Flanagan, and T. Hall, Design for Testability in Digital ASICS,
[Online] Available http://www.ul.ie/~strunzldft__notes/course.html, January 23,
1995.

[18] CL. Wey, “UUT Modeling for Digital Test - A Self-Test Approach,” Proceedings of
the IEEE Fourth Annual Phoenix Conference on Computers and Communication, pp.
312-316, March 1985.

[19] CL. Wey, “A Searching Approach Self-testing Algorithm for Analog Fault Diagno-

sis,” in Testing and Diagnosis of Analog Circuits and Systems, edited by R.-W. Liu,
Chapter 6, pp. 147-186, North-Holland, 1991.

92

"IIIIIIIIIIIIIIIIIII