Optimizing Utilization of Memory Hierarchy Based on Code Motion

（邦訳：コード移動に基づくメモリ階層利用最適化）

澄川靖信
東京理科大学理工学部情報科学科助教

［背景］プロセッサとメモリアクセス時間の差の拡大
［問題］性能差を解消するためのレジスタとキャッシュメモリの効率的な使用
［貢献］メモリ階層の利用を統一的に効率化するコード移動法の実現

現代の多くのコンピュータはレジスタ・キャッシュメモリ・メインメモリを使用している．これらのメモリは，左から順に，短時間でアクセスできるが，格納できるデータ量が少ないので，階層的に使うことによってシステムの高速化と拡張性を実現している．しかしながら，プロセッサとメモリアクセス時間の差は年々拡大しており，今後もこの傾向が続くと考えられるので，メインメモリへのアクセス回数を減らすことが重要である．

本研究では，プログラムにある命令の実行点を変更することによってメインメモリへのアクセス回数を減らす枠組みを，コンパイラのコード最適化の手法として実現した．本手法は次の2種類に分類できる．

1）メモリ参照のレジスタ参照への変更．

冗長なメモリ参照命令を，以前の実行結果を記録する変数を使用するように変更して，除去する．変数のデータはレジスタに記録されるので，冗長なメモリ参照の除去はメモリ参照回数を低減する．

2）キャッシュミスによるメインメモリへのアクセス回数の低減．
キャッシュメモリのデータを再利用できるように配列参照の実行順序を変更する．

本研究で実現した手法を以下に述べる．

1.　冗長性の除去

本研究では冗長性を除去する最適化の1つの手法である部分冗長除去（partial redundancy elimination, PRE）を基本とする．一般的なPREはプログラム全体を解析して字面が同じ冗長な命令を除去する．しかしながら，字面の異なる冗長な命令を除去するためにはPREを繰り返し適用する必要があるので解析コストが高くなる傾向があることと，ループの繰返しを跨いだ冗長性を除去できないことの2つの問題がある．これらの問題を解決するために次の2つの手法を実現した．

1-1.　異なる字面の冗長性を検出できる最適化手法である大域値番号付けと，プログラムの一部を解析する質問伝播を組み合わせることによって，解析効率の向上を実現した．

1-2.　1-1の提案手法で使用した質問伝播を，異なる繰返しの冗長性を解析できるように拡張し，プログラムの実行効率を向上することを示した．

2.　キャッシュミスの低減

プログラムがメインメモリのx番地のデータを使うとき，x番地を含む近傍の番地からデータを読み出し，そのコピーをキャッシュメモリに格納する．配列のデータはメインメモリ上に連続して配置されるので，プログラムが同じ配列へのアクセスを連続して実行するとキャッシュメモリのデータを再利用できる可能性が高い．また，多次元配列の場合，上位次元はその下位次元の配列を意味するので，多くの上位次元が連続して一致する配列参照を連続して実行すると，データを再利用できる可能性がさらに高いと考えられる．

本研究では，PREを，冗長性の除去だけでなく，配列の参照順序の連続化と，同一の配列参照の中でも上位次元から連続して一致する次元数が多いものを続けて実行するように各参照を移動するように拡張し，多くのプログラムでキャッシュミス数を低減することを確認した．

本研究によって，PREを基本とした統一的な枠組みでメモリ階層利用の効率化を行うことが可能となった．

（2015年6月10日受付）

取得年月日：2015年3月
学位種別：博士（理学）
大学：東京理科大学

推薦文：（プログラミング研究会）

本論文は命令を並べ替えることによって，メモリ階層の有効利用を促進する手法を提案している．命令の移動に基づくメモリ階層の統一的な扱いは珍しく，コード最適化の分野に新しい道を開いた意味は大きい．

著者からの一言：

指導教員の滝本教授，ならびにプログラミング研究会をはじめとする国内外の学会でお会いした皆様にいただいたご指導，ご支援のおかげで，これまでの成果を博士論文としてまとめることができました．お世話になりました方々にこの場をお借りして改めて御礼申し上げます．今後も計算機科学の発展に貢献できるように，研究に励んで参ります．

2014年度へ戻る

このページの先頭へ