講演抄録/キーワード |
講演名 |
2023-06-08 16:00
FPGAによるプリム法の並列化とその性能評価 ○王 紀恒・金澤健治・安永守利(筑波大) RECONF2023-3 |
抄録 |
(和) |
無向グラフ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 / / / / |
文献情報 |
信学技報, vol. 123, no. 71, RECONF2023-3, pp. 13-16, 2023年6月. |
資料番号 |
RECONF2023-3 |
発行日 |
2023-06-01 (RECONF) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
査読に ついて |
本技術報告は査読を経ていない技術報告であり,推敲を加えられていずれかの場に発表されることがあります. |
PDFダウンロード |
RECONF2023-3 |
研究会情報 |
研究会 |
RECONF |
開催期間 |
2023-06-08 - 2023-06-09 |
開催地(和) |
高知工科大学永国寺キャンパス |
開催地(英) |
Eikokuji Campus, Kochi University of Technology |
テーマ(和) |
リコンフィギャラブルシステム,一般 |
テーマ(英) |
Reconfigurable system, etc. |
講演論文情報の詳細 |
申込み研究会 |
RECONF |
会議コード |
2023-06-RECONF |
本文の言語 |
日本語 |
タイトル(和) |
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 |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第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) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2023-06-08 16:00:00 |
発表時間 |
25分 |
申込先研究会 |
RECONF |
資料番号 |
RECONF2023-3 |
巻番号(vol) |
vol.123 |
号番号(no) |
no.71 |
ページ範囲 |
pp.13-16 |
ページ数 |
4 |
発行日 |
2023-06-01 (RECONF) |