PLACE IN RETURN BOX to remove this checkout from your record.

TO AVOID FINES return on or before date due.

 

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

I.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

MSU Is An Affirmative Action/Equal Opportunity Institution

ON THE DESIGN OF A COMPUTER-AIDED DESIGN SYSTEM
FOR
DIGITAL CIRCUITS

By
Tao Shinn Chen

A DISSERTATION

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

DOCTOR OF PHILOSOPHY

Department of Electrical Engineering

1988

ABSTRACT

ON THE DESIGN OF A COMPUTER-AIDED DESIGN SYSTEM
FOR
DIGITAL CIRCUITS

By
Tao Shim: Chen

A methodology for automating the design processes for digital circuits is investi-
gated. This research focuses on establishing both the unification and consistency for the
overall design environment. The study at the unification issue focuses on the circuit
representation in all aspects in order to provide a tool-independent and component-
oriented design database. And the objective of the consistency issue is to minimize

redundant or repetitive tasks during the design processes.

Several tools are developed to illustrate this methodology. There are a graphic tool
with interactive visualization for design capture, a logic-timing simulator at the MOS
transistor-switch level, and a verification tool for circuit layout. The embedded theory for
the methodology and tools is established and proven. For the graphic tool, the major
endeavor focuses on developing efficient data structures for any circuit schematic with
unlimited drawing size and only having fastest graphic operations executed to obtain the
shortest computer response time. Next, a totally new method is used for switch-level
simulation. This approach not only has linear-time complexity but also obeys the law of
excluded middle. Moreover, the bidirectional problem for simulating MOS transistors at
pure logic level is solved. The performance analysis shows that this tool can simulate a
15,000-transistor circuit with the speed of less than 25 seconds per clock on a typical
workstation (SUN-3). Finally, a rule-based verification approach provides a static way to
validate circuit structures from the layout level to a system level without specifying the
inputs. The fundamental work which verifies a transistor network by its Boolean func-

tions is developed. This method ensures full correctness of the circuit topology because it

takes all components into account.

Since the system was implemented in C and Prolog languages and the machine
dependent codes are separated as much as possible, it is easily portable to other machines
which have the graphic display capability. Future work should be directed toward
increasing the rate of automation with consideration of human factor, extending the work
into the field of computer-aided engineering, and incorporating a hardware description

language, such as VHDL, for circuit algorithmic and behavioral development.

Acknowledgments

Thank my advisor, Dr. P. David Fisher, for his detailed review and very construc-
tive criticism of my dissertation. My wife, Rueyeh, also deserves the appreciation for her
endless support. And, for all the persons in the Electronic Research and Development
Laboratory, especially Brian Musson, I acknowledge their assistance and excellent per-

formance for maintaining the computer systems.

iv

TABLE OF CONTENTS

LIST OF TABLES ........................................................................................................ vii
LIST OF FIGURES ..................................................................................................... viii
Chapter 1. Introduction .................................................................................................. 1
1.1 Problem Statement ................................................................................ 1

1.2 Approaches ............................................................................................ 2

1.3 Outline of the Thesis ............................................................................. 5

Chapter 2. Design Methodology .................................................................................... 6
2.1 The Characteristics of Digital Circuit Design ....................................... 7

2.2 Working Environments ......................................................................... 9

2.2.1 Design Capture Environment .................................................... 11

2.2.2 Simulation and Verification Environment ................................ 12

2.2.3 Team Work Environment .......................................................... 13

2.2.4 Documentation Environment .................................................... 14

2.3 Circuit Representation ......................................................................... 15

2.3.1 Format ....................................................................................... 15

2.3.2 Generic Component Model ....................................................... 18

Chapter 3. Unified Design Database ............................................................................ 20
3.1 Database Model ................................................................................... 20

3.2 Database Operations ............................................................................ 25

3.2.1 Projection ................................................................................... 26

3.2.2 Design Flattening ....................................................................... 28

Chapter 4. Graphical Approach for Design Capture ................................................... 32
4.1 Overview ............................................................................................. 32

4.2 Data Structures .................................................................................... 34

4.3 Tasks ................................................................................................... 37

Chapter 5. Logic-Timing Simulation at Transistor-Switch Level ............................... 43
5.1 Overview ............................................................................................. 43

5.2 Circuit Model ...................................................................................... 46

5.3 Signal-Flow Determination ................................................................. 50

5.3.1 Strength Determination Algorithm ........................................... 54

5.4 Simulation Theory ............................................................................... 57

5.4.1 Multiple-Delay Model ............................................................... 64

5.4.2 Tuning for CMOS Digital Circuits ........................................... 67

5.5 Performance Analysis ......................................................................... 68

5.6 Key Examples ..................................................................................... 69

Chapter 6. Rule-Based Verification for CMOS Gate Structures ................................. 75
6.1 Overview ............................................................................................. 75

6.2 The Knowledge Domain ..................................................................... 78

6.3 The Boolean Model ............................................................................. 8O

6.4 Implementation in Prolog .................................................................... 83

Chapter 7. Conclusion .................................................................................................. 88
7.1 Summary ............................................................................................. 88
7.2 Future Research and Development ..................................................... 92
LIST OF REFERENCES .............................................................................................. 93

vi

LIST OF TABLES

Table 5-1 The logic representation of voltage values. ................................................. 48
Table 5-2 The NMOS enhancement-mode transistor model. ...................................... 49
Table 5-3 The PMOS enhancement-mode transistor model. ....................................... 49
Table 5-4 Signal-flow determination of a non-OFF transistor. ................................... 54
Table 5-5 Performance analysis of SWSIM on a SUN-3 workstation. ....................... 69

vii

LIST OF FIGURES

Figure 2-1 A consistent working environment. ........................................................... 11
Figure 2-2 The functional method. .............................................................................. 16
Figure 2-3 The extensional method. ............................................................................ 17
Figure 2-4 The definitional method. ............................................................................ 18
Figure 2—5 The model of a component. ....................................................................... 19
Figure 3-1 The entity-relationship diagram of STOCK. ............................................. 21
Figure 3-2 A typical structure of STOCK. .................................................................. 22
Figure 3-3 The structure of a component file. ............................................................. 23
Figure 3-4 The structure section of a J-K master/slave flip flop. ................................. 23
Figure 3-5 The U0 node and symbol sections of a J -K flip flop. ................................ 24
Figure 4-1 The editing process of a circuit schematic. ................................................ 34
Figure 4-2 A typical circuit schematic. ........................................................................ 35
Figure 4-3 A typical wire bundle. ................................................................................ 37
Figure 4-4 The data structure of a wire bundle. ........................................................... 38
Figure 4-5 Joint verification. ........................................................................................ 40
Figure 5-1 A two-input XOR gate. .............................................................................. 45
Figure 5-2 The graph representation of the circuit in Figure 5-1. ............................... 51
Figure 5-3 The graph hierarchy of a general transistor graph. .................................... 53
Figure 5-4 The general diagram of a basic building element. ..................................... 58
Figure 5-5 The structure of a delay ring. ..................................................................... 66
Figure 5-6 The performance of SWSIM on a SUN-3 workstation. ............................. 69
Figure 5-7 Delay demonstration using pass transistors. .............................................. 71
Figure 5-8 A timing diagram for the circuit in Figure 5-7. ......................................... 71
Figure 5-9 An inverter with Schmitt trigger feedback. ................................................ 72
Figure 5-10 A timing diagram for the circuit in Figure 5-9. ....................................... 72
Figure 5-11 A dynamic D-type flip-flop. ..................................................................... 72
Figure 5-12 A timing diagram for the circuit in Figure 5-11. ..................................... 73
Figure 5-13 A timing diagram for the circuit in Figure 5-1. ....................................... 73
Figure 5-14 A 4-bit barrel shifter. ................................................................................ 73
Figure 5-15 A timing diagram for the circuit in Figure 5-14. ..................................... 74
Figure 5-16 A self-oscillating circuit. .......................................................................... 74
Figure 5-17 A timing diagram for the circuit in Figure 5-16. ..................................... 74
Figure 6-1 The rule-based approach for digital circuit verification. ............................ 77
Figure 6-2 The hierarchical verification system. ......................................................... 78
Figure 6-3 The topology of a CMOS gate structure. ................................................... 80
Figure 6-4 An un-complete gate. ................................................................................. 82
Figure 6-5 A complete gate (NAND). ......................................................................... 83
Figure 6-6 A NOR gate representation. ....................................................................... 84
Figure 6-7 A latch example. ........................................................................................ 86
Figure 6-8 A 4-bit parity generator. ............................................................................. 87

viii

Chapter 1 Introduction

The computer-aided design (CAD) for digital circuits involves three major objec-
tives, i.e., design capture, design verification, and layout implementation. Since Mead
and Conway [36] simplified the complexity of the design rule for integrated circuit lay-
out, circuit implementation with customized chips spread rapidly. And, the current tech-
nology of integrated circuit design continues to evolve resulting in chips with greater
functional complexity and speed. This thesis concerns the methodology for designing a
CAD system which takes full advantage of current computer technology in order to

enhance the custom integrated circuit design environment.

1.1 Problem Statement

A CAD system, which assists human to complete design tasks, must integrate many
different tools in order to handle all aspects of a design. As a result, many systems are
tool oriented. The translation of design data among different tools not only requires
designers to handle different sets of tools but also may introduce unconscious errors in
the design. Moreover, inconsistency of tools also may generate repetitive and/or redun-
dant work. To cope with this, new methodologies are required in order to speed up the

overall design process while minimizing the number of design errors.

Another crucial issue is design verification. It is well known that the complementary
metal-oxide-semiconductor (CMOS) technology has brought the digital circuit design
down to the transistor level. The traditional design method which focuses on the gate
level in general doesn’t meet the requirements for designing high-performance circuits.
Although the logic simulation technology at the gate level has almost achieved linear-
time complexity [26] [32], it can not apply directly to MOS transistors due to the bidirec-
tional feature of these devices. As a result, many researchers use approximate circuit

theory to deal with this problem [12] [24] [25] [34] [41]. However, the performance of

2

their simulators can not reach the linear-time complexity and is generally circuit-
topology dependent. Moreover, their simulators are not suitable for CMOS logic design
because the corresponding layout has not yet been implemented. To solve this problem,
a new simulation technique, which is based on the MOS-transistor—logic model [10],
needs to be developed. Such a simulator generates a new class of switch-level simulation
which is higher than the current switch-level simulation and lower than the gate level
simulation. Therefore, it is very suitable for analyzing digital transistor networks, such as

pass transistor logic [43], before the layouts are implemented.

It is also well known that simulation may not discover some errors due to the com-
plexity of digital circuits. To verify a layout from its circuit topology ensures the correct-
ness of its function. However, one of the major difficulties of this approach is the variety
of possible circuit structures that must be addressed [13] [14]. To deal with it, formal
verification is required, which can take advantage of the circuit hierarchy in order to

reduce the circuit complexity.

1.2 Approaches

The design process for digital circuits involves a set of diversified tasks which span
design input to device fabrication and testing. Some portions of the design process are
changing rapidly due to advanced fabrication technology. However, some other portions,
such as the digital theory, remain almost the same. This is very similar to compiler tech-
niques, i.e., the theory in the front end is fairly stable, but the back-end techniques vary
from one processor to another. This same phenomenon guides the methodology of
designing a CAD system. Another phenomenon in VLSI circuits is that the circuits are
notoriously "unforgiving" with respect to design errors. Any defect in the design of a
chip usually makes it useless. This implies that the verification tools are more and more
important since debugging is usually impossible after a design is fabricated. Based on

these facts, this research primarily focuses on the front end of the design process.

The front end is separated from the whole design process down to the transistor
level. The fundamental elements in the front end are MOS transistors, i.e., they are
modeled as switches or attenuators with some delay values. In other words, the goal of
this research is to provide an enhanced environment to implement digital circuits from
design input above the transistor level to design verification at the (ideal) transistor level.
This environment supports necessary facilities to verify a design before it is translated
into the physical layout level. Therefore, this CAD system is intended for use in the
areas of full custom design, cell-based design, and random logic design. To achieve the
objectives, three tasks are involved, i.e., develop a method for design capture, a tech-
nique for tool integration, and a design-verification methodology.

The initial task in implementing digital circuits is to capture the circuit connectivity.
This can be realized by drawing the circuit schematics. The schematic-entry interface is a
graphic tool using pop-up menus, icons and multiple-window management for design
capture. The complexity of circuit schematics is unified by two objects, i.e., the connect-
ing wires and the circuit components. Wires are modeled as continuous line segments
while components are modeled as a set of elementary drawing commands. By interpret-
ing the drawing commands, any kind of graphic symbol can be used to represent a com-
ponent without program modification. This tool can be used not only as a circuit-
schematic editor but also as a general-purpose graphic editor for some kinds of network
analyses. This approach creates an environment which makes the drawings at any
structuredescription level possible, as long as it is higher than the layout level. Other
techniques, including circuit expansion from the design level down to the (ideal) transis-
tor level, hierarchical design methodology and documentation environment, are

developed and integrated into the CAD system.

The second task is to develop a technique for tool integration. The objectives of this
task are to combine individual tools together, to update inefficient tools, and to accom-

modate new tools. This work implies that tools should be as independent as possible on

4

their interesting data format and location. As part of the work required here, a unified
database was developed to store circuit components. This database can grow in two
directions, i.e., not only can new components be added but also new attributes of old
components can be created without any modification to existing tools. Therefore, this
database serves as the kernel for the CAD system. In order to create a team-design
environment and take advantage of existing information provided by the UNIX file sys-
tem, this database is realized as several directories, and components are files in these
directories. A designer can use his/her own local database and share his/her work with
other designers through the access of a group and/or global database.

The design verification task focuses on the ideal transistor level. Since this is the
lowest level for logic timing simulation, the greatest accuracy above the switch level can
be obtained by modeling MOS transistors with different delay values. A new algorithm
for switch-level simulation with or without unit-delay constraints is developed. Here,
digital circuits are modeled as time-invariant, linear, discrete-time dynamical systems,
much like systems are modeled in control theory. And, MOS transistors are modeled as
bidirectional switches. Since simulation is often done prior to the circuit layout, at which
time the load and routing capacitances are not known, the delay of each transistor is
obtained from the fanout information. A simulator based on the new algorithm is imple-
mented, and it is proved that it can simulate any digital CMOS circuit. The computa-
tional complexity is linear with respect to the number of transistors in the target circuit.
Clearly, it is more versatile than the current event-driven simulators, such as MOSSIM II
[24], since they can not simulate oscillating circuits and the simulation speed is circuit-

topology dependent.

Since simulation only depends on the input data, some errors may not be covered
during simulation. A tool for symbolic verification is also developed. This rule-based
symbolic verifier recognizes the CMOS gate structures in a circuit and generates the

verified Boolean equations for the gates.

The research and development work reported here results in a schematic-entry CAD
system for CMOS digital circuits with an open architecture. Currently, this CAD system
is at the transistor-logic level for design verification and at any structural description
level for design capture. However, it is easily extended down to the layout level by
accommodating some tools for layout generation and verification, and up to the
functional-description level by adopting some hardware description language for design

capture, e.g. VHDL [16] [17].

1.3 Outline of the Thesis

This thesis contains seven chapters. Chapter 1 is the introduction which provides the
problem statement, general approach, and overview of the accomplishments of this
research. Chapter 2 explains the design methodology of the CAD system. The charac-
teristics of typical digital circuit design methodology is considered first in this chapter.
Then, the consistent working environment which supports the design process is
described. At the end, the representation method for digital circuits is given which guides
the development of this system. Chapter 3 concerns the structure of the embedded com-
ponent database. The database operations and design "flattening" down to a specific com-
ponent level are presented. Based on the unified database, several tools are developed.
They are discussed in the rest of chapters.

Chapter 4 introduces the idea of design and implementation of a universal graphic
tool for design capture. The data structures and necessary tasks are described. Chapter 5
is dedicated to the switch-level simulation. The simulation theory and the method which
overcomes the bidirectional feature of MOS transistors in order to support the transistor-
logic models are provided. Chapter 6 describes the techniques for structure verification.
The outline of a hierarchical verification system and the work at the MOS transistor level
are depicted. Chapter 7 provides summary and conclusion. The extensibility of this sys-

tem is also discussed in this chapter.

Chapter 2 Design Methodology

The complexity of digital circuit design has increased rapidly due to the progress of
integrated circuit (IC) technology. The systems of yesterday are the boards of today,
while the boards of yesterday are the ICs of today. Design is a creative activity. How-
ever, it involves so many details in order to turn a concept into a VLSI circuit or system.
The goals of computer—aided design (CAD) are to minimize all redundant or repetitive
work and let designers concentrate on the creative aspects of a design. Two major issues
of designing a CAD system are the working environment during the design process and
the design representation. A friendly user interface is usually used to describe the
environment of a system. However, to deal with a complete design task, it is only an

essential condition.

Design representation is another crucial issue. For a specific tool, design representa-
tion is much easier since only one aspect of the design needs to be of concern and
modeled. For example, a simple NAND gate may be modeled as a graphic symbol in a
schematic editor, a set of statements in some hardware description language, a layout in a
layout editor, or several transistors, capacitors, and resistors in circuit simulators. Indivi-
dual tools, no matter how powerful, are rarely useful unless well integrated into a system
[6]. A complete CAD system integrates many tools to achieve the design task. There-
fore, it must have the capability to model as many aspects as possible. In other words, a
design representation method must be developed in order to provide a uniform user inter-

face for the development and use of CAD tools in an open system [7].

This chapter concerns the design methodology of building such a CAD system for
digital circuits in the digital logic-design field. At the beginning, we characterize the digi-
tal circuits. Then, the working environment and design representation issues are dis-

cussed.

7

2.1 The Characteristics of Digital Circuit Design

A general design of digital circuits has three dimensions. The creation of a circuit
occupies two dimensions since the components in the circuit must be placed and con-
nected. The other dimension transforms a "dumb" circuit into a "smart" circuit. The
micro-code design for a processor is an example. Although the third dimension may not
be covered in a circuit design, the progress of VLSI technology shrinks the area of pure
two-dimension designs. However, since the theory used in the third dimension is much
like that in the programming world, we restrict the characteristic analysis of digital cir-

cuit design in the electronic world.

Rubin [1] gave a description of characteristics of digital circuit design. Based on
his characterization, digital circuit design has four characteristics, i.e., hierarchy, dif-
ferent views, connectivity, and "flat" geometry in circuit layout. However, if we
emphasize the "digital" portion, other characteristics can be obtained.

We characterize the endeavor of digital circuit design as follows:

(1) Simple primitive components -- A digital circuit, no matter how complicated it
is, usually contains very few primitive components. For examples, a digital CMOS cir-
cuit only contains PMOS and NMOS enhancement transistors and a T'I'L circuit only
contains NAND gates in the digital world. Most efforts in designing a digital circuit
focus on the selection of components and making the connection of the selected com-

ponents to compliance with the design specifications.

(2) Hierarchy -- The hierarchical approach is the natural way to design a digital cir-
cuit. According to the design specifications, a circuit is decomposed into many functional
blocks. Each block is further divided into lower level blocks, etc. By hiding low-level
details, one can view a design as a component tree. Recrusively, the whole structure of a
digital circuit is a complex tree with the primitive components at the bottom of hierarchy,
i.e, the leaves of the tree. A design which restricts all the components in the same level is

said a "flat" design [6]. Due to the complexity of today’s digital circuits, it is almost

impossible to design circuits this way.

(3) Connectivity -- The unified view of a digital circuit is a collection of com-
ponents. Defining the relationship among the components is the major activity in circuit
design. However, after the connectivity is established, the design endeavor concentrates
on minimizing any parasitic phenomenon which is introduced by the connecting materi-
als. Therefore, a design process can be further separated into two phases. The first
phase, called logic design, deals with logic (ideal) components and the second phase,
called implementation, is to reduce harmful parasitic effects which are introduced by

connecting wires and real components.

Based on this methodology, a layout tool which mixes logic design and implemen-
tation together is not a satisfactory solution for digital circuit design because these tools
would require the designer to pay attention to many details simultaneously in the imple-
mentation while doing logic design. Hence, one can say such a tool is an implementation
tool rather than a design tool. However, this does not mean a layout tool is not necessary.
On the contrary, it is an essential tool for integrated circuit design. The t0pic of argument

is that it is merely a "too ", not a complete design "system".

(4) Documentation -- A chip or circuit board is almost useless if there is no manual
along with it. All chips look the same regardless their actual size or shape. Digital cir-
cuits are usually embedded in some system to perform the desired function. Chips or cir-
cuit boards are generally intermediate products. Their complexity requires documents to
carry necessary information for down stream work. Hence, a design is not completed
until its document is finished. An apparently redundant work is to draw the whole design
again in preparing the document after a design is almost finished. Although a circuit
schematic can be printed or plotted alone, many manuals require that it appears along
with the text. A complete CAD system should take care of this requirement and minim-

ize any redundant work.

9

Briefly, our design methodology recognizes that digital circuit design is an endeavor
of defining connections among the components. The design process benefits from
hierarchical representation. Hierarchy divides design efforts into many levels. Therefore,
at a giving level, the design complexity is greatly reduced. Most tools can take advantage
of hierarchical design to speed up their execution. Moreover, the separation of the design
process into two phases frees designers to concentrate on the creative aspects of circuit
design. The logic design phase let designers focus on the creation of a circuit. Then, the
created logic circuit is modified in the implementation phase to get rid of any fatal parasi-
tics.

Notice that the implementation phase in the design process does not mean to pro-
duce final chips or circuit boards. For integrated circuits, the results from the implemen-
tation phase is the mask data. And, for circuit boards, it means the generation of informa-

tion needed for board layout.

2.2 Working Environments

Several papers can be found which discuss the design methodology of a complete
CAD system. Dunn describes the VLSI design methodology used at IBM [8]. This sys-
tem called DAV ranges from graphic schematic entry for design capture to test genera-
tion for validating real chips. McCalla, et a1. describes a VLSI design system called
ChipBuster which is used in Hewlett-Packard [6]. His description also provides a general
view of CAD system designs. Burling describes the product design and introduction sup-
port systems called SysCAD which is used in AT&T [9]. SysCAD contains many subsys-
tems in order to provide a complete solution for circuit design. Harrison, et a1. introduces
the Berkeley design environment by discussing its fundamentals, i.e., a data manager

called Oct and a graphic editor called VEM [7].

One common feature among these CAD systems is that each of them has a design
database serving as the kernel. The database provides different aspects of a circuit to dif-

ferent tools and acts as a library for design sharing and for concurrent access by

10

designers. The other feature is that the graphic-entry approach is used by each for design

capture.

From their discussions, we conclude that the working environment for digital circuit
design can be classified into five portions. There are design capture, simulation and
verification, team work, documentation, and implementation. The environment for design
capture provides tools for creating the tapology of a circuit and defining the circuit
hierarchy. The simulation and verification environment supports tools for validating a
design and may also provide data for circuit testings. The team work environment is a
network and database facility which supports the necessary mechanism for sharing
design achievement. The documentation environment provides tools for recording
design results. And, finally, the implementation environment supports tools for generat-

ing detail specifications for constructing a circuit.

Nowadays, many CAD systems emphasize on the implementation environment and,
more or less, ignore the other environments. Therefore, designers must repeat some tasks
which have already done previously. For example, a hardware description language can
be used to create a circuit design. However, after a design is created and validated by
some simulation actions, the circuit schematic may still need to be created for documen-
tation. Or, when using a graphic tool to create a circuit topology, one may need to gen-
erate a input file which specifies the topology for simulations and he/she still needs doing
the circuit layout separately. For all of these repetitive tasks, design endeavor is distri-

buted and shrunk.

In our methodology, we focus on the logic design phase with one objective being to
provide a consistent working environment. Figure 2-1 is an abstract illustration, where A,
B, etc., represent different working environment. To minimize the repetitive tasks, con-
sistency among design environments is essential. And, the creativity of a designer is

enhanced by providing a pure logic design environment.

11

   

DESIGN —@
Figure 2-1 A consistent working environment.

2.2.1 Design Capture Environment

Two approaches are currently used for design capture. One is text entry and the
other is graphic entry [10]. Since a general digital circuit design has three dimensions,
each approach has advantages and disadvantages. The text entry approach, such as a
hardware description language, is very suitable for designing circuits at the behavioral
level. Many highly structured circuits, such as ROMS and PLAs, are easily described in
text approach. However, text approach has one deficiency; it is awkward to describe the
connectivity of a design. On the other hand, graphic entry overcomes this since a circuit
schematic is much easier for people to understand the relations among components.
Moreover, if a text description of the circuit is also required, this text-level description
can easily be automatically provided once the circuit has been captured schematically.
We assert that schematic entry for design capture is a valuable tool for a complete logic

design system, even if some hardware description language is supported.

Hierarchy and connectivity guide the design of a schematic editor. According to the
hierarchy feature of a circuit design, the objects at any given structural level are com-
ponents and connecting wires. A schematic editor provides an interface for making all

the connections among the components and a mechanism for "packing" a design at one

12

level and turning it into a component at a higher level. Based on these unified facts, one
can implement a schematic editor for design capture at any structural level in the hierar-

chy. such as transistors, to the system level.

We designed and implemented a schematic editor based on the above considera-
tions. Chapter 4 describes our approach. This tool takes advantage of evolving worksta-
tion capabilities, e. g., popup menus, icons, and multiple-window management for design

capture. It ranges from the MOS transistor level to any higher structural level.

2.2.2 Simulation and Verification Environment

Design verification usually occupies a large portion of design endeavor [8]. Since
the hierarchy of a design is generally established in the design capture environment,
simulation at the current design level can be achieved by modelling the components at
the current level [11]. Another approach is to "flatten" the whole design and simulate at a
level which contains only the same components or the primitive components. Gate-level,
switch-level, and circuit-level simulators use the second approach. Ruehli and Ditlow
gave a good overview of simulation and verification technique for VLSI circuits [12].
Clearly, simulation at the lowest design level may have the greatest accuracy since all the

details are involved.

To deal with the simulation issue, we developed a theory for logic timing simula-
tion. Chapter 5 presents this simulation dreary. The approach models a digital circuit as a
network which consists of different kinds of basic build elements, where the basic build-
ing element need not be a primitive component. However, the I/O function and the delay

time of a basic build element must be specified or calculated before simulation.

The computational complexity of this simulation theory was proven to be linear
with respect to the number of basic build elements in the circuit being simulated. The
disadvantage of this approach is that it can not handle the bidirectional characteristics of

MOS transistors. However, an algorithm called the strength determination algorithm

13

(SDA) was developed, which overcomes the bidirectional problem. The simulation
theory is still valid after SDA determines the signal flows among the transistor network
of a design. The computational complexity of SDA was also proven to be linear with

respect to the number of transistors. SDA is also described in Chapter 5.

The result obtained from the simulation is a logic timing diragram. The resolution
of the timing diagram is the minimun delay time of the basic building elements. Several

examples can be found in Chapter 5.

Another approach to validate a design is to verify its structure [13] [14]. A sym-
bolic approach can verify a design without specifying the input data. Since the structure
of a circuit is established in the logic design phase, verification with the structure seems
very attractive after the implementation phase is nearly finished. For example, the layout
of a integrated circuit design can be verified by its circuit structure, which was esta-
blished in the logic design phase. This is because the simulation approach may not cover
all of the possible input patterns and the structure verification method does not have this

drawback.

A tool which generates a set of corresponding Boolean equations fiom a CMOS cir-
cuit layout was also developed. It validates a layout at the gate level, and the generated
Boolean equations can be used as input for verification at a higher level. The embedded

theory for this tool is presented in Chapter 6.

2.2.3 Team Work Environment

Team work can be classified as being vertical and horizontal [18]. A vertical team
work implies that a task is divided into up-stream work and down-stream work. For
example, "a chip which is designed by A and then fabricated by B" is a vertical team
work. And, horizontal team work implies everybody is working at the same stage.
Clearly, in the logic design phase, the horizontal attribute of team work is a very impor-

tant feature.

14

The major consideration in the horizontal team work environment is the desire to
minimize the problems which are introduced by the duplication of a component during
the design process. It ensures that every designer can obtain the original component. For
example, a designer may finish an ALU design and copy it to other designers. Later, this
designer finds that there is an error in the ALU component. The price to make all the
c0pies being the same may be very high. This is especially true for many geometric lay-
out tools.

In this methodology, the team work environment is established by the structure of
the design database. The database stores all the components in a design. Each designer
has his or her own local database. A group which consists of several designers owns a
group database. And, finally, a global database can be accessed by all the designers. This
approach ensures that every designer can obtain the original component. Hence, it

reduces the duplication problem.

The UNIX file structure helps us to design such a team work environment. This
environment is built into the schematic editor. When a designer needs a component
which does not belong to him or her, a search is automatically made from the group data-
bases to the global database in order to find the component. Therefore, everyone can

obtain the original and newest version of a component.

2.2.4 Documentation Environment

Documents should be treated as part of the design result. Although many word-
processing tools are available and friendly to use, redrawing the schematic of a circuit
design is an obviously repetitive and redundant task. Inconsistency may happen between
circuit design and art work. Moreover, the requirement of mixing text and pictures

should be considered.

We take advantage of the word-processing facility in UNIX systems to achieve

these documentation objectives in circuit design. This facility is a set of programs called

15

TROFF [2]. A schematic can be automatically translated into a series of drawing com-
mands in TROFF. These drawing commands are text but can be interpreted and printed
out as same as the original schematic. The drawing commands can be mixed among other

text and the final printout has the quality which is comparable to that of real text books.

This approach for documentation has another benefit. Design documents can be
mailed through computer networks worldwide. Nowadays, electronic mail facilities are
more and more popular and much cheaper, even faster, than other transmission or
delivery methods. However, only text is usually allowed to be sent. Since we translate a

schematic into text before printing, this restriction is of no effect to our approach.

2.3 Circuit Representation

A well-defined circuit representation method can fully support the development of
CAD systems since it provides a common interface to different tools and users [6] [7] [8]
[9] [15]. The representation method should take circuit hierarchy and conectivity into
account. We adopt the format used in predicate calculus since it meets the requirements

of circuit representation.

2.3.1 Format

The circuit representation methods with predicate calculus format can be classified

into three categories [3]. There are functional, extensional, and definitional methods.

(1 ) Functional Method -— Figure 2—2 shows an example using this method. An out-
put is represented as a function of several inputs. There are two disadvantages to this
technique. One is that only combinational circuits can be represented at the gate level,
the other is every output needs a separate expression. However, a MOS transistor net-
work is difficult to describe with this method since the transistors are bidirectional in the

nature. And, feedback connections are also hard to be represented with this approach.

(2) Extensional Method -- This method represents circuits as modules and connec-

tion statements. An example is shown in Figure 2-3. The first argument in the modules is

16

 

nor(and(A.n0t(B).C).and(n0t(C),D).and(B.D))
Figure 2-2 The functional method.

the function of that module, the second argument is the input variables, the last argument
is the output variables. A connect statement shows a connection between the first argu-
ment and the second argument. This method can be at a higher level than the functional
method and it can accommodate arbitrary types of circuits. But, one disadvantage is that
modules are not represented by a single term with no systax relationship among them. In
other words, wire names are multi-defined. Once again, like the functional method, this
approach can not represent a MOS transistor network since it inherently defines the input

and output attributes in module statements.

(3 ) Definitional Method -- This method is illustrated by an example in Figure 2-4.
Components are described by Horn clauses [4] whose head is the circuit to be defined,
and whose body is a composition of either already defined or primitive components. In
other words, high-level components are much like rules and primitive components are
facts in the Prolog environment [4]. The sequence of components in the body is arbi-

trary, but the sequence of the arguments in the head is fixed.

This kind of hierarchical representation makes modular decomposition a very easy
task. Notice that the internal connections in a circuit are named by variables which do not
appear in the head of the clause. These features make the definitional method more

attractive since it masks low-level details. Thus, both circuit hierarchy and connectivity

17

 

 

 

 

 

 

 

 

 

 

 

prset
1
bL *

\ e Pr -
a o— } I Q ' z
clock‘ > CK
—l>°——K -
c d Tip
clear

component(and,[a,b],[e]).
component(not,[c],[d]). _
component(ikmsff,[J,K,CK,Pr,Cr],[Q,Q]).
connect(and(b),z,jkmsff(Q)).
connect(not(c),and(e),jkmsff(J)).
connect(clock,jkmsff(CK)).
connect(not(d),jkmsff(K)).
connect(clearjkmsff(Cr)).
connect(presetjkmsff(Pr)).

Figure 2-3 The extensional method.

are realized by this definitional method. Moreover, a MOS transistor network can be
represented because this method does not restrict input and output relationships within a
circuit.

The definitional method is chosen to represent digital circuits in our CAD system.
Based on this representation, a generic component model is developed. The design data-

base adopts the model and becomes the kernel of this CAD system.

2.3.2 Generic Component Model

In many cases, a design tool only models one or two aspects of a component. A
complete CAD system has many tools to achieve design automation. The supported data-
base in a CAD system should have the capability of providing a specific tool with all
necessary data. Therefore, a component model must provide all the aspects in order to

satify the needs of different tools. Figure 2-5 shows the abstract idea of a component

18

 

 

 

 

 

 

 

 

 

 

 

—l
:2: 3%.”- y
C; “{>°— ‘1 t4_1__[_ x 6
E >—_]t3TE I > out

 

 

demo(a,b,c,d,out) :- not(out,t5),not(t5,out),and(a,b,t2),
not(c,t1),xor(a,b,t3),nt(t2,t4,t1),
nt(t3,t4,c),nt(out,t4,d).

Figure 2-4 The definitional method.

model. Consistency and hierarchy are the requirements to develop such a generic model.

The definitional method uses the component name to identify a component. Hierar-
chy implies that all the information which concerns the component must be found
through the component name. Connectivity implies that the component communicates
with other components through its input and output nodes which are the arguments in the
component clause. The sequence of the component arguments is important since a
specific node can be identified by knowing its position.

We model a component as a file with well-defined syntax. A component file is
divided into arbitrary sections. Each section is dedicated to one aspect of the component.
Sections are related through the sequence of the input and output nodes. For example, a
schematic edtior may find the graphic symbol of a component from one of the sections in
the component file and obtains the I/O node positions from a section which defines the

I/O attributes.

There is a very special section called the structure section which defines the struc-

ture of a component. In this section, the definitional method is adopted. A component

19

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

I/O nodes
MYOUt /
Structure Symbol

 

 

 

 

 

 

Figure 2-5 The model of a component.

structure is defined by other low-level components. The names of the low-level com-
ponents are the file names which are used to find those components. Only the primitive
components are defined by themselves. Hence, a hierarchical component tree is
inherently formed by the structure section. Notice that the component hierarchy matches
with the design hierarchy. This feature makes the add of a hardware description
language, such as VHDL [16], into the CAD system much easier since the hierarchical

programmability can be made consistent with the design hierarchy [5] [17].

A detailed description of our component model will be disscussed in Chapter 3
since the model is part of the design database.

Chapter 3 Unified Design Database

A typical design process usually is iterative, tentative, and evolutionary. To com-
plete such a complex process, which may involve many design tools, a well-defined data-
base with flexibility and extensibility is very essential for accommodating the different
tools. However, the techniques and systems developed are usually to support business
data processing. Database support for engineering remains to a large extent an open
issue in CAD research because the representing entity for engineering database is much

more complex.

Many endeavors have focused on this issue. Staley and Anderson not only presented
a thorough specification for CAD databases but also gave a good survey in this field [19].

Their specification provides a clear goal for designing an engineering database.

A database to support this CAD system is described in this chapter. We adopt the
relational model [20] as the fundamental database structure. Since there is only one type
of representing entity, this database is called STOCK. Digital components are the entities
in STOCK. The STOCK structure and its operations are discussed in this chapter.

3.1 Database Model

The relational data model in database theory is used to realize STOCK. However,
owing to different requirements, the data model which is applicable to business database

management must be modified in order to build such a design database.

The circuit representation method which was discussed in the previous chapter
guides the STOCK design. The method defines a circuit as a component network. And,
the circuit being defined can be used as another component for other circuits. Based on
this unified point of view, there is only one type of entities in the design database,
namely, the component type. Our design methodology treats any digital circuit as a com-

ponent. Specifically, STOCK only contains one type of data, i.e., circuit components.

20

21

The architecture of STOCK is described by using the entity-relationship diagram,
see Figure 3-1. The rectangle with bold edges represents a typical component entity,
ellipses are the component attributes, and relationships among different components are
represented by diamonds. Currently, each component has at most four attributes, i.e., the
component name, the component structure, the graphic symbol, and the 110 nodes of the
component. The name is used to identify the component in STOCK. The structure attri-
bute describes the interconnection of the component. A component in STOCK is usually
defined by other components except for the primitive components which are defined by

themselves. Hence, the "contains of' relationship is embedded in the structure attribute.

 

Component

w

 

Figure 3-1 The entity-relationship diagram of STOCK.

STOCK is realized as several file directories. The directories in STOCK essentially
have the same structure. There is a special file called "elsewhere" which is used to assist
the automatic searching process. If a component can not be found in the current direc-
tory, this file will be opened and the search will go to the directories which are states in

"elsewhere". This method distributes STOCK among directories which may even reside

22

on different machines. Clearly, the database maintenance problem is also reduced and
localized. In other words, STOCK is a distributed database with unidirectional links. A
typical structure of STOCK is illustrates in Figure 3-2. In the figure, each designer owns
a local stock, several designers which form a group have a group stock, and all the
designers have the right to access the global stock. More sophisticated structure can also

be built by modifying the directory links.

 

 

 

Figure 3-2 A typical structure of STOCK.

In STOCK, a component is realized as a file and each attribute occupies a space
called a "section". We use the term "section" rather than the traditional term "reco "
because attributes have different formats and lengths. From the entity-relationship
diagram in Figure 3-1, there are four attributes which must be modeled. Since a com-
ponent is a file, the name attribute is handled by the operating system. Therefore, a com-
ponent file currently has three sections to store the rest attributes. Figure 3-3 shows the
structure of a typical component file which is divided into several sections. Notice that
the sequence of sections is arbitrary. The section head which contains the section name is

the key for finding the selected section.

23

 

Structure Section

 

I/O Node Section

 

Symbol Section

 

 

 

 

Figure 3-3 The structure of a component file.

The structure section of a component file defines the circuit topology which is the

internal structure of the component. This definition is hierarchical, i.e., other components

at the lower level, not necessarily the lowest level, are used to describe the component. In

other words, a component is defined by other components, except for those at the lowest

level. The components at the lowest level are defined by themselves. Figure 3-4 is an

example of a component which is a J-K master/slave flip flop. The structure of this com-

ponent is defined by several logic gates. These gates are also components in STOCK and

they can be described by themselves or MOS transistors. It depends on whether those

gates are primitive or not. Clearly, this approach utilizes the concept of hypertext [42].

 

nand3(%4,%0,% 1,@0).
nand3(%1,%2,%5,@1).

nand2(@2,@ 6,@4).
nand2(@3,@6,@5).
nand2(@4,%4,%5).
nand2(@5,%5,%4).
not(%l,@6).

 

nand3(%6,@0,@3,@2).
nand3(@2,@ 1,%3,@3).

 

 

 

 

 

 

  

 

 

 

 

 

 

 

 

 

 

%6
T
%0 %5
%lo—T
702: F %4
I\.
V o
%3

Figure 3-4 The structure section of a J -k master/slave flip flop.

The U0 nodes of a component occupy a section which defines the sequence, the

location, and other attributes of input and output nodes. This section takes care of the

24

connectivity problem of a circuit. Therefore, we can say that the I/O nodes are "hot
spots" of a component. A circuit schematic is a network of components which are con-
nected by wires at their 1/O terminals. Or, a layout tool must know those hot spots before

the placement and routing can proceed.

The symbol section is used to portray a graphical representation for a component.
Some drawing commands, such as drawing a line, a rectangular, a circle, and printing
text, are defined. A component’s symbol can be obtained by executing these commands.
Figure 3-5 compares the drawing commands to the symbol of a J-K flip flop. It also

shows the I/O node section of this component.

 

03
12201020
211221
12301030 A
110281330
110321330 Pr.
02201 12401040 —J
12301 21142K
22401 122592252
322581 220490 —>
443400 52291
543200 1222228
62221 22014Pr -—K Q_—-
522511 Cr
143203520 ‘
mamas... 3232395,, ?
23242Q_
410103550

 

 

 

 

 

 

 

 

 

 

 

The symbol section
Figure 3-5 The U0 node and symbol sections of a J-k flip flop.

At this moment, the I/O node section only has a high relationship with the symbol
section. Actually, the graphic locations of I/O nodes are determined by the parameters in
the drawing commands. The reason we duplicate the information is to enhance the
importance of node locations. By explicitly marking the locations, we eliminate a lot of

restrictions in the drawing commands. In other words, the component’s symbol can be

25

anything and it can be easily modified by changing the drawing commands. Moreover,
this arrangement also makes the wiring process in schematic design capture simpler and
more accurate since we need not extract the node locations from the symbol of a com-

ponent.

3.2 Database Operations

According to the above database model, STOCK is a relational model with 4-tuples.
Let R (name, structure, I/O nodes, symbol) be the relation of STOCK, the operations can
be expressed with the relational algebra [20].

The union operation is achieved by adding a new link into the file "elsewhere".
Specifically, let R1 and R 2 be two relations, R =R1 u R 2 will be obtained after the link of
R2 is added into the file "elsewhere" in R 1.

Since most tools are only interested in some aspects of a component, the most fie-
quent operation in STOCK is the combination of selection (0) and projection (1:). For
instance, during the schematic design capture session, n3,4(ol(R )) is executed in order to
obtain the graphic symbol and I/O node locations for a component. And, during the
design flattening process, 1:2(01 (R )) is the operation to discover all the low-level com-

ponents.

In order to integrate new tools, new attributes should be able to be added easily.
The natural join operation is the way to add new attributes. For example, let
S (name,layout) be the relation which represents component layouts. Then, the natural
join of R and S produces a 5-tuple relation, i.e., (name, structure, I/O nodes, symbol, lay-
out). Clearly, the major difficulity in developing a new attribute is chosing its format , not
the database operations themselves. However, several standard formats for layout attri-
butes, such as the CIF and GDS II [23], are very useful if we want to extend the system

into VLSI layout design.

26

3.2.1 Projection

One of the major differences between a business database and an engineering data-
base is the attributes. For a business database, attributes usually contain a small amount
of information, such as a string or a number. However, for an engineering database, an
attribute may be used to model an aspect of a design, such as the layout or graphic sym-
bol. Therefore, the amount of data is both greater and more complicated. The design of
an attribute format is independent on the database operations. Tools which handle some
specific attributes must have the capability to understand the format of attributes. Only
the selection and projection operations are needed to provide the necessary attributes to a
specific tool. In other words, when a tool queries a component, the database manager pro-

jects the necessary attributes from STOCK.

The current attributes in a component file are discussed in this section. Each attri-
bute starts with a "it" character at the beginning of a line. The attribute name follows

after the "it" character. Two names are supported, i.e., a numeric name and an ordinary

name. Comments can also be added at a component file anywhere as long as a . charac-

ter begins a comment line. The following shows a typical component file :

.3-bit synchronous counter
#1 structure
nand3(%4,%0,%1,@0).
nand3(%1,%2,%5,@1).
nand3(%6,@0,@3,@2).
nand3(@2,@1,%3,@3).
nand2(@2,@ 6,@4).
nand2(@3.@6,@5).
nand2(@4,%4,%5).
nand2(@5,%5,%4).
not(% 1,@ 6).

#2 nodes 45 6O

0 2 20 I

1 2 301

2 2 401

3 22 58 I

4 43 40 O

5 43 20 O

6 22 2 I

#3 shape

27

NHMNv—MNv—NHI—HH NHO
thNNNNN—‘NHHN ~th)
AuthgmNO NO
\OONHNOO 2N...
N r-v- 8H9
N we.) R‘ N
U: or O
N 8::

‘NwNO
NNMHNO

reeag
i P

The structure section defines the internal structure of a component. Each line in this
section represents a component at the lower levels, not necessarily at the lowest level,
with a function-like format. The "function" name is the lower-level component name
which can also be found in STOCK. Arguments are used to define I/O terminals of the
lower-level component. Those arguments starting with "%" indicate they are the I/O
nodes of the component file. On the other hand, internal nodes are represented by the
arguments starting with "@". The number in the arguments defines the sequence of
nodes. This mechanism is simple, but powerful, and it is hierarchical in the nature. The
naming technique in arguments provides an easy way to flatten a schematic into a transis-
tor network. The lower-level component name indicate where to find the component in
STOCK during the flattening process.

The 1/0 node section is currently closely related to the shape section currently.
Each line in this section represents an I/O node; the first field in the sequence number; the
second and third fields define the location of a node; and, finally, the rest of the field is

reserved to describe other properties of a node for future extension.

28

The shape section defines drawing commands to make up a component symbol.
Each line in this section is a drawing command. The first field is the command code. The
rest fields are necessary parameters to execute the command. We summarize the avail-

able drawing commands as follows:

COMMANDS FORMAT and DESCRIPTION

dSCALE : 0 scale_factor
define the scale factor for a shape. This must be at the first line.

dLINE: 1 x0 y0 x1 yl
draw a line from (x0,y0) to (x1,y1).

dLABEL : 2 x y label
write the label at (x,y).

dARC: 3hkx0y0x1y1
draw an are at (h,k) from (x0,y0) to (x1,y1) clockwise.

dRECT : 4 x0 y0 x1 yl
draw a rectangular. (x0,y0) is the left-upper comer.
(x1,y1) is the right-lower corner.

dCIRCLE : 5 h k r
draw a circle at (h,k) with radius r.

Although STOCK only provides four attributes at this moment, its extensibility has
already been considered. New attributes can be added without affecting the current attri-
butes by using the natural join operation. Hence, other tools which operate on the current
attributes do not need to be modified. The structure section provides all interconnection
information about a component. Therefore, a lower-level component can be easily
replaced or modified by changing its name or modifying its contents. (For example, this
is very necessary to build a self-testable circuit [21].)

3.2.2 Design Flattening

Usually, a circuit design needs to be "flattened" before some simulation actions can
be taken. This section shows how to flatten a design hierarchy fiom STOCK in order to

facilitate the switch-level simulator in validating the circuit at the transistor level.

29

The whole process is divided into three steps which are shown as follows:
(1) from a schematic to the corresponding circuit network at the design level;
(2) from the circuit network to the corresponding transistor network; and, finally,

(3) from the transistor network to the corresponding network with numeric node

names and a reference table.

Steps (1) and (3) are trivial; so, we skip them. Only Step (2) will be discussed. The
input to Step (2) is a temporary file coming from Step (1) with the following format.
Here, we use an example which is a 3-bit counter to explain the input and output relation-
ship in design flattening.

A circuit netlist at the design level
nor2(ikmsff_0_4,jkmsff_l_4,nor2_3_2).
jikmsff(nor2_3_2,ck,nor2_3_2,crjkmsff_2_4,jkmsff_2_5,vdd).

jikmsfffikmsff_0_5,ckjkmsff_0_5,cr,jkmsff_l_4,jkmsff__1__5,vdd).
jkmsff(vdd,ck,vdd,cr,jkmsff_0_4,jkmsff_0_5,vdd).

 

Step (2) takes the above input and generates the following output which only con-

tains CMOS transistors.

The corresmnding circuit at the transistor level

nt(gnd,t_1_000_6,ck).
nt(gnd,t_2_002_0,vdd).
nt(gnd,t_2_019_0,ck).
pt(vdd,t_1_000_0,ck).
pt(vdd,t_1_000_l,vdd).
nt(t_2_001_1,t_1_000_1,q3).
pt(vdd,t_ 1_000_1 ,q3).
nt(t_2_002_1,t_1_000_2,t_1__000_3).
pt(vdd,t_1_000_2,t_l_000_0).
pt(vdd,t_1_000_2,t_1_000_3).
nt(t_2_003_1,t_1_000_3,cr).

The procedure at Step (2) can obtain the transistor-level description no matter what
level the initial circuit description takes. Actually, this procedure has three parts. The first
part, called discover, translates a circuit network into the next lower-level representation.

The second part, called examtr, examines a network to determine whether it is only com-

posed of transistors or not. The last part, called manager, executes discover several times

30

until the result passes the check provided by examtr. The following is the procedure dis-

cover.

Procedure discover
Input : A circuit network at any level
l(scutput : The corresponding circuit network at the next low level
gin
open Input file for READ;
open Output file for WRITE;
readline called component from Input file;
while (not end_of_file(1nput))
begin
separate component into component name and arguments;
open component_name file from STOCK for READ;
readline called compt_low_level from component_name file;
while (not end_of__file(component_name))
begin
separate compt_low_level into compt_name_low_level and
arguments__low_level;
change_name for arguments_low_level according to arguments;
change_intemal_name for compt Iow_leveI;
writeline called compt_low_leveI_ to Output file;
red’adlrn' e called compt_low_level from component_name file;
en °
close component_name file;
readline called component from Input file;
end;
close Input file;
close Output file;
end.

The above algorithm assumes that a component file in the stock only contains the
structure section to facilitate the description. component_name gives us the place to find
the component. Change_name and change_intemal_name recognize the symbols "%"
and "@". They replace every I/O node by the corresponding name at the higher level.
Internal nodes are renamed with new names which are the combinations of the iteration
times of discover, the line number in the component file, and the sequence of the nodes.

This method guarantees that any internal node is unique after flattening. The followings
is the algorithm for the second part.

Procedure examtr
Input : A circuit network at any level
Output : Yes/No
begin
open Input file for READ;
readline called component from Input file;

31

while (not end_of_file(1nput))
bcgin
separate component into component_name and arguments;
If (component_name not equal to (pt or nt)) return(No);
readline called component from Input file;
end;
return(Yes);
end.

In the above algorithm, pt and nt are PMOS and NMOS transistors. Currently, they
are the primitive components in STOCK.

procedure manager
Input : A circuit network at any level
Output : The corresponding transistor network
begin
copy Input file to temp] file;
create temp2 file;
repeat forever
begin
set input of discover to temp] ;
set output of discover to temp2;
execute discover;
set input of examtr to temp2;
execute examtr;
if (return(examtr) equal to Yes) break];
set input of discover to temp2;
set output of discover to temp] ;
execute examtr;
if (return(examtr) equal to Yes) break2;
end;
break]:
begin
copy temp2 file to Output file;
return;
end;
break2;
begin
copy temp] file to Output file;
return;
end;
end.

Procedure manager executes discover and then it uses examtr to decide the execu-
tion flow of the flattening procedure. The corresponding transistor network is generated

after the execution of the above algorithms.

Chapter 4 Graphical Approach To Design Capture

This chapter discusses the approach adopted to build a universal schematic editor
(USE) with friendly graphical interface. This tool is developed based on the important

features of a circuit design, i.e., connectivity and hierarchy.

USE allows the designer to express a digital circuit at the same level that he/she
thinks. The hierarchy information of a circuit is canied in STOCK. The output from
USE is a high-level circuit description (netlist) which states the connectivity of a circuit
design. Based on the generated netlist, a new component can be created. And down-
stream work, such as implementation and/or verification, can be carried out. Moreover,
USE is technology independent. It merely takes care of the component hierarchy and
connectivity. The implementation or verification issues of a design are left for other
tools. Hence, USE can easily cooperate with different kinds of implementation or

verification tools through the use of a component database.

4.1 Overview

Before USE is discussed, we need to define the netlist of a circuit. A netlist is the
representation of a component network. It canies all the information at the design level.
In other words, the design endeavor during the creation phase is to generate such a not-
list. Then, in the simulation or verification phase, the design effort is to modify the gen-
erated netlist in order to compliance with design specifications. Therefore, a design cap-
ture tool should possess a way to generate and modify a netlist with interactive visualiza-

tion of a design.
Definition 4-1 (Netlist) : A netlist is used to represent a circuit design with the fol-
lowing format:
C1011, t 12. I 13» ---)~

C 2021. 122. 123. ...).
C3031, ‘32, ‘33, ...).

32

33

Where C;,i >0, are the names of the components, and ti; , j >0, are the 1/0 nodes of C5.
All lower-level information which concerns of the components can be found in STOCK.

The connection relationship among different nodes is represented by an identical name.

Based on this definition, a design process can be expressed as the work to create and
modify such a netlist. To facilitate the work with interactive visualization, the graphics
approach to design capture is preferred at structural level [23]. Figure 4-1 shows the edit-
ing process in USE. In order to create a human readable circuit schematic and obtain the

netlist, a typical procedure is as follows:

(1) The designer acquires the necessary components from the stock. Then, he/she

puts the components at the desirable places on the screen.

(2) The designer connects all the components to form a circuit. The appearance of
wires are specified by the designer to increase the clearity for future
modification.

(3) The designer marks some important nodes by giving them names. The timing

of these nodes then can be observed later.
(4) A circuit schematic can be saved and loaded during the editing process.

(5) A design can be modified by adding or deleting components and drawing or

erasing wires. It also can be packed and becomes a new component.

There are only two kinds of objects in USE, i.e., wires and components. However,
since a schematic can become a component, USE can be used to create a circuit design at
any structural level from the primitive level, e. g., transistors, resistors, and capacitors.
The data strutures which can represent any shape of wires and components is described
in the next section. Based on the structures, tasks for wiring and component editing are

analyzed and developed.

34

 

 

 

 

 

 

 

 

 

 

 

 

CIRCUIT .
STOCK SCHEMATIC SChcmanc
files
\J V
Component Editing

Figure 4-1 The editing process of a circuit schematic.

4.2 Data Structures

A circuit schematic is a two-dimensional diagram of variable size. The components
can have all kinds of shapes. And wires have different lengths and can extend to every-
where just like a spider web. Figure 4-2 shows a typical circuit schematic. Since the data
size is varying from one schematic to another, run-time memory allocation is a must and
linked lists to represent components and wires are necessary. Based on the data structures
discussed in this section, USE can easily and quickly draw any kind of circuit schemat-

ics.

Circuit Components

From a component point of view, USE is an interpreter which translates a set of
primitive drawing commands into a graphic symbol on the screen. The drawing com-
mands are defined in STOCK as a component attribute. USE also needs to know the I/O

node locations in order to connect them. This information also can be found in STOCK.

35

0111

 

Figure 4-2 A typical circuit schematic.

In order to speed up the graphic operations, such as zoom, pan, and redraw, the
drawing commands for all the same components are interpreted at most only once. The
images of different components are saved and the fastest graphic operation, i.e., map-
ping, is used. In other words, the major graphic operations in USE are line drawing and
memory mapping. Clearly, the speed is very high even on a small personal computer.

The components form a linked list with each element representing one component.
Each element stores all the information of this particular component, including the loca—
tion, the range, the label, the name, the drawing commands, and its I/O node information.
The 1/0 nodes of a component form a linked list which is part of the component data
structure. The images of the components also form a linked list. The component name is
the key to match an image with a selected component. This approach which let many
components share an image can reduce the run-time memory size significantly. Since two
components in STOCK may have the same circuit structure but different graphic symbol,

this approach does not put any limitation on drawings.

36

Wires

A "wire" is the object used to connect components. Those connections should be
qualified from the designer’s point of view. In the logic design level, wires carry only the
information of connections. Other attributes, such as the dimensions and the materials,
are not considered. In other words, we model a wire as an object which provides the con-
nectivity among components to the designer. In order to create a designer-acceptable
schematic, two types of wires are necessary, i.e., T-type and J-type wires. Any shape of a
wire, no matter how complex it is, can be represented with these two types. A T-type
wire is used to establish the first connection between two nodes. Then, J-type wires are
used to connect a wire, which is a T-type or J-type, to other nodes. In other words, the
terminals of a T-type wire are some [[0 nodes of components. And, for a .l-type wire,
one terrrrinal is an I/O node and the other terminal is on a T-type or J-type wire. Figure
4-3 gives an example, where node 1 to node 5 are connected together by a wire bundle. A
"wire bundle" is the name we used to describe a wire with arbitrary shape. After the
designer makes the connections, there is no need to distinguish which is the T-type wire
and which are the .l-type wires. Of course, from the designer’s point of view, the distinc—
tion is not necessary at all as long as a wire bundle has been formed. A reasonable data
structure is developed to maintain the connection relationship among nodes. Some obvi-
ous maintenance tasks are creating and deleting a wire bundle and disjoining a node from
a wire bundle. The wire model with two different types has the advantage that it makes
the internal data structure unified and simplifies the algorithm development.

A wire, either T-type or J-type, is formed by one or more line segments. A corner is
the point where two line segments join with an arbitrary-degree angle. Certainly, 0, 45,
and 90 degrees are commonly used in drawing a circuit schematic. A wire bundle also
has a name used to identify it in order to search the corresponding data structure and then

the maintenance tasks can be performed.

Based on the above description, a wire is specified by its name, type, terminals, and

37

N1:

 

3.” 3

 

 

 

___°N2

 

it
N5

Figure 4-3 A typical wire bundle.

the comer locations. The joined degree of a corner is implicitly carried by the comer’s
location. A complex linked list is developed to represent wires. T-type and J-type wires
are so similiar that the same data structure is used. Figure 4-4 and 4-5 illustrate our
approach. In this figure, N represents a node, C represents a comer, and J represents a
joint on the wire. Figure 4-4 says the wire bundle has a T-type wire and three J-type
wires. The T-type wire, which has two corners, connects node N1 and N 2. One J—type
wire connects node N3 and joint J 1, another J -type wire connects node N4 and joint 12,
and the last .I-type wire connects node N 5 and joint 13. Hence, node N1, N 2, N 3, N4, and
N 5 are connected together by this wire bundle. Joint 11, 12, and J3 must be on the wire in
other to show the conductivity of these nodes. The wire bundle which is represented in
Figure 4-4 is shown in Figure 4-3.

Moreover, a hash table is used to increase the searching speed among all the wires.
This table provides a link to some position of the wire list. The wire name decides the

hash function. Hence, a wire is easy to find by its name.

4.3 Tasks

The design caputure process in USE is divided into three major tasks. There are
component editing, wiring, and graphic issues. The first task deals with component crea-

tion, deletion, name assignment, etc. Wiring task deals with the creation and modification

38

 

—-lmj ~11 [~21 tL+Wwi~M°

 

 

Cl l-l’rlthsLtl-l
l \

C2

 

1'1121 I [M] \11
’ L-J’slilWItJ-l

 

Figure 4-4 The data structure of a wire bundle.

of wire bundles. And, the last task makes USE friendly to use with vividly high-speed
graphic operations.

Most of the algorithms which implement the commands in USE are trivial if the
data structure is known. Therefore, only those with more significant meaning are dis-

cussed.

Node Disconnection

Modification of a schematic is the major activity during a circuit design. The kernel
portion of this modification is to disconnect a selected node from its wire bundle. For
example, to delete a component, all of its I/O nodes must be disconnected from the wires
which connect to the component. And, this action must not affect the connectivity of
other components. Since a wire bundle may be very complex in a large circuit schematic,

the method to disconnect a node from a wire bundle needs to be carefully analyzed.

From the definition of the wire model, a connected node can only be at three posi-
tions, i.e., the start point of a T-type wire, the end point of a T-type wire, and the end
point of a J—type wire. Let us call the start point of a T-type wire t(x0,y0), the end point
of a T-type wire t(xn,yn), and the end point of a J-type wire j(xn,yn). Therefore, we can
call the start point of a J-type wire j(x0,y0). Also, it is clear that the disjoined position
must be at the beginning of some J-type wire. We call it dj(x0,y0) which is the nearest

39

joint to the disconnecting node along the wire bundle. After these definitions, we find that
the wire from the node which needs to be disconnected to the disjoined position only has
four possibilities :

(1) Part of a T-type wire from t(x0,y0) to dj(x0,y0);

(2) Part of a T-type wire from t(xn,yn) to dj(x0,y0);
(3) Part of a J-type wire from j(xn,yn) to dj(x0,y0);
(4) A complete J -type wire from j(xn,yn) to j(x0,y0).

Condition (4) is the simplest. We only need to take care of a .1 -type wire which has a
complete data structure. For other conditions, this function not only needs to delete the
unwanted piece of the wire but also needs to merge the J-type wire which starts from
dj(x0,y0) into the rest part of the wire. Let us call the wire which contains the unwanted
piece wire] and the wire starting from dj (x0,y0) wire2. Then, we can rewrite the above
conditions into more executable forms:

(1) Wire2 is reversed and merged into the rest of wire]. So, dj(x0,y0) becomes a

corner and j(xn,yn) of wire2 becomes the starting point of wire].

(2) Wire2 is merged into the rest of wire]. So, dj(x0,y0) becomes a corner and
j(xn,yn) of wireZ becomes the end point of wire].

(3) Same as condition (2).

(4) Wire2 is null. Hence, the whole wire] needs to be deleted.

The reason why wire2 in (1) needs to be reversed is to meet the definition of wire
structures. With the above analysis, no matter how complex a wire bundle is, any node

can be disconnected efficiently.

Joint Verification

To create a J-type wire, the joint which is the starting point of the wire must be
specified along a wire bundle. This specification must be verified to ensure the conduc-

tion property of a wire bundle. Hence, the connectivity of components is obtained. For

40

example, when the designer needs to connect a J -type wire, the first thing he/she needs to
do is choose a node which has already been connected to some other nodes by a wire
bundle. Then, hc/she can make a connection from any place on the wire bundle to the
desirable node. A J -type wire represents such a connection. In other words, the starting
point of a J-type wire may be anywhere as long as this point is on the correct wire bun-
dle. This operation needs to be confirmed in order to create a readable schematic and
correct netlist. Since the wire model is a composition of many segments of lines, this
checking is hierarchical. We check a wire bundle by checking each wire that belongs to
the wire bundle and examine a wire by checking every segment which makes up the

wire. To check a point whether it is on a segment, we use the following approach:

(x.y)

 

c ‘ (x1,y1)

0
(x0.y0)

Figure 4-5 Joint Verification.
In Figure 4-5, a is the length of the segment; b is the distance between (x0,y0) and

(x,y); c is the distance between (x1,y1) and (x,y). And, the angle 0 can be obtained by

the equation:

2
9 = COS—1( 01"ch )
Then, the distance from the point to the segment is

h =bsin0

After obtaining h , we can decide whether (x,y) is on the segment or not.

41

It is worth noting that this method is independent on the slope of the segment. Slope
can not be used to implement this verification because the slope of a segment ranges
from negative infinity to positive infinity. Hence, comparison with slopes can not give a
satisfied solution. On the contrary, the method is universal for any kind of line segments.
Actually, the above description is not completed. We also need to decide whether (x,y) is
in the range of the segment, i.e., x is between x0 and x1, and y is between yo and yl,

before the above calculation can be performed.

Projecting function

USE does not put any limitation of the circuit size. Idealy, any size of circuit
schematic can be created. In other words, the canvas to draw a schematic has no size
limit. However, the only limitation is the capability of integer representation in the com-
puter. For a 32-bit machine, the canvas size is (232—1)x(232—1) which is large enough to
store any kind of circuit diagrams. Since the canvas is infinite, a projecting function must

exist to map part of the canvas onto the graphic window.

Actually, the canvas does not exist. The data structure which represents a schematic
is generated by projecting the coordinates on the graphic window onto the corresponding
coordinates on the "virtual canvas". Therefore, all graphic operations operate according
to the projecting function. The zoom operation is usually achieved by changing the zoom
factor and the pan operation is achieved by changing the displacement. However, since
there is no center point in an un-completed schematic, the zoom operation can move the
schematic far away from the graphic window. In order to zoom a schematic without
affecting its position on the graphic window, a displacement is needed before changing

the zoom scale.
Let (Rx, R,) be the coordinate on the virtual canvas and (W,, W,) be the
corresponding coordinate on the graphic window. The projecting function f is expressed

as follows:

Where Z is the zoom factor. (D 1,, D 1,) and (D2,, 02’) are two displacement values, one
is before and the other is after the zoom operation.
The reverse projecting function f '1 is easy to derive from f . f ‘1 is as follows:
W, = (R,+D1,)Z +D2,; Wy = (Ry-+0 1,)Z +D2,.
The projecting function provides a powerful mechanism which maps the internal
data structure onto the graphic window which has a limited size and vice versa. As a
result, the virtual canvas is almost infinite and schematics with arbitrary sizes can be

created.

Chapter 5 Logic-Timing Simulation at Transistor-Switch Level

A switch-level logic-timing simulator with linear-time computational complexity
called SWSIM is described in this chapter. MOS transistors are modeled as bidirectional
switch-attenuators with ideal capacitors associated with the gate terminals. The simulat-
ing circuit is represented as a composite graph which consists of a set of node connected
by transistor edges. During simulation, each transistor has a state (ON, l/20N, or OFF),
and each node has a logic value and strength. The strength is used to establish the
signal-flow direction during the simulation run. We developed a linear-time algorithm to
evaluate the node strength. This technique ensures that the simulation of bidirectional

transistors can be easily handled at the logic level.

5.1 Overview

Recent years, CMOS technology has boosted the development of Application-
Specific Integrated Circuits (ASICs). Digital circuit design at the gate level has no
longer met the requirements of designing an ASIC chip. The cost of fabricating ASIC
chips is dominated by the silicon area occupied by the chips. It has been shown that such
chips can have better performance and use less silicon area if they are implemented at the
MOS transistor level. A typical example is the cache comparator design at MC68030
[35]. The designers implemented a series of exclusive-OR (XOR) gates for address com-
parison in an elegant way. This circuit was designed at the transistor level. If those gates
were designed at the gate level, it would have cost much more area and had a lower
operating speed.

Since a chip is designed at the transistor level, logic simulation at the same level
becomes very essential to obtain accurate logic behavior of the chip. Hence, switch-level

simulation for MOS circuits plays an important role in the field of digital ASIC design.

43

44

However, the bidirectional characteristic of MOS transistors deters the application
of logic simulation theory at the transistor level. As a result, some researchers, such as
Bryant [24], Schaefer [34], and Lengauer and Na' her [25], applied a circuit simulation
technique which is used for obtaining the analog behavior of a circuit into a discrete set
of data to obtain the digital behavior at the logic level. In Bryant’s model, a wire is
modeled as an input node or a storage node with different sizes to represent the effect of
their relative capacitances in charge sharing. Transistors are modeled with different
strengths and three states, i.e., open, closed, and indeterminate states. The different sizes
of nodes can confuse a circuit designer since no capacitors appear in the circuit diagram.
Thus, the simulation may be wrong if the simulator generates error node sizes. This may
happen if a design has not been translated into a layout. In other words, this model forces
designers to take care of the analog world while doing pure digital design at the transistor
level. Inevitably, his model is quite different from that in the designer’s mind. Moreover,
the transistor states in his model are not sufficient even though transistors can have dif-
ferent strengths. For example, using an NMOS transistor in the closed state to pass VDD,
the result is degraded by the threshold voltage, but PMOS transistors do not decrease the
voltage. Therefore, in a closed state, both PMOS and NMOS transistors should produce
different results when they pass VDD even though they have the same strength. This
example also implies that the node states in Bryant’s model, which represent low, high,

and invalid voltages, are insufficient to characterize a digital circuit.

Besides the above problems, the simulator based on his model, called MOSSIM II,
can not handle inputs with random timing and can not simulate self-oscillating circuits.
(MOSSIM II was designed primarily for simulating clocked systems.) Even for some cir-
cuits, such as the XOR gate in Figure 5-1., it can not be simulated correctly. (But, his

newest version of the simulator can handle this gate.)

In Schaefer’s model, a transistor is modeled as a resistor and a non-input node is

modeled as a capacitor. Apparently, Schaefer simplified the transistor model in the ana-

45

 

 

 

vdd
0
W A- ’ p
A H r—0 OUT

 

 

 

—'| t: ‘L—I ntl HQ
ntO

 

 

 

 

 

 

 

Bc g
gnd

Figure 5-1 A two-input XOR gate.

log world in order to obtain faster simulation speed in circuit simulation. Therefore, the
performance of his simulator is not comparable to the logic simulators even though the

results are the same.

Since Bryant and Schaefer both applied circuit simulation techniques for switch—
level simulation, their simulators are circuit-topology dependent and do not have linear-
time complexity. This makes the use of switch-level simulations less attractive for large
circuits.

However, SWSIM overcomes the difficulty of modeling bidirectional MOS transis-
tors in the logic level. It is a pure logic simulator at the transistor level. Moreover, to
prevent the NP-complete problem which occurs in the ternary logic simulation [26],
SWSIM does not use any "valid but unknown" logic value. Hence, SWSIM obeys the
law of Excluded Middle. This is because a prediction is made during initialization to get
rid of any unknown logic value. For example, a latch in a circuit whose value can not be
decided by the circuit input, such as a reset, may have either 1 or 0, but not unknown,
after initialization. This prediction method correctly represents the power-on sequence of

a circuit. As a result, SWSIM achieves the following goals:

46

(1) The computational complexity is linear with respect to the number of transis-

tors for each simulation step.

(2) The signal-flow determination algorithm makes the simulation of bidirectional
MOS transistors possible at the logic level.

(3) There is no restriction for input timing and circuit topology. Hence, any
CMOS logic family and self-oscillating circuits can be simulated correctly.

(4) The transistor models predict sufficiently well the digital logic behavior of

MOS transistors.
(5) The law of Excluded Middle is obeyed. No NP-complete problem occurs.

(6) The simulation speed is very fast. Hence, it is suitable for simulating an entire

chip with more than 10,000 transistors.
In this chapter we first describe the circuit model and digital behavior of transistors.
Next, the theory of signal-flow determination in digital CMOS circuits is stated. Then,
the simulation theory is presented. Finally, the performance analysis and some key exam-

ples are given.

5.2 Circuit Model

This section describes the simulation domain of SWSIM. In this domain, only the
digital behavior of CMOS circuits is concerned and modeled. We want to provide a
well-defined area for circuit designers. In this area, we prove that SWSIM can simulate
circuits well.

Definition 5-2-1 (Simulation domain) : The simulation domain of SWSIM is digi-
tal CMOS circuits which are composed of only MOS enhancement-mode transistors.
Each NMOS (PMOS) transistor virtually has the same behavior.

Clearly, there is no circuit-topology restriction in Definition 5-2-1. Next, we define

the meaning of logic values in SWSIM.

47

Definition 5-2-2 (Logic value) : Logic values are used to represent voltages in real
circuits. Logic value 1 represents voltages from VDD —V1 to VDD , where VT is the
threshold voltage of MOS transistors. And, logic value 0 represents voltages from GND
to VT. Finally, the logic value x is used to represent the high-impedance condition or vol-
tage value between VDD —VT and VT .

Based on this definition, we say that logic 1 is a ’perfect 1’ or ’poor 1’, and logic 0
is a ’perfect 0’ or ’poor 0’. (A ’poor 1’ corresponds to a voltage which approaches
VDD -VT, and a ’poor 0’ corresponds to a voltage approaching VT [10].) Let r0, r1, p0,
and pl represent ’perfect 0’, ’perfect 1’, ’poor 0’, and ’poor 1’, respectively. Hence, logic
0 and l are external logic values which will be viewed in the output timing waveforrrr,

and r0, r1, p0, pl are internal logic values which SWSIM uses. X is used in both ways.

One interesting property of CMOS circuits is that many circuits utilize the gate
capacitor for proper operation. We model these gate terminals as storage nodes which
retain their values in the absence of inputs. This technique provides an ideal model for
dynanric storage.

Definition 5-2-3 (Gate capacitor effect) : The gate capacitor of MOS transistors is
an ideal capacitor, i.e., there is no leaking current during simulation time. As a result, a
logic I or logic. 0 can be stored at the gate of a transistor during a time period if and only
if this gate is isolated during the period.

According to this definition, we introduce four other internal logic values ,i.e., x0,
x1, xp0, xpl. The leading character it implies they are high impedance. Therefore, x0
means the node is high impedance and stores an r0; xpl means the node is high
impedance and stores a p1; etc. These high-impedance states are reported in the timing
waveform as the logic value x which appears between 1 and 0. Altogether, SWSIM has
nine internal logic values and three external logic values, as shown in Table 5-1. This
distinction is essential for generating easily readable timing waveforms without losing

any serious information. Now, we define the MOS transistor models based on these logic

48

values.

 

 

 

 

 

 

 

 

 

Voltage level Internal logic External logj;

VDD r1

VDD-VT pl 1

High-impedance or

voltage between thresholds x, x0, xp0, XI’ xpl x
V 90

T 0
GND r0

 

 

Table 5-1 The logic representation of voltage values.

Definition 5-2-4 (P-switch) : A P-switch is used to model a PMOS enhancement-
mode transistor. A P-switch is a perfect switch to pass logic 1 and a poor switch to pass
logic 0. The gate terminal is a storage node. The switch is ON if the value of the gate ter-
minal is r0 or x0 , and it is 1/20N if the gate terminal has a p0 or xp0. If the gate termi-
nal has a value r1, pl, x1, xpl, or x, then the P-switch is OFF.

Definition 5-2-5 (N-switch) : An N-switch is used to model an NMOS
enhancement-mode transistor. An N-switch is a perfect switch to pass logic 0 and a poor
switch to pass logic 1. The gate terminal is a storage node. The switch is ON if the value
of gate terminal is r1 or x1 , and it is l/ZON if the gate terminal has a pl or xpl. If the
gate terminal has a value r0, p0, x0, xpo, or x, then the N-switch is OFF.

When an NMOS (PMOS) is l/ZON, it can pass an r0 or p0 (r1 or p1), but not rl or
pl (r0 or p0). This situation models transistors as attenuators which degrade the signal

voltage with an amount of VT. Table 5-2 (5-3) states the NMOS (PMOS) transistor
model based on the above definitions.

Definition 5-2-6 (Short-circuit effect) : If a node has r1 and r0 at the same time
instant, r0 is assigned to this node. In general, the priority of assignment is r0 > rl > p0
> pl > x. And xp0, xpl, x0, and x1 are treated as x.

49

 

 

 

 

Transistor State ON 1 ON OFF
Input value Value passed

r0 r0 10 x
r1 p1 x x
p0 P0 90 x
pl p1 x x

x x x x
x0 x x x
x1 x x x
xpO x x x
xpl x x x

 

Table 5-2 The NMOS enhancement-mode transistor model.

 

 

Transistor state ON IQON OFF .
Input value Value passed

r1 r1 r1 x
10 p0 x x
p1 p1 p1 x
PO P0 X X

x x x x
x0 x x x
x1 x x x
xpO x x x
ml x x x

 

 

 

 

Table 5-3 The PMOS enhancement-mode transistor model.

This definition represents the short-circuit effect. Whenever there is a conducting
path (resistance = 0) from GND to a node, the node value is always 0. This is true in the
circuit theory. However, many logic simulators do not use this fact. Instead, they use a
third value to represent this situation and claim the node has unknown value. Thus, an
NP-complete problem occurs [26]. Since SWSIM deals with MOS transistors, many real-
istic properties of the elements are considered and adopted to avoid problems which can
not happen is the real circuits. SWSIM ensures that a circuit which is built according to

the definitions can be simulated correctly.

5.3 Signal-Flow Determination

To achieve this linear-time logic simulation at the transistor- switch level, determin-
ing the signal flow through transistors is an essential task. Some timing analysis pro-
grams, such as Crystal [27] and TV [28], require flow analysis first. Clocksin and Leeser
[29] presented a method for automatically determination of signal flow. Their method
only provides statistical analysis of the signal flow without considering the inputs. Thus,
they label many transistors bidirectional even though they are not. In other words, their
method only ensures the labeling of unidirectional transistors. Any transistor in which the
signal flow can not be decided are labeled bidirectional. We introduce a method of
dynamically determining the signal flow at each simulation step based on the current cir-
cuit condition. Thus, the signal flow of a given transistor may have different directions at
different simulation steps. Moreover, the determination must be fast, otherwise the simu-

lation performance will be seriously degraded.

To accomplish this, we give every node in a circuit a new attribute called strength.
It can be thought of as a driving force and the difference of the forces between a transis-
tor channel decides the signal-flow direction. We use a technique which is very similar to
the depth-first search in the graph theory [30] for evaluating the strength of the nodes. If
the source and drain node of a transistor have the same strength, the signal-flow direction
is decided by the node values. Hence, we say the signal-flow direction of a transistor is a
function of four arguments, i.e., the strength and the values of the non-gate nodes. Before
defining the transistor graph, we define the strength in all input nodes. Here, we treat the

power lines, VDD and GND, as input nodes for unifying descriptions.

Definition 5-3-1 (Input-node strength) : For any input node at a time instant, the
strength of this node is fixed and defined as the node value a if a 6 {r0, r1, p0, pl}.
Otherwise, the strength of the input node is x.

Since strength is defined according to the input-node values, the strength of a node

also agrees with the short-circuit effect. This is to say if a node has been assigned two

51

different kinds of strength, the stronger strength will dominate the node.

Definition 5-3—2 (Transistor graph): A CMOS transistor circuit is a composite
graph G (V, E), where V is the set of all nodes and E is the set of all transistor channels
between the non-gate terminals. The gate terminal of a transistor is not only a node but
also a label for this transistor edge.

As an example, Figure 5-2 is the graph of the circuit in Figure 5-1. In this graph,
every transistor is represented as an edge and the edge label. Hence, this transistor net-
work forms a composite graph which is represented by three sub—graphs as shown in Fig-

ure 5-2.

vdd A

A_ OUT 13¢ our

and A-
Figure 5-2 The graph representation of the circuit in Figure 5-1.

Clearly, given a graph G (V, E), we can divide it into two graphs based on the
transistor type. So, we have the following lemma:

Lemma 5-3-1 (P-graph and N-graph) : A transistor graph G (V, E) is the union of
a P-graph, GP (VP ,Ep ), and an N-graph, G, (VmEn ), where Ep (En) is the set of all
PMOS(NMOS) transistors.

Proof : The proof follows directly since the primitives are only PMOS and NMOS

transistors. C]

It is the first level in the hierarchy to distinguish a general transistor graph G (V, E).
Clearly, extracting GP (6,.) from G is the same as separating Ep (En) from E since E, n

5,, =e.

52

During simulation, each node has a strength at each time instant, and a transistor
state is decided by the value in its gate node. According to Tables 5-2 and 5-3, a transis-
tor graph can be further divided into 5 intrinsic graphs. This is the second level of the
hierarchy. For example, an intrinsic graph G,o(V,o,E, 0) is a graph where V,o is the node
set with strength r0 and E,o is a set of transistors which can merely pass r0. Clearly,
Em (E, 1) can not contain a PMOS (NMOS) transistor.

Proposition 5-3-1 (Intrinsic graph) : A transistor graph G (V ,E) is divided into
five inn’iHSiC graphs. They are Gro(VroEr0). Gr1(VrlrErl), Gp0(Vp0.Ep0). Gp1(Vp1.Epr).
and G, (VJr ,EJr ). Let a 6 {r0, r1, p0, pl, x]; then, Ga (Va ,Ea) is an intrinsic graph for a .
Every node belonging to Va has a strength a and every transistor in Ea has a state which
can pass a.

Proof : We can find an intrinsic graph 0,, (Va ,Ea) by searching from all the input
nodes with strength a . If a transistor can pass a , we collect it in Ea and put its non-gate
terminals in Va . If a transistor decreases the strength by the threshold value, we put the
node which has the weak strength in the input-node list for other searches. So, Ga is
formed after the search is done. And, since p0 (pl) strength can be generated from r0
(r1) through a PMOS (NMOS) transistor but a p0 (pl) can not generate a r0 (r1) strength
during a search. It is essential that the process starts by finding 0,0, then G”. In other
words, the search should start from the input nodes with stronger strength, since it may

generate poor strength for some nodes. C]

Figure 5-3 shows the hierarchy of a general transistor graph. Note that the intrinsic
graphs may overlap each other. And a node may belong to more than one node sets.

However, the strongest strength wins the competition for the final value.

The search for finding the intrinsic graphs implies that the strength of all nodes can
be found after the short-circuit effect is applied to decide the final strength of the nodes.

Hence, the short-circuit effect decides not only the node value during simulation but also

53

63.09%
u_°;

 

9
O

 

 

C399
““0

Figure 5-3 The graph hierarchy of a general transistor graph.

the node strength during signal-flow determination. It is a very important feature in

SWSIM.

Proposition 5-3-2 (Strength competition) : Given a non-input node N and two dif-
ferent intrinsic graphs, Ga (Va,Ea) and G, (Vb,Eb ), let N 6 Va n Vb. If a > b, then b
has no effect on the strength of N .

Proof .' Clearly, this property coincides with the short-circuit effect described ear-
lier. If node N only appears in Va and Vb , the strength is a because a has a stronger
strength. However, if node N is also contained in other intrinsic graphs, the current

strength a still needs to compete with others. Cl

Proposition 5-3-1 and 5-3-2 give a method of finding the strength of all nodes in a
general transistor graph. Note that the strength of the input nodes can not be changed in
any condition. Based on the strength information, the signal-flow direction of a transistor

is decided as follows:

54

Definition 5-3-3 (Signal-flow determination) : The signal-flow direction of a non-
OFF transistor is decided by four parameters. They are the strengths and values of the
non-gate nodes. Let the transistor have two non-gate terminals, T1 and T 2, S() be the
strength, and V0 be the value of its argument which is a node. Table 5-4 lists the deter-

mination.

 

 

Condition direction
S(T1) >S(T2) T1—)T2
S(T1)<S(T2) Tlt—Tz

S (T1)=S(T2)=V (T1)=V (T2) T1 (--> T2
5 (Tr)=S (T2)=V (T1)¢V (T2) T1 -> T2
S (T1)=S(T2)=V(T2)¢V(Tr) T1 <- T2

 

 

 

Table 5-4 Signal-flow determination of a non-OFF transistor.
(Conditions at higher columns have higher priority.)

The above definition is obtained based on circuit theory. For other conditions which
did not list in Table 5-4, the values at T1 and T2 become x at the next simulation step

since the previous values are not supported by their strength.

5.3.1 Strength Determination Algorithm

In the above section, we translated the problem of signal-flow determination into a
strength evaluation problem. The strength evaluation problem can be solved by finding
those intrinsic graphs and applying the short circuit effect. Here, we present an algorithm
describing the process and prove that it is of linear-time complexity with respect to the
number of transistors in the graph.

This algorithm called the Strength-Determination Algorithm (SDA) is divided into
five parts. It finds all the intrinsic graphs and solves the competition of node strength at
the same time. The input to this algorithm is a general transistor graph and all nodes have

their values at some time instant. The output is the strength information of all nodes in

the graph.

55

It is reasonable that we assume the input values are members of {r0, r1, it} before

we start to describe this algorithm. The SDA is as follows :

(1)
(2)

(3)
(4)

(5)
(6)

Strength-Determination Algorithm

Set the strength of all nodes 1!.

Let T be an input node with value r0. Execute the procedure
decide_r0_strength( T ).

Repeat (2) until all input nodes with value r0 have been used.

Let T be an input node with value r1. Execute the procedure
decide_r] _strength( T ).

Repeat (4) until all input nodes with value r1 have been used.

Exit.

Since we restrict the input values, the strength p0 (pl) is only generated by PMOS

(NMOS) transistors if they pass r0 (r1). Therefore, decide_r0_strength() will invoke

decide _p0_strength( ) if the condition mentioned above happens. The following are the

procedures which really decide the node strength.

(1)

(2)
(3)

(1)

(2)
(3)

(1)

decide_r0_strength (T 1)
Let T 2 be a non-input node and connected to T1 with a transistor edge Tr. If
Tr e G", its state is ON or l/ZON, and S (T2) < r0, then let S (T2) = r0 and
execute decide_r0_strength(T2).
If Tr 6 GP, its state is ON, and S(T2) < p0, then let S(T2) = p0 and execute
decide _p0_strength( T 2).
Repeat from (1) to (2) until all transistors with one non-gate terminal con-
nected to T1 have been visited.

decide _p0_strength(T 1)
Let T2 be a non-input node and connected to T 1 with a transistor edge Tr. If
Tr e G", its state is ON or 1/20N, and S (T2) < p0, then let S (T2) = p0 and
execute decide _pO_strength( T 2).
If Tr 6 GF , its state is ON, and S (T2) < p0, then let S (T2) = p0 and execute
decide _pO_strength( T2).
Repeat from (1) to (2) until all transistors with one non-gate terminal con-
nected to T1 have been visited.

decide_rl_strength (T 1)

Let T2 be a non-input node and connected to T1 with a transistor edge Tr. If
Tr 6 GP, its state is ON or l/20N, and S (T2) < r1, then let S (T2) = r1 and
execute decide_r]_strength(Tz).

56

(2) If Tr e G... its state is ON, and S (T2) < pl, then let S (T2) = pl and execute
decide _p] _strength(T 2).

(3) Repeat from (1) to (2) until all transistors with one non-gate terminal con-
nected to T 1 have been visited.

decide _pl_strength(T 1)

(1) Let T2 be a non-input node and connected to T1 with a transistor edge Tr. If
Tr e G , its state is ON or 1/ZON, and S(T2) < pl, then let S (T2) = pl and
execute decide _p] _strength(T2).

(2) If Tr e G", its state is ON, and S (T2) < pl, then let S (T2) = pl and execute
decide _p] _strength(T 2).

(3) Repeat from (1) to (2) until all transistors with one non-gate terminal con-
nected to T1 have been visited.

The above procedures are very similiar to each other with the principal differences
among them being the transistor types and states. Clearly, they all have the same compu-
tational complexity. After the strength of all nodes is obtained, the signal-flow direction
is determined by applying Definition 5-3-3. Then the simulation theory, which will be
discussed in the next section, can be applied to the transistor network. Next, we prove
the time complexity of the above procedures is linear.

Proposition 5-3-3 (Time complexity) : Given a transistor graph G (V,E ), the com-
putational complexity of the strength-determination algorithm is 0 ( IE I).

Proof: For a transistor Tr e E , let T1 and T 2 be the non-gate nodes of Tr . Also, let
the number of visits to Tr be vs. If Tr is in the OFF state, vs = 0. If Tr e Gp and it is
ON (l/ZON), we have vs S 3(2). Because Tr can pass rl, p0, pl when it is ON. There-
fore, the maxinum number for visiting Tr is 3. If Tr e G, , we still have vs S 3 since Tr

can pass r0, p0, pl when it is ON.

Thus, it follows that the upper bound of the number of visits to Tr is three. This is
true for all the transistors in G(V,E ). So, the number of visiting the transistors by the

algorithm is bounded by 3 IE I. Hence, the time complexity is 0 ( IE I). C]

After the signal-flow directions of a transistor network are decided, the theory for

57

logic simulation can be applied to evaluate the circuit. Note that signal-flow determina-
tion must be done before running each simulation step. Fortunately, the speed of the
singal-flow determination is linear and so fast that the influence to the overall perfor-

mance is small.

5.4 Simulation Theory

Here, we present the simulation theory used in SWSIM. Based on the theory, cir-
cuits can be simulated with linear-time complexity. However, this simulation theory can
not handle a primitive component which has bidirectional characteristics. In other words,
this dreary can not be applied to an element where its input and output nodes are not
uniquely defined. This is not a problem in SWSIM since the signal-flow directions are

decided before each simulation step runs.

Generic model for digital circuit

This generic model can be used for simulating digital circuits at any logic level. It
describes a circuit as a network of basic building elements. There are no restrictions on
the structure of the network. The BBEs in a network can have arbitrary connections in
their input/output terminals. For example, two BBEs in a network can have common out-
puts, feedback connections, and/or cascade connections. However, the input and output

nodes of a BBB must be known before running each simulation step.

Definition 54-] (Basic Building Element): The basic building elements (BBEs)
are the most primitive components modeled in a digital network. The outputs of a BBB
are solely decided by its inputs, i.e., BBEs are combinational circuit building blocks. Let
a BBB have n inputs and m outputs whose inputs are i 1, i 2, ..., i,, and outputs are 01, 02,

..., 0,, (see Figure 5-4). We have
vt'+t. (0;) =f j (V: (i 1). vi (1' 2). VI (13.)). 15] Sm

where the notation is as follows: v, (i 1) is the value of node i1 at time t; v, (i 2) is the value

58

of node i 2 at time t, etc.; vy'w (of) is the value of node 01- at time t+td which is driven by
this BBE. The functions f j, lSjSm , describe the behavior of the BBB. f ,- can be a for-
mula in two-valued Boolean algebra, three-valued ternary algebra, or a general

mathematical function in a high-level representations.

 

i1—— 91
‘2‘?“ BBB , 92

 

 

 

 

in 9m

 

 

 

Figure 5-4 The general diagram of a basic building element.
Definition 5-4-1 assumes that all kinds of BBEs have the same delay time, tag. The

outputs in a BBB at the next time step are governed by the inputs in the present time step.

And, for later use, we define a procedure f 335 to calculate all f ,- , 1Sj Sm , at time t.
fBBE t for (i=1 :J'Sm :J'++) vtlt. (01')=fj(Vt(i1)th(i2)s---:Vt(in))3

The output of f 335 is a set of all output node-value pairs.

Definition 5-4-2 (Uniform System): If a circuit can be decomposed into a number
of BBEs which conform to Definition 541, then the circuit is called a uniform system
regardless of the Circuit’s topology.

This definition says that a uniform system consists of BBEs only. A uniform system
may have different types of BBEs. The structure of a uniform system is less important.

Hence, a uniform system can have arbitrary connections among the BBEs.

Definition 5-4-3 (Node): The input and output terminals of a BBB are called nodes.
Nodes are the connecting wires in a uniform system. A node only has a unique value for
an instant in time.

The above definition states the attribute of a node. Nodes may have other attributes.
Since the interconnection of a uniform system is not concerned, other attributes of a

node, such as input and feedback, are unimportant.

59

Definition 5-4-4 (State): The state S (U, t) of a uniform system U at a time instant
t is a set ofall node-value pairs in U.
S(U, t) = {<d1, v,(d1)>, <d2, v,(d2)>, ..., <dk, v,(dk)>},
where U has a total of k nodes. <dj , v,(d,- )>, 15. j Sk, are all 2-tuples whose first element

is a node name and the second element is the node value at time t .

According to the above definition, the state of a uniform system, S (U , t), com-

pletely describes the state of U at time t .

Definition 5-4-5 (Excitation): An excitation Ex (U, I) of a uniform system U at
time t is a set of all input node-value pairs in the system U, i.e., an Ex (U, t) gives all
input values to the system U at time t . Formally,

Ex(U, t) = {<i1, v,(i1)>, <i2, v,(i2)>, ..., <ip , v,(ip )>},
where the system U has p input nodes.

Clearly, the excitation of a system can be changed each time when a new simulation
process runs. Ex(U , t) defines the values of the input nodes at time t and those input
values are at least fixed during the time interval [t, t+1). For example, the power supply
to a uniform system is treated as one of the elements in the excitation set. The value of
the power node is a constant through the whole simulation run.

Lemma 5-4-1 : S (U, t) contains Ex (U, t), where S (U, t) is the state of a uniform
system U at time t and Ex (U, t) is an excitation to the system U at time t.

Proof: S (U, t) is the set of all node-value pairs and Ex (U, t) is the set of all input
node-value pairs in U at time t. Since input nodes are part of all nodes in a system, we
have that S(U, t) D Ex(U, t). Notice that S(U, t)—Ex (U, t) is not obtained from
Ex (U , t ). 13

Now, a potential problem arises. How does one decide the value of a common out-
put node from several outputs of connected BBEs? A common output node is the node

where outputs of more than one BBEs join. This feature is called bus connection. Here,

60

we define a competition function to evaluate the real value of a common output node. In
real circuits, a competition function may vary to suit different technologies. For example,
T‘l‘L gates with wired logic may use an AND operator to define the competition function
when T'I‘L circuits are modeled. On the contrary, wired-OR logic is used for ECL gates

to implement the competition function. However, a general definition is as follows:

Definition 5-4-6 (Competition function): If a node d is a common output node of
several BBEs, say 4 , in a uniform system, then the node value v, (d) is decided by a
function called the competition function Comp . Formally,

v,(d) = Comp (vi , vé ,..., vq') ,

where vi is the output value from one of the connected BBEs, vi from another con-
nected BBEs, etc. There is no limitation to the number of arguments in a competition
function. These arguments compete together to decide the actual value of the common
output node d at time t. Of course, no competition function is needed, if a system has no
common output nodes. This is sometimes true in high-level circuit descriptions. For con-
venience, a competition function is sometimes denoted as Comp (...), since the number of
its arguments may vary.

The above definitions depict the generic model of a digital circuit. Obviously, this
model is easy to adjust for different levels of circuit description. Speed and accuracy in

the simulation task depend on the resolution of a specific model.

Simulation theory for the generic model

As with other simulation models, this simulation performs a set of steps. Each step
is one unit delay time td . There are no changes in a uniform system during the time inter-
val (t, t+td). The simulation process drives the states of a uniform system U from the
initial state S (U, 0) to the next state S (U, 1), then S (U, 2), S (U, 3), ..., etc. From those
states, values of all nodes are obtained. They provide the transient response of the sys-

tem. The law of transition in a uniform system is presented here. We prove that all uni-

61

form systems follow the transition law. Also, the computational complexity of the sirnu-
lation theory is given.

Suppose we already know the state of a uniform system U at time t. This means we
can use that information to calculate f 333 for all the BBEs in U. Then, we can apply the
competition function to all the common output nodes in order to obtain the real values of
those nodes. Hence, all node values except the input nodes in U at time t+td are
obtained. Based on the above description, we define a procedure f y (S (U , t )) to evaluate
the node values at time t+td . Let a uniform system U have b BBEs (i.e., BBE 1, BBE 2,...,

BBEb) and c common output nodes (i.e., d1, d2, ..., dc ). The procedure is as follows:

fU(S(U.t)): { for (i=l;ij;j-H-) evaluatefBBEj;

for 0:1; 150; j‘H') Vt+t.(dj) = Comp (...); i

f u is called the behavior of U. It depends on the relationship among the embedded
BBEs and the technology used to implement the system. The output of f U (S (U , t)) is
defined as a set of all node-value pairs except the input nodes in U at time t+t4. Also, a

valid initial state can be obtained by assuming td=0 and evaluate f u (S (U ,0)).

Definition 5-4-7 (Transition Law): The law of transition
S(U,t+t4)=f.(S(U, t)) u Ex(U, t+td) ,
where S(U, t+td) is the state of U at time t+td; fU(S(U, t)) is the behavior of U;
S (U, t) is the current argument of f U; and Ex (U, t+td) is an excitation of U at time
£44,].

The transition law says that a new state can be derived from an existing state and a
new excitation. A state at time t+td can not be obtained unless an excitation at the same
time is also known. The transition law is the main principle in the sirrrulation task. It
gives the method to predict the feature of a uniform system at t+td fi'om the current time
t. Actually, the transition law is very similar to the state equation of a linear, time-

invariant, discrete-time dynamical system in the control theory [31].

62

Theorem 5-4-1: Every BBE behaves according to the transition law.

Proof: For a BBB with n input nodes, i1, i2, ..., in, and m output nodes, 01, 02, ...,
0",, let Ex(BBE , t) and Ex (BBE , t+td) are excitations of the BBB at time t and t+td,
respectively. At time t , the state of the BBB is

S(BBE, t) =Ex(BBE, t) u (<01, v, (01)>, <02, v,(02)>, <o,,,, v,(o,,,)>},
where

Ex (BBE , t) = {<i 1, v, (i 1)>, <i2, v,(i2)>, ..., <i,,, v,(i,, )>].
Let f 333 represent the behavior of the BBB, we use S (BBE , t) as the argument to evalu-
ate f 335. Formally,
fBBE (5 (335. t)) = (<01. Vt+x.(01)>i <02, Vr+t,(0 2)>. ..., <0m . Vt+:.,(0m )>}

Hence, we obtain

S(BBE , t+td) =f335 (S (BBE, t)) u Ex(BBE, t+td).

Theorem 5-4-2: Let system W be composed of two systems U and V such that the
connection between U and V is arbitrary. Moreover, the following are true:
(a) U and V follow the transition law;
(b) all of the BBEs in U and V have the same delay time;
(c) a competition function exists in W.
Then W also follows the transition law.
Proof: S (W, t) can be obtained from S (U, t), S (V, t), and the competition func-
tion of W. Since U and V follow the transition law, we have
S(U, t+td) =fU(S(U, t)) u Ex (U, t+td)

S(V.t+ta)=fv(S(V.t)) U EX(V,t+td)
Then we can apply the competition function of W among the common output nodes in

these two sets S (U, t+td) and S (V, t+td ). Hence, all node values except the input nodes
of W are obtained. This procedure is exactly the same as evaluating f w (S (W, t)).

Hence, we have

63
S(W.t+td)=fW(S(W.t)) U Ex(W.t+t.i).
where Ex (W, t+td) is an excitation of W at t+td .

Clearly, Ex(W, t+td) is a subset of Ex(U, t+td) u Ex(V, t+td). [:1

Theorem 5-4-3: A uniform system always follows the transition law if a competi-
tion function exists.

Proof .' Partition a uniform system into individual BBEs, then hierarchically apply
Theorem 5-4-1 and 5-4-2. We have

S(U.t+td)=fu(S(U.t)) U Ex(U.t+td).
which is always true at all levels. D

This theorem establishes the principle for simulating a uniform system which is

governed by the transition law.

Theorem 5-4-4: The computational complexity in simulating a uniform system for

one step is linear with respect to the number of BBEs in the system.

Proof: For one simulation step, let the time needed to calculate the behavior of a
BBB in a uniform system is T333 , i.e., we spend T333 to evaluate f 333 for one BBE. Let
the time needed to compute the competition function for a common output node is
Tom . Although Temp may vary for the number of arguments in the function, the worst
case can be used to estimate Temp, i.e., there is always an upper bound for Tam in
terms of the maximum number of connected BBEs in a common output node. Therefore,
for a uniform system U with b BBEs and c common output nodes, f u (S (U , t)) can be
evaluated in time:

bT333 + cTCmp S (b +c )Max. (T333.TCW)
Clearly, c is decided by the connecting topology of the BBEs and is bounded by the
maximun number of input/output nodes of a BBB and b . Hence, the computational com-

plexity is O(b).

In the above proof, we neglected the time needed to obtain an excitation. This is
because it is a very small fraction of the total simulation time, since the number of inputs

in a system is usually much smaller than the number of BBEs.

5.4.1 Multiple-Delay Model

In the previous section, we established the simulation theory for uniform systems.
However, using uniform systems to model digital circuits does not complete the task.
One obvious problem is the following. Due to the various load of the components in a
digital circuit, the delays usually are very different among the basic building elements.
Although the unit-delay approach is good to verify a circuit topology, it leaves too much
work in the lower level design. Circuit designers still need to decide the size of all BEES
based on the output loads or fan-out numbers. In some worse case, buffers may be

needed in order to drive the next stage.

The above problems occurring in the unit-delay simulation can be solved if the
building blocks of a digital circuit can be modeled as multiple-delay elements. Thus, a
functional block at high level description, such as an arithmetic logic unit, can be
modeled as a building element with its own delay value. And since the same elements in
a circuit with different delays can be modeled, the simulation results are more accurate
than those for unit-delay simulation.

Based on the above discussion, we present a multiple—delay model for the building
elements in digital circuits. Then, we will prove that the transition law is still valid in
such circuits.

Definition 5-4-8 (Building Element): The building elements (BE) are the com-
ponents in a digital circuit with the following features. A BE may have more than one
input and output. Each output has its own delay value. Let a BB have n inputs and m out-

puts whose inputs are i1, i 2, ..., in and outputs are 01, 02, ..., o,l . And, the delay of an out-

65

puts of is de, where 151' Sm . Then we say the value of of at time t+de is solely decided
by the inputs at time t , i.e.,

Vita“; (Oj) =fj (Vt (i1)tVt (i2)9“°’vI (13.)). 15.1.9"
Where the notation follows Definition 5-4-1 except T4,- . Now, by is the delay time

which only associates with the output of.

Based on the above definition, we realize that a BB is a multiple-delay component
and can be used to model any digital component above the transistor level. The output
values are decided not only by the input value but also by the delays which may vary
among these outputs. By evaluating the functions f ,- , lSj Sm , we obtain all the output
values of a BB. These values are at different discrete time instants because each output
has its own delay. However, according to the transition law, the simulator needs to obtain
all of the node values at the next time step before it can move on to the next step. There-
fore, we need to define a mechanism for each output of which can not only record
VAL, (01') but also provide v,'+1 (01') to the simulator. We called the mechanism Delay
Ring.

A delay ring is a number of storage cells which record some simulation results dur-
ing a time interval. These cells form a ring, as shown in Fig. 3. Let an output of of a
building element in a digital circuit has delay time d, then the delay ring which associ-
ates to 0,- has d cells. Each delay ring has two pointers, one called Producer and the other
called Consumer. The producer is used for writing the value v,'+d (01-) into the ring. The
consumer is used for reading the value v,'+1(oj) from the ring. Before the simulation goes
to the next step, these two pointers needs to move to the next cells respectively. Clearly,
a delay ring is a data structure to hold the simulation results of a output node from the
next time step to the time step t+d , where t is the current time and d is the delay of the

output node. And the two pointers are dedicated to ring operations.
Let Dop (of) be the delay ring operating function of 01-. We describe 00,, (01-) as the

following procedures:

(1)
(2)
(3)
(4)
(5)

 

 

0 o ucer Consumer
Figure 5-5 The structure of a delay ring.
Evaluate v,'+d (0,) by the input/output definition function f j .
Store v,'+d (of) at the location pointed to by the producer of the delay ring.
Read v,'+1 (of) from the location pointed to by the consumer of the delay ring.
Move the two pointers one step counterclockwise.

Return the value read, i.e., v,'+1 (oj ).

Briefly, 00,, (of) stores the new simulation result, which will be used after the delay

time, and returns the value for next simulation step.

Now, we can define the evaluating function for a given building element called f 33.

The f 33 is defined as the following executing sequence:

far; = f0r(i=1;jSm;j++) vt'+r(0,-)=Dop(0,-);

The output of evaluating f 33 is a set of all output node-value pairs at the next time step.

The delay ring operating function of a BB makes the BE acting as a basic building

element. Hence, the law of transition can be applied to a network which is composed of

components with different delay values. The simulation time step is the smallest delay

among all the components in the network. As a result, circuits which contain elements

from different levels in the circuit-description hierarchy can be simulated.

67

5.4.2 Tuning for CMOS Digital Circuits

Now, we tune the generic model to satisfying the CMOS circuit technology. First,

we model PMOS and NMOS transistors as unit-delay BBEs.

Proposition 5-4-1 (Transistor model) : The PMOS and NMOS transistors are
BBEs in a CMOS digital circuit.

Proof : Since we represent a CMOS circuit as a transistor graph, the strength-
deternrination algorithm can be applied to evaluate the node strength. And, according to
Definition 5—3-3, the signal-flow direction of a transistor can be decided. Hence, the
transistor model shown at Table 5-2 (5-3) can be used to calculate f 333 , where BBE is a

transistor. D

Since a transistor can be modeled as a BBB, a CMOS digital circuit is a uniform
system. Therefore, the transition law can be applied for simulation. However, a competi-

tion function specified for CMOS circuits still needs to be determined.

Proposition 5-4-2 (Competition function for CMOS circuits) : The CMOS com-

petition function is dominated by the short-circuit effect.

Proof : The proof for this proposition is trivial since it follows the circuit theory. [II

In order to obey the law of Excluded Middle, SWSIM uses a prediction method dur-
ing initialization. At the begining, all nodes have the value of unknown. The unknown
value at the gate node of a PMOS (NMOS) transistor turns it ON (1/20N). Such a PMOS
(NMOS) transistor is used to pass an r1 (p0). Then, the initialization proceeds until a rea-
sonable state is reached. A reasonable state of a circuit is a state which all the node
values agree with the circuit behavior. This state is used as the state at the time instant 0
for later simulation. According to the competition function, an rl (p0) can be replaced by

an r0 (r1). Therefore, if the predictions are wrong for some nodes, they will be corrected

68

in the next initialization steps. As a result, no latches in a circuit can have any value other
than logic 0 or logic 1. The simulation sequence of transistors determines the real initial

value of a latch if it can not be evaluated by the circuit input.

Clearly, the initialization algorithm is very similiar to the strength—determination
algorithm. Hence, it is also of linear-time complexity for each initialization step.

In summary, the generic model presented in this section captures the unification
properties of digital circuits at any logic level. The time complexity of simulation was
proven to be linear with respect to the circuit size. The drawback of this model at the
transistor level is overcome by the signal-flow determination algorithm. At the end of this
section, we tuned the generic model for application to digital CMOS circuits. Based on

this model, SWSIM was implemented.

5.5 Performance Analysis

Here, we use one type of the circuits in the quick simulator benchmark [32] to
analyze the performance of SWSIM. For the linear feedback shift registers (LFSR) at the
first level in this benchmark, we choose N =10 and M =7, where N is the total number of
stages and M is the feedback stage. Hence, we have 428 transistors to form a building

block at the second level. (Refer to Greer’s paper [32] for the circuit structure.)

Table 5-5 shows the simulation data. The circuit names also represent the hierarchi-
cal structures of those LFSRs. For example, R-7-4 is an LFSR which has 7 stages at the
second level and 4 stages at the third level. The first level structure is an LFSR with 10
D-type flip-flops and the feedback comes from the 7th flip-flop. Clearly, this is the struc-
ture of R-l. The second field in the table is the total number of transistors in these cir-
cuits. Each circuit was simulated 5 times. The simulation period was 5 clocks with each
clock = 5000 steps, where a step is defined as the unit delay time. The results are listed
from the third field to the seventh filed in the table. Finally, the last field is the average

time per clock. The time unit is in seconds.

69

 

 

 

Circuit name #Tr 1 2 3 4 5 seconds/clock
R-l 428 6.8 6.6 6.7 6.5 6.6 1.33
R-2 856 9.3 9.3 9.0 8.8 8.7 1.80
R-3 1284 13.2 12.9 12.8 12.7 12.7 2.57
R-4 1712 16.4 16.2 16.1 15.9 16.1 3.23
R-S 2140 19.7 20.0 19.7 19.8 19.9 3.96
R-6 2568 22.9 23.3 23.3 22.9 23.3 4.63
R—7 2996 27.2 27.0 26.9 27.3 26.7 5.40
R-7-2 5992 48.5 48.3 48.4 48.5 47.9 9.66
R-7—3 8988 71.7 71.7 71.8 71.9 71.8 14.36
R-7-4 1 1984 96.2 95.8 96.3 96.2 96.0 19.22
R-7-5 14980 120.8 120.8 120.6 120.5 120.4 24.12

 

 

Table 5-5 Performance analysis of SWSIM on a SUN-3 workstation.
(Each run took 5 clocks with 1 clock = 5000 steps.)

Figure 5-6 shows the graph obtained from Table 5-5. SWSIM is demonstrated to be
of linear-time complexity by this graph. Moreover, SWSIM can simulate many CMOS
circuits which can not be simulated properly in other simulators. The examples in the

next section demonstrate some of them.

25 —

20 —

15 -
Seconds/clock

10 —

5..

 

0

 

l l f
5000 10000 15000
Number of transistors

O-i

Figure 5-6 The performance of SWSIM on a SUN-3 workstation.

5.6 Key Examples

This section shows some representative circuit examples simulated in SWSIM.

70

Both the circuit diagrams and their timing results are listed.

Delay Demonstration

Figure 5-7 is a NOT gate with its input A connected to several pass transistors.
When the Control signal goes high, the effect of In will be seen at the Out node after 5
unit time. However, when Control goes low, those pass transistors are turned off. Node A
becomes high-impedance after one unit delay time. The capacitor associating with A still
let Out high. The timing diagram is shown in Figure 5-8. This example shows the delay
calculations in SWSIM.

Another example, as shown in Figure 5-9, demonstrates the effect of Schmitt trigger
feedback. Without the feedback transistors, the delay time should be double. Figure 5-10
is the timing diagram. Some switch-level simulators mentioned in the Trimberger’s book

[33] can not deal with this circuit.

Clocked CMOS Logic

This example shows a 2-phase static D flip-flop. Figure 5-11 illustrates a circuit
which is built from several transmission gates and inverters. The structure of transmis-
sion gates and inverters is omitted since they are well known. The timing diagram for
the specific inputs is given in Figure 5-12. One may find this circuit in the Weste and
Eshraghian’s book [10]. Although the timings of C and C looks unsynchronized, their
"effect" is synchronized. This is because the gates connected to C store the previous

value.

Pass Transistor Logic

The circuit in Figure 5-1 is an XOR gate made by some pass transistors. Figure 5-13

shows its timing diagram.

71

Dynamic CMOS Logic
We use a 4-bit barrel shifter as an example. Figure 5-14 shows the circuit. Figure
5-15 is the timing diagram for all possible inputs. L,- are the inputs, S,- are the control sig-

nals, and R; are the output nodes where 0 Si 5 3.

Self-oscillating Circuits

Here, we use a cascade of three inverters to demonstrate the simulation of self-
oscillating circuits. Since each inverter is composed of a PMOS transistor and a NMOS
transistor, the delay of each inverter is a unit time. Figure 5-16 is the circuit and Figure

5-17 is the timing diagram.

 

 

VDD
1“ ’11. _1_L _LL _1_L 0‘“
T r T r I
Control GND

Figure 5-7 Delay demonstration using pass transistors.

15 30 45

 

Figure 5-8 A timing diagram of the circuit in Figure 5-7.

72

..BJ'I;

HE
I

GND

Figure 5.9 An inverter with Schmitt trigger feedback.

 

 

 

 

0153045607590105

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

A ll 11 II II
B
Our

 

 

 

Figure 5-10 A timing diagram for the circuit in Figure 5-9.

P

 

A

CH>°——l>°9 —B[3—H>—T—{§2—1—l>~ .Q

a: Larges

VDD -

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 5-11 A dynamic D-type flip-flop.

73

5 90 105 120 135 150 165 180 195

 

iiorznnnnnnnnn
irnrrrnnnnnni

 

.Fflflflr‘mfli‘mflflflfl

 

 

 

 

 

 

 

 

______ r__

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 5-12 A timing diagram for the circuit in Figure 5-11.

15 30 45 60 75 90105

 

Figure 5-13 A timing diagram for the circuit in Figure 5-1.

 

s3 s2 {51 ,so vpo
CK:
L3'—D‘*—’[ - - - ., {>o—oR3
HEM 7.571%
L2""D’—“ ,...J ‘rJ ‘T‘r ‘ :D’—‘R2
le—{>~—1 ' ~ *3
...4

wee...l"’i:fi‘3i3 M

Figure 5.14 A 4-bit barrel shifter.

 

 

 

 

 

 

 

 

 

 

 

 

 

{>HR0

 

 

 

 

 

 

tie it

 

 

 

 

 

 

 

 

74

15 30 45 60 75 90 105 120 135 150 165 180 195 210 225 240 255 270 285 300 315

 

Figure 5-15 A timing diagram for the circuit in Figure 5-14.
A E B i: C 1:
Figure 5-16 A self-oscillating circuit.
0 15 30 45 60 7 90

HHHHHHHHHHHWSHHHH

rfiflflnnnnnnnnnflnnn
mwmmmmm

Figure 5-17 A timing diragrarn for the circuit in Figure 5-16.

>

 

w

 

 

 

 

 

 

 

 

O

 

Chapter 6. Rule-Based Verification for CMOS Gate Structures

Simulation is not the only method, to validate a circuit structure. Another method
which translates the structure into a different format and then verifies it at the different
domain may be more suitable in some cases, In this chapter, a tool to verify a digital cir-
cuit layout by extracting and evaluating its Boolean functions is described. The conect-
ness of generated Boolean functions imply the validation of hardware structures at the
gate structure. And, the Boolean functions can be used as the input for higher-level
verification. We describe such a verification system that uses rule-based techniques. The
system verifies a circuit’s layout by generating and checking the corresponding Boolean

functions.

6.1 Overview

Circuit verification of a VLSI chip layout is one crucial step in the custom—oriented
design process. It is the designer’s responsibility to ensure the validation of the circuit
structures. VLSI circuits are notoriously "unforgiving" since any "unconscious" error in
the physical layout can make the prototype unworkable. Unfortunately , a VLSI proto-
type is almost uncorrectable nowadays. This is the feature which makes verification play

an important role in the VLSI design process.

In general, circuit verification can be cataloged into two fields, i.e., static and
dynamic. Furthermore, static circuit verification can be divided into two hierarchical lev-
els. The first level is the verification of geometric dimensions of physical layout, known
as design rule checking [36]. Usually, design rule checking is implemented in graphic
layout editing systems, such as in the MAGIC VLSI layout tool [37]. It can check the
physical layout during the interactive layout-editing period and make sure that there are
no violations against the fabricating resolution in the geometric dimensions. The second

level of static verification is used to guarantee the correctness of higher level circuit

75

76

structures. For example, the layout of a NAND gate must not only obey the design rule

checker in the layout system but also must be functionally correct.

The work done in this research falls into this latter category. But, instead of using
binary patterns to verify MOS digital circuits, we use Boolean expressions to do func-
tional verification at the gate level. We select this approach because two disadvantages
exist in the current approach: First, if there are many input lines, functional verification
requires the generation of a comparable number of output values. And the same problem
exists for circuit testing. Specifically, for N inputs, 2"I testing patterns are needed. And,
second, there is no way of extracting information regarding the structure of the target cir-
cuit. Of course, hardware verification at the level that is higher than the gate level also

can be achieved if the hardware structures are specified or standardized.

The last kind of circuit verification is dynamic, which means that the verification
involves another dimension, i.e., timing. Timing verification can decide the speed of a
circuit, solve run-time bugs, etc. Since Boolean algebra has no timing relations among

variables, dynanric circuit verification is beyond the scope in the chapter.

The purpose of this tool is to verify a circuit layout at the transistor level. The
method we use here can also be used to synthesize a combinational circuit fiom its
Boolean equation. Given a Boolean equation, better circuit performance is usually
expected if we implement the equation at the transistor level. After a circuit layout is
created by following our synthesis method, the best way to verify it is using a symbolic
verification technique. In comparing our approach to that of others [39] [40], ours is more
friendly and easier to use.

We adopt Prolog [4] to implement our system based on the following rationale:
First, the topic has a well-defined domain. Second, circuit structures may be represented
simply in Prolog. And, finally, Prolog provides a powerful capability for symbolic pro-

cessing.

77

This verification system provides the following information about the circuit: First,
for each gate in the target circuit, the system generates a Boolean expression to describe
the gate. And, second, the interconnection of all gates in the target circuit are checked.
Two basic, but important features are short—circuit checking and functional-completeness
checking. Short-circuit checking can prevent an inadvertent conducting path from vdd to
gnd through a transistor network. Functional-completeness checking ensures that there
is only one unique output value for each input pattern. Actually, all necessary logic infor-
mation, except the timing information, can be obtained by manipulating the results.

Hence, hardware structures can be verified statically.

Figure 6-1 illustrates the verification system. A VLSI layout of a circuit is extracted
and the corresponding Boolean expression with AND, OR, and NOT logic primitives is
generated for each gate in the circuit. Two basic checks are performed in this phase to
verify the gate structures. The circuit domain is restricted here to CMOS complementary
logic [10]. Some complex structures, such as a PLA, can also be transformed into
Boolean expressions. After phase I, a sot of Boolean expressions is obtained which
describes the target circuit. It carries all necessary logic information needed for high-
level circuit structure verification. A good example of the verification is the implementa-

tion of a logic-level simulator with the following primitives: AND, OR and NOT.

 

 

. . ' 'hfighLIEQEI‘ '
(i: (grafurt Boolean Structure
y I Verification

 

 

 

 

 

   
 

  

Geometric
Design Rule
Checking

   
   

Figure 6-1 The rule-based approach for digital circuit verification.

78

Figure 6-2 shows the concept of a hierarchical verification system. At the lowest
level, a geometric design rule checker is used to guarantee the correctness of physical
dimensions of a circuit layout. At the next level, logic information is extracted from the
layout, and the correctness of each gate is verified. Next, high-level hardware structures
can be checked, e.g., flip-flops and registers. And, finally, the whole circuit can be
verified based on those recognized structures. This tool focuses on the gate-level

verification.

 

System
Verification

 

Standard
Hardware
Recognition

 

Gate Level
Verification

 

Geometric
Design Rule
Check

 

 

 

Figure 6-2 The hierarchical verification system.

6.2 The Knowledge Domain

In this section, models are described for digital MOS circuits, including connecting
wires, circuit components, and logic gates. These models serve as the basis for formally

describing a circuit’s layout in the rule-based verification system.

(1) Connecting Wires

In the real world, each connecting wire in a circuit has its own resistor and capacitor
values, and the dimension of a wire may change the behavior of a high-speed circuit. But,
when we are only concerned about a circuit’s static behavior, a connecting wire may be

regarded as a variable in a Boolean expression, and each wire may be assigned a unique

79
name in a specific circuit.

(2) Circuit Components

Only transistors are considered to be active components in our circuit representa-
tion. They are the logic primitives at the lowest level. Boolean models for MOS transis-
tors are established in the next section. In the abstract physical layout of a MOS circuit, a
transistor is made by covering a diffusion layer with a polysilicon layer. This geometric
information must be mapped into models for standard circuit components, such as
transistors, resistors, and capacitors, before verification takes place. Since Boolean alge-
bra has no direct relationship to resistors and capacitors in the MOS digital circuits, we
assume all circuit components, except transistors, can be ignored. This means that only

the transistor types and connections are what we need at the lowest level.

(3) Gate Structures

There are many kinds of gate structures in the MOS circuits. CMOS complemen-
tary logic, NMOS logic, dynamic CMOS logic and pass-transistor logic are typical exam-
ples [10]. A VLSI circuit designer may put more than one kind of gate structures into a
design. This makes verification more complex. As a starting point, CMOS complemen-
tary logic is chosen as the circuit structure domain in our system. We choose this
because this MOS implementation technology contains all of the information required to
fully describe a circuit’s interconnection topology. Consequently, it is not too difficult to
recognize any other standard gate structures from the represented interconnection. The
knowledge of generating a Boolean expression, which corresponds to a specified CMOS

complementary gate, is described in the next section.

Using this approach, some higher level circuit representations can also be recog-
nized and extracted to do circuit layout verification. A typical example is a simple latch
composed of two feedback-connected N AND gates. Since there are a variety of high-

level structures, we leave this for future extensions of this work. This feature will lead

80

the verification system into a specific tool which has expertise to verify some kinds of

circuit components with well-defined complex structures.

6.3 The Boolean Model

The following rules give the Boolean model of CMOS complementary gates.
Models for other types of gate structures can be developed in the same manner. This
model can not only be used to verify a layout but also can be used to implement a
Boolean equation at the transistor level.

Rule 1 (Transistor Definition): A transistor, Tr (s ,d ,g ), is defined as a path from s
to d and the path is controlled by g , where s is the source terminal, d is drain, and g is
gate. Tr is a variable and can take on the symbolic values nt or pt which define the
transistor type as being N-diffusion or P—diffusion, respectively.

Rule 2 (Function Node Definition): A function node is defined as an output node
of a gate. For two different transistors, nt(sl, d1, g 1) and pt (s2, d2, g2), if d1 equals d2

or g2 then d1 is a function node. Or, if g1 equals (1; or g; then g1 is a function node.

vdd

 

I ——«———Q Pnet

 

 

 

 

 

 

 

Nnet

l

gnd
Figure 6-3 The topology of a CMOS gate structure.

 

 

 

 

Rule 3 (Transistor Network Definition): A Pnet (P-transistor network) is defined

as a network between vdd and a function node. Arr Nnet (N-transistor network) is a

81

network between gnd and a function node. Thus, A Pnet and an Nnet with the same
function node form a gate (see Figure 6-3). A gate has a "unique" Boolean equation
which is obtained from its Pnet and Nnet. Let f be the equation and all inputs to the
gate is a vector I . Then, from the Pnet , we have

f = Br»... (1' )
And, from the Nnet , we have

f = Bit... (I)
Where B denotes a Boolean equation derived from its subscript and its arguments are the

items in the equation.

Rule 4 (NOT (-) Operator) : For a pt (s ,d ,g ), if it is a necessary path from vdd to
a designate function node F then g will show up in the Boolean expression of F . In
other words, a P-transistor conducts when g- is present. And an N-transistor, nt (s ,d ,g ),

conducts when g is present.

Rule 5 (AND (J Operator) : If two transistors, T r1(Sl.D 1,01) and Tr2(S2.D 3G2)
have the relationship Tr1=Tr2 and S 1=D1 then the gates 01 and G2 are connected by an
AND operator. Therefore, we define a conducting path in a transistor network (Pnet or
Nnet) as a path from vdd (or gnd) to a function node F . Hence, a conducting path of F
is a minterm in the Boolean expression of F . If there are rrrore than one of the same gates
existed in a path, they are reduced. Only one gate per item is allowed in a given path.

This is the first minimization work.

Rule 6 (OR (+) Operator) : A transistor network for a function node F may have
more than one conducting path. Each path is combined together by the OR operator. A
path may be a subset of other paths. This implies that some minimization work can be
done in this rule. Only the paths which are subsets of other paths need to be taken into
account. By applying Rule 4, 5 and 6, the system can derive a Boolean expression with

NOT, AND and OR primitives from a transistor network.

82

 

 

 

 

a
gnd

Figure 6-4 An un-complete gate.

Rule 7 (Completeness Checking) : For a given function node F, logic 1 is
obtained from the Pnet and logic 0 from the Nnet. For all possible input patterns to the
gate, a logic value of F should be obtained. In other words, F should be completely
defined in terms of mapping every input pattern (see Figure 6-4 and Figure 6-5). To
check a gate is complete, we first apply De Morgan’s rules to the equation BNM (I) and
then use maxterrn decomposition rules to convert the equation from product-of- sum form
into sum—of-product form. During the decomposition, we minimize those intermediate

equations by adopting the following rules:

a+E=1
a5 =0
a+1=1
ad =a
a+a=a
aa =a
E =a
a+0=a
a0 =0

The formula used to minimize a Boolean expression

83

vdd

in

L ' Aoutput
b’ it}
|:

'l

 

 

 

 

 

I
I

 

 

e
gnd

Figure 6-5 A complete gate (NAND).

Rule 8 (Short-Circuit Checking) : A path which conducts from vdd through a
function node to gnd is not allowed. But, if it happens, then a short circuit exists in the
gate which owns the path. Specifically, if one of the minterms which is obtained from the
Pnet of a gate is the same as a minterm in the Nnet then there is a short circuit in that
gate. This kind of error may be discovered by the completeness checking but is more

time-consuming.

6.4 Implementation in Prolog

Prolog is a language with very complex building functions, such as unification of
variables, different kinds of tree manipulations, and database (facts and rules) manage-
ment [38]. Circuits are represented in Prolog as a set of facts. Each fact represents an
elementary circuit component. Figure 6-6 shows a NOR gate representation. Clearly,
facts in a circuit representation give all the structural information needed to generate its
Boolean equations. Rule 1 in the last section provides the definition of transistors’ facts.
Hence, we can define our program as a mapping mechanism which maps a CMOS digital

circuit from transistor structures into a set of syntactic Boolean equations.

Next, the function node definition becomes a rule in Prolog. Based on this rule, all

84

vdd

t1

 

 

 

gnd

The representgtion of the NOR gate:

pt(vdd,tl ,a).
pt(tl ,f,b).
nt(gnd,f,a).
nt(gnd,f,b).

The corresponding Boolean Quations:
f = 5+5, f = a 'b;

 

Figure 6-6 A NOR gate representation.

gates in the target circuit can easily be separated. Then the program recursively processes
each function node to find its corresponding Boolean equation. A similar strategy can be
applied to NMOS circuits because there is always a load transistor in order to form a

gate.

After finding a function node, the system defines the Pnet and Nnet which form the
gate. Thus, the problem is reduced to a single-gate problem. In CMOS theory, a Pnet is
used to produce a logic 1 and an Nnet to produce a logic 0. Therefore, a Boolean equa-
tion, which generates positive logic, can be obtained form the Pnet. And a Boolean equa-
tion which generates negative logic can be obtained from the Nnet. So, the target gate is
represented by two complementary Boolean equations. For each input to the gate, either

the Pnet or Nnet should generate a high-impedance output, but not both. This attribute is

85

examined by short-circuit checking and functional-completeness checking. The first type
of checking takes the minterms which exist in the complementary logic equations to
compare with in order to prevent a short path. Functional-completeness checking applies
De Morgan’s rules, maxterm decomposition and reducing rules mentioned above to the
equations. Then, the results are compared with their corresponding complementary equa-
tions. Even today, it is still crucial to compare with two Boolean equations in an accept-
able execution time. However, the method we have adopted in completeness checking
can perform well, since the equations are generated by the hardware structures. Here, we
show an example to illustrate our minimization technique. The Boolean equation we
want to minimize is

z =a-b_-c +E-b-c +a-b-c +E-b-'c
After we apply De Morgan’s rules to f, we have

2' : (5+b +c')(a +b-+E)(E+b+c')(a +b +5)

Then, we apply maxterm decomposition rules to the above equation. Step by step, we get
the result:

2' = (E+b +c—)(a +17 +E)(E-b +a 5+5)

= (5+1; +E)(a 5+5)
= E-c'+b 6+5
= c
The performance of the system is dominated by two factors: the sequence of the
transistor facts and maxterm decomposition in completeness checking. Other factors
have linear execution time. In Prolog, the sequence of facts determines the time needed
to retrieve the necessary information. In the worst case, Prolog needs to spend the max-
imum time to obtain a fact in its database. To reduce the influence of this factor, those
transistors’ facts which form a gate should be placed as close together as possible. Next,
unfortunately, maxterm decomposition has exponential executing time with respect to the

number of maxterms in a given equation. However, the performance is still superior than

Karnaugh-map method. For example, in Figure 6—8, the equation of output 2 has 8 max-

86

terms after applying De Morgan’s theorems. But, z has 16 possibilities to reduce it by

using the Karnaugh-map method, since 2 has 4 input variables.

Figure 6-6 is a NOR gate example. Figure 6-7 shows the results from a latch. The
latch is made by two NAND gates which was illustrated in Figure 6-5. A more complex
example is given in Figure 6-8 which is a 4-bit parity generator.

vd

v

 

 

 

 

r1 t2

 

 

 

If
_1_L
I

a.—"—'I —e b

 

 

A

I

gnd

 

The representation of this latch:

pt(vdd,s,a).
pt(vdd,s,r).
pt(vdd,r,b).
pt(vdd,r,s).
nt(tl ,s,a).
nt(gnd,tlr).
nt(t2,r,b).
nt(gnd,t2,s).

The result:

it}:

.0

U

in it
“I ‘I

II
9 G“

In ‘I
II
or a

Figure 6-7 A latch example.

87

 

gnd
The representation 0Q 4-bit parity generator:

pt(vdd,tl_,d). pt(tl,t2,c). pt(tl,t3,c‘).
pt(t2,t4,b )4. pt(t3,t4,b). pt(t4,z,a).
pt(vdd,t6,d). pt(t6,t2,c:). pt(t6,t3,c).
pt(t2,t7,b). pt(t3,t7,b ). pt(t7,z,&').
nt(gnd,t11,d). nt(tl 1,t9,§). nt(tl 1,t10,c).
nt(t9,t8,b). _ nt(t10,t8,b ). nt(t8,z,c7).

nt(gnd,t13_,d). nt(tl3,t10,E). nt(tl3,t9,c).

nt(t9,t12,b ). nt(t10,t1_2,b). nt(t12,z,a).
pt(vdd,a:,a). pt(vdd,b ,b). pt(vdd,c:,c).
pt(vdd,d,d). nt(gnd,§_,a). nt(gnd,b ,b).
nt(gnd,E,c). nt(gnd,d ,d).
The results:
2 = a -b -c ~d+a -b -d -Z"+a -c -d -i2'+a b-E-d-I-b -c -d ~a"+b a-E- "+e
z- = a -b -c ~d+a -b .r-Jm -c -b’-d'+a ~d -b--E'+b -c ~E-d+b -d -a'-c‘+c
E =6, (7 =a;
b- = 5, b- =b;
E = c', E = c;
(7 =5, c7 =d;

Figure 6-8 A 4-bit parity generator.

Chapter 7 Conclusion

The goal of this research is to establish a methodology for building a database-
centered CAD system [19] for digital circuits. The component-oriented design database
minimizes the data size and complexity by taking the hierarchical nature of digital cir-
cuits into account. New tools can be added by performing the natural-join operation in

order to put new attributes into the current database.

Three essential tools are designed and implemented, i.e., a schematic editor, a
switch-level simulator, and a transistor-to-gate-level verifier. By applying these tools to

some key circuits, the performance of this CAD system can be demonstrated.

7.1 Summary

One of the major features of this research is that we adopt a component-oriented
instead of tool-oriented architecture to design this CAD system. Hierarchy and connec-
tivity of digital circuits are the most important principles which guide the development of
the design methodology. To present the design methodology, we first analyze the
characteristics of digital circuit design from the unified point of view. Based on the
analysis, a typical design process is divided into two phases, i.e., the logic design phase
and implementation phase. During the logic design phase, designers deal with logic
(ideal or well-done) components. The effort in this phase focuses on establishing the rela-
tionship of components, building the hierarchy of a circuit, and validating the design.
After the logic circuit has been constructed, designers turn into the implementation phase
to reduce harmful parasitic effects which are introduced by connecting wires and real
components. In other words, this approach is intended to free circuit designers to concen-
trate the creative aspects of design activities and simplifies the effort for a single tool

development.

88

89

The working environment to complete a design is also investigated. The con-
sistency is the major concern in order to provide an environment with minimum redun-
dant and repetitive tasks. We recognize that the whole design process is composed of
many individual tasks from design specification, design capture, design verification,
documentation, and implementation to design realization. Some of the tasks may repeat
or can be eliminated. A tool-oriented system can not reduce the amount of tasks but a
component-oriented system can since the results from different tasks are integrated and
well-organized.

To fully support a component-oriented system, the circuit representation method is
crucial. It must have the capability to represent any kind of circuits. In other words, it
must be broad and still simple enough in order for many different tools. A representation
method which has the format used in predicate calculus is adopted. This unified method,
called the definitional method, not only takes good care of circuit hierarchy and connec-

tivity but also can well represent bidirectional components such as MOS transistors.

Based on the design methodology, the design database and the essential tools to

support our approach are summaried as follows :

The design database of this system is called STOCK. Nowadays, database support
for engineering remains a relatively open issue in CAD research because the representing
entity is much more complex than in other applications, e.g., business. (Therefore, many
CAD systems are tool-oriented.) However, from the hierarchical point of view, any digi-
tal circuit, no matter how complex or simple it is, is merely a circuit component at some
structural level. STOCK is designed to contain only one type of entities, i.e., circuit com-
ponents. The complexity of representing a large circuit is minimized by its hierarchy. In
STOCK, a component is usually defined by other components except for the primitive
components which are defined by themselves. Different aspects of components can be
added without modifying old tools or other unrelated components. Hence, new tools can

be easily added to the system. STOCK is realized as several file directories. Each direc-

90

tory is a single component database with a link to other database. Those unidirectional
links make STOCK a distributed database which can support horizontal team work. The
database management issues are also distributed and localized. This exactly matches the

nature of real component stocks.

We assert that the circuit schematic is an essential part of the overall documenta-
tion, even for a system which supports some hardware description language. Conse-
quently, a universal schematic editor, called USE, was designed and implemented. This
general-purpose schematic editor was developed from the elementary definition of a cir—
cuit netlist. One of the major design endeavors was spent on developing efficient and
unified data structures for circuit schematics with un-limited drawing size. The other was
focused on restricting the type of graphic operations in order to only use the fastest, i.e.,
memory mapping and line drawing. Hence, the computer response time is very short for
each graphic interactive period, such as zoom or pan. USE can be used to construct any
mixed-level circuit from the transistor level to a system level. It supports hierarchy for
design capture, i.e., a schematic can become a component in STOCK. Therefore, USE

allows designers to express a digital circuit at the same level that he/she thinks.

Verification is the major activity during the design process. However, because of the
progress in IC technology, digital circuit design at the gate level no longer meets fully
the requirements in designing the integrated circuits. It has been shown that integrated
circuits can have better performance and use less silicon area if they are designed at the
MOS transistor level [35]. A logic-timing switch-level simulator, called SWSIM, was
designed and implemented. SWSIM was designed for CMOS digital circuits. Transistors
are modeled as both switches and attenuators with an ideal capacitor associated with each
gate terminal. As a result, transistors have three states, i.e., ON, l/ZON, and OFF. And,
node voltages are represented by nine logic values. In other words, the MOS-transistor
logic models which was shown in Weste and Eshraghians’ book [10] are exactly
modeled. To solve the bidirectional problem, a method for deterrninating the signal-flow

91

directions was developed. The simulation theory for uniform systems was deve10ped as
well. The generic model of a uniform system can be used to model almost any kind of
digital circuits. However, the input and output nodes of a basic building element must be
specified before the model can be applied. The strength-determination algorithm solved
this problem. Hence, the simulation theory can be applied to CMOS digital circuits,
which have bidirectional components.

SWSIM has linear computational complexity with the speed comparable to the
gate-level simulators. A performance analysis is presented and some key examples are
given in Chapter 5. The performance analysis shows the speed is less than 25
seconds/clock for a 15,000-transistor circuit on a SUN-3 workstation. Moreover, the law
of excluded middle is always obeyed. This prevents the NP-complete problem [26] which
has occurred in gate-level simulation. There is also no restriction for input timing and cir-

cuit topology. Theoretically, any CMOS logic family can be simulated correctly.

To validate a circuit structure without specifying the inputs can overcome the draw-
backs of traditional simulation approach for some cases. A hierarchical verification sys-
tem from the layout level to system level was proposed, and the fundamental work up to
the gate level was implemented. This rule-based approach to verify the transistor struc—
ture of a circuit takes advantage of the Prolog language. Through the use of Prolog’s
internal database, a circuit can be represented as facts and high-level structure can be
represented as rules. The reasoning method which represents the circuit knowledge at a
giving level validates the circuit structure statically. This method ensures full correctness
of the circuit structure since it takes all components into account. In summary, a

component-oriented CAD system with three tools was developed and evaluated.

Nowadays, tool—oriented systems need a set of translation programs to be the inter-
faces among different tools. This ad hoc approach increases complexity and may easily
introduce inconsistency all over the design process. Some redundant tasks are inevitable

in order to present the same information with different formats. However, a component-

92

oriented system overcomes this drawback. Most tools in such a system read the input
from the component database and, then, put the results back into the database. Since dif-
ferent tools consider different aspects of a circuit component, the format of the com-
ponent database must be very flexible in order to accommodate many tools. Hence,
inefficiency may exist through the database operations. This is the bottleneck of a
component-oriented system. To prevent this, our representation method takes full advan-

tage of the circuit hierarchy in order to minimize the component size and complexity.

Currently, the whole system is implemented in C and Prolog with about 14,000
statements. By using the schematic editor, any CMOS digital circuit from the transistor
level to a system level can be created. The circuit, then, can be expanded into the transis-
tor level and simulated with the switch-level simulator SWSIM. Or, the Boolean func-

tions of the circuit can be generated and verified with the rule-based verification tool.

7.2 Future Research and Development

Based on the current work, future research and development should be directed
toward increasing the rate of automation, extending this work into the field of computer-
aided-engineering (CAE), and incorporating a hardware description language, e.g.,
VHDL [15] [16] [17], for circuit algorithmic and behavioral development. In other
words, tool integration in order to handle the whole process from design capture to
implementation is the major task in the future. Certainly, to refine existing tools and

implement new tools are also very important.

To extend the system into the CAB field, we consider three kinds of implementation. There
are the integrated circuit (IC) layout, the printed circuit board (PCB) layout, and the whole sys-
tem integration. Since a chip, which is at the highest level of IC layout, is still a component in the
design database, the CAB techniques for PCB layout can be integrated into this system after the
necessary 1C layout tools are integrated According to the same reason, several PCBs which form
a complete system is also a component in the database. Therefore, tools for integrating a whole

system are needed and should be developed using the design methodology described herein.

LIST OF REFERENCES

LIST OF REFERENCES

[1] S. M. Rubin, Computer Aids for VLSI Design, Addison-Wesley Publishing Com-
pany, Reading, Massachusetts, chapter 1, 1987.

[2] Sun Microsystems, Inc., "Using Nroff and Troff on the SUN Workstation", Feb,
1986.

[3] G. Gabodi, P. Camurati, and P. Prinetto, "Experiences in Prolog-based DF'I‘ rule
checking", IEEE International Conference on Computer-Aided Design, pp. 909-
914, 1986.

[4] W. F. Clcoksin and C. S. Mellish, Programming in Prolog, 2nd edition, Springer-
Verlag, Berlin, Heidelberg, 1984.

[5] S. M. Rubin, Computer Aids for VLSI Design, Addison-Wesley Publishing Com-
pany, Reading, Massachusetts, chapter 8, 1987.

[6] B. McCalla, B. Infante, D. Brzezinski, and J. Beyers, ”ChipBuster VLSI Design
System", IEEE International Conference on Computer-Aided Design, pp. 20-23,
1986.

[7] D. S. Harrison, P. Moore, and R. L. Spickelmier, "Data Management and Graphics
Editing in the Berkeley Design Environment", IEEE International Conference on
Computer-Aided Design, pp. 24-27, 1986.

[8] L. N. Dunn, "IBM’s Engineering Design System Support for VLSI Design and
Verification", IEEE Design and Test of Computers, vol. 1, pp. 30—40, Feb. 1984.

[9] W. A. Burling, B. J. Bartels Lax, L. A. O’Neill, and T. P. Pennino, "Production
Design and Introduction Support Systems", AT&T Technical Journal, vol. 66, issue
5. Pp. 21-38, Sop/Oct. 1987.

[10] N. Weste and K. Eshraghian, Principles of CMOS VLSI Design, A system Perspec-
tive, Addison-Wesley Publishing Company, Reading, Massachusetts, 1985.

[11] M. H. Doshi, R. B. Sullivan, and D. M. Schuler, "THEMIS Logic Simulator - A
Mix Mode, Multi-Level, Hierarchical, Interactive Digital Circuit Simulator", 21st
Design Automation Conference, pp. 24-31, 1984.

[12] A. E. Ruehli and G. S. Ditlow, "Circuit Analysis, Logic Simulation, and Design
Verification for VLSI", IEEE Proceedings, vol. 71, pp. 34-48, Jan. 1983.

[13] R. E. Bryant, "Symbolic Verification of MOS Circuits", Proceedings of Chapel Hill
Conference on VLSI, pp. 419-438, 1985.

93

94

[14] C. E. Wu, L. M. Ni, and A. S. Wojcik, "Functional Recognition of Static CMOS
Circuits", IEEE International Conference on Computer-Aided Design, pp. 306-313,
1987.

[15] G. M. Nurie, "LOGAL+ -- A Hardware Description Language for Hierarchical
Design and Multilevel Simulation", IEEE International Conference on Circuits and
Computers, pp. 600-603, 1982.

[16] J. D. Nash and L. F. Saunders, "VHDL C‘ritique", IEEE Design & Test on Comput-
ers, pp. 54-65, Apr. 1986.

[17] R. Waxman, "Hardware Design Languages for Computer Design and Test", IEEE
Computer, pp. 90-97, Apr. 1986.

[18] C. W. Rosenthal and J. M. Dishman, "Computer-Aided Engineering and Design for
Interconnection Technology", AT&T Technical Journal, vol. 64, issue 4, pp. 57-69,
Jul/Aug. 1987.

[19] S. M. Staley and D. C. Anderson, "Functional Specification for CAD Database",
Computer Aided Design, vol. 18, no. 3, pp. 132-138, Apr. 1986.

[20] J. D. Ullman, Principles of Database Systems, 2nd edition, Pitman Publishing Lim-
ited, London, chapter 1 and 5, 1982.

[21] T. W. Williams, "VLSI Testing", IEEE Computer, pp. 126-136, Oct. 1984.

[22] S. M. Rubin, Computer Aids for VLSI Design, Addison-Wesley Publishing Com-
pany, Reading, Massachusetts, Appendix B and C, 1987.

[23] W. Andrews, "Silicon Compilers still struggling toward widespread acceptance",
Computer Design, pp. 37-43, Feb. 1988.

[24] R. E. Bryant, "A switch-level model and simulator for MOS digital systems", IEEE
Trans. Comput. , vol. 033, pp. 160-177, Feb. 1984.

[25] T. Lengauer and S. Nt'iher,"An analysis of ternary simulation as a tool for race
detection in digital MOS circuits", INTEGRATION, the VLSI journal , vol. 4, pp.
309-330, 1986.

[26] H. P. Chang and J. A. Abraham,"The complexity of accurate logic simulation",
Proceedings of IEEE International Conference on Computer-Aided Design . PP.
404-407, 1987.

[27] J. K. Ousterhout,"Crystal: A timing analyzer for NMOS VLSI circuits", Proceed-
ings of the 3rd Caltech VLSI Conference , pp. 57-69, 1983.

[28] N. P. Jouppi,"TV: An NMOS timing analyzer", Proceedings of the 3rd Caltech
VLSI Conference , pp. 71-76, 1983.

95

[29] W. F. Clocksin and M. E. Leeser,"Automatic determination of signal flow through
MOS transistor networks", INTEGRATION, the VLSI journal , vol. 4, pp.53-63,
1986.

[30] S. Even, Graph Algorithms , Computer Science Press, Rockville, Maryland,
Chapter 3, 1979.

[31] C.-T. Chen, Linear System Theory and Design , CBS College Publishing, New
York, Chapter 3, Section 7, 1984.

[32] D. L. Greer, "The quick simulator benchmark", VLSI systems design , pp. 40-49,
Nov. 1987.

[33] S. M. Trimberger, An Introduction to CAD for VLSI , Kluwer Academic Publishers,
Norwell, Massachuestts, Chapter 9, 1987.

[34] T. J. Schaefer,"A transistor-level logic-with-timing simulator for MOS circuits",
Proceedings of the 22nd Design Automation Conference . PP. 762-765, 1985.

[35] T. Hamilton, P. Harrod, and S. Dehgan,"MC68030 process and circuit technology",
Proceedings of IEEE International Conference on Computer Design . pp. 590-593,
1987.

[36] C. Mead & L. Conway, Introduction to VLSI System, Addison-Wesley, Reading,
Massachusetts, 1980.

[37] J. K. Ousterhout, et al., "MAGIC: A VLSI Layout System", let Design Automa—
tion Conference, pp. 152-159, 1984.

[38] A. Colmerauer, "Theoretical Model of Prolog 11", Logic Programming and Its
Applications, chapter 1, Ablex, Norwood, New Jersey, 1986.

[39] R. E. Bryant,"Symbolic Verification of MOS Circuits", Proc. Chapel Hill Confer-
ence on VLSI, pp.419-438, 1985.

[40] C. E. Wu, et al.,"A Rule-Based Circuit Representation for Automated CMOS
Design and Verification",Proc. 24th Design Automation Conference, pp. 786-792,
1987.

[41] C. Svensson and R. Tjt'imstro' m, "Switch-Level Simulation and the Pass Transistor
Exor Gate", IEEE Trans. Computer-Aided Design, vol. 7, pp. 994-997, 1988.

[42] J. Conklin, "Hypertext : An Introduction and Survey", IEEE Computer, pp. 17-41,
Sep.l987.

[43] C. Pedron and A. Stauffer, "Analysis and Synthesis of Combinational Pass Transis-
tor Circuits", IEEE Trans. CAD, vol. 7, no. 7, pp. 775-786, July 1988.