WEKO3
アイテム
並列ルーティングプロセッサの試作研究
https://ipsj.ixsq.nii.ac.jp/records/15652
https://ipsj.ixsq.nii.ac.jp/records/15652b4ea3547-4463-45d1-a58e-9c454ea0d8ab
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL2706009.pdf (810.4 kB)
|
Copyright (c) 1986 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1986-06-15 | |||||||
| タイトル | ||||||||
| タイトル | 並列ルーティングプロセッサの試作研究 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A Wavefront Machine - New Parallel Processing Architecture for Interactive Routing Design | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| その他タイトル | ||||||||
| その他のタイトル | アーキテクチャ | |||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部電子通信学科／現在 （株）東芝 | ||||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部電子通信学科 | ||||||||
| 著者所属 | ||||||||
| 松下通信工業（株）電波事業部移動通信技術部 | ||||||||
| 著者所属 | ||||||||
| NTT武蔵野電気通信研究所基幹交換技術部 | ||||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部電子通信学科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Science and Engineering, Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Science and Engineering, Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Matsushita Communication Industrial Corporated | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| NTT Telecommunication Networks Laboratories | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Science and Engineering, Waseda University | ||||||||
| 著者名 |
橘, 昌良
× 橘, 昌良
|
|||||||
| 著者名(英) |
Masayoshi, Tachibana
× Masayoshi, Tachibana
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本論文では Leeの迷路法を並列化 ハードウェア化した並列ルーティングプロセッサの構成法 試作結果 及び対話型設計システムヘの応用について論じる.Leeの迷路法は グリッドに対応するN×Nのプロセッサアレイを用意することにより 径路探索時間をO(N＾2)からO(N)に短縮することが可能である.しかし 必要とするハードウェア量はO(N＾2)で増加し 実用規模のシステムでは膨大なものとなる.これに対して 本論文で提案するアーキテクチャは ウェーブフロント上のセルのみにプロセッサが割り当てられる方式であるため O(N)台のプロセッサにより 処理時間をO(M)に短縮することが可能となっている.また 実際に128×128のグリッドを扱える 64台のプロセッサによる構成の試作を行った.迷路法には 数々の変形があり これらのアルゴリズムは 配線領域が混雑していない段階では ソフトウェアによる実行でも平均的には O(M)の時間で径路を発見できることが知られているが 処理が進み配線領域が混雑している段階では O(N＾2)の時間を必要とする.これに対して 並列ルーティングプロセッサは 配線領域の混雑度に関係なくO(M)の時間で径路を発見することができる.この特徴は 配線工程の最終段階において 対話型システムを使用し 障害となっている既配線の引きはがし 及び再配線を行う際には さらに有効なものとなる. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN00116647 | |||||||
| 書誌情報 |
情報処理学会論文誌 巻 27, 号 6, p. 639-647, 発行日 1986-06-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7764 | |||||||
