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

DOI

書誌事項

タイトル別名
  • Shared-Memory Parallelization of FP-growth with Dynamic Load Estimation and Balancing

抄録

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

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1390851320454027392
  • NII論文ID
    130008051574
  • DOI
    10.11517/pjsai.jsai2021.0_2h1gs3a04
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
    • CiNii Articles
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ