| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2025-03-06 15:55 Single-Source Shortest Path FPGA Accelerator Using Multiple Parallel Searches with High-Level Synthesis and Linked List Implementation ○Haopeng Meng・Kazutoshi Wakabayashi・Makoto Ikeda（The University of Tokyo）  VLD2024-120 HWS2024-91 ICD2024-111 |
|
| 抄録 | （和） | (まだ登録されていません) |
| （英） | This study explores accelerating single-source shortest path (SSSP) computations, including Dijkstra and A* algorithms, using high-level synthesis (HLS) and dynamic data structures. Current approaches focus on parallel node exploration with Multi Queue, nearest-node searches via memory partitioning, and parallel expansion of adjacent edges. However, these methods often require independent designs in traditional RTL implementations. The interdependence between node-parallel and edge-parallel searches introduces design complexity, limiting parallelism to a single aspect and underutilizing computational concurrency. Existing memory partitioning strategies also typically use fixed partitioning, which can degrade performance for varying graph types. To overcome these limitations, we propose an HLS-based method that optimizes queue processing with linked lists. During graph data writes, adjacent edges of the same node are automatically distributed across different memory partitions. This approach includes linked list and queue structures tailored for HLS, facilitating smooth migration of C++ code to FPGA hardware. By enabling pipeline parallelism for both node expansion and adjacent edge exploration, our design maximizes temporal and spatial concurrency. This results achieve near-linear speedup in cycles. In contrast, software parallelism exhibits a significant decline in performance beyond four parallel threads and requires graphs with more than 100 million nodes to achieve noticeable acceleration. | |
| キーワード | （和） | / / / / / / / |
| （英） | High-Level Synthesis / Digital Design / single-source shortest path / Dijkstra / A-Star / / / | |
| 文献情報 | 信学技報, vol. 124, no. 400, VLD2024-120, pp. 96-101, 2025年3月. | |
| 資料番号 | VLD2024-120 | |
| 発行日 | 2025-02-26 (VLD, HWS, ICD) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | VLD2024-120 HWS2024-91 ICD2024-111 |
|
| 研究会情報 | |
| 研究会 | HWS ICD VLD |
| 開催期間 | 2025-03-05 - 2025-03-08 |
| 開催地（和） | みんなの貸会議室 那覇旭町店 |
| 開催地（英） | |
| テーマ（和） | システムオンシリコンを支える設計技術, ハードウェアセキュリティ, 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | VLD |
| 会議コード | 2025-03-HWS-ICD-VLD |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Single-Source Shortest Path FPGA Accelerator Using Multiple Parallel Searches with High-Level Synthesis and Linked List Implementation |
| サブタイトル（英） | |
| キーワード(1)（和/英） | / High-Level Synthesis |
| キーワード(2)（和/英） | / Digital Design |
| キーワード(3)（和/英） | / single-source shortest path |
| キーワード(4)（和/英） | / Dijkstra |
| キーワード(5)（和/英） | / A-Star |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | Haopeng Meng / Haopeng Meng / モウ コウホウ |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： The University of Tokyo) |
| 第2著者 氏名（和/英/ヨミ） | 若林 一敏 / Kazutoshi Wakabayashi / |
| 第2著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： The University of Tokyo) |
| 第3著者 氏名（和/英/ヨミ） | 池田 誠 / Makoto Ikeda / |
| 第3著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： The University of Tokyo) |
| 講演者 | 第1著者 |
| 発表日時 | 2025-03-06 15:55:00 |
| 発表時間 | 25分 |
| 申込先研究会 | VLD |
| 資料番号 | VLD2024-120, HWS2024-91, ICD2024-111 |
| 巻番号（vol） | vol.124 |
| 号番号（no） | no.400(VLD), no.401(HWS), no.402(ICD) |
| ページ範囲 | pp.96-101 |
| ページ数 | 6 |
| 発行日 | 2025-02-26 (VLD, HWS, ICD) |
[研究会発表申込システムのトップページに戻る]