An efficient routing database

ABSTRACT

Routing is an important problem in the process of design creation. In this paper, we focus on the problem of designing a database for the non-partitioned routing problem. New technology libraries describe constraints that are hard to manage in grid-based approaches to the routing database. While general region query based data-structures have been proposed, they typically suffer from speed problems when applied to large blocks. We introduce an interval-based approach. It provides more flexibility than grid-based techniques. It exploits the notion of preferred direction for metal layers to manage the memory efficiently. It supports efficient region queries. We finally present a comparison study for real industrial designs on this database.

REFERENCES

• 1: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 2: C. Y. Lee, "An algorithm for path connection and its applications", IRE Transactions on Electronic Computers, EC-10:346--365, 1961
• 3: F. Rubin, "The Lee path connection algorithm", Transactions on Computers, C-23:907--914, 1974
• 4: R. A. Finkel and J. L. Bentley, "Quad trees: a data structure for retrieval on composite keys", Acta Inform. 4:1--9, 1974
• 5: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 6: Gershon Kedem, The quad-CIF tree: A data structure for hierarchical on-line algorithms, Proceedings of the 19th conference on Design automation, p.352-357, January 1982
• 7: J. K. Ousterhout, "Corner Stitching: a data structuring technique for VLSI layout tools", IEEE Trans. On Computer-Aided Design, Vol 3, No 1, January 1984
• 8: J. B. Rosenberg, "Geographical data structures compared: a study of data structures supporting region queries", IEEE Trans. On Computer-Aided Design, Vol. 4, No. 1, pages 53--67, January 1985
• 9: R. L. Brown, "Multiple storage quad trees: a simpler faster alternative to bisector list quad trees", IEEE Transactions on Computer-Aided Design, Vol 5, No. 3, July 1986
• 10: Y. D. Fontayne and R. J. Bowman, "The Multiple Storage Radix Hash Tree: An Improved Region Query Data Structure", International Conference on Computer-Aided Design, pages 302--305, 1987
• 11: D. Marple, M. Smulders and H. Hegen, "Tailor: A layout system based on trapezoidal corner stitching", IEEE Trans. On Computer-Aided Design, Vol. 9, No. 1, pages 66--90, January 1990
• 12: Glenn G. Lai , Don Fussell , D. F. Wong, HV/VH trees: a new spatial data structure for fast region queries, Proceedings of the 30th international conference on Design automation, p.43-47, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164562]
• 13: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 14: A. Hetzel, A sequential detailed router for huge grid graphs, Proceedings of the conference on Design, automation and test in Europe, p.332-339, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 15: David W. Hightower, A solution to line-routing problems on the continuous plane, Proceedings of the 6th annual conference on Design Automation, p.1-24, January 1969 [doi>10.1145/800260.809014]
• 16: W. Heyns , W. Sansen , H. Beke, A line-expansion algorithm for the general routing problem with a guaranteed solution, Proceedings of the 17th conference on Design automation, p.243-249, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804534]
• 17: Jason Cong , Jie Fang , Kei-Yong Khoo, An implicit connection graph maze routing algorithm for ECO routing, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.163-167, November 07-11, 1999, San Jose, California, United States
• 18: K. Clarkson , S. Kapoor , P. Vaidya, Rectilinear shortest paths through polygonal obstacles in O(n(logn)²) time, Proceedings of the third annual symposium on Computational geometry, p.251-257, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41985]
• 19: S. Q. Zheng, J. S. Lim and S. S. Iyengar, "Finding Obstacle-Avoiding Shortest Paths Using Implicit Connection Graphs", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 15, No. 1, Jan. 1996
• 20: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 21: An integrated placement and synthesis approach for timing closure of PowerPC/sup TM/ microprocessors, Proceedings of the 1997 International Conference on Computer Design (ICCD '97), p.206, October 12-15, 1997
• 22: A Robust Solution to the Timing Convergence Problem in High-Performance Design, Proceedings of the 1999 IEEE International Conference on Computer Design, p.250, October 10-13, 1999

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design

Keywords:
database, physical design, routing