A Study on Approaches to the Efficient Use of Partial Results of Divide-and-Conquer Accumulation

条件を満たすすべての点（解）に関する統計的な処理として，なんらかの指標で集計を行いたい場合はしばしばある．その際，点の存在可能な領域（探索空間）に関して階層的に分割統治を行い，部分領域に関して探索/集計した部分的な結果を得ることができれば，結果のない部分領域だけ探索/集計する形で耐障害性を高めたり，並列処理によって速度向上を得たりする機会が増えると期待できる．しかし，すでに求めた部分的な集計結果を更新する形で次の部分領域の探索/集計を続ける方式と比較すると，個別の集計先の初期化コストが問題となり得る．ヒストグラムを得る集計はその代表例といえ，全階級が0の初期配列の準備コストは問題といえる．特に枝刈り等で探索時間や条件を満たす点がほとんどない場合には，初期化オーバヘッドは相対的に大きくなる．そこで，本発表では，一括割当てした連続メモリのバッファ上に，複数の部分領域それぞれで見つかった点の階級のリストを得ておき，必要に応じて部分領域別に集計するプログラミング手法を提案する．提案方式では，共通バッファ上のheadから各リストの要素をtailの位置に追加していくことで，部分領域別に条件を満たす点の仮集計リストを効率良く求めつつ，リストごとのheadとtailを空き領域の先頭に設置する初期化や分割された隣り合う領域に関するリストの連結（分割統治後のマージ）も素早く行うことが可能となる．

As statistical analysis over all points (solutions) that satisfy a given condition, we often summarize them. If we can hierarchically divide and conquer the domain (search space) of possible points and we can obtain partial results of search/summarization for hierarchical subdomains, we can improve fault tolerance by searching/summarizing points only for a subdomain where the result is unavailable, and also we can achieve parallel speedups. However, in comparison to the cases where we continue to search/summarize points for the subsequent subdomain by updating the once obtained partial result, initialization of each initial summary (for accumulation) may be costly. To summarize points as histograms is a typical example, where we usually initialize an initial array of all zeros over all ranks. The initialization cost is relatively high if search time is small by pruning and/or there are few points satisfying the condition. In this presentation, we propose programming styles where we allocate a sufficient buffer as consequent memory for continuously obtaining a list of ranks of found points for each of multiple subdomains over the buffer, and make a summary of each subdomain as needed. In the proposed approach, by starting at the head position over the common buffer and subsequently appending list elements at the tail position, we can not only efficiently obtain a semi-summarized list of found points for each of multiple subdomains but also enable quick initialization by setting the head and tail of each list at the beginning of the current free buffer area and quick append of lists for the divided lateral subdomains (merging after divide-and-conquering).