ログイン 新規登録
言語:

WEKO3

  • トップ
  • ランキング
To
lat lon distance
To

Field does not validate



インデックスリンク

インデックスツリー

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 論文誌(トランザクション)
  2. プログラミング(PRO)
  3. Vol.14
  4. No.5

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

https://ipsj.ixsq.nii.ac.jp/records/213895
https://ipsj.ixsq.nii.ac.jp/records/213895
a997c9eb-b39d-49f6-81a5-3d5026654b03
名前 / ファイル ライセンス アクション
IPSJ-TPRO1405002.pdf IPSJ-TPRO1405002.pdf (727.9 kB)
Copyright (c) 2021 by the Information Processing Society of Japan
オープンアクセス
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
著者名 松田, 知樹

× 松田, 知樹

松田, 知樹

Search repository
森畑, 明昌

× 森畑, 明昌

森畑, 明昌

Search repository
著者名(英) Tomoki, Matsuda

× Tomoki, Matsuda

en Tomoki, Matsuda

Search repository
Akimasa, Morihata

× Akimasa, Morihata

en Akimasa, Morihata

Search repository
論文抄録
内容記述タイプ 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
収録物識別子 AA11464814
書誌情報 情報処理学会論文誌プログラミング(PRO)

巻 14, 号 5, p. 1-14, 発行日 2021-11-25
ISSN
収録物識別子タイプ ISSN
収録物識別子 1882-7802
出版者
言語 ja
出版者 情報処理学会
戻る
0
views
See details
Views

Versions

Ver.1 2025-01-19 16:58:47.300108
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3