端子回りの接続構造から結線可能性を判定する方法

スポンサーリンク

概要

• 論文の詳細を見る

• 片面プリント基板の配線は,「それぞれの配線が互いに交差せず,かつすべての配線は与えられた配線領域に収まる」という制約を充足する配線問題である.特にジャンパの使用を許さない場合は,与えられた端子と配線からなるグラフの平面性を判定するNP完全問題となる.しかも配線の組合せからなる探索空間の大きさに比べて許容解の数が非常に少ないため,ヒューリステイックによる探索の絞り込みでは解を求める事は困難である.本稿では,一本の配線について,その近傍の配線との平面性判定を使用した配線可能性のテスト方法を述べる.この手法はバス構造に対して無駄な配線の発生を抑えるため,グローバルルータにおける配線の組合せから生ずる探索空間を効果的に絞り込む.バス構造の配線問題を図1を例にして説明する.ここで隣り合っている4個の端子の間には配線を通す余裕は無いとする.端子Aを図のように配線すると端子1と端子2を同時に配線することはできなくなる.リップアップルータでは,交差が生じた時に交差した配線のいずれかを引き剥し,再配線を行なう事で交差違反の解消を図る.この交差違反の改善をバスに適用すると再配線したものが隣にある残りのバスに対して交差をするため,バスに関わる全ての配線の交差違反を解消する事は困難である.そのためバス配線はグローバルルータの探索で処理するのではなく前処理で特別なバス配線プログラムを使用するものもある.ここで提案するのは,具体的な配線経路(配線パターンと呼ぶ)を作成する事無しに交差競合を見つける手法である.図1を例にすると,端子Aの配線と端子Aから連結(間に配線の余裕のない状態)しているものの集まりは位相的に同型な図2(以降,連結端子表現と呼ぶ)に置き換えられる.図1の端子1のすべての配線パターンは連結端子表現では直線として表現される.逆に図2で交差する線は実際の配線パターンでも交差する.したがって,連結端子表現で配線不可能ならば端子Aの配線パターンは配線不可能である.本方式の利点は次の4点である.(l)バス構造を特別視することなく位相的な構造で扱うためあらゆるタイプのバス構造に対処可能,(ハグローバルルータにおける無駄な配線候補の排除,(3)配線探索とバスの処理を分離しない事で,配線領域が配線によって埋まることで発生するバス構造に対処可能,(4)配線パターンを作成しない事から交差テストが高速である,節3では交差テストを配列操作に置き換えるアルゴリズムを示す.多層配線への適用を考えると,各層で平面配線を追及する事でスルーホールの使用を抑えることに利用できる.

• 1996-03-06

著者

• 江藤 博明

  日本アイ・ビー・エム株式会社東京基礎研究所

• 濱 利行

  日本アイ・ビー・エム株式会社東京基礎研究所

• 濱 利行

  日本ibm東京基礎研究所

• 江藤 博明

  日本アイ・ビー・エム株式会社サイエンス・インスティチュート

• 江藤 博明

  日本アイ・ビー・エム 東京基礎研

• 濱 利行

  日本アイ・ビー・エム(株)東京基礎研究所

関連論文

• 端子回りの接続構造から結線可能性を判定する方法
• ジョブ割付問題のオブジェクト指向問題解決部品ライブラリー
• 推論オペレータ導出のための問題構造のモデル化 : 汎タスクレベルのマクロ構造
• 汎タスクレベルにおける推論オペレータの導出
• ポータブルなPrologコンパイラーの実現
• 無効化とタイムアウトを考慮したLRUキャッシュの解析
• トラック積み合わせ最適化に基づく配送形態最適化事例(輸送・配送)
• ユークリッド距離におけるCritical Cutの効率的生成方法
• パッケージ内配線のための概略配線手法
• 容量制約を満たした配線経路探索方法 (<特集> レイアウトと一般)
• 一層自動配線のための適応型グリッド生成法
• 89-35 抽象アルゴリズミック・デバッギング
• 1-S-9 製鋼熱延同期スケジュール : 中国鋼鉄様における事例(企業事例交流会)
• 2-E-9 位置制約のあるスケジューリング問題に対する期待値に基づいたヒューリスティック手法(スケジューリング(1))
• 配線経路探索高速化のためのクリティカルカット削減方法
• JSIAIワークステーション(3) : ウインドウシステムからみたOSの条件
• JSIAIワークステーション(2) : アーキテクチャとOS
• propolice : スタックスマッシング攻撃検出手法の改良(次世代移動通信ネットワークとその応用)
• propolice : スタックスマッシング攻撃検出手法の改良
• propolice:スタックスマッシング攻撃検出手法の改良
• パケットのデータサイズ・時刻系列を使ったコネクション・チェインの発見
• パケットのデータサイズ・時刻系列を使ったコネクション・チェインの発見
• セルコントローラ・IFCの制御言語設計
• モジュール構造を持つプロローグのデータベースインターフェース
• 製鋼・熱延スケジューラ連携によるDHCRスケジュール作成方法 (特集 製鉄業における製造工程最適化のためのOR技術)
• 製鋼・熱延スケジューラ連携によるDHCRスケジュール作成方法(製鉄業における製造工程最適化のためのOR技術)
• 特集にあたって(製鉄業における製造工程最適化のためのOR技術)
• 2-C-2 スラブ山繰り問題のためのヒューリスティックアルゴリズム(離散最適化(2))

もっと見る 閉じる

スポンサーリンク