著者

勝原 達也 滝本 宗宏

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.48, no.SIG12(PRO34), pp.52-65, 2007-08-15

---

命令レベル並列性を高める有効な手法の 1 つとして、命令スケジューリングがある。特に、投機的実行を許す命令スケジューリングは、さらに並列度を高められる点で効果的であることが知られている。投機的実行は、元のプログラムに存在しなかった冗長性を導入する可能性があるので、1 つの命令をスケジュールするたびに共通部分式の削除を適用することが効果的である。本発表では、共通部分式の削除で取り除くことができない部分冗長性を扱う部分冗長除去に注目し、部分冗長除去に基づく大域命令スケジューリングを提案する。本手法は、あるプログラム点に対して、投機的命令スケジューリングを含むコードの上方移動を行うごとに、部分冗長除去のデータフロー解析を適用する。解析結果から最適化効果が認められる場合、実際にプログラムを変更することで、命令スケジューリングを実現する。部分冗長除去の性質は、プログラムの実行パスを長くしないことを保証し、大域命令スケジューリングで問題となる補償コードを最適なプログラム点に自動的に挿入する。また、本手法は、ループ構造を認識することなく、ループスケジューリング手法の 1 つである、ループシフティングを実現することができる。さらに本論文では、本手法を COINS コンパイラ・インフラストラクチャ上で実装し、最適化効果を検証する。