| Paper Abstract and Keywords |
| Presentation |
2005-12-01 09:30
A Study on Shortest Path Routing Algorithm on Reconfigurable Processor
Sho Shimizu, Yutaka Arakawa, Naoaki Yamanaka (Keio Univ.), Kosuke Shiba (IPFlex) |
| Abstract |
(in Japanese) |
(See Japanese page) |
| (in English) |
n 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(\sqrt{n})$, and scalable for the number of nodes. |
| Keyword |
(in Japanese) |
(See Japanese page) |
| (in English) |
Reconfigurable processor / DAPDNA2 / Shortest path algorithm / Dijkstra algorithm / Parallel processing / / / |
| Reference Info. |
IEICE Tech. Rep., vol. 105, no. 451, RECONF2005-59, pp. 1-6, Nov. 2005. |
| Paper # |
RECONF2005-59 |
| Date of Issue |
2005-11-24 (RECONF) |
| ISSN |
Print edition: ISSN 0913-5685 |
| Download PDF |
|
| Conference Information |
| Committee |
RECONF |
| Conference Date |
2005-11-30 - 2005-12-02 |
| Place (in Japanese) |
(See Japanese page) |
| Place (in English) |
Kitakyushu International Conference Center |
| Topics (in Japanese) |
(See Japanese page) |
| Topics (in English) |
|
| Paper Information |
| Registration To |
RECONF |
| Conference Code |
2005-11-RECONF |
| Language |
Japanese |
| Title (in Japanese) |
(See Japanese page) |
| Sub Title (in Japanese) |
(See Japanese page) |
| Title (in English) |
A Study on Shortest Path Routing Algorithm on Reconfigurable Processor |
| Sub Title (in English) |
|
| Keyword(1) |
Reconfigurable processor |
| Keyword(2) |
DAPDNA2 |
| Keyword(3) |
Shortest path algorithm |
| Keyword(4) |
Dijkstra algorithm |
| Keyword(5) |
Parallel processing |
| Keyword(6) |
|
| Keyword(7) |
|
| Keyword(8) |
|
| 1st Author's Name |
Sho Shimizu |
| 1st Author's Affiliation |
Keio University (Keio Univ.) |
| 2nd Author's Name |
Yutaka Arakawa |
| 2nd Author's Affiliation |
Keio University (Keio Univ.) |
| 3rd Author's Name |
Naoaki Yamanaka |
| 3rd Author's Affiliation |
Keio University (Keio Univ.) |
| 4th Author's Name |
Kosuke Shiba |
| 4th Author's Affiliation |
IPFlex (IPFlex) |
| 5th Author's Name |
|
| 5th Author's Affiliation |
() |
| 6th Author's Name |
|
| 6th Author's Affiliation |
() |
| 7th Author's Name |
|
| 7th Author's Affiliation |
() |
| 8th Author's Name |
|
| 8th Author's Affiliation |
() |
| 9th Author's Name |
|
| 9th Author's Affiliation |
() |
| 10th Author's Name |
|
| 10th Author's Affiliation |
() |
| 11th Author's Name |
|
| 11th Author's Affiliation |
() |
| 12th Author's Name |
|
| 12th Author's Affiliation |
() |
| 13th Author's Name |
|
| 13th Author's Affiliation |
() |
| 14th Author's Name |
|
| 14th Author's Affiliation |
() |
| 15th Author's Name |
|
| 15th Author's Affiliation |
() |
| 16th Author's Name |
|
| 16th Author's Affiliation |
() |
| 17th Author's Name |
|
| 17th Author's Affiliation |
() |
| 18th Author's Name |
|
| 18th Author's Affiliation |
() |
| 19th Author's Name |
|
| 19th Author's Affiliation |
() |
| 20th Author's Name |
|
| 20th Author's Affiliation |
() |
| Speaker |
Author-1 |
| Date Time |
2005-12-01 09:30:00 |
| Presentation Time |
25 minutes |
| Registration for |
RECONF |
| Paper # |
RECONF2005-59 |
| Volume (vol) |
vol.105 |
| Number (no) |
no.451 |
| Page |
pp.1-6 |
| #Pages |
6 |
| Date of Issue |
2005-11-24 (RECONF) |
|