Using 'graph isomorphism' in Electronic Design Automation
Have you heard about Electronic Design automation (EDA) ?
Wikipedia says: "EDA is a category of software tools for designing electronic systems such as integrated circuits and printed circuit boards. The tools work together in a design flow that chip designers use to design and analyze entire semiconductor chips. Since a modern semiconductor chip can have billions of components, EDA tools are essential for their design."
This article tries to highlight how EDA can take advantage of graph theory algorithms (specifically isomorphism) in order to solve one of the fundamental problem which is checking if two netlists are the equivalent.
The image below shows the nMOS & pMOS symbols.
Image shows the nMOS & pMOS symbols (the difference is an arrow direction).
CMOS consists of 4 terminals [Source, Drain, Gate and Bulk].
Hint: remember the terminals of the above devices, we will use them in graph representation
Schematic representation
Now, we will move to the schematic part, Logic gates such as NAND, NOR, XOR, Flip-Flop etc.. could be represented in transistors level using nMOS & pMOS devices.
VLSI books can help in designing logic gates using the transistors.
I recommend [CMOS VLSI Design: A Circuits and Systems Perspective by David Harris and Neil Weste] book for more information.
Chapter 4 explains Logic to schematic representation.
Below figure shows the transistor schematic representation for NAND gates and their netlist data.
By visual observation, the two netlists represent the same logic gate (NAND) even though the transistors names, nets and inputs names are different (we excluded vdd/gnd for simplicity).
But how can we check that programmatically?
Netlist can be considered as an undirected graph
>> Representing netlist using graph could help us . .
First of all, graphs are one of the most used data structures now, they are being used in social media [facebook, twitter instagram . .], maps etc.
Graph is a set of items connected by edges.
Each item is called a vertex or node.
Formally, a graph is a set of vertices and a binary relation between vertices,
adjacency[1].
[1] https://xlinux.nist.gov/dads/HTML/graph.html [cited on 31-Jul-2017]
Our Graph properties:
Node: Transistors names, transistors terminals, ports, internal nets. In this case all transistor terminals signals will be represented by node except bulk (will not be included).
Edge: any binary connection between port-terminal, internal net-terminal & transistor name-{terminal, port, internal net}.
As shown in the below figure, two schematics are represented by graphs. They have the same nodes number and connectivity. The only differences are: transistors, nets and ports names.
But how can we check if the two netlists graphs above are equivalent?
Isomorphism algorithm can do that!
>>Isomorphism definition:
'Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. Formally, two graphs and with graph vertices are said to be isomorphic if there is a permutation of such that is in the set of graph edges iff is in the set of graph edges [2]'.
[2]. http://mathworld.wolfram.com/IsomorphicGraphs.html [cited on 31-Jul-2017]
Isomorphic Graphs
To prove two graphs are isomorphic you must give a formula (picture) for the functions f and g. If two graphs are isomorphic, they must have[3]:
- The same number of vertices
- The same number of edges
- The same degrees for corresponding vertices
- The same number of connected components
- The same number of loops
- The same number of parallel edges
[3]. http://www.uow.edu.au/~bmaloney/wuct121/GraphsWeek10Lecture2.pdf [cited on 31-Jul-2017]
Coding . .
- Reading netlist files
.subckt NAND_1 vdd vss x in_0 in_1
% MOS Drain Gate Source Type
pMOS_0 x in_0 vdd pmos
pMOS_1 x in_1 vdd pmos
nMOS_0 node_0 in_1 gnd nmos
nMOS_1 x in_0 node_0 nmos
nand1.txt
.subckt NAND_2 vdd gnd out A1 A2
%MOS Drain Gate Source Type
MN0 net_1 A2 gnd nmos
MN1 out A1 net_1 nmos
MP0 out A1 vdd pmos
MP1 out A2 vdd pmos
nand2.txt
#!/usr/bin/env python
from collections import namedtuple
trans_data = namedtuple('transistor_data', ['trans_name', 'drain', 'gate', 'source'])
def read_netlist(fp):
""" Reads netlist file """
trans_all = []
for line in fp:
if 'nmos' not in line and 'pmos' not in line:
continue
line = line.split()
trans = trans_data(trans_name=line[0],
drain=line[1],
gate=line[2],
source=line[3])
trans_all.append(trans)
return trans_all
def main():
""" Main func """
nand1_netlist = read_netlist(open('nand1.txt').readlines())
nand2_netlist = read_netlist(open('nand2.txt').readlines())
if __name__ == '__main__':
main()
2. Creating undirected graph using networkX library:
#!/usr/bin/env python
?
from collections import namedtuple
import networkx as nx
import networkx.algorithms.isomorphism as iso
import matplotlib.pyplot as plot
trans_data = namedtuple('transistor_data',
['trans_name', 'drain', 'gate', 'source'])
def read_netlist(fp):
""" Reads netlist file """
trans_all = []
for line in fp:
if 'nmos' not in line and 'pmos' not in line:
continue
line = line.split()
trans = trans_data(trans_name=line[0],
drain=line[1],
gate=line[2],
source=line[3])
trans_all.append(trans)
return trans_all
def create_graph(netlist):
""" Represent netlist using graph structure"""
graph = nx.Graph()
for tran in netlist:
graph.add_edges_from([(tran.trans_name, tran.drain),
(tran.trans_name, tran.gate),
(tran.trans_name, tran.source)])
nx.draw(graph, with_labels=True)
plot.show() # To plot graphs
return graph
def main():
""" Main func """
nand1_netlist = read_netlist(open('nand1.txt').readlines())
nand2_netlist = read_netlist(open('nand2.txt').readlines())
nand1_g = create_graph(nand1_netlist)
nand2_g = create_graph(nand2_netlist)
if nx.is_isomorphic(nand1_g, nand2_g):
print 'The two netlist are equivialant !'
else:
print 'The two netlist are NOT equivialant '
if __name__ == '__main__':
main()
#The next lines plots the graphs fro netlists using matplotlib:
nx.draw(graph, with_labels=True)
plot.show() # To plot graphs
graphs as matplotlib draws is shown below:
Let us try to change the netlist for NAND_2 and check the results. The below graph shows how extra node exists in NAND2, that makes graphs not isomorphism.
Output: The two netlist are NOT equivialant
What if we want to add more constraints ?
If we want to consider two netlists equivalent if the ports names are the same for two netlists ?
This will be discussed in the next article.