分割統治型総和の部分的計算結果を効率良く利用する方式の研究

• Item type: Trans(1)
• 公開日: 2019-05-21
• タイトル: 分割統治型総和の部分的計算結果を効率良く利用する方式の研究
• タイトル / 言語: en
• タイトル: A Study on Approaches to the Efficient Use of Partial Results of Divide-and-Conquer Accumulation
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [発表概要，Unrefereed Presentation Abstract]
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 九州工業大学大学院情報工学府
• 著者所属: 九州工業大学大学院情報工学研究院
• 著者所属: 京都大学学術情報メディアセンター
• 著者所属: 京都大学大学院情報学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Artificial Intelligence, Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): Academic Center for Computing and Media Studies, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者名: 佐多, 育斗; 八杉, 昌宏; 平石, 拓; 馬谷, 誠二
• 著者名(英): Ikuto, Sata; Masahiro, Yasugi; Tasuku, Hiraishi; Seiji, Umatani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 条件を満たすすべての点（解）に関する統計的な処理として，なんらかの指標で集計を行いたい場合はしばしばある．その際，点の存在可能な領域（探索空間）に関して階層的に分割統治を行い，部分領域に関して探索/集計した部分的な結果を得ることができれば，結果のない部分領域だけ探索/集計する形で耐障害性を高めたり，並列処理によって速度向上を得たりする機会が増えると期待できる．しかし，すでに求めた部分的な集計結果を更新する形で次の部分領域の探索/集計を続ける方式と比較すると，個別の集計先の初期化コストが問題となり得る．ヒストグラムを得る集計はその代表例といえ，全階級が0の初期配列の準備コストは問題といえる．特に枝刈り等で探索時間や条件を満たす点がほとんどない場合には，初期化オーバヘッドは相対的に大きくなる．そこで，本発表では，一括割当てした連続メモリのバッファ上に，複数の部分領域それぞれで見つかった点の階級のリストを得ておき，必要に応じて部分領域別に集計するプログラミング手法を提案する．提案方式では，共通バッファ上のheadから各リストの要素をtailの位置に追加していくことで，部分領域別に条件を満たす点の仮集計リストを効率良く求めつつ，リストごとのheadとtailを空き領域の先頭に設置する初期化や分割された隣り合う領域に関するリストの連結（分割統治後のマージ）も素早く行うことが可能となる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 12, 号 2, p. 21-21, 発行日 2019-05-21
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会