著者

稲石大祐 木村 啓二 藤本 謙作 尾形 航 岡本 雅巳 笠原 博徳

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告計算機アーキテクチャ(ARC) (ISSN:09196072)

巻号頁・発行日

vol.1998, no.70, pp.31-36, 1998-08-05

被引用文献数

2

---

従来のコンパイラによる単一プロセッサ用キャッシュ最適化は個々のループを対象としているため、プログラム全体に比べると局所的な最適化が多く、プログラム全域を対象としたキャッシュ最適化は行われていない。そこで本稿では、最早実行可能条件解析を利用した単一プロセッサ上でのFORTRANプログラムのキャッシュ最適化手法を提案する。OSCAR FORTRANマルチグレイン自動並列化コンパイラは、FORTRANプログラムをループ・サブルーチン・基本ブロックの3種のマクロタスク(MT)に分割し、各MTに最早実行可能条件解析を行いマクロタスクグラフ(MTG)を生成する。MTGは制御依存及びデータ依存に基づくMT間の実行順序制約、及びMT間で授受されるデータに関する情報を表現する。本手法ではこのMTGを用いて、先行MTによってアクセスされたデータにアクセスする後続MTが先行MTの直後に実行されるよう大域的なコード移動を行い、キャッシュヒット率を向上させる。本手法は、OSCAR FORTRANマルチグレイン自動並列化コンパイラ中に、最適化された逐次型FORTRANを出力するプリプロセッサ機能として実現されている。CG法プログラムを用いた本キャッシュ最適化手法の性能評価結果を行ったところ167MHz UltraSPARC上で最高62%の速度向上が得られた。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.