[fbq]Hello,
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.
Thanks
VSD Team
