A Global Routing Algorithm Based on the Multi-Commodity Network Flow Method (Special Section on VLSI Design and CAD Algorithms)

スポンサーリンク

概要

• 論文の詳細を見る

• A global routing problem is formulated as a multi-commodity network flow problem. This formulation gives no restriction over the shape of a routing patten and makes it possible to obtain the optimal solution by using a mathematical programming method. Moreover, it can be naturally extended to the problem even optimizing routing length objectives for net delay and clock skew performances by using the goal programming method. An approximation algorithm solving the multicommodity network flow problem is proposed by adding a merge step of wires whose source-sink pairs are exactly the same and a step restricting an area for searching routes. Experimental results show that this global routing algorithm connected with a linesearch detailed router can generate a complete routing for interblock routing problems with more than 2400 wires in two industrial chips. The total amount of processing time for both problems is about 90 minutes on a mainframe computer.

• 社団法人電子情報通信学会の論文
• 1993-10-25

著者

• Shiraishi Yoichi

  Central Research Laboratory Hitachi Ltd.

• Fukuda Kazuyuki

  Hitachi VLSI Engineering, Corp.,

• Fukuda Kazuyuki

  Hitachi Vlsi Engineering Corp.

• Sakemi J

  Hitachi Ulsi Engineering Corp. Tokyo Jpn

関連論文

• A Global Routing Algorithm Based on the Multi-Commodity Network Flow Method (Special Section on VLSI Design and CAD Algorithms)

スポンサーリンク