| Presentation | 2006-03-02 Shortest Path Algorithm on Parallel Reconfigurable Processor DAPDNA-2 Hiroyuki ISHIKAWA, Sho SHIMIZU, Yutaka ARAKAWA, Naoaki YAMANAKA, Kosuke SHIBA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Shortest path algorithm / Reconfigurable processor / DAPDNA-2 |
| Paper # | NS2005-162 |
| Date of Issue |
| Conference Information | |
| Committee | NS |
|---|---|
| Conference Date | 2006/2/23(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 | Network Systems(NS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Shortest Path Algorithm on Parallel Reconfigurable Processor DAPDNA-2 |
| Sub Title (in English) | |
| Keyword(1) | Shortest path algorithm |
| Keyword(2) | Reconfigurable processor |
| Keyword(3) | DAPDNA-2 |
| 1st Author's Name | Hiroyuki ISHIKAWA |
| 1st Author's Affiliation | Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University() |
| 2nd Author's Name | Sho SHIMIZU |
| 2nd Author's Affiliation | Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 3rd Author's Name | Yutaka ARAKAWA |
| 3rd Author's Affiliation | Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 4th Author's Name | Naoaki YAMANAKA |
| 4th Author's Affiliation | Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 5th Author's Name | Kosuke SHIBA |
| 5th Author's Affiliation | IPFlex Inc. |
| Date | 2006-03-02 |
| Paper # | NS2005-162 |
| Volume (vol) | vol.105 |
| Number (no) | 627 |
| Page | pp.pp.- |
| #Pages | 4 |
| Date of Issue | |