@article{oai:nagoya.repo.nii.ac.jp:00008567,
 author = {三田, 勝史 and SANDA, KATSUSHI and 朝倉, 宏一 and ASAKURA, KOICHI and 渡邉, 豊英 and WATANABE, TOYOHIDE},
 issue = {4},
 journal = {情報処理学会論文誌},
 month = {Apr},
 note = {ループ文の並列実行では,イタレーション単位の並列実行が基本となっている.しかし,複雑なループ伝搬依存が存在するループ文では,イタレーション間の並列性を抽出することは困難である.また,計算機クラスタ環境では,タスク間通信オーバヘッドなどによりイタレーション単位の細粒度並列処理は適さない.本稿では,ループ文の並列実行方式である漸進処理を提案する.漸進処理では,同一配列データを操作する複数のループ文をパイプライン的に実行させる.ループ文はそれぞれ並列実行されるが,各ループ文内のイタレーションは逐次的に実行されるので,複雑なループ伝搬依存が存在しても適用可能である.また,イタレーションでなく,ループ文全体がタスク生成の単位となるので,タスク起動のオーバヘッドを削減でき,計算と通信のオーバラップにより通信オーバヘッドを減少させることができる.漸進処理を適用するためには,ループ文における配列データ要素の操作順序を解析する必要がある.我々はループ文での操作順序をアクセス・パターンとして定義し,漸進処理を効率的に行うためにアクセス・パターンの類似性を解析する漸進処理適用判定アルゴリズムを開発した.また,様々なループ文に対して漸進処理適用判定アルゴリズムを適用し,アルゴリズムの有効性についても調査した., Traditionally, in parallel execution of loops, iterations are executed in parallel. However, we can not extract parallelism among iterations for the loop which has complex loop-carried dependences. In addition, iteration-based parallel execution is not suitable to the computer cluster environment because of task granularity. In this paper, we propose the incremental processing for parallel execution of loops. In the incremental processing, plural loops which access same array data are executed in parallel with the pipeline method. We can apply incremental processing to loops with complex loop-carried dependences since incremental processing makes full use of parallelism among loops and iterations in loops are executed sequentially. Furthermore, loops are executed in parallel by means of overlap between computation and communication, which reduces communication overhead among tasks. For incremental processing, analysis of the access order on array elements in the loop is very important. We introduce the access pattern which defines the access order in loops, and develop the algorithm for analyzing the similarity of access patterns. We also examine the effectivity of our algorithm for parallel execution of loops with shared arrays.},
 pages = {847--859},
 title = {配列データを共有したループ文の並列実行のための漸進処理手法},
 volume = {42},
 year = {2001}
}