|
Electronic Design Automation (EDA) algorithms are typically graph-based. For example, a logic circuit can be modeled as a graph of vertices, each vertex representing a digital function. This article describes a tool for exploring EDA algorithms with the help of the Boost Graph Library (BGL).
July 01, 2003
URL:http://www.drdobbs.com/exploring-eda-algorithms-with-the-boost/184401676
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:
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).
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.
In order to use a graph algorithm, some software infrastructure for the following aspects needed to be created:
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.
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 :
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.
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:
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:
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.
 |
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.
"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/
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].
I spent a great deal of time working through issues specifically related to my VC6 compiler. Having had to solve these issues myself, it seems proper that I describe them briefly for the benefit of those intending to use my program.
Typical problem:
I first saw this error when trying to use both write_graphviz and read_graphviz functionality in my code. Notice it is a link error:
dfs2.obj : fatal error LNK1179: invalid or corrupt file: duplicate
comdat "?policies@?$iterator_adaptor@Vconst_iterator@ ...
Solution:
Select "Project Settings"/"C/C++" Tab/"Optimization" Category, and change from (default) "Disable" to "Only _inline". While in the dialog, take out Settings/"C/C++"/Debug Info:Program Database for "Edit & Continue", to avoid D2016 : '/ZI' and '/Ob1' that command-line options are incompatible.
At various times as I used different graph algorithms, I would get C1076: "compiler limit : internal heap limit reached." This has to be added directly to the C/C++ Preprocessor scroll window (for example, /Zm200).
The lack of Koenig lookup in VC6 shows up in different guises (see references). For example, in one line of my code:
std::transform(startEI,endEI,
std::back_inserter(vSignals),
GetSignalFunctor
This also points to the need for incremental build/compile because multiple errors can occur in a line of template call.
When property_maps are used, sometimes passing the wrong type (edge instead of vertex, or vice versa) will cause a fatal error C1001: INTERNAL COMPILER ERROR. Example :
_EdgeAttrMap[v]["label"]=signal; // edge accessed with vertex
When I subscribed to CUJ two years ago, I also bought its Release 4 CD-ROM so that I could have access to past issues. This has turned out to be a time saver on this project because, as mentioned in the section on "Multivalued logic", I was able to find and use Art Walker's enum++, with some minor enhancements (see references).
Another very useful class that I incorporated into my program is Maurice Fox's Debug class (see references). It is a general purpose trace, debug, and timing class, which allows me to view the calling tree of functions with the outputs I specify.
I was able to extend it for my purposes, for example, to show a sample hierarchical trace:
* => backtraceGraph 1: vertex label== = U3:nand ...
** => discover_vertex 1: vertex label== = U3:nand ...
** => discover_vertex 1: vertex label== = U2:nand ...
** => discover_vertex 1: vertex label== = J:in ...
** => discover_vertex 1: vertex label== = K:in ...
** => discover_vertex 1: vertex label== = M:in ...
* => implicateVertex 1: vertex label== = J:in ...
** => setAllVertexOutputs 1: vertex label== = J:in ...
** => discover_vertex 1: vertex label== = J:in ...
** => discover_vertex 1: vertex label== = U2:nand ...
This Debug class can be compiled away with a DEBUG_OFF define, although as Maurice Fox says in his article, "Usually you're just kidding yourself when you do that, though". In fact, the performance overhead in several projects in which I have used Debug are typically less than 1%, so I tend to agree with Maurice and leave the class compiled in.
Another tool that comes in handy is Leor Zolman's STL Decryptor ( see references ).
Similarly, when you look at the code, you'll see how I manage namespaces by following Herb Sutter's "Migrating to Namespaces" ( see references ) recommendations.
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.