read_sdc is been considered as a very critical command in EDA world, as this is the command which defines your specifications, and if not written and interpreted correctly, can lead a huge delay in tapeout cycle.Continue reading
Hello ….continuing from Part1 and Part2 After the terrible layout we saw in last 2 blogs, without considering euler’s path, its now time to mend things and do it the right way, i.e. create an accurate gate input ordering using euler’s path, extracting stick diagram and finally drawing the layout. […]Continue reading
Hello ….lets continue from here So I have been bragging about that ‘art of layout’ is a combination of euler’s path and stick diagram. But you need a proof why am I saying that Let’s first find out what happens if we decide to go only by stick diagram and […]Continue reading
Hello I wrote about euler’s path and stick diagram in two different blogs, but now is the time to show you how are they connected. It’s simple and, seems, they can’t be separated out from each other. To prove that, let’s take a random logic using the below pull-up network…… […]Continue reading
…and that’s exactly the perception that I am determined to solve. People in my physical design course have had a glimpse of design rule check (DRC) step as a part of physical design flow, where I had mentioned that I will get back to DRC concepts. Well, I did…. in my newly (pre)launched […]Continue reading
On the Lines followed by people all over the globe “Learn By Doing”, last week, I was browsing through the internet to collect information about routing algorithms, and check out, here’s what attracted me.
Maze Routing – Lee’s Algorithm
It’s very basic, with immense in-depth knowledge on algorithm. Might be, as I was highly engrossed in tuning timing parameters of Static Timing Analysis for all these years, and never thought anything outside Timing, so found the algorithm fascinating.
I found it so interesting, and flowed with topic and explored more on Line-Search Algorithm, Steiner Tree Algorithm, etc. Well, then suddenly realized, how interesting it would be to implement a pictorial view of the algorithm on the design which I had been doing so far on Udemy.
And it begun, here you go, below you will find some cool images describing about the algorithm. Also, I will come up with my own lectures on Algorithms, very soon. Also, learnt a lot, how difficult, and interesting job it would be to route only 2 points. Just imagine (from an algorithm point of view), how interesting it would be to have our own algorithm to route multiple points and, eventually completely route your own design.
So, back to the saying “Learn By Doing” Routing, by itself, means an algorithm to connect at least 2 points using shortest available path and using real physical wires, while maintaining recommended wire/via design rules (DRC).
Lee’s Algorithm i.e. Maze Routing, is, perhaps, the most widely used algorithm to find path between 2 points. Let’s have a glimpse of the algorithm using below images: Assume, we have to connect cell1 with cell2, as shown in below image:
The 3 steps to do this are:
*To identify the ‘Source’ and ‘Target’ pins for cell1 and cell2 and create Routing grid as shown below.
Now since, the data flows from cell1 to cell2, the output of cell1 becomes source ‘S’ and the input of cell2, becomes target ‘T’
* Based on the distance of wave-front, from ‘S’, the adjacent grid boxes are progressively filled till it hits target node ‘T’ , as shown in below images
* The shortest and the least detoured path is back-traced from ‘T’ to ‘S’, shown in below images
Lee’s Algorithm guarantees there is exists a valid path and it’s the shortest path.
But, this algorithm is too time and memory consuming, To overcome, these short-comings, there are other more advanced algorithms like Line search Algorithm, Steiner Algorithms, etc.
Let’s look into those algorithms in detail in Algorithms course which I am currently working on and will be releasing soon. You can also get access to all images related to Routing Algorithm lectures. Find out how in my next post.