大規模グラフ処理のための再構成可能カスタムアクセラレータの開発

开发用于大规模图形处理的可重构定制加速器

• 批准号: 15J04973
• 负责人: 武井 康浩
• 金额: $ 1.09万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2015
• 资助国家: 日本
• 起止时间: 2015-04-24 至 2017-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15J04973/
• 关键词: カスタムアクセラレータ; 大規模グラフ処理; FPGA

本年度の研究実績として、外部ストレージとのデータ転送時間を削減するためのグラフデータ圧縮法、および最短経路検索の計算に必要な中間結果の記憶量の削減手法を提案した。大規模グラフにおける最短経路検索を処理する場合において、入力グラフのデータ量が外部メモリ以上の場合は転送帯域の小さいストレージを使用する必要があり、転送時間が増大する。そのため、コンパクトな記憶量と高効率な処理を両立する簡潔データ構造を入力グラフに適用して、データ伸長のためのハードウェアをFPGAに実装した。アメリカの道路ネットワーク（2395万ノード、5833万エッジ）を簡潔グラフ化した場合のデータ量について、エッジのアドレスを示すIndex情報のデータ量が88%削減されていることが確認された。しかしながら，エッジの重みと接続ノードを示すデータ量が大きいため、グラフ全体のデータ量の削減率が18%にとどまっていることが確認されたため、テキスト圧縮を応用したデータ圧縮法の応用を検討している。最短経路検索における中間結果の記憶量削減について、最短経路問題のアルゴリズムであるダイクストラ法におけるノードアクセスの順序を考慮して、現在ノードにおける距離のデータを専用レジスタに記憶して、新たに現在ノードに隣接した未確定ノードのデータを前の現在ノードデータに上書きできるアクセラレータをFPGAに実装した。格子グラフにおける1 点対全点最短経路問題の処理中にノードメモリに格納されるノードデータ数について、全体のノード数の約1/3 程度であることが確認された。また、 FPGAアクセラレータの処理性能の見積もりをCPUと比較すると，ノード数が4096 のグラフの最短経路検索に対して，CPU の約60 倍の処理速度になる見積もりが得られた。

This year, we have studied the method of calculating the time of delivery, the method of calculating the shortest route, the method of calculating the necessary results, and the method of calculating the time of dispatch. Large-scale equipment is required to ensure that the shortest route is closed, and that the input volume is in line with that of the external vehicle. The delivery domain is small and the delivery time is high. In this paper, the author points out that the input force is very high, and that the input force is very high. In this paper, the system is used in the system, and the system is used in the system. In the system, the system is used in the system, and the equipment is installed in the system.

项目成果

Evaluation of an FPGA-Based Shortest-Path-Search Accelerator

基于 FPGA 的最短路径搜索加速器的评估

• 发表时间: 2015
• 作者: Yasuhiro Takei;Masanori Hariyama and Michitaka Kameyama
• 通讯作者: Masanori Hariyama and Michitaka Kameyama

FPGA-Oriented Design of an FDTD Accelerator Based on Overlapped Tiling

面向 FPGA 的基于重叠平铺的 FDTD 加速器设计

• 发表时间: 2015
• 作者: Yasuhiro Takei;Hasitha Muthumala Waidyasooriya;Masanori Hariyama and Michitaka Kameyama
• 通讯作者: Masanori Hariyama and Michitaka Kameyama

Data-Transfer-Aware Design of an FPGA-Based Heterogeneous Multicore Platform with Custom Accelerators

具有定制加速器的基于 FPGA 的异构多核平台的数据传输感知设计

• DOI: 10.1587/transfun.e98.a.2658
• 发表时间: 2015
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: Yasuhiro Takei;Hasitha Muthumala Waidyasooriya;Masanori Hariyama and Michitaka Kameyama
• 通讯作者: Masanori Hariyama and Michitaka Kameyama