A heuristic global router for polycell layout

A novel heuristic global routing algorithm has been developed and implemented. The advantage of using heuristics for routing is that they can achieve a close-to-optimal solution in a reasonable amount of computation time. It is shown that in most cases the router achieves as good or better layout area and total wirelength as the TimberWolf global router which uses the inherently time-expensive technique of simulated annealing. It is concluded by using good heuristics that the potentially computation-intensive problem of optimal global routing can be solved efficiently without trading off a significant amount of optimality