最早実行可能条件解析を用いたキャッシュ利用の最適化

• Item type: SIG Technical Reports(1)
• 公開日: 1998-08-05
• タイトル: 最早実行可能条件解析を用いたキャッシュ利用の最適化
• タイトル / 言語: en
• タイトル: A Cache Optimization with Earliest Executable Condition Analysis
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学理工学部電子電気情報工学科
• 著者所属: 早稲田大学理工学部電子電気情報工学科
• 著者所属: 早稲田大学理工学部電子電気情報工学科
• 著者所属: 早稲田大学理工学部電子電気情報工学科
• 著者所属: （株）東芝
• 著者所属: 早稲田大学理工学部電子電気情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Electrical, Electronics and Computer Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Department of Electrical, Electronics and Computer Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Department of Electrical, Electronics and Computer Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Department of Electrical, Electronics and Computer Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): TOSHIBA Corporation
• 著者所属(英): en
• 著者所属(英): Department of Electrical, Electronics and Computer Engineering, Waseda University
• 著者名: 稲石大祐; 木村, 啓二; 藤本, 謙作; 尾形, 航; 岡本, 雅巳; 笠原, 博徳
• 著者名(英): Daisuke, Inaishi; Keiji, Kimura; Kensaku, Fujimoto; Wataru, Ogata; Masami, Okamoto; Hironori, Kasahara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 従来のコンパイラによる単一プロセッサ用キャッシュ最適化は個々のループを対象としているため、プログラム全体に比べると局所的な最適化が多く、プログラム全域を対象としたキャッシュ最適化は行われていない。そこで本稿では、最早実行可能条件解析を利用した単一プロセッサ上でのFORTRANプログラムのキャッシュ最適化手法を提案する。OSCAR FORTRANマルチグレイン自動並列化コンパイラは、FORTRANプログラムをループ・サブルーチン・基本ブロックの3種のマクロタスク(MT)に分割し、各MTに最早実行可能条件解析を行いマクロタスクグラフ(MTG)を生成する。MTGは制御依存及びデータ依存に基づくMT間の実行順序制約、及びMT間で授受されるデータに関する情報を表現する。本手法ではこのMTGを用いて、先行MTによってアクセスされたデータにアクセスする後続MTが先行MTの直後に実行されるよう大域的なコード移動を行い、キャッシュヒット率を向上させる。本手法は、OSCAR FORTRANマルチグレイン自動並列化コンパイラ中に、最適化された逐次型FORTRANを出力するプリプロセッサ機能として実現されている。CG法プログラムを用いた本キャッシュ最適化手法の性能評価結果を行ったところ167MHz UltraSPARC上で最高62%の速度向上が得られた。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Cache optimizations by a compiler for a single processor machine have been mainly applied to a singlenested loop. On the contrary, this paper proposes a cache optimization scheme using earliest executable condition analysis for FORTRAN programs on a single processor system. OSCAR FORTRAN multi-grain automatic parallelizing compiler decomposes a FORTRAN program into three types of macrotasks (MT), such as loops, subroutines and basic blocks, and analyzes the earliest executable condition of each MT to extract coarse grain parallelism among MTs and generates a macrotask graph (MTG). The MTG represents data dependence and extended control dependence among MTs and an information of shared data among MTs. By using this MTG, a compiler realizes global code motion to use cache effectively. The code motion technique moves a MT, which accesses data accessed by a precedent MT on MTG, immediately after the precedent MT to increase a cache hit rate. This optimization is realized using OSCAR multi-grain compiler as a preprocessor to output an optimized sequential FORTRAN code. A performance evaluation shows about 62% speed up compared with original program on 167MHz UltraSPARC.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 情報処理学会研究報告計算機アーキテクチャ（ARC）; 巻 1998, 号 70(1998-ARC-130), p. 31-36, 発行日 1998-08-05
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会