データ並列化の用語のようですがブロック分割とサイクリック分割の違いを教えてください
-
ひとまず「ブロック分割 サイクリック分割」で検索すると、このスタックオーバーフロー記事が最初に Hit しましたが、それぞれの用語が利用されている他ページのソースはありますか?– Yuki InoueCommented 2016年4月24日 9:34
-
確かにGoogleでこのページがトップになりますが,それ以降のページはだいたい並列計算の文脈で同じような説明がされています– takoikaCommented 2016年4月24日 13:12
-
@YukiInoue 専門家じゃないのでわからないですが、公共出版物が表記を間違えることは数少ないです。普通に英語にして調べてみるのはどうですか?"Cyclic division"とか"Block segmentation"という訳になりました。– todoCommented 2016年4月24日 15:57
-
@YukiInoue 原文ありましたよ。books.google.co.jp/…– todoCommented 2016年4月24日 16:05
-
distribution reduction partition Mappingでもいいんですかね?netlib.org/scalapack/slug/node75.html– todoCommented 2016年4月24日 16:16
3 件の回答
1次元のデータの分割方法です. 1次元配列を分割する例で示します. 長さN
の配列a
をM
ブロックに分割するとき
m
番目のブロックの要素が, a[i+N/M*m]
で指定されるのがブロック分割,
a[N/M*i+m]
なのがサイクリック分割です.
ここでi
はどちらも0~N/M-1
をとります.また簡単のためにN
はM
でわりきれると仮定しています. 図がわかりやすいのでのせます
[0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4] //ブロック
[0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4] //サイクリック
N=30
,M=6
の場合をのせました. 上がブロック分割,下がサイクリック分割です.ここで各色はブロックに対応しています.
画像処理やcudaでスレッドに分割する場合は2または3次元のデータを考える場合が多いですが,その場合には各次元それぞれブロックまたはサイクリックで分割します.
下記のようなイメージではないでしょうか?
- サイクリック分割
データを1行(または1列)ごとに分割する方式
1 → あいうえお
2 → かきくけこ
3 → さしすせそ
- ブロック分割
データを決められたブロックサイズ毎に分割する方式
例:(1ブロック = 8Byte)
1 → あいうえ
2 → おかきく
3 → けこさし
4 → すせそ
- ブロックサイクリック分割
ブロック分割とサイクリック分割の中間の分割方式
データを決められた行数(複数行)ごとに分割する方式
1 → あいうえお
かきくけこ
2 → さしすせそ
たちつてと
データ(通常、2次元以上の配列)を複数の計算機(複数のプロセス、複数のスレッド等の場合もある)で処理する際、データをいくつかの塊に分けて、個々の計算機がそれらを並列に処理していくのがデータ並列処理です。
ブロック分割とサイクリック分割は、塊に分ける方法の種類です。
ブロック分割は、一定の大きさの領域(ブロック)に分けていく方法です。
サイクリック分割は、1行(もしくは1列)の領域に分けていく方法です。
例として、1024x1024画素の画像を処理する場合を考えましょう。
[ブロック分割]
32x32画素をブロックとすると、元の画像は32x32個(1024個)のブロックに分けられます。
この1024個のデータブロックを個々の計算機に割り当てて並列に処理をしてゆきます。
[サイクリック分割]
元の画像は、1024個の行データに分けられます。
この1024個の行データを個々の計算機に割り当てて並列に処理をしてゆきます。
処理するデータが順次到達するような場合(例:カメラのCCDから取り出される画像データ)、「1行のデータが揃ったら、それを計算機に割り当てて処理を始める」という処理が繰り返されるので、サイクリック(cyclic)と呼ばれると聞いたことがあります。