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

• Item type: SIG Technical Reports(1)
• 公開日: 1996-03-05
• タイトル: ループによって運ばれる依存を有するループの並列実行時間の見積り
• タイトル / 言語: en
• タイトル: Estimating Parallel Execution Time of Loops with Loop - Carried Dependences
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属: Center for Supercomputing Research and Development University of Illinois at Urbana - Champaign
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Nara Institiute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Nara Institiute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Center for Supercomputing Research and Development, University of Illinois at Urbana - Champaign
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Nara Institiute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Nara Institiute of Science and Technology
• 著者名: 中西, 恒夫; 城和貴; D.PolychronopoulosConstantine; 福田, 晃; 荒木, 啓二郎
• 著者名(英): Tsuneo, Nakanishi; Kazuki, Joe; Constantine, D.Polychronopoulos; Akira, Fukuda; Keijiro, Araki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ループは並列性の重要な源であり、またプログラムの実行時間の大部を占める。そのためこれまで、マルチプロセッサ用に様々なループのイタレーション単位（中粒度）での最適化技法が提案、使用されてきた。一方、スーパースカラ技術をはじめとする、近年のプロセッサ内部における細粒度並列処理技術の普及により、ループボディ内での最適化技法が重要になりつつある。ループ全体の並列実行時間の下限は、こうした異なる粒度での最適化手法の効果を、統一的かつ定量的に評価するのに有用な尺度であろう。ループ全体の並列実行時間の下限は、ループを完全に展開したコードの依存グラフのクリティカルパスのコストを求めることにより得ることができる。しかしながら、ループを完全に展開することは実用上極めて問題である。本稿では、問題を整数計画問題に帰着させ、このクリティカルパスのコストを、ループを一切展開することなく得る手法を提案する。さらに提案手法を実装、実際のプログラムに適用し、提案手法が実用的な時間でクリティカルパスのコストを与えることを示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Loops are a rich source of parallelism and account for the largest part of program execution time, thus various kinds of loop restructuring schemes have been applied to loops. On the other hand optimization schemes for loop bodies increase their importance because of popularization of the fine-grain parallel processing technology such as the superscalar technology in recent years. The infimum of parallel execution time of a whole loop will be a reasonable criterion to evaluate the application effects of these optimization schemes with different granularity in a unified and quantitative manner. The infimum can be obtained by completely unrolling a given loop, generating a dependence graph (DAG) of the unrolled loop, and evaluating a critical path cost of the dependence graph. However, this method lacks scalability against the loop size. In this paper we propose a scheme to evaluate the critical path cost of the dependence graph of the completely unrolled code of a given loop without unrolling the loop at all by reducing the problem into an integer programming problem. Furthermore, we do an experimental implementation to apply the proposed scheme to actual programs and demonstrate that the practical computational complexity of our algorithm is extremely small and especially independent of the loop size.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 情報処理学会研究報告計算機アーキテクチャ（ARC）; 巻 1996, 号 23(1995-ARC-117), p. 25-30, 発行日 1996-03-05
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会