Hi
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. The 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 realised, 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:
