Exploring EDA Algorithms with the Boost Graph Library

Introduction

Electronic design automation (EDA) algorithms are very much graph-based. For example, a logic circuit can be considered as a graph of vertices, each vertex representing some digital function. A simulation algorithm will start at the inputs and propagate the changes until output vertices are reached. An automatic test pattern generation (ATPG) algorithm may start with a simulated fault on one edge, and work backwards and forwards to find the set of inputs that will make the fault observable at some set of outputs.

This article describes a tool that I created to learn and explore EDA algorithms on different circuits. Since this is a learning tool, I concentrate more on how I leveraged other open source tools and C/C++ Users Journal (CUJ) contributions to put the infrastructure together.

The outcome is a medium-sized project (started by a letter from Michael Solem in a March 2002 CUJ; see references) that:

• currently builds and runs (which provides a working baseline),
• can be used as a C++ and BGL learning tool,
• and, can be used as an EDA algorithms learning tool.

The most recent CUJ article on Boost Graph Library (BGL) (Vitaly Ablavsky's "Applying BGL to Computational Geometry"; see references) hints at VC6 compiler problems and encourages the user to take the effort to learn BGL. I've provided a sidebar on the common problems encountered and their solutions or workarounds.

Finally, I'll also illustrate the value of reading CUJ, and, getting the CD-ROM ( in my case, Release 4) for past articles and source code (see sidebar 2).

BGL provides an executable specification for graph algorithms

The BGL (Boost Graph Library; see references) provides standardized access to generic graph structures and algorithms so that many problems that require a graph solution can be easily mapped and implemented, in a reusable manner. This allows the user to concentrate on his problem area and rely on BGL's high-level graph concepts for graph access and manipulation.

BGL can be adapted to work with any pre-existing graphs by creating adaptors for the target graph format. In fact, adaptors already exist for use with AT&T's Graphviz (see references), LEDA, and Stanford Graphbase. This means that a graph algorithm developed with BGL can be reviewed and, better yet, executed by peers anywhere in the world. Test graphs can similarly be exchanged and imported.

Software infrastructure

In order to use a graph algorithm, some software infrastructure for the following aspects needed to be created:

1. circuit visualization
2. circuit input/output
3. circuit representation
4. multivalued logic
5. trace and debug

As it turns out, BGL provided a simple and effective solutions for 1-3, while browing the CUJ CD-ROM provided reusable components for 4 and 5.

Using BGL in an ATPG algorithm

I was interested in a basic automatic test pattern generation ( ATPG ) algorithm as described in Application-Specific Integrated Circuits by Michael John Sebastian Smith (see references). Although I could follow the high-level description given, there were details missing, and I decided to implement it with BGL to get a flavor for what it actually took.

The problem can be stated as follows : Given an electrical cicuit and a selected fault on one net (either stuck-at-one or stuck-at-zero), we want to find the set of inputs that will make the fault observable at an output.

Informally, the algorithm can be described as :

1. Set the objective vertex to the vertex thats input is the fault to be simulated.
2. Start with an objective vertex or set of objective vertices
3. Backtrace from the objective vertex to input nodes, and set the input nodes to values that will help meet the objective. This generally means using enabling logic values so that the fault will be propagated.
4. For each backtrace set of input nodes and values, simulate the circuit to see if it is possible to reach some output. As the simulation progresses and the fault is propagated, update the D Frontier. If we reach an output, we are done. Repeat with 2, picking an objective from the D Frontier.

If you are wondering what the D Frontier is, that's exactly what I wondered after reading the textbook. By attempting to implement the algorithm, it quickly became clear why and how we need this structure. This class is encapsulated in the source file, DFrontier.hpp.

To implement step 3, BGL has the concept of a reverse_graph that allows a directed graph to be traversed backwards. In fact, the code below shows the implementation used in the backtraceVertex function:

backtraceVertex(){
...
BacktraceVisitor<reverse_graph><G> > backtraceVisitor(_g,_e,_setVS); depth_first_visit(*_pRG,v,backtraceVisitor,&GraphColorMap[0]);
...
}

Step 4 requires a special kind of forward graph traversal.

I originally started using a BGL depth first search (DFS) visitor because the simulation can stop as soon as we reach an output, and we want to drive an input as far as we can before trying another input. There was a catch — the DFS does a complete traversal and there is no provision to break out of the search early.

Posing the question on the BGL Web site, the main suggestion was to throw an exception in the visitor code and catch it in the calling code. I found an alternate solution by looking at the BGL's depth_first_search.hpp and changed a line of depth_first_visit_impl traversal loop from :

for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { ... }

to :

for (tie(ei, ei_end) = out_edges(u, g); (ei != ei_end) && (vis.continueSearch()); ++ei){ ... }

By exposing a function called continueSearch() in my DFS visitor, I could use it to break out of a DFS traversal when I needed to.

Unfortunately, further testing revealed a flaw in the use of DFS. It turns out that the propagation of simulation values may require visiting a vertex several times, essentially as many times as changes arrive at the inputs. A DFS traversal only visits a vertex once. I ended up with a custom traversal implemented in the pair of functions propagateVertex and propagateChange. The beauty of using BGL is that this sort of discovery and rework is much easier to do.

Circuit visualization and IO

GraphViz is the short name for the Graph Visualization Project. Developed at AT&T and placed in open source, it provides a collection of tools for manipulating graph structures and generating graph layouts (see references).

My motivation for using Graphviz came directly from the BGL documentation. "The Graphviz package provides tools that automatically layout and draw graphs. It is available at http://www.research.att.com/sw/tools/graphviz/. In fact, all of the graph drawings in the BGL book (see references) were created using Graphviz. The Graphviz tools use a special file format for graphs, called dot files. BGL includes a parser for reading this file format into a BGL graph".

BGL's built-in support for Graphviz graphs and digraphs, saves me the time in building a graph visualization system. Besides, my requirements were quite basic:

1. Add labels to edges and vertices (typically by editing the .dot file)
2. Viewing the input and output graphs (with the dotty utility)

There are two general ways of using Graphviz with BGL. One is to use it solely for visualization. In this case, the code will copy the Graphviz graph or digraph into an internal graph structure for processing, and then write out a Graphviz graph at the end. The other way is to directly operate on the Graphviz graph/digraph itself. The value of the property called "label" is displayed in the dotty window when the graph is viewed. This seemed simpler, and was the approach I took. However, there was one minor problem — the default definition of GraphvizDigraph in Graphviz.hpp is:

typedef subgraph<adjacency_list><boost::vecS, boost::vecS,
boost::directedS, GraphvizVertexProperty, GraphvizEdgeProperty,
GraphvizGraphProperty> > GraphvizDigraph;

In order to traverse the diagraph in both directions, this line has to be changed to:

typedef subgraph<adjacency_list><boost::vecS, boost::vecS,
boost::bidirectionalS, GraphvizVertexProperty, GraphvizEdgeProperty,
GraphvizGraphProperty> > GraphvizDigraph;

The bglgraphviz.lib then has to be rebuilt and linked in with the main program.

Circuit representation

An electrical circuit consists of logic units or devices and electrical connections (called nets) between them. A logic unit's output may be connected to the inputs of several other logic units. Special devices called inputs and outputs pertain to where electrical signals may be applied and observed/measured.

The nature of outputs driving inputs suggests that a GraphvizDigraph is a natural representation. Vertices are used to represent the logic devices. For simplicity, the vertex label has the format <name:func>. Logic values are read and written on the edge labels. BGL provides a convenient syntax to access these properties. They look like vertexMap[vertexId]["label"] for vertex labels and edgeMap[edgeId]["label"] for edge labels.

While a GraphvizDigraph captures the essential pieces of a circuit for my purposes, I should point out that its use implies some simplifications:

1. In an electrical circuit diagram, the output of a logic unit X, can be connected to several other logic units, A, B, and C, for example. This is approximated by attaching multiple directed edges from X to A, X to B, X to C. Internally, our algorithm will set all output edges to the same value.
2. I was not able to use custom shapes in Graphviz. Thus, the vertex shapes defaulted to ellipse, instead of the standard electrical model symbols (e.g., triangle for inverters, half-ellipses for nands and nors). I instead used the naming convention (U2:not, U3:nand, U5:in, etc.) to specify the different logic units.
3. Edge connections are not orthogonal as in standard electrical circuits, but curved.

Multivalued logic

The ATPG algorithm uses a 5 value logic system called the D-Calculus (Michael John Sebastian Smith's Application-Specific Integrated Circuits; see references). The 5 basic logic values are ZERO, ONE, D, _D, and X. D and _D are used to represent a simultaneus good circuit/bad circuit state. For example, D is used to represent a ONE in a good circuit, and a ZERO in a bad circuit, while _D is used to represent a ZERO in a good circuit, and a ONE in a bad circuit. The X is the standard "undefined" or "don't care" state. Xs are typically used to initial circuits to simulate a random power-up situation.

The five-value logic system is ideally implemented as a enum. However, the C++ enum has several shortcomings that limit their usage. Art Walker's enum++ ( see references ) is a tool that generates first-class enumerations that provide for type-safe, bounded symbol sets, with IO support built in. I only needed to add additional support for functors.

With a simple one-line input specification to the enum_gen tool, like so:

enum DLogic{ ZERO,ONE,D,_D,X};

and I got working code.

Running the program

Figure 1

The program was developed on VC6 Sp3 and Comeau 4.3.0.1. At the time of writing, Boost was at 1.25.1. The source code distribution contains a test directory, with a sample Not2.dot circuit. The Graphviz dotty tool can be used to view the circuit/graph.

By invoking atpg.exe -atpg -r Not2.dot -w Not2_out.dot, the output circuit Not2_out.dot is created and again can be viewed with dotty. Use atpg.exe -h for some usage information.

Figure 1 shows how the circuits look on my machine.

References

"A Handy Debugger Class", Maurice J Fox, C/C++ Users Journal, April 2001
"An STL Error Message Decryptor for Visual C++", Leor Zolman, C/C++ Users Journal, July 2001
"Application-Specific Integrated Circuits", Michael John Sebastian Smith, Addison-Wesley, Section 14.5.1 The D-Calculus
"Application-Specific Integrated Circuits", Michael John Sebastian Smith, Addison-Wesley, Section 14.5.2 Basic ATPG Algorithm
"Applying BGL to Computational Geometry", Vitaly Ablavsky, C/C++ Users Journal, August 2002
"BUG: Full Koenig Lookup Works Only For Operators", Knowledgebase article Q242190
"Enum++ - an enum class generator", Art Walker, C/C++ Users Journal, March 1999
"Migrating to Namespaces", Herb Sutter, Dr. Dobb's Journal, October 2000
The Boost Graph Library (page 82), by Jeremy Siek and others, Addison-Wesley 2001
"We Have Mail", letter from Michael Solem, C/C++ Users Journal, March 2002

Web sites

Boost Graph Library at http://www.boost.org/libs/graph/doc/table_of_contents.html
Graphviz tools at http://www.research.att.com/sw/tools/graphviz/

About the Author

Kwee Heong Tan is a software engineer with 9 years of experience in C/C++ and 6 years in Perl. He holds an M.Sc in Computer Science and a B.E. in Electrical Engineering. He has worked for the EDA companies Mentor Graphics and Genedax Design Automation over the last 13 years on various tools and products like library management, VHDL validation, IC layout and verification, and design framework on both Unix and Windows. He is currently between jobs and can be reached at [email protected].