| ID | 96883 |
| Title Transcription | ハイセン モンダイ ノ ヘイレツ ショリ ホウシキ ニ カンスル ケンキュウ
|
| Author | |
| Content Type |
Thesis or Dissertation
|
| Description | 本論文は，プリント基板やVLSI内部の配線問題の並列処理に関する研究の成
果をまとめたものであり，次の6章から構成される. 第1章では，プリント基板やVLSI内部の配線問題の発達の歴史的背景と，本 研究を行うに至った直接の背景について述べると共に，本研究の目的と得られ た諸成果の概略を述べる. 第2章では，プリント基板やVLSI内部の配線問題とその逐次解法について述 べ，歴史的な2つの並列化方式とその問題点について述べる.そして並列計算 機のアーキテクチャを概説し，専用並列計算機と汎用並列計算機による並列配 線方式と配線処理の現状について述べる. 第3章では，計算機アーキテクチャに対して依存性を抑えるために，アーキ テクチャ固有の機能を使用せず，並列計算機が本来持っている基本的な機能 (プロセッサ間通信)のみを用いて構成されるプロセッサ競合方式による並列 配線処理方式を提案する.これは，計算モデルにマスタ・スレーブモデルを用 いて計算機アーキテクチャに対する依存性を抑え，かつ計算粒度の粗い並列処 理において高い並列性を得るための方式である.この方式を分散メモリ型並列 計算機と共有メモリ型並列計算機においてそれぞれ評価した結果，分散メモリ 型では63台のプロセッサにより約30倍の高速化を実現し，共有メモリ型で は7台のプロセッサにおいて約7倍の高速化を実現した.また，両方式の比較 検証を行ったことについて述べる. 第4章では，プロセッサ競合方式で問題であった配線品質に関する解決方法 として，引き剥し再配線処理の反復による経路改善を並列に実行する並列経路 改善方式を提案する.これはプロセッサ競合方式を基本モデルに用いて複数の 配線経路の引き剥し再配線処理を同時に行うものである. この方法では，配線 コストを用いた経路探索法により配線経路間の交差・接触を許容し，ペナルティ を用いた評価により配線順序に対する依存性を抑える.本方式をMIMD型並列 計算機により評価した結果，配線品質の改善が確認されたことについて述べる. 第5章では，多端子ネットの配線問題において並列経路改善方式を適用し， 部分引き剥し再配線のための経路探索法を提案する.これは多端子ネットの経 路探索が複数の部分的な経路探索から構成されることに着目し，この部分的な 探索単位による並列処理によりプロセッサへの処理の動的割り当て，及びネッ ト内の並列性とネット間の並列性を用いた2段階の高度な並列処理を可能にす る.更に，引き剥し再配線による経路改善において，配線経路を部分的に引き 剥すことにより経路改善のための再配線回数を削減する.本方式を逐次プログ ラムで評価した結果，経路改善において探索回数の削減と，配線結果が収束す るまでの経路改善回数の削減が確認されたので，これらの詳細と並列処理への 適合性，及び動的処理割り当てと並列性抽出の方針についての考察について述 べる. 第6章は結論であり，本研究で得られた諸結果を総括的に述べると共に，今 後の課題について述べる. |
| Published Date | 1995-03
|
| Remark | 画像データは国立国会図書館から提供(2012/3。JPEG2000形式を本学でpdfに変換して公開)
|
| FullText File | |
| language |
jpn
|
| MEXT report number | 甲第764号
|
| Diploma Number | 甲工第42号
|
| Granted Date | 1995-03-26
|
| Degree Name |
Doctor of Engineering
|
| departments |
Center for Administration of Information Technology
|
