情報処理学会 第79回全国大会講演要旨

Graph500ベンチマークのTop-downアプローチによる幅優先探索において，複数レベルの並列性を利用する階層的並列処理手法を提案する。Top-downアプローチによる幅優先探索では，従来より探索最前線（Frontier）レベルの並列性を利用する並列探索が行われているが，提案手法では複数レベル（Frontierレベルと隣接頂点Neighborsレベル）の並列性を利用することにより，さらなる速度向上を実現する。提案手法はOpenMP実装されており，並列システムIBM POWER S812L（12コア，SMT=8）上で性能評価を行った結果，Graph500ベンチマークにおいて，従来手法より高い速度向上を得ることができ，提案手法の有効性が確認された。