group shared memoryを使う

今回は256要素の配列の総和を求める計算をする。リダクション(Reduction)ともいう。
こちらがその簡素なコード
C#(Host.cs)
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Host : MonoBehaviour
{
    public ComputeShader shader;
    void Start()
    {
        float[] host_A = new float[256];
        for(int i = 0; i < 256; i++)
        {
            host_A[i] = 1f * i;
        }
        float[] host_B = { 0f };//この数字はなんでもいい。Bは結果がはいる側

        ComputeBuffer A = new ComputeBuffer(host_A.Length, sizeof(float));
        ComputeBuffer B = new ComputeBuffer(host_B.Length, sizeof(float));

        int k = shader.FindKernel("sharedmem_samp0");

        // host to device
        A.SetData(host_A);

        //引数をセット
        shader.SetBuffer(k, "A", A);
        shader.SetBuffer(k, "B", B);

        // GPUで計算
        shader.Dispatch(k, 1, 1, 1);//ここでは1*1*1並列を指定。ComputeShader側で256並列を指定している

        // device to host
        B.GetData(host_B);
        Debug.Log(host_B[0]);

        //解放
        A.Release();
        B.Release();
    }

    // Update is called once per frame
    void Update()
    {
    }
}

ComputeShader

#pragma kernel sharedmem_samp0
RWStructuredBuffer<float> A;//256要素
RWStructuredBuffer<float> B;//1要素

groupshared float block[256];
[numthreads(256, 1, 1)]
void sharedmem_samp0(int id : SV_DispatchThreadID, int grid : SV_GroupID, int gi : SV_GroupIndex) {
	float a = A[id];
	block[gi] = a;
	//共有メモリに書き込まれた
	GroupMemoryBarrierWithGroupSync();
	for (int i = 128; i > 0; i /= 2) {
		if (gi < i) {//128,64,32,16,8,4,2,1
			block[gi] += block[gi + i];
		}
		GroupMemoryBarrierWithGroupSync();//ここは256スレッドすべてで実行
	}

	//あとは0番目のデータを抽出するだけ
	if (gi==0)
		B[0] = block[0];
} 
https://github.com/toropippi/Uinty_GPGPU_SharedMem_AtomicAdd/tree/master/gpgpu_sample3

前の記事のように
Assetsフォルダ内にScriptsフォルダを作成して以下の2つを作成
・右クリック→Create→C# script→「Host」
・右クリック→Create→Shader→Compute Shader→「ComputeShader」
空のobjectにC#をアタッチし、そのオブジェクトの「shader」に「ComputeShader」をアタッチ
そして実行

結果

samp3結果0

解説するとまずC#側でhost_Aという配列変数に0,1,2,3,4・・・255の数値を格納しGPUに転送。GPU側で全要素を並列に足し算しC#側に結果を戻し表示している、という感じ。
検算してみると
0,1,2,3・・・なのでN*(N-1)/2なので256*255/2=32640。
あってる。

解説

今回初見の命令は全部ComputeShader側コードで
・groupshared float block[256];
・int grid : SV_GroupID, int gi : SV_GroupIndex
・GroupMemoryBarrierWithGroupSync();

の3つ。

groupshared float block[256];

これはカーネルで共有メモリを使いたいときに宣言する。float型×256要素を確保している。共有メモリとはうまく使うことでいろいろ高速化できる優れもの。で以下の特徴がある
・グループ内(この場合256スレッド)でしか内容が共有されない
・他グループからはアクセス不能
・そのカーネル実行中にのみアクセスできる
・カーネル終了後はアクセスできない
・カーネル終了後は自動で消えるので解放処理はいらない
・実体はL1キャッシュに存在する
・1グループで使える最大サイズは32KB(DirectX 11の場合)
・L1なのでグローバルメモリよりはるか高速に(10倍-100倍)アクセスできる

int grid : SV_GroupID, int gi : SV_GroupIndex

次にこれ。
void sharedmem_samp0(int id : SV_DispatchThreadID, int grid : SV_GroupID, int gi : SV_GroupIndex) {
この行の後ろ2つのやつだ。
SV_DispatchThreadIDは前もでてきたようにスレッドidであり、上のコードにならってみるとカーネルが256並列なので0~255の値が各スレッドで割り当てられている

SV_GroupIDはグループidで、カーネル256並列を1グループ*256スレッドという形で実行しているのでグループは一つしかないため、このグループidには0が割り当てられることになる。
この場合の1と256は
C#の
shader.Dispatch(k, 1, 1, 1)
とComputeShaderの
[numthreads(256, 1, 1)]
に対応している。
C#ではグループ数の指定、ComputeShaderカーネルでは1グループあたりのスレッド数の指定をしていたというわけだ。
SV_GroupIndexはグループ内のスレッドindexで0~255の値が割り当てられることになる。

GroupMemoryBarrierWithGroupSync();

最後にこれ。
これはグループ内で全スレッドの同期をとる命令。GPUはいくら並列演算器とはいえ、全部のコアが全く同じプログラムの行を実行しているわけではない。256並列なら0番目スレッドと255番目のスレッドではタイミングがズレているかもしれない。メモリにアクセスする際に順番がバラバラだと困ったことになるので、足並みをそろえてほしいときに使う。
注意としては1グループ=256スレッドの場合、256すべてのスレッドでGroupMemoryBarrierWithGroupSync();が実行されないと次の行に進まないということ。これは多分OpenCLやCUDAでも同じ考えだろう。

総和アルゴリズムについて

今回のやつを一応図解しておく。わかりやすくするために0~7の総和で考える。
reduction


最終的に共有メモリの0番目の要素に結果が集まる形である。

とりあえずnumthreadsには64の倍数を指定しておくとなぜ良いのか

前回の記事で
・numthreadsには1~1024までの数字しか指定できない
・とりあえずnumthreadsには64の倍数を指定しておくと良い
と書いているが、特に2番目、なぜそうしたほうが良いのかという理由はまだ説明できていない。その理解のためにはグループ、スレッドの抽象概念の理解とハードウェアのほうの理解両方が必要であり、いよいよ避けて通れなくなってきた。

これを理解するために早速あるプログラムの実験をしてみよう
C#(Host.cs)
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;

public class Host : MonoBehaviour
{
    public ComputeShader shader;
    ComputeBuffer A;
    int cnt;
    int time0;
    int time1;
    uint[] host_A;
    int[] k;
    int N;
    int[] timelist;
    int knum;
    int THREADNUM;
    void Start()
    {
        N = 11;
        THREADNUM = 256 * 1024;
        timelist = new int[N];
        host_A = new uint[THREADNUM];
        A = new ComputeBuffer(host_A.Length, sizeof(uint));
        k = new int[9];
        k[0] = shader.FindKernel("sharedmem_samp1");
        k[1] = shader.FindKernel("sharedmem_samp2");
        k[2] = shader.FindKernel("sharedmem_samp4");
        k[3] = shader.FindKernel("sharedmem_samp8");
        k[4] = shader.FindKernel("sharedmem_samp16");
        k[5] = shader.FindKernel("sharedmem_samp32");
        k[6] = shader.FindKernel("sharedmem_samp64");
        k[7] = shader.FindKernel("sharedmem_samp128");
        k[8] = shader.FindKernel("sharedmem_samp256");
        //引数をセット
        for (int i = 0; i < 9; i++)
        {
            shader.SetBuffer(k[i], "A", A);
        }
        cnt = 0;
        knum = 0;
    }
    

    void Update()
    {
        if (cnt < N) {
            gpuvoid();
        }
        
        if (cnt == N) {
            Array.Sort(timelist);//中央値を選択したい
            Debug.Log("グループスレッド数="+(1<<knum)+"\n計算時間        "+timelist[N/2]+"ms");
            
            knum++;
            if (knum == 9)
            {
                A.Release();
            }
            else
            {
                cnt = -1;
            }
        }

        cnt++;

    }

    void gpuvoid()
    {
        time0 = Gettime();
        // GPUで計算
        shader.Dispatch(k[knum], THREADNUM >> knum, 1, 1);
        // device to host
        A.GetData(host_A);
        time1 = Gettime() - time0;
        timelist[cnt] = time1;
    }

    //現在の時刻をms単位で取得
    int Gettime()
    {
        return DateTime.Now.Millisecond + DateTime.Now.Second * 1000
         + DateTime.Now.Minute * 60 * 1000 + DateTime.Now.Hour * 60 * 60 * 1000;
    }
}



ComputeShader
#pragma kernel sharedmem_samp1
#pragma kernel sharedmem_samp2
#pragma kernel sharedmem_samp4
#pragma kernel sharedmem_samp8
#pragma kernel sharedmem_samp16
#pragma kernel sharedmem_samp32
#pragma kernel sharedmem_samp64
#pragma kernel sharedmem_samp128
#pragma kernel sharedmem_samp256
RWStructuredBuffer<uint> A;
#define LPNM 2048


uint SinRandom(uint id) {
	uint x = id;
	float y;

	for (int i = 0; i < LPNM; i++) {
		y = sin(1.234f*(float)(x % 12345));
		y = 2.3456f / (y+1.0001f);
		x = (uint)(100000000.0f*y) + id;
	}
	return x;
}


[numthreads(256, 1, 1)]
void sharedmem_samp256(uint id : SV_DispatchThreadID) {
	A[id] = SinRandom(id);
}

[numthreads(128, 1, 1)]
void sharedmem_samp128(uint id : SV_DispatchThreadID) {
	A[id] = SinRandom(id);
}

[numthreads(64, 1, 1)]
void sharedmem_samp64(uint id : SV_DispatchThreadID) {
	A[id] = SinRandom(id);
}

[numthreads(32, 1, 1)]
void sharedmem_samp32(uint id : SV_DispatchThreadID) {
	A[id] = SinRandom(id);
}

[numthreads(16, 1, 1)]
void sharedmem_samp16(uint id : SV_DispatchThreadID) {
	A[id] = SinRandom(id);
}

[numthreads(8, 1, 1)]
void sharedmem_samp8(uint id : SV_DispatchThreadID) {
	A[id] = SinRandom(id);
}

[numthreads(4, 1, 1)]
void sharedmem_samp4(uint id : SV_DispatchThreadID) {
	A[id] = SinRandom(id);
}

[numthreads(2, 1, 1)]
void sharedmem_samp2(uint id : SV_DispatchThreadID) {
	A[id] = SinRandom(id);
}

[numthreads(1, 1, 1)]
void sharedmem_samp1(uint id : SV_DispatchThreadID) {
	A[id] = SinRandom(id);
}


https://github.com/toropippi/UintyGPGPU/tree/master/gpgpu_sample3a

これはGPU上で適当なランダムな値を生成してグローバルメモリに書き込むというサンプルだが、注目するべきはループの回数。2048ループと非常に多く、かつループ内には除算も入っており、これは完全に演算律速となる問題だ。これを256*1024並列でGPU上で実行する。その際全体の並列数は変えずに、グループスレッド数だけを変えて実行してみる。

AMD(RX 480)のグラボのとき
amdjikan


NVIDIA(MX150(Pascal))のグラボのとき
nvidia


見やすくグラフにしてみる
amd

nv


見やすくするために実行時間の逆数を棒グラフにしている。フレームレートを見ていると考えれば良い。横軸はグループスレッド数だ。

グループスレッド数を1→2→4と倍々に増やしていくと、それに応じて速度が倍々に増えているのがわかる。そしてAMDでは64、NVIDIAでは32で頭打ちになる。
これらの結果からAMDのグラボではグループスレッド数を64、128、256にしたとき最大パフォーマンスが、NVIDIA(Pascal)のグラボではグループスレッド数を32、64、128、256にしたとき最大パフォーマンスが得られると経験的にわかった。
ComputeShaderは一応両方のベンダーのグラボで実行できるわけだから、多くの状況を想定するならグループスレッド数を最低でも64にしておくほうが安全ということになる。


ではなぜNVIDIAで32、AMDで64が頭打ちになるかというと、NVIDIAでいうところの「Warp」、AMDでいうところの「Wavefront」が関係している。あまり詳しいわけではないがざっくりいうとこんな感じ

Warp
NVIDIAのGPUでは32スレッド分を1まとまりの単位として実行する。その単位がWarp
・Maxwell,Pascalアーキテクチャでは32スレッドを32CUDA Coreが1cycleで実行する
・Fermi,Kepler,Volta,Turingアーキテクチャでは32スレッドを16CUDA Coreが2cycleで実行する
・16 or 32のスレッドが同じタイミングで同じ行のプログラムを実行する

Wavefront
AMDのGPUでは64スレッド分を1まとまりの単位として実行する。その単位がWavefront
・64スレッドを16PEが4cycleで実行する(PE=CUDA coreみたいなもん)
・16スレッドが同じタイミングで同じ行のプログラムを実行する


だからグループスレッドに1を指定してしまうと、AMDのGPUなら1cycle目で16PEのうち15PEが空回りし2~4cycle目で16PE全部が空回りする。そしてNVIDIAのPascalだと32CUDA Core中31CUDA Coreが何もしないで空回りすることになってしまう。
こんな感じにとんでもない無駄を生む可能性があるため、この概念を少しでも理解し、グループスレッド数を指定できるようになりたい。
ここまでわかればとても奇数や素数を指定する気にはならないだろう。2のべき乗でと考えると選択肢は64,128,256,512,1024に限られる。512,1024までいくと古いグラボやShaderModelによって実行できない場合があるので64,128,256の3つが現実的になるのかなと思う。
なお192とかは確かに64の倍数だけどなんか気持ち悪い・・・

補足

WindowsだとGPUのタスクが重すぎて2秒とか反応しないとOSが検知してドライバー強制終了させるのがデフォルトのようだ。
そんなことをされたらデバッグが捗らないのでここを参照してレジストリをいじっておく
https://support.borndigital.co.jp/hc/ja/articles/360000574634


※本ブログで紹介しているソースコードはすべてCC0 パブリックドメインです。
ご自由にお使いください



UnityでGPGPUその2 並列計算と時間測定、コアレスアクセスなど


UnityでGPGPUその4 ComputeShaderでAtomic演算