バルク回帰並列処理：依存のあるループの並列実行方式

• Item type: Trans(1)
• 公開日: 2001-11-15
• タイトル: バルク回帰並列処理：依存のあるループの並列実行方式
• タイトル / 言語: en
• タイトル: Bulk Recurrent Parallel Processing : A Method of Parallel Execution for Non - doall Loops
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: システムソフトウェア・コンパイラ
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 広島市立大学情報科学部
• 著者所属: 広島市立大学大学院情報科学研究科
• 著者所属: 広島市立大学情報科学部
• 著者所属(英): en
• 著者所属(英): Faculty of Information Sciences, Hiroshima City University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Hiroshima City University
• 著者所属(英): en
• 著者所属(英): Faculty of Information Sciences, Hiroshima City University
• 著者名: 川端, 英之; 谷口, 宏美; 津田, 孝夫
• 著者名(英): Hideyuki, Kawabata; Hiromi, Taniguchi; Takao, Tsuda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，ループ運搬依存を含むループの効率的な並列化手法を提案する．依存のあるループの並列化においては，ループ中で繰り返し実行される命令列（ループボディ）全体の計算処理をprefix計算における要素演算と見なしてアルゴリズム変換によって並列化する方法がある（回帰演算の並列化手法の適用）．回帰演算の並列化手法は，pipeline 法やdoacross 法の適用が困難なループに対しても有効であるなどの特徴を持つが，その単純な適用は総計算量の大幅な増加を引き起こし，プロセッサ数が少ない並列計算機では必ずしも高速化につながらない．これに対し，本論文で提案する手法は，依存のあるループへの回帰演算の並列化手法の適用において「ループ運搬依存の量」に着目したループ変換を導入する．これにより並列化にともなう計算量の増加を抑え，数台?数十台程度のプロセッサから成る並列計算環境において効率の良い並列実行を可能にする．疎結合計算機やSMP 計算機を用いた実測では，pipeline 法やdoacross 法が適用できないループに対してプロセッサ数に比例した高速化が可能であることが確かめられた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper,we propose an efficient method to parallelize non-doall loops.Parallelization techniques for linear recurrences are applicable for many non-doall loops which are not amenable to such methods as pipeline method and doacross method.However,naive application of parallelization for recurrences to non-doall loops can cause additional volumes of computation for parallel execution of the loops,so that speedup on computers with small number of processors is not necessarily guaranteed.In order to tackle this problem,we introduce a loop transformation technique into the parallelizing method for recurrences.The transformation is based on the idea of reducing “the amount of loop-carried dependence,”and suppresses the growth of the amount of computation.Experimental results show the method is efficient for loops which can not be parallelized by doacross method on both shared-memory SMP systems and distributed-machine environments.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11560614
• 書誌情報: 情報処理学会論文誌ハイパフォーマンスコンピューティングシステム（HPS）; 巻 42, 号 SIG12(HPS4), p. 111-123, 発行日 2001-11-15
• 出版者 / 言語: ja
• 出版者: 情報処理学会