一層自動配線のための適応型グリッド生成法
スポンサーリンク
概要
- 論文の詳細を見る
プリント基板は年々小型軽量化し配線の複雑度も増している。複雑度が増すにつれて配線作業は人間の配線能力を超えるために、コンピュータによる自動配線が必要となる。小型軽量化をめざした製品に内蔵される基板は多層化の傾向にある。配線問題はNP困難であることが知られているが、配線層が増えると探索空間が増えるものの、実行可能解の比率も高くなるために、配線品質を別にすれば、実行可能解に至るまでの平均的な探索時間が減るために問題は簡単になる。実際、多層基板の配線はコンピュータによる自動配線が一般的に使用されている。一方で、家電製品のような大量生産品に埋め込まれる基板は、一層、両面基板を使用してコストを削減している。層数が減ることにより、実行可能解の比率が極端に減るために配線問題は非常に難しくなる。このため、現在のところ現実に使用可能な一層基板用の自動配線システムは存在していない。人手に頼っているのが現状である。我々は、昨年より一層基板用の自動配線システムのプロトタイプの開発を進めてきた。本稿では、プロトタイプで使用した配線領域上のグリッド生成法について述べる。高速かつ確実に100%の自動配線システムを実現するためには、次の2つの技術を確立する必要がある。(1)ネット(接続すべき端子の集合)の結線を高速に探索する技術(2)各ネットの結線が交差しないような配線順序決定、既配線修正のための有効なヒューリスティクス多層自動配線では(2)の有効なヒューリスティクスがもっとも重要な課題であるが、一層自動配線では、本質的に探索を続けることを避けられないため、現実的な時間内に実行可能解を見つけるためには高速な結線の探索技術も重要である。本稿で述べるグリッド生成法は(1)のネットの結線の高速探索のための技術である。まず、一層自動配線プロトタイプの仕様と配線戦略の概要を述べ、プロトタイプの戦略に適したグリッド生成法を詳細に述べる。
- 一般社団法人情報処理学会の論文
- 1995-09-20
著者
関連論文
- 端子回りの接続構造から結線可能性を判定する方法
- ジョブ割付問題のオブジェクト指向問題解決部品ライブラリー
- 推論オペレータ導出のための問題構造のモデル化 : 汎タスクレベルのマクロ構造
- 汎タスクレベルにおける推論オペレータの導出
- ポータブルなPrologコンパイラーの実現
- 無効化とタイムアウトを考慮したLRUキャッシュの解析
- トラック積み合わせ最適化に基づく配送形態最適化事例(輸送・配送)
- ユークリッド距離におけるCritical Cutの効率的生成方法
- パッケージ内配線のための概略配線手法
- 容量制約を満たした配線経路探索方法 (<特集> レイアウトと一般)
- 一層自動配線のための適応型グリッド生成法
- 89-35 抽象アルゴリズミック・デバッギング
- 1-S-9 製鋼熱延同期スケジュール : 中国鋼鉄様における事例(企業事例交流会)
- 2-E-9 位置制約のあるスケジューリング問題に対する期待値に基づいたヒューリスティック手法(スケジューリング(1))
- 製鋼・熱延スケジューラ連携によるDHCRスケジュール作成方法 (特集 製鉄業における製造工程最適化のためのOR技術)
- 製鋼・熱延スケジューラ連携によるDHCRスケジュール作成方法(製鉄業における製造工程最適化のためのOR技術)
- 特集にあたって(製鉄業における製造工程最適化のためのOR技術)
- 2-C-2 スラブ山繰り問題のためのヒューリスティックアルゴリズム(離散最適化(2))