自動並列化コンパイラにおける性能指向型統合的並列化・コード最適化技術に関する研究

点击翻译按钮获取中文摘要

今年度は,i)選択的データフロー解析適用技術の開発,ii)性能指向型統合的並列化/コード最適化処理適用アルゴリズムの開発,iii)プロファイリングに基づくプログラム実行時間予測技術の開発を行うことを計画し,以下の成果を得た.1.昨年度,選択的データフロー解析適用技術の手段として考案した剰余区間演算は情報処理学会論文誌に採録された.剰余区間演算は,従来浮動小数点の誤差解析等で用いられていた区間演算に法と剰余の概念を導入し,整数集合に対して代数演算および集合演算を定義した演算体系である.2.今年度の最大の業績は,剰余区間演算を単調データフローシステムに組み込み,変数ならびに式の値域を静的に解析するアルゴリズム,剰余区間伝播を考案したことである.単調データフローシステムを用いて値域解析を行うアルゴリズムはすでに発表されているが,これらのアルゴリズムはループのストライドが1より大きいケースでは解析の精度が落ちる.また,プログラム中の分岐条件式がX<Yのように簡単なものに限られた.剰余区間は整数の飛びが表現できるためループストライドが1より大きいケースに対処でき,また剰余区間伝播はX+Y<Zのような複雑な分岐条件式にも対処できる.配列添字式の値域解析に剰余区間伝播を適用することによりデータ依存解析や配列参照解析が行えるほか,並列処理以外の分野では,シリコンコンパイルにおいて重要なデータパス幅の解析にも剰余区間伝播を利用できる.さらに,剰余区間演算は演算の際に,実際の整数集合よりは大きな答えを出す演算誤差の問題があるが,剰余区間演算の誤差削減法の研究を昨年度に続けて行った.3.遺伝的アルゴリズムを用いてプログラム分割ならびにデータ分割配置の最適化を行った.分枝限定法では大きな問題が解けなかったが,遺伝的アルゴリズムを用いたところ,大きな問題の解が実用的な時間で得られた.