24253


データ並列化の用語のようですがブロック分割とサイクリック分割の違いを教えてください


CC BY-SA 3.0
2016-04-22T01:35:24.473
24236
2016-04-22T08:37:03.837
2016-04-22T02:54:45.453
10455
10455
question
cuda メモリ管理
ブロック分割とサイクリック分割の違いを教えてください


下記のようなイメージではないでしょうか？

* * *

  * サイクリック分割  
データを1行(または1列)ごとに分割する方式

１ → あいうえお  
２ → かきくけこ  
３ → さしすせそ

* * *

  * ブロック分割  
データを決められたブロックサイズ毎に分割する方式

例：（1ブロック = 8Byte）  
１ → あいうえ  
２ → おかきく  
３ → けこさし  
４ → すせそ

* * *

  * ブロックサイクリック分割  
ブロック分割とサイクリック分割の中間の分割方式  
データを決められた行数(複数行)ごとに分割する方式

１ → あいうえお  
かきくけこ

２ → さしすせそ  
たちつてと


CC BY-SA 3.0
2016-04-22T05:31:12.120
24240
2016-04-22T05:31:12.120
24236
answer


データ（通常、２次元以上の配列）を複数の計算機（複数のプロセス、複数のスレッド等の場合もある）で処理する際、データをいくつかの塊に分けて、個々の計算機がそれらを並列に処理していくのがデータ並列処理です。

ブロック分割とサイクリック分割は、塊に分ける方法の種類です。

ブロック分割は、一定の大きさの領域(ブロック)に分けていく方法です。  
サイクリック分割は、１行（もしくは１列）の領域に分けていく方法です。

例として、1024x1024画素の画像を処理する場合を考えましょう。

[ブロック分割]  
32x32画素をブロックとすると、元の画像は32x32個(1024個）のブロックに分けられます。  
この1024個のデータブロックを個々の計算機に割り当てて並列に処理をしてゆきます。

[サイクリック分割]  
元の画像は、1024個の行データに分けられます。  
この1024個の行データを個々の計算機に割り当てて並列に処理をしてゆきます。  
処理するデータが順次到達するような場合（例：カメラのCCDから取り出される画像データ）、「１行のデータが揃ったら、それを計算機に割り当てて処理を始める」という処理が繰り返されるので、サイクリック(cyclic)と呼ばれると聞いたことがあります。


CC BY-SA 3.0
2016-04-22T05:45:58.553
24241
2016-04-22T05:45:58.553
217
24236
answer


1次元のデータの分割方法です． 1次元配列を分割する例で示します． 長さ`N`の配列`a`を`M`ブロックに分割するとき  
`m`番目のブロックの要素が， `a[i+N/M*m]`で指定されるのがブロック分割，  
`a[N/M*i+m]`なのがサイクリック分割です．  
ここで`i`はどちらも`0~N/M-1`をとります．また簡単のために`N`は`M`でわりきれると仮定しています． 図がわかりやすいのでのせます  
[![画像の説明をここに入力](https://i.stack.imgur.com/THJ9k.png)](https://i.stack.imgur.com/THJ9k.png)

[code]

    [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] //サイクリック
    
[/code]

`N=30`,`M=6`の場合をのせました． 上がブロック分割，下がサイクリック分割です．ここで各色はブロックに対応しています．  
画像処理やcudaでスレッドに分割する場合は2または3次元のデータを考える場合が多いですが，その場合には各次元それぞれブロックまたはサイクリックで分割します．


CC BY-SA 3.0
2016-04-22T08:22:33.797
24253
2016-04-22T08:37:03.837
2016-04-22T08:37:03.837
14418
14418
24236
answer