A 4-geometry maze router and its application on multiterminal nets

Abstract

The maze routing problem is to find an optimal path between a given pair of cells on a grid plane. Lee's algorithm and its variants, probably the most widely used maze routing method, fails to work in the 4-geometry of the grid plane. Our algorithm solves this problem by using a suitable data structure for uniform wave propagation in the 4-geometry, 8-geometry, etc. The algorithm guarantees finding an optimal path if it exists and has linear time and space complexities. Next, to solve the obstacle-avoiding rectilinear and 4-geometry Steiner tree problems, a heuristic algorithm is presented. The algorithm utilizes a cost accumulation scheme based on the maze router to determine the Torricelli vertices (points) for improving the quality of multiterminal nets. Our experimental results show that the algorithm works well in practice. Furthermore, using the 4-geometry router, path lengths can be significantly reduced up to 12% compared to those in the rectilinear router.

References

1. Ahuja, R. K., Mehlhorn, K., Orlin, J. B., and Tarjan, R. E. 1990. Faster algorithms for the shortest path problem. J. Assoc. Comput. Mach. 37, 2 (April), 213--223.]]
2. Barraquand, J. and Latombe, J. C. 1991. Robot motion planning: A distributed representation approach. Int. J. Robotics Res. 10, 6 (Dec.), 628--649.]]
3. Brimberg, J. 1995. The Fermat-Weber location problem revisited. Math. Programm. B 71, 1, 71--76.]]
4. Cieslik, D. 1991. The 1-Steiner-minimal-tree problem in Minkowski-spaces, Optimization 22, 2, 291--296.]]
5. Cieslik, D. 1998. Steiner Minimal Trees, Kluwer Academic Publishers, Dordrecht, The Netherlands.]]
6. Dí-az de León S., J. L., and Sossa A., J. H. 1998. Automatic path planning for a mobile robot among obstacles of arbitrary shape. IEEE Trans. Syst. Man. Cybernet. B. 28, 3 (June), 467--472.]]
7. Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numer. Math. 1, 269--271.]]
8. Dinic, E. A. 1978. Economical algorithms for finding shortest paths in a network, In Transportation Modeling Systems, Y. S. Popkov and B. L. Shmulyian, Eds. Institute for System Studies, Moscow, Russia, 36--44.]]
9. Dreyer, D. R. and Overton, M. L. 1998. Two heuristics for the Euclidean Steiner tree problem. J. Glob. Opt. 13, 1, 95--106.]]
10. Fawcett, J. and Robinson, P. 2000. Adaptive routing for road traffic. IEEE Comput. Graph. Appl. 20, 3 (May/June), 46--53.]]
11. Ganley, J. L. and Cohoon, J. P. 1994. Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles. Proceedings of the IEEE International Symposium on Circuits and Systems, vol. 1. 113--116.]]
12. Georgakopolulos, G. and Papadimitrious, C. H. 1987. The 1-Steiner tree problem. J. Algorith. 8, 1, 122--130.]]
13. Goldberg, A. V. 2001. Simple shortest path algorithm with linear average time. Proceedings of the European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, Vol. 2161. Springer-Verlag, Berlin Germeny, 230--241.]]
14. Hart, P. E., Nilsson, N. J., and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybernet. 4, 2, 100--107.]]
15. Henzinger, M. R., Klein, P., Rao, S., and Subramanian, S. 1997. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55, 1 (Aug.), 3--23.]]
16. Joel, J. H. 1976. Some variations of Lee's algorithm. IEEE Trans. Comput. C-25, 1 (Jan.), 19--24.]]
17. Hwang, F. K. 1979. An O(n log n) algorithm for suboptimal rectilinear Steiner trees. IEEE Trans. Circ. Syst. CAS-26, 75--77.]]
18. Jan, G. E., Lin, M. B., and Chen, Y. Y. 1997. Computerized shortest path searching for vessels. J. Marine Sci. Tech. 5, 1, 95--99.]]
19. Kahng, A. and Robins, G. 1992. A new class of iterative Steiner tree heuristics with good performance. IEEE Trans. Comput.-Aided Des. Integrat. Circ. Syst. 11, 7, 893--902.]]
20. Kimmel, R., Amir, A., and Bruckstein, A. M. 1995. Finding shortest paths on surfaces using level sets propagation. IEEE Trans. Patt. Anal. Mach. Intell. 17, 6 (June), 635--640.]]
21. Kuhn, H. W. 1973. A note on Fermt's problem. Math. Programm. 4, 98--107.]]
22. Lee, C. Y. 1961. An algorithm for path connections and its applications. IRE Trans. Electron. Comput. EC-10, Sept., 346--365.]]
23. Lee, J. H., Bose, N. K., and Hwang, F. K. 1976. Use of Steiner's problem in suboptimal routing in rectilinear metric. IEEE Trans. Circ. Syst. CAS-23, 470--476.]]
24. Lin, Y. L., Hsu, Y. C., and Tsai, F. S. 1990. Hybrid routing. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 9, 2 (Feb.), 151--157.]]
25. Ogniewicz, R. L. and Kubler, O. 1995. Voronoi tessellation of points with integer coordinates: Time-efficient implementation and online edge-list generation. Patt. Recogn. 28, 12 (Dec.), 1839--1844.]]
26. Rubin, F. 1974. The Lee path connection algorithm. IEEE Trans. Comput. C-23, 9 (Sept.), 907--914.]]
27. Sherwani, N. A. 1999. Algorithms for VLSI Physical Design Automation, 3rd. ed. Kulwer Academic Publishers, Boston, MA, 260--279.]]
28. Smith, J. M.-G., Lee, D. T., and Liebman, J. S. 1981. An O(n log n) heuristic for Steiner minimal tree problems on the Euclidean metric. Networks 11, 1, 23--39.]]
29. Teig, S. L. 2002. The X architecture: Not your father's diagonal wiring. In Proceedings of the 2002 International Workshop on System-Level Interconnect Prediction (San Diego, CA, Apr. 6--7), ACM Press, New York, NY, 33--37.]]
30. Thorup, M. 1999. Undirected single-source shortest paths with positive integer weights in linear time. J. Assoc. Comput. Mach. 46, 3, 362 -- 394.]]
31. Winter, P. 1993. Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs. Discrete App. Math. 47, 2, 187--206.]]
32. Xing, Z. and Kao, R. 2002. Shortest path search using tiles and piecewise linear cost propagation. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 21, 2 (Feb.), 145--158.]]

Index Terms

• Hardware

  • Electronic design automation

    • Physical design (EDA)

      • Placement

      • Wire routing