A Fast Longer Path Algorithm for Routing Grid with Obstacles Using Biconnectivity Based Length Upper Bound
スポンサーリンク
概要
- 論文の詳細を見る
In recent VLSI systems, signal propagation delays are requested to achieve the specifications with very high accuracy. In order to meet the specifications, the routing of a net often needs to be detoured in order to increase the routing delay. A routing method should utilize a routing area with obstacles as much as possible in order to realize the specifications of nets simultaneously. In this paper, a fast longer path algorithm that generates a path of a net in routing grid so that the length is increased as much as possible is proposed. In the proposed algorithm, an upper bound for the length in which the structure of a routing area is taken into account is used. Experiments show that our algorithm utilizes a routing area with obstacles efficiently.
- 2009-12-01
著者
-
TAKAHASHI Atsushi
Graduate School of Science and Technology, Tokyo Institute of Technology
-
KOHIRA Yukihide
School of Computer Science and Engineering, the University of Aizu
-
Takahashi Atsushi
Graduate School Of Engineering Osaka University
-
Takahashi Atsushi
Faculty of Engineering, Tokyo Institute of Technology
-
SUEHIRO Suguru
Department of Communications and Integrated Systems, Tokyo Institute of Technology
-
Suehiro Suguru
Department Of Communications And Integrated Systems Tokyo Institute Of Technology
-
Kohira Yukihide
School Of Computer Science And Engineering The University Of Aizu
-
Kohira Yukihide
School Of Computer Sci. And Engineering The Univ. Of Aizu
-
Takahashi Atsushi
Graduate School Of Engineering Osaka Univ.
関連論文
- A-3-10 Top Layer Plating Lead Maximization for BGA Packages
- 2層BGAパッケージのための詳細ビア配置手法の評価(クロック合成及び実装設計,システムオンシリコンを支える設計技術)
- 入力べクトルと回路の内部状態を考慮したピーク電力高速見積もり手法(低電力設計と回路設計技術,システムオンシリコンを支える設計技術)
- PCB配線設計のための一層複線指定長自動配線手法(システム設計と高位・論理設計,物理設計及び一般)
- 最小総変位配置実現問題のための高速位相変更手法(物理設計,物理設計及び一般)
- 単層プリント基板配線のための効率的な高混雑度領域特定および45度線による混雑度緩和法(回路最適化技術,システム設計及び一般)
- エラー検出回復方式における加算器の性能評価(システム設計・高位論理設計,システムオンシリコンを支える設計技術)
- 一般同期方式における消費電力を抑えたクロック木構成のためのクラスタ分割法(クロック合成及び実装設計,システムオンシリコンを支える設計技術)
- A Clustering Based Fast Clock Schedule Algorithm for Light Clock-Trees(Special Section on VLSI Design and CAD Algorithms)
- A-3-1 一般同期方式におけるクラスタ分割に基づくクロック木の性能評価(A-3.VLSI設計技術,一般セッション)
- A-3-4 単層プリント基板配線のための高混雑度領域特定手法(A-3.VLSI設計技術,一般セッション)
- Routability Driven Via Assignment Method for 2-Layer Ball Grid Array Packages
- MILP-Based Efficient Routing Method with Restricted Route Structure for 2-Layer Ball Grid Array Packages
- VLSI設計自動化の現状と将来展望(プロセス・デバイス・回路シミュレーション及び一般)
- Gate-Level Register Relocation in Generalized Synchronous Framework for Clock Period Minimization(Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
- A Fast Longer Path Algorithm for Routing Grid with Obstacles Using Biconnectivity Based Length Upper Bound
- Minimal Forbidden Minors for the Family of Graphs with Proper-Path-Width at Most Two
- Universal Graphs for Graphs with Bounded Path-Width
- Schedule-Clock-Tree Routing for Semi-Synchronous Circuits (Special Section on VLSI Design and CAD Algorithms)
- Optimal Time-Multiplexing in Inter-FPGA Connections for Accelerating Multi-FPGA Prototyping Systems
- CAFE Router : A Fast Connectivity Aware Multiple Nets Routing Algorithm for Routing Grid with Obstacles
- FPGA上に実現した可変レイテンシ回路の動作検証(論理設計2,システムオンシリコンを支える設計技術)
- 最小総変位配置実現問題に対し効率的な位相変更手法CRP手法の提案(物理設計,システムオンシリコンを支える設計技術)
- A Fast Clock Scheduling for Peak Power Reduction in LSI
- Minimization of Delay Insertion in Clock Period Improvement in General-Synchronous Framework
- A-3-4 Optimal Register Merging Method after Register Relocation in Semi-Synchronous Framework
- ゲートレベルシミュレーションによるエラー検出・回復方式回路の評価(論理設計2,システムオンシリコンを支える設計技術)
- A-3-20 準ニュートン法を用いた自由角度配線のための逐次改善手法(A-3.VLSI設計技術,一般セッション)
- A Via Assignment and Global Routing Method for 2-Layer Ball Grid Array Packages(Discrete Mathematics and Its Applications)
- Routability Driven Via Assignment and Routing for 2-Layer Ball Grid Array Packages
- エラー検出回復方式における様々な加算器の性能評価(システムと信号処理及び一般)
- エラー検出回復方式における様々な加算器の性能評価(システムと信号処理及び一般)
- エラー検出回復方式における様々な加算器の性能評価(システムと信号処理及び一般)
- エラー検出回復方式における様々な加算器の性能評価(システムと信号処理及び一般)
- Routing of Monotonic Parallel and Orthogonal Netlists for Single-Layer Ball Grid Array Packages(Physical Design,VLSI Design and CAD Algorithms)
- Clock Period Minimization Method of Semi-Synchronous Circuits by Delay Insertion(Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
- 集合対間配線問題に関する一考察(配置配線,物理設計及び一般)
- MSA: mixed stochastic algorithm for placement with larger solution space (VLSI設計技術)
- A Semi-Synchronous Circuit Design Method by Clock Tree Modification(Special Section on VLSI Design and CAD Algorithms)
- Clock Schedule Design for Minimum Realization Cost (Special Section on VLSI Design and CAD Algorithms)
- Clock Period Minimization of Semi-Synchronous Circuits by Gate-Level Delay Insertion (Special Section on VLSI Design and CAD Algorithms)
- Cost-Radius Balanced Spanning/Steiner Trees (Special Section on Discrete Mathematics and Its Applications)
- Practical Fast Clock-Schedule Design Algorithms(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
- Low Area Pipelined Circuits by the Replacement of Registers with Delay Elements(Circuit Synthesis,VLSI Design and CAD Algorithms)
- Multi-Clock Cycle Paths and Clock Scheduling for Reducing the Area of Pipelined Circuits(System Level Design,VLSI Design and CAD Algorithms)
- Routability Driven Via Assignment and Routing for 2-Layer Ball Grid Array Packages (デザインガイア2006--VLSI設計の新しい大地を考える研究会)
- Routability Driven Via Assignment and Routing for 2-Layer Ball Grid Array Packages (デザインガイア2006--VLSI設計の新しい大地を考える研究会)
- An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations (ディペンダブルコンピューティング)
- An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations
- PCB一層配線における集合対間配線のフローを用いた配線長差削減アルゴリズム(実装技術と低消費電力化,デザインガイア2011-VLSI設計の新しい大地-)
- PCB一層配線における集合対間配線のフローを用いた配線長差削減アルゴリズム(実装技術と低消費電力化,デザインガイア2011-VLSI設計の新しい大地-)
- A-3-3 単層プリント基板配線のための各ネットの配線長達成性を考慮した等長配線手法(A-3.VLSI設計技術,一般セッション)
- 一般同期方式における最適2クラスタ分割手法
- Flow Control Scheme Using Adaptive Receiving Opportunity Control for Wireless Multi-Hop Networks
- Single-Layer Trunk Routing Using Minimal 45-Degree Lines
- PCB一層配線における集合対間配線のフローを用いた配線長差削減アルゴリズム
- FPGA上に実現した可変レイテンシ回路の性能評価(再構成回路,システムオンシリコンを支える設計技術)
- FOREWORD
- 準ニュートン法を用いた自由角度配線手法 (物理設計)
- An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations
- An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations
- PCB一層配線における集合対間配線のフローを用いた配線長差削減アルゴリズム
- A New Variation of Adaptive Simulated Annealing for 2D/3D Packing Optimization
- 動的遅延分布の高速な見積もり手法(システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- 動的遅延分布の高速な見積もり手法(システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- 動的遅延分布の高速な見積もり手法(システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- 動的遅延分布の高速な見積もり手法(システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- A New Variation of Adaptive Simulated Annealing for 2D/3D Packing Optimization
- 単層プリント基板のための各ネットの目標配線長達成性を考慮した配線手法(配線設計,システムオンシリコンを支える設計技術)
- A-3-6 指定長幹配線間題において配線長を調整する領域に関する一考察(A-3.VLSI設計技術)