配列集約ループの実行時情報を用いた漸増化による効率化

• Item type: Trans(1)
• 公開日: 2021-11-25
• タイトル: 配列集約ループの実行時情報を用いた漸増化による効率化
• タイトル / 言語: en
• タイトル: Optimizing Array Aggregating Loops by Incrementalization using Runtime Information
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [通常論文] 配列集約，漸増化，実行時情報
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学大学院総合文化研究科
• 著者所属: 東京大学大学院総合文化研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Arts and Sciences, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Arts and Sciences, The University of Tokyo
• 著者名: 松田, 知樹; 森畑, 明昌
• 著者名(英): Tomoki, Matsuda; Akimasa, Morihata
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 配列の要素を集約し，総和・最大値・平均値などを求める処理を繰り返す場合，各繰り返しでの集約結果を再利用することで効率が改善することが多い．Liuら（ACM TOPLAS，2005）はこの効率化を自動的に行う手法を提案した．しかし，Liuらの手法は効率的なコードの生成を制約ソルバによる論理式の単純化に頼っており，どのようなプログラムであれば効率化が可能なのか判然としなかった．これは，プログラムの些細な変更で効率化の成否が変わりかねないため，看過できる問題ではない．本論文では，Liuらの手法をベースに，制約ソルバを用いずに同様の効率化を行う手法を提案する．主要な着想は次の3点である．まず，効率化結果が長方形状の領域の処理の組合せになると仮定することで，論理式の単純化を回避すること．次に，実際にループを実行して得られた配列要素のアクセス履歴を用いることで，論理式を用いたプログラム解析を避けること．そして，自然に書かれたプログラムはその計算の規則性をよく表していると仮定することで，具体的なアクセス履歴からその一般的な法則性を現実的なコストで推測することである．この手法は，制約ソルバの使用を避けられることに加え，プログラムの構文的な細部に効率化の成否が依存しにくい，効率化結果の計算量を自動的に求めることができる，という長所がある．一方で，この手法には効率化結果の正しさが保証されないという欠点もある．以上をふまえた提案手法の現実的な利用方法についても論じる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: When a loop repeatedly summarizes array elements to calculate the total, the maximum, the average, etc., reuse of previously calculated summaries often improves efficiency. Liu et al. (ACM TOPLAS, 2005) proposed a method of automatically performing such optimization. Its drawback is the unpredictability of the result caused by the reliance on logical formula simplification using a constraint solver. This drawback is not negligible because a minor modification of the program may lead to unexpected failure. This paper proposes a method that performs optimization similar to theirs without using constraint solvers. It consists of three key ideas. First, it avoids simplifications of logical formulae by assuming that the optimized code consists of iterations over rectangular regions. Second, it uses concrete execution traces instead of logical formulae. Third, it infers invariants from the execution traces at realistic costs by postulating naturally written programs to represent the invariant. The proposed method uses no constraint solvers. Moreover, it is more agnostic to syntactic code variations and can automatically estimate the computational complexity of the optimized code. Unfortunately, the optimized code is not guaranteed to be correct. We discuss two practical use-case scenarios for which the correctness issue is less problematic.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 14, 号 5, p. 1-14, 発行日 2021-11-25
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会