| 講演名 | 2005-12-01 リコンフィギュラブルプロセッサを用いた最短経路探索に関する一検討(ネットワーク, デザインガイア-VLSI設計の新しい大地を考える研究会-) 清水 翔, 荒川 豊, 山中 直明, 斯波 康祐, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | IPネットワークにおけるルーチングアルゴリズムとして一般的に用いられているOSPF (Open Shortest Path First)では, ダイクストラ法を用いて最短経路探索を行っている.ダイクストラ法は逐次型計算アーキテクチャをベースとしており, 計算量がノード数nに対してO(n^2)であり, ノード数の増加に伴って計算量が急激に増加する.本論文では, データフロー型パラレルプロセッサのアーキテクチャに適したノード数nに比例しない並列最短経路アルゴリズムMPSA (Multi-route Parallel Search Algorithm)を提案し, ダイナミックリコンフィギュラブルプロセッサDAPDNA2上で実装を行う.提案アルゴリズムでは, 再帰的な計算によるループ間の依存性をなくし, 行列演算に帰着させることで並列計算による最短経路探索を実現する.それにより, 計算量がO(√ |
| 抄録(英) | In IP networks, we ordinally use OSPF(Open Shortest Path First) as a routing protocol. OSPF find the shortest path using Dijkstra's Shortest Path Algorithm. Dijkstra's Algorithm is suitable for program counter based CPU, however it is not scalable for the number of nodes in the networks since its computational complexity is O(n^2). In this paper, We propose a parallel shortest path algorithm MPSA(Multi-route Parallel Search Algorithm) and implement the proposed algorithm on DAPDNA2 which is based on data-flow parallel reconfigurable processor architecture. Our proposed algorithm is expressed as matrix operations, so it become high parallelism. As a result, its computational complexity is O(√ |
| キーワード(和) | リコンフィギュラブルプロセッサ / 最短経路探索 / ダイクストラ法 / 並列処理 |
| キーワード(英) | Reconfigurable processor / DAPDNA2 / Shortest path algorithm / Dijkstra algorithm / Parallel processing |
| 資料番号 | RECONF2005-59 |
| 発行日 |
| 研究会情報 | |
| 研究会 | RECONF |
|---|---|
| 開催期間 | 2005/11/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Reconfigurable Systems (RECONF) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | リコンフィギュラブルプロセッサを用いた最短経路探索に関する一検討(ネットワーク, デザインガイア-VLSI設計の新しい大地を考える研究会-) |
| サブタイトル（和） | |
| タイトル（英） | A Study on Shortest Path Routing Algorithm on Data-flow Parallel Reconfigurable Processor DAPDNA2 |
| サブタイトル（和） | |
| キーワード(1)（和/英） | リコンフィギュラブルプロセッサ / Reconfigurable processor |
| キーワード(2)（和/英） | 最短経路探索 / DAPDNA2 |
| キーワード(3)（和/英） | ダイクストラ法 / Shortest path algorithm |
| キーワード(4)（和/英） | 並列処理 / Dijkstra algorithm |
| 第 1 著者 氏名（和/英） | 清水 翔 / Sho SHIMIZU |
| 第 1 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 2 著者 氏名（和/英） | 荒川 豊 / Yutaka ARAKAWA |
| 第 2 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 3 著者 氏名（和/英） | 山中 直明 / Naoaki YAMANAKA |
| 第 3 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 4 著者 氏名（和/英） | 斯波 康祐 / Kosuke SHIBA |
| 第 4 著者 所属（和/英） | アイピーフレックス株式会社 IPFlex Inc. |
| 発表年月日 | 2005-12-01 |
| 資料番号 | RECONF2005-59 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 451 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |