Graph Extractor from Spice Netlist & Euler Path Generator

This repository cointains source code that is aimed at converting a spice netlist (digital) to its corresponding layout. The layout is generated using the Open Source Tool named Magic. Here, fn.sp contains the spice netlist of the function Y = ~[(B+D).(A+C)+(E.F)]. We're trying to automatically generate layout for this boolean fuction. This project is initially built for digital circuits and later to be scaled/modified for analog circuits.

The project is in a very early stage and might not yet be ready for productive use.

Assumptions -- The Design Engineer/Characterization Engineer has designed the circuit and performed the circuit simulations and has generated the spice netlist. A tutorial on how to perform circuit simulations using ngspice can be found here.

A very brief description of this project can be found here. This work has been carried out by going through Mr. Kunal Ghosh's lecture on Custom Layout. You can have a look at the course here.

Description

1. The first step is to extract the graph information (edges & nodes etc) from the spice netlist. (The ideal way to do this is to tree-ify the netlist. This is a very hard problem and it falls under Tech Mapping Problem.)

2. The second step is to generate the Euler Path (common to both PMOS & NMOS networks) from the graph for optimal placement of Poly's.

3. Next, we paint the layout using the stick diagram.

4. Final Step - DRC Check/Clean

Note -- There are some pre-requisites to understand/reproduce this project.

1. Working Knowledge of Data Structures and Algorithms in any programming language. I have used C++ here.
2. Knowledge of Graphs.
3. Knowledge of grep/awk/sed & tcl.

You can get proficient in programming by following the steps given here in the Competitive Programming Section. A tutorial on finding the Euler Path can be found here. The layouts are drawn using Magic Layout Tool. Installation instructions can be found here.

Conventional Work Flow

It takes enormous amount of time to calculate the positions of each component like distance between the poly, total height & width of the cell, spacing between the cells etc and draw the layout adhering to the DRC rules. This project is an attempt to reduce the Engineering Effort that is put in drawing the layout.

Layout Generation Engine (An abstract flow diagram)

A brief document on this layout_generator flow can be found here.

Euler Path Existence (pseudo-code)

Input : Graph containing vertices and edges.
Output : Returns Euler Path Existence.
There are basically 4 methods. (Note: This is the pseudo code for Euler Path Existence and not for Euler Path Generation.)

1. addEdge
2. DFS
3. isConnected
4. isEulerean

---

0. Initialize graph 'adj' and no. of Vertices V
1. addEdge(node1, node2)

2. DFS(vertex, visited[])
3. visited[vertex] <- true //Mark the current node as visited
4. list < int> :: iterator node //initialize iterator to adjacency list
5. foreach (node in adj)
6. if(!visited[i])
7. DFS(i,visited) //recursive call

8. isConnected() //method to check if the graph is connected
9. foreach (i in V)
10. visited[i] <- false //mark all nodes as not visited
11. foreach(i in V) //Find vertex with non-zero degree
12. if (adj[i].size() != 0) break;
13. if(i==V) return true
14. DFS(i,visited)
15. foreach(i in V)
16. if(visited[i]==false & adj[i].size>0) return false else return true

17. isEulerean()
18. if(isConnected==false) return 0

/* 0 --> If graph is not Eulerian
1 --> If graph has an Euler path (Semi-Eulerian)
2 --> If graph has an Euler Circuit (Eulerian) */

19. foreach(i in V)
20. if(adj[i].size() & 1) odd++
21. if(odd>2) return 0 else return (odd)?1:2

---

Details

Step 0 -- Clone the repository

$  git clone https://github.com/sethupathib/final_layout_generator.git

Step 1 -- Extract edges/node information from the spice netlist. The edges and node details are extracted from the Netlist using grep+awk+sed. (There is some work that is to be done here). The shell script to extract the node/edge details can be found here. The extracted file has to be further processed to feed the algorithm to get the Euler Trail. (Work Pending)

• Change directory to "Execution"

$  cd Execution

• Run the shell script.

$  source read_spice.sh

• You get the following ouput.

• Input & Output File Comparison

• This output file needs some more processing to be fed to the algorithm. (I'm currently work on this right now). Comparison of the obtained file and the file format that the algorithm requires -->

Step 2 -- Feed the extracted file to the Euler Trail finding algorithm. Source code for the algorithm can be found here. The algorithm takes majorly 2 values. They are -->

1. Total number of edges.
2. The Edge List.

Command to run the algorithm is as follows.

$  g++ EulerTrail.cpp -o EulerTrail

$  ./EulerTrail < inputs.txt

You get the following output. This is the Euler Path for the combined graph

Pending Work

• The file conversion needs to be worked upon.
• Graph Splitting. Need to go through this. It's very important. As of this moment, the algorithm only returns the Euler Path for the Combined (PMOS + NMOS) graph.
• Layouting for the given PDK's seems to be a very hard task.
• Routing the Layout. (This seems to an extremely difficult task mainly because it is done after placing the poly's in the design)
• Pass Transistor's. Layouting for pass transistor logic is a bit complicated as it requires adding dummy nodes/edges and forming the graph.
• Random Graph Generator (This is important for testing the algorithm)
• To know more about bridges and articulation points in a graph.
• I need to solve a lot of problems and get to know about some advanced concepts like Dynamic Programming and Memoization applied on graphs.
• Running ALIGN on the reference designs and getting a functionally correct and DRC clean layout.

Major Contributions by the Author

• There were two major things that created a lot of impact.

1. Graph Extraction and Euler Path Generation.
2. Researching about various other projects on GitHub that does "Analog Layouting". That's where I found out about ALIGN and MAGICAL and this research led to a lot of things. It basically gave a hope to the fellow designers that analog layouts can be automatically generated.

Note

• A usable version of this software is available here (Digital Layout Generator). It has been developed by Thomas Kramer. (PhD @ ETH-Zurich).
• This objective of this project is to replicate the work done by Thomas thereby getting an exponential learning curve.
• The usage of the tool is quite basic. However, developing the entire toolchain from scratch was a major challenge.
• A CS grad can crack this problem with a little effort. However, I am not from CS. Hence, it took me a lot of time to get acquainted with CS concepts.
• Euler Path finding problem is a DIV-2/D problem on codeforces.com.
• Euler Path Finding on an Undirected Graph.
• Bridges in a Graph
• This project was initially aimed at generating Analog Layouts. However, that seemed to be an Herculean task. So, we tried for Digital Layouts. There are still a lot of things to be done. (Layouts for various PDK's, DRC's etc). While researching about this, we discovered another project that does the exact same thing. You can find it here. This (ALIGN - Analog Layouts Intelligently Generated from Netlists) is a massive multi-million dollar project involving multi-org & multi-institutional NDA's and top researchers in the world and funded by DARPA, Department of Defense, USA.
• After we got to know more about ALIGN, we started pivoting and developing over ALIGN infrastructure. We are in touch and working together with the researchers on ALIGN.

Post Script

• We had a tough time understanding the usage of ALIGN. However, we were able to crack it with some efforts. We were able to get the layouts of the reference designs that came with ALIGN and we tried to run ALIGN on some of our designs. We're not yet sure about the correctness since we haven't done any post layout simulations. Some of the layouts that we obtained can be found below. A tutorial on how to use ALIGN can be found here.

Layout of an Operational Transconductance Amplifier --

Layout of bandgap reference design --

• For more details, you can check here.
  
• Details on ALIGN architecture can be found here.

Author

Sethupathi Balakrishnan, EDA Researcher, EDA Lab, NTU-Taiwan

Acknowledgments

• Kunal Ghosh, Director, VSD Corp. Pvt. Ltd.
• Philipp Gühring, Software Architect, LibreSilicon Assocation

Contact Information

• Sethupathi Balakrishnan, SoC Design Engineer, b.sethupathi@gmail.com
• Kunal Ghosh, Director, VSD Corp. Pvt. Ltd. kunalghosh@gmail.com
• Philipp Gühring, Software Architect, LibreSilicon Assocation, pg@futureware.at