B-014
GPU による看板配置問題の効率的並列計算

◎大石真生・渡邉貴之（静岡県大）

看板配置問題とは、道路上に看板を配置する際に少数でより多くの人の目に留まるように効果的な配置場所を求める問題である。複数の看板の配置場所を決定するために集合媒介中心性を用いる。集合媒介中心性とは、単独のノードに着目した媒介中心性を集合としてのノード群の協調的振る舞いに拡張した中心性である。先行研究では、集合媒介中心性に基づく看板配置問題の近似解をGPUによるedge-basedの並列処理で求めるアルゴリズムを提案している。しかし、ネットワークの直径が大きい道路網に対しては並列処理による高速化の効果が得られていない。本報告では不要なメモリアクセスや分岐を削減するためにwork-efficient技法を取り入れてアルゴリズムの効率化を行い、その結果を示す。