| 講演名 | 2023-06-08 FPGAによるプリム法の並列化とその性能評価 王 紀恒(筑波大), 金澤 健治(筑波大), 安永 守利(筑波大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 無向グラフGの部分グラフのうち，連結かつ閉路を含まないものを木という．Gの全ての頂点が含まれる木を全域木，全域木のうち，枝のコストの総和が最小であるものを最小全域木という．最小全域木には，通信ネットワークの最適設計，巡回セールスマン問題における上界・下界の算出など，多くの応用が存在する．本研究では，最小全域木を求める厳密解法のひとつであるプリム法をFPGA上に並列実装し，その性能評価を行った．評価の結果，提案手法の実行速度は最速で，Intel CPUによる実行速度の2.1倍の高速化を実現できた． |
| 抄録(英) | A subgraph of an undirected graph G that is connected and contains no closed paths is called a tree, a global tree is a tree that contains all vertices of G, and a minimum global tree is a global tree with the minimum total cost of all its branches. There are many applications of minimum global tree, such as optimal design of communication networks and calculation of upper and lower bounds in traveling salesman problems. In this study, we implemented the Prim's method, one of the exact solution methods for minimum global tree, in parallel on FPGA and evaluated its performance. The evaluation results showed that the proposed method was the fastest, 2.1 times faster than the execution speed on Intel CPUs. |
| キーワード(和) | FPGA / プリム法 / 高位合成 / 並列化 |
| キーワード(英) | FPGA / Prim's algorithm / High-Level Synthesis / Parallelization |
| 資料番号 | RECONF2023-3 |
| 発行日 | 2023-06-01 (RECONF) |
| 研究会情報 | |
| 研究会 | RECONF |
|---|---|
| 開催期間 | 2023/6/8(から2日開催) |
| 開催地（和） | 高知工科大学永国寺キャンパス |
| 開催地（英） | Eikokuji Campus, Kochi University of Technology |
| テーマ（和） | リコンフィギャラブルシステム，一般 |
| テーマ（英） | Reconfigurable system, etc. |
| 委員長氏名（和） | 山口 佳樹(筑波大) |
| 委員長氏名（英） | Yoshiki Yamaguchi(Tsukuba Univ.) |
| 副委員長氏名（和） | 井口 寧(北陸先端大) / 泉 知論(立命館大) |
| 副委員長氏名（英） | Yasushi Inoguchi(JAIST) / Tomonori Izumi(Ritsumeikan Univ.) |
| 幹事氏名（和） | 小林 悠記(NEC) / 佐藤 幸紀(豊橋技科大) |
| 幹事氏名（英） | Yuuki Kobayashi(NEC) / Yukinori Sato(Toyohashi Univ. of Tech.) |
| 幹事補佐氏名（和） | 竹村 幸尚(インテル) / 長名 保範(熊本大) |
| 幹事補佐氏名（英） | Yukitaka Takemura(INTEL) / Yasunori Osana(Kumamoto Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Reconfigurable Systems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | FPGAによるプリム法の並列化とその性能評価 |
| サブタイトル（和） | |
| タイトル（英） | Parallelization of Prim's Algorithm Using FPGA and Its Performance Evaluation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | FPGA / FPGA |
| キーワード(2)（和/英） | プリム法 / Prim's algorithm |
| キーワード(3)（和/英） | 高位合成 / High-Level Synthesis |
| キーワード(4)（和/英） | 並列化 / Parallelization |
| 第 1 著者 氏名（和/英） | 王 紀恒 / Noritsune O |
| 第 1 著者 所属（和/英） | 筑波大学(略称：筑波大) University of Tsukuba(略称：Univ. of Tsukuba) |
| 第 2 著者 氏名（和/英） | 金澤 健治 / Kenji Kanazawa |
| 第 2 著者 所属（和/英） | 筑波大学(略称：筑波大) University of Tsukuba(略称：Univ. of Tsukuba) |
| 第 3 著者 氏名（和/英） | 安永 守利 / Moritoshi Yasunaga |
| 第 3 著者 所属（和/英） | 筑波大学(略称：筑波大) University of Tsukuba(略称：Univ. of Tsukuba) |
| 発表年月日 | 2023-06-08 |
| 資料番号 | RECONF2023-3 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | RECONF-71 |
| ページ範囲 | pp.13-16(RECONF), |
| ページ数 | 4 |
| 発行日 | 2023-06-01 (RECONF) |