並列単層配線を改良する新しい手法の提案
スポンサーリンク
概要
- 論文の詳細を見る
自動配線とは,ネットワーク上の複数個のピンをつなぐパスを見つける手法である.その際,新しいパスはすでに配線されているパスと交差してはならない.自動配線における基本的な問題点は,計算時間が長いこと,必要なメモリの量が多いことである.最近になって,並列計算機を用いて配線問題の高速化を図る研究がいくつか発表されている.我々は迷路法に基づく2つの並列アルゴリズムを考案した.本アルゴリズムの特徴は,分割された配線領域を跨ぐ短い配線が未配線のまま,ルーティングが進行するのを避けるため,境界線を移動するような領域分割を行う点にある.これにより,配線領域の大きさに比べてネットの配線長が短いような場合,特に高い並列性が得られる.本稿では,これらの手法とその実行結果を他のいくつかのアルゴリズムと比較して示す.
- 一般社団法人情報処理学会の論文
- 1993-08-19
著者
関連論文
- 自動車ドライバ挙動解析のための光学式モーションキャプチャの開発と評価(感性情報処理とマルチメディア技術および一般)
- 自動車運転者の挙動計測のためのGPS同期モーションキャプチャシステム(画像処理・インタフェース,ITS情報処理,一般)
- 不規則問題に対する並列化コンパイル手法
- 並列化コンパイラTINPARにおけるスカラ変数処理
- 不規則アクセスを伴うループの並列化コンパイル技法 : Inspector/Executorアルゴリズムの高速化
- タイルドディスプレイを用いた高精細ボリュームレンダリングシステムの実装
- 情報科学・工学, 私はこう考える : これからのアーキテクチャ, 私はこう考える
- 自動車運転者の挙動計測のためのGPS同期モーションキャプチャシステム
- 静的解析による並列論理型言語KL1のメッセージ通信最適化
- 並列論理型言語処理系KLICにおける通信の高速化
- 並列論理型言語KL1の最適化手法
- 並列論理型言語KL1の最適化手法
- PIM/mフロントエンド・プロセッサの速度性能評価
- 分散環境における構造体管理
- PSI-IIの性能評価 : If_Then_Else,Neck_Cut
- パーソナル逐次型推論マシンPSIの評価 : 実行速度とハードウェア各部の性能について
- PSIへのコンパイラ向きProlog命令の試験実装と評価
- マルチPSI要素プロセッサPSI-IIのメモリ管理とプロセス管理
- マルチPSI重要素プロセッサPSI-IIの最適化手法
- マルチPSI要素プロセッサPSI-IIのアーキテクチャ
- 計算機アーキテクチャの昨日、今日、明日
- HPCへの期待 : アーキテクチャの立場から
- 並列計算機の現状と将来
- Pascalマシンとチューニングによる高速化
- ユニバーサル・ホスト計算機QA-2の高機能順序制御方式
- ユニバーサル・ホスト計算機QA-2による逐次型Prologマシンのエミュレーション
- 低レベル並列処理計算機による3次元色彩図形表示処理
- 形式的手法によるキャッシュ・プロトコルの設計検証 : 超並列計算機JUMP-1への適用例
- アーキテクチャの立場からみた超並列処理 (超並列処理)
- 1.5MLIPS40ビット推論プロセッサ
- スタック領域が不要な深さ優先順コピー型ゴミ集め方式
- 分散環境におけるユニフィケーションの実現
- 超並列プロトタイプ計算機JUMP-1の構想
- レイトレーシング法を高速処理する専用並列レンダリング・マシン『熱視線』の要素プロセッサ・アーキテクチャ : VLIW アーキテクチャおよび性能評価
- レイトレーシング法を高速処理する専用並列レンダリング・マシン『熱視線』の要素プロセッサ・アーキテクチャ : マクロパイプライン・アーキテクチャおよび性能評価
- 収束過程の可視化によるアルゴリズム設計支援 : インタラクティブシミュレーションの高速化
- メッセージ交換型並列計算機のための並列化コンパイラTINPAR
- 並列化コンパイラTINPARにおける専用通信ライブラリの実装と性能評価
- メッセージ交換型並列計算機のための並列化コンパイラTINPAR : 最適化手法と性能評価
- メッセージ交換型並列計算機のための並列化コンパイラ
- プログラム並列化におけるデータ分割支援システム
- 特集「並列処理」の編集にあたって (並列処理)
- 楽しい研究を目指して
- 視角制限ピクセル並列処理によるボリューム・レンダリング向きの超高速専用計算機のアーキテクチャ
- ピクセル並列処理によるボリューム・レンダリング向きの超高速専用計算機アーキテクチャー
- ピクセル並列処理によるボリューム・レンダリング向きの超高速専用計算機アーキテクチャ
- ボリュームレンダリング専用並列計算機ReVolver/C40の試作
- セルフ・クリーンアップ型ライトバック・キャッシュの提案
- ディレクトリ型キャッシュコヒーレンスプロトコルの性能評価
- 細粒度プロセッサ間通信をサポートする高機能キャッシュ・システム
- シミュレーティド・アニーリングによる静的タスク配置へのヒューリスティクスの適用とその評価
- 『順風』: MSP (Multi threaded Streaming/FIFO)型ベクトル・プロセッサ・プロトタイプ : MSFV アーキテクチャに関する評価 (並列処理)
- 『順風』 : MSF(Multithreaded Streaming/FIFO)型 ベクトル・プロセッサ・プロトタイプ : MSFVアーキテクチャに関する評価
- 可変構造型並列計算機のメッセージ・プール指向型並列オペレーティング・システム : 複数スレッドの並列生成
- ボリュームレンダリング専用並列計算機ReVolverのアーキテクチャ
- 実時間3次元動画システムにおける動画記述
- 並列単層配線を改良する新しい手法の提案
- 工業高専におけるマイクロプラグラミング教育
- 並列自動配線アルゴリズムAmon
- 静的解析による並列論理型言語の実行最適化
- マルチスレッド処理をサポートするVLIWプロセッサ・アーキテクチャ