GPU-BOXにおける中規模グラフに適した並列幅優先探索手法

摘要

グラフ探索アルゴリズムの1つである幅優先探索（BFS）は様々な分野で応用されており，マルチGPUシステムを用いた高速化が近年盛んに研究されている．本研究では，bin sortを応用してCUDAスレッド間のタスクバランスを整えることで，頂点数が2~(15)～2~(25)程度の中規模グラフに有効な並列BFSアルゴリズムを提案し，Ethernet ベースのシステム仮想化技術ExpEtherを用いたマルチGPUシステムの試作機であるGPU-BOXを利用して評価を行う．また2つの先行研究のBFSと比較することで本研究で提案するBFSの特徴と課題について分析する．結果としては，提案BFSを2つの先行研究BFSと比較するとそれぞれ最大6.3倍，10倍の性能を達成し，GPU-BOXを用いた評価ではGPU数を増やすことで緩やかではあるが性能向上が見られた．