CPUに最適化したSTR-R木による空間結合殻カウント

三橋 龍也  川島 英之  西道 啓博  建部 修見  

誌名
電子情報通信学会論文誌 B   Vol.J100-B   No.12   pp.961-973
発行日: 2017/12/01
Online ISSN: 1881-0209
論文種別: 招待論文 (知的環境とセンシングのシステムとソフトウェア論文特集)
専門分野: 
キーワード: 
空間結合カウント,  STR-R木,  周期境界条件,  SIMD,  

本文: FreePDF(2MB)


あらまし: 
本論文の研究対象は空間結合殻カウントである.空間結合殻カウントとは,空間結合を行った後にカウントを行う処理である.空間結合殻カウントは天文学ではhalo周辺に存在するparticleの数を数え上げるために用いられる.この処理はシミュレーション結果に対して一度だけ実行される.空間結合殻カウントの効率化には,効率的な空間結合が必要である.そこで我々はCPUに最適化したsort-tile-recursive-R木を提案する.提案手法は並列基数整列法,並列ノード梱包法,そしてsingle instruction multiple data命令を活用する.天文データを用いた実験において,提案手法は高性能R木に対して26.8倍の性能改善を示した.我々は更に主記憶に収まらない大規模データを扱うために,局所実体化法を提案する.この方式を効率化するために,我々は構築・検索・破壊パイプライン法を提案する.提案方式は従来技法に比べて27.5倍の高性能化を達成した.コードはGitHubで公開済である.