DYNAJUST: an efficient automatic routing technique optimizing delay conditions

ABSTRACT

A new routing technique DYNAJUST, Dynamic Wire Length Adjustment, is described. It accurately realizes specified wire lengths to fulfill delay conditions. The implementation, based on the combination of shortest path algorithms, is proposed to achieve a high completion ratio in a short processing time. The technique is useful in practical situations where high accuracy is required of many nets.

REFERENCES

• 1: A. E. Dunlop , V. D. Agrawal , D. N. Deutsch , M. F. Jukl , P. Kozak , M. Wiesel, Chip layout optimization using critical path weighting, Proceedings of the 21st conference on Design automation, p.133-136, June 25-27, 1984, Albuquerque, New Mexico, United States
• 2: Yasushi Ogawa , Tatsuki Ishii , Yoichi Shiraishi , Hidekazu Terai , Tokinori Kozawa , Kyoji Yuyama , Kyoji Chiba, Efficient placement algorithms optimizing delay for high-speed ECL masterslice LSIs, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.404-410, July 1986, Las Vegas, Nevada, United States
• 3: Ralph Linsker, An iterative-improvement penalty-function-driven wire routing system, IBM Journal of Research and Development, v.28 n.5, p.613-624, September 1984
• 4: Toshihiko Tada , Akihiko Hanafusa, Router system for printed wiring boards of very high-speed, very large-scale computers, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.791-797, July 1986, Las Vegas, Nevada, United States
• 5: Michael Burstein , Mary N. Youssef, Timing influenced layout design, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.124-130, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317845]
• 6: H. Terai~ et al., "Performance Analysis of Automatic Placement and Routing for Large-Scale CHOS Mastersllces" in Proc IEEE International Conference on Computer Design~ VLSI{ in Computers (ICCD) 1983, pp. 536-539.
• 7: S. Asahara, et al. ~ "An Analysis of Wiring Performances of a Routing System for High Density Printed Wiring Boards", IECE Trans. Vol. J65-A, pp. 159-166 (1982) (in Japanese).
• 8: Ikuo Nishioka , Takuji Kurimoto , Hisao Nishida, A minicomputerized automatic layout system for two-layer printed wiring boards, Proceedings of the 14th conference on Design automation, p.1-11, January 1977
• 9: 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]
• 10: C.Y. Lee, "An Algorithm for Path Connections and Its Applications", IRE Trans. Electron. Comput., Vol. EC-10~ pp. 346-365~ 1961.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

General Terms:
Algorithms, Design