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

情報処理学会

書誌事項

タイトル別名
  • Optimizing Array Aggregating Loops by Incrementalization using Runtime Information

この論文をさがす

説明

配列の要素を集約し，総和・最大値・平均値などを求める処理を繰り返す場合，各繰り返しでの集約結果を再利用することで効率が改善することが多い．Liuら（ACM TOPLAS，2005）はこの効率化を自動的に行う手法を提案した．しかし，Liuらの手法は効率的なコードの生成を制約ソルバによる論理式の単純化に頼っており，どのようなプログラムであれば効率化が可能なのか判然としなかった．これは，プログラムの些細な変更で効率化の成否が変わりかねないため，看過できる問題ではない．本論文では，Liuらの手法をベースに，制約ソルバを用いずに同様の効率化を行う手法を提案する．主要な着想は次の3点である．まず，効率化結果が長方形状の領域の処理の組合せになると仮定することで，論理式の単純化を回避すること．次に，実際にループを実行して得られた配列要素のアクセス履歴を用いることで，論理式を用いたプログラム解析を避けること．そして，自然に書かれたプログラムはその計算の規則性をよく表していると仮定することで，具体的なアクセス履歴からその一般的な法則性を現実的なコストで推測することである．この手法は，制約ソルバの使用を避けられることに加え，プログラムの構文的な細部に効率化の成否が依存しにくい，効率化結果の計算量を自動的に求めることができる，という長所がある．一方で，この手法には効率化結果の正しさが保証されないという欠点もある．以上をふまえた提案手法の現実的な利用方法についても論じる．

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.

収録刊行物

関連プロジェクト

もっと見る

キーワード

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

問題の指摘

ページトップへ