WEKO3
アイテム
配線問題の並列処理方式に関する研究
https://tokushima-u.repo.nii.ac.jp/records/2001876
https://tokushima-u.repo.nii.ac.jp/records/2001876f354df6a-8098-4299-ad80-f3662817e96e
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
LID201206131002.pdf (23.6 MB)
|
|
| Item type | 文献 / Documents(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2012-06-13 | |||||||||||
| アクセス権 | ||||||||||||
| アクセス権 | open access | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_db06 | |||||||||||
| 資源タイプ | doctoral thesis | |||||||||||
| 出版タイプ | ||||||||||||
| 出版タイプ | NA | |||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_be7fb7dd8ff6fe43 | |||||||||||
| タイトル | ||||||||||||
| タイトル | 配線問題の並列処理方式に関する研究 | |||||||||||
| 言語 | ja | |||||||||||
| タイトル | ||||||||||||
| タイトル | ハイセン モンダイ ノ ヘイレツ ショリ ホウシキ ニ カンスル ケンキュウ | |||||||||||
| 言語 | ja-Kana | |||||||||||
| 著者 |
佐野, 雅彦
× 佐野, 雅彦
WEKO
158
|
|||||||||||
| 抄録 | ||||||||||||
| 内容記述タイプ | Abstract | |||||||||||
| 内容記述 | 本論文は，プリント基板やVLSI内部の配線問題の並列処理に関する研究の成果をまとめたものであり，次の6章から構成される. 第1章では，プリント基板やVLSI内部の配線問題の発達の歴史的背景と，本研究を行うに至った直接の背景について述べると共に，本研究の目的と得られた諸成果の概略を述べる. 第2章では，プリント基板やVLSI内部の配線問題とその逐次解法について述べ，歴史的な2つの並列化方式とその問題点について述べる.そして並列計算機のアーキテクチャを概説し，専用並列計算機と汎用並列計算機による並列配線方式と配線処理の現状について述べる. 第3章では，計算機アーキテクチャに対して依存性を抑えるために，アーキテクチャ固有の機能を使用せず，並列計算機が本来持っている基本的な機能(プロセッサ間通信)のみを用いて構成されるプロセッサ競合方式による並列配線処理方式を提案する.これは，計算モデルにマスタ・スレーブモデルを用いて計算機アーキテクチャに対する依存性を抑え，かつ計算粒度の粗い並列処理において高い並列性を得るための方式である.この方式を分散メモリ型並列計算機と共有メモリ型並列計算機においてそれぞれ評価した結果，分散メモリ型では63台のプロセッサにより約30倍の高速化を実現し，共有メモリ型では7台のプロセッサにおいて約7倍の高速化を実現した.また，両方式の比較検証を行ったことについて述べる. 第4章では，プロセッサ競合方式で問題であった配線品質に関する解決方法として，引き剥し再配線処理の反復による経路改善を並列に実行する並列経路改善方式を提案する.これはプロセッサ競合方式を基本モデルに用いて複数の配線経路の引き剥し再配線処理を同時に行うものである. この方法では，配線コストを用いた経路探索法により配線経路間の交差・接触を許容し，ペナルティを用いた評価により配線順序に対する依存性を抑える.本方式をMIMD型並列計算機により評価した結果，配線品質の改善が確認されたことについて述べる. 第5章では，多端子ネットの配線問題において並列経路改善方式を適用し，部分引き剥し再配線のための経路探索法を提案する.これは多端子ネットの経路探索が複数の部分的な経路探索から構成されることに着目し，この部分的な探索単位による並列処理によりプロセッサへの処理の動的割り当て，及びネット内の並列性とネット間の並列性を用いた2段階の高度な並列処理を可能にする.更に，引き剥し再配線による経路改善において，配線経路を部分的に引き剥すことにより経路改善のための再配線回数を削減する.本方式を逐次プログラムで評価した結果，経路改善において探索回数の削減と，配線結果が収束するまでの経路改善回数の削減が確認されたので，これらの詳細と並列処理への適合性，及び動的処理割り当てと並列性抽出の方針についての考察について述べる. 第6章は結論であり，本研究で得られた諸結果を総括的に述べると共に，今後の課題について述べる. |
|||||||||||
| 言語 | ja | |||||||||||
| 書誌情報 |
発行日 1995-03 |
|||||||||||
| 備考 | ||||||||||||
| 言語 | ja | |||||||||||
| 値 | 画像データは国立国会図書館から提供(2012/3。JPEG2000形式を本学でpdfに変換して公開) | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| 報告番号 | ||||||||||||
| 学位授与番号 | 甲第764号 | |||||||||||
| 学位記番号 | ||||||||||||
| 言語 | ja | |||||||||||
| 値 | 甲工第42号 | |||||||||||
| 学位授与年月日 | ||||||||||||
| 学位授与年月日 | 1995-03-26 | |||||||||||
| 学位名 | ||||||||||||
| 言語 | ja | |||||||||||
| 学位名 | 博士（工学） | |||||||||||
