| 講演名 | 2006-03-02 並列リコンフィギュラブルプロセッサDAPDNA-2を用いた最短経路探索 石川 浩行, 清水 翔, 荒川 豊, 山中 直明, 斯波 康祐, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 代表的なルーティングプロトコルであるOSPFでは,最短経路探索にダイクストラ法が用いられる.ダイクストラ法は,ネットワーク規模の拡大にともない,最短経路を求めるための計算量が急激に増加するという問題がある.本研究では,複数の経路を並列に探索するアルゴリズムを提案し,IPFlex社が開発した並列リコンフィギュラブルプロセッサDAPDNA-2を用いて提案アルゴリズムの実装を行った.特性評価の結果,DAPDNA-2上では従来のダイクストラ法と比較して提案アルゴリズムは計算クロック数が最大で約99.6%減少することを示した. |
| 抄録(英) | This paper proposes a parallel shortest path algorithm and implement the proposed algorithm on DAPDNA-2 of IPFlex Inc. Conventional Dijkstra's shortest path algorithm finds shortest paths from the start node in OSPF. When the network scale is large, calculation time of Dijkstra's shortest path algorithm increases rapidly. To meet those shortcoming, proposed scheme can decrease calculation time from O(N^2) to O(N). As a result of simulations, we show that calculation time of the proposed algorithm decreases by 99.6% compared to Dijkstra's algorithm on DAPDNA-2. |
| キーワード(和) | 最短経路探索 / 並列リコンフィギュラブルプロセッサ / DAPDNA-2 |
| キーワード(英) | Shortest path algorithm / Reconfigurable processor / DAPDNA-2 |
| 資料番号 | NS2005-162 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NS |
|---|---|
| 開催期間 | 2006/2/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Network Systems(NS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 並列リコンフィギュラブルプロセッサDAPDNA-2を用いた最短経路探索 |
| サブタイトル（和） | |
| タイトル（英） | Shortest Path Algorithm on Parallel Reconfigurable Processor DAPDNA-2 |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 最短経路探索 / Shortest path algorithm |
| キーワード(2)（和/英） | 並列リコンフィギュラブルプロセッサ / Reconfigurable processor |
| キーワード(3)（和/英） | DAPDNA-2 / DAPDNA-2 |
| 第 1 著者 氏名（和/英） | 石川 浩行 / Hiroyuki ISHIKAWA |
| 第 1 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 2 著者 氏名（和/英） | 清水 翔 / Sho SHIMIZU |
| 第 2 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 3 著者 氏名（和/英） | 荒川 豊 / Yutaka ARAKAWA |
| 第 3 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 4 著者 氏名（和/英） | 山中 直明 / Naoaki YAMANAKA |
| 第 4 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 5 著者 氏名（和/英） | 斯波 康祐 / Kosuke SHIBA |
| 第 5 著者 所属（和/英） | アイピーフレックス株式会社 IPFlex Inc. |
| 発表年月日 | 2006-03-02 |
| 資料番号 | NS2005-162 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 627 |
| ページ範囲 | pp.- |
| ページ数 | 4 |
| 発行日 | |