| Presentation | 2005-12-01 A Study on Shortest Path Routing Algorithm on Data-flow Parallel Reconfigurable Processor DAPDNA2 Sho SHIMIZU, Yutaka ARAKAWA, Naoaki YAMANAKA, Kosuke SHIBA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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(√ |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Reconfigurable processor / DAPDNA2 / Shortest path algorithm / Dijkstra algorithm / Parallel processing |
| Paper # | RECONF2005-59 |
| Date of Issue |
| Conference Information | |
| Committee | RECONF |
|---|---|
| Conference Date | 2005/11/24(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Reconfigurable Systems (RECONF) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Study on Shortest Path Routing Algorithm on Data-flow Parallel Reconfigurable Processor DAPDNA2 |
| Sub Title (in English) | |
| Keyword(1) | Reconfigurable processor |
| Keyword(2) | DAPDNA2 |
| Keyword(3) | Shortest path algorithm |
| Keyword(4) | Dijkstra algorithm |
| Keyword(5) | Parallel processing |
| 1st Author's Name | Sho SHIMIZU |
| 1st Author's Affiliation | Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University() |
| 2nd Author's Name | Yutaka ARAKAWA |
| 2nd Author's Affiliation | Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 3rd Author's Name | Naoaki YAMANAKA |
| 3rd Author's Affiliation | Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 4th Author's Name | Kosuke SHIBA |
| 4th Author's Affiliation | IPFlex Inc. |
| Date | 2005-12-01 |
| Paper # | RECONF2005-59 |
| Volume (vol) | vol.105 |
| Number (no) | 451 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |