ループによって運ばれる依存を有するループの並列実行時間の見積り

概要

論文の詳細を見る
ループは並列性の重要な源であり、またプログラムの実行時間の大部を占める。そのためこれまで、マルチプロセッサ用に様々なループのイタレーション単位(中粒度)での最適化技法が提案、使用されてきた。一方、スーパースカラ技術をはじめとする、近年のプロセッサ内部における細粒度並列処理技術の普及により、ループボディ内での最適化技法が重要になりつつある。ループ全体の並列実行時間の下限は、こうした異なる粒度での最適化手法の効果を、統一的かつ定量的に評価するのに有用な尺度であろう。ループ全体の並列実行時間の下限は、ループを完全に展開したコードの依存グラフのクリテイカルバスのコストを求めることにより得ることができる。しかしながら、ループを完全に展開することは実用上極めて問題である。本稿では、問題を整数計画問題に帰着させ、このクリティカルパスのコストを、ループを一切展開することなく得る手法を提案する。さらに提案手法を実装、実際のプログラムに適用し、提案手法が実用的な時間でクリテイカルバスのコストを与えることを示す。
一般社団法人情報処理学会の論文
1996-03-05