CUDAを用いた根付き木における高速距離計算手法

摘要

本稿では，CUDAを用いた根付き木における高速距離計算手法を提案する．近年，一般的な計算を高速かつ並列に行うGPGPUが普及しているが，そのほとんどが単純な繰り返し実行に対する手法であり，グラフアルゴリズムに適用する手法はほとんど提案されていない．本稿では，グラフのリストランキングに対する高速化手法の紹介とその応用としての根付き木における高速距離計算手法を提案する．また，実験により，頂点数が1000000個の場合に，C言語によるプログラムと比較して，約200倍の高速化を確認した．