[2H1-GS-3a] 知識の利用：基礎

[2H1-GS-3a-04] 動的なタスク量推定と負荷分散を備えた FP-growth 法の共有メモリ型並列化

〇櫻井 健太朗¹、亀谷 由隆¹ (1. 名城大学)

キーワード：頻出パターン発見、並列化

トランザクションデータベースに頻出するパターンを効率的に列挙するアルゴリズムとしてFP-growth法があり、データベースから有用なパターンを得ることができる。しかし巨大なデータセットに対する実行時間は依然問題である。そこで本研究では、メニーコアマシン上での共有メモリ型システムにおけるFP-growth法の並列処理によって高速化を行う。並列化はタスク並列のアプローチを取り、各タスクはFP-Treeから条件付きトランザクション集合を取得し、条件付きFP-Treeを構築後、次の分岐に対するタスクを生成する。タスクの並列処理ではWork-Stealingによる動的負荷分散を行ってスレッド間のロードバランスを向上させる。その際、条件付きFP-Treeに基づくタスク量推定を行ってスケジューリングコストを軽減する。また、計算資源を効率的に使用するために、ガーベジコレクションを持たないコンパイル型言語であるRustを用いて実装する。実験の結果、多くのベンチマークデータにおいてJava実装と比べたときのメモリ消費の軽減と、既存手法を上回る速度向上が得られることを確認した。