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

URI http://harp.lib.hiroshima-u.ac.jp/hiroshima-cu/metadata/5700
File
Title
バルク回帰並列処理 : 依存のあるループの並列実行方式
Title Alternative
Bulk Recurrent Parallel Processing : A Method of Parallel Execution for Non-doall Loops
Author
氏名 川端 英之
ヨミ カワバタ ヒデユキ
別名 KAWABATA Hideyuki
氏名 谷口 宏美
ヨミ タニグチ ヒロミ
別名 TANIGUCHI Hiromi
氏名 津田 孝夫
ヨミ ツダ タカオ
別名 TSUDA Takao
Abstract

本論文では, ループ運搬依存を含むループの効率的な並列化手法を提案する.依存のあるループの並列化においては, ループ中で繰り返し実行される命令列(ループボディ)全体の計算処理をprefix計算における要素演算と見なしてアルゴリズム変換によって並列化する方法がある(回帰演算の並列化手法の適用).回帰演算の並列化手法は, pipeline法やdoacross法の適用が困難なループに対しても有効であるなどの特徴を持つが, その単純な適用は総計算量の大幅な増加を引き起こし, プロセッサ数が少ない並列計算機では必ずしも高速化につながらない.これに対し, 本論文で提案する手法は, 依存のあるループへの回帰演算の並列化手法の適用において「ループ運搬依存の量」に着目したループ変換を導入する.これにより並列化にともなう計算量の増加を抑え, 数台〜数十台程度のプロセッサから成る並列計算環境において効率の良い並列実行を可能にする.疎結合計算機やSMP計算機を用いた実測では, pipeline法やdoacross法が適用できないループに対してプロセッサ数に比例した高速化が可能であることが確かめられた. / 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.

Description Peer Reviewed
Journal Title
情報処理学会論文誌. ハイパフォーマンスコンピューティングシステム
Volume
42
Issue
SIG_12(HPS_4)
Spage
111
Epage
123
Published Date
2001-11-15
Publisher
社団法人情報処理学会
ISSN
0387-5806
NCID
AA11560614
NAID
110002726167
Language
jpn
NIIType
Journal Article
Text Version
出版社版
Rights
ここに掲載した著作物の利用に関する注意:本著作物の著作権は(社)情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。 The copyright of this material is retained by the Information Processing Society of Japan (IPSJ). This material is published on this web site with the agreement of the author (s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof. All Rights Reserved, Copyright (C) Information Processing Society of Japan.
Relation URL
Old URI
Set
hiroshima-cu