式評価順序の最適化による微視的並列度向上

概要

論文の詳細を見る
並列命令実行を前提にした場合、構文木をなるべくバランスするよう式の評価順序をきめ、木の高さを出来るかぎり低くした方が、全体のクリティカルパス長が短くなり高速となる。このような最適化(以下、ハイトリダクションと呼ぶ)は論理回路設計や、大規模並列処理の分野では、重視されてきたが、命令セットレベルでの並列度をあげるための最適化手法としてはあまり取り上げられていない。これは、従来、ハイトリダクションの適用が一つの式、あるいは、基本ブロック内に限定して考えられていたため、実質的な性能向上があまり大きくなかったためと考えられる。しかし、現在では、データフロー解析、ループアンロール等の手法と組み合わせることにより、従来考えられていたよりもはるかに大きな式を並列化の対象とできる。このため、ハイトリダクションの適用による性能向上は、従来の数10%のレベルから、数倍のレベルまで来ていると考えられ、並列処理の性能を左右する重要な技術になると思われる。以下、命令セットレペルでの並列最適化を前提に、アルゴリズムの検討とその拡張および問題点について述べる。
一般社団法人情報処理学会の論文
1992-02-24