日別アーカイブ: 2013年10月23日

OpenGL ES 2.0 で迷路シェーダー

昔 Direct3D 10 で作成した迷路シェーダーを Mobile GPU に移植してみました。
if 文の塊で非常に複雑な内容となっています。
そのため GPU によってはいくつか問題がありました。

迷路生成 (Nexus 10)
gpumaze 迷路生成

迷路探索 (Nexus 7)
gpudotmaze 迷路探索

このシェーダーでは各ピクセルが状態を持っており、自分の周囲のピクセルを
参照して次の状態を決定します。
例えば壁、床、成長点、移動判定中など、状態遷移の繰り返しで迷路の生成や
探索を行っています。
周囲のサンプリングは上下左右の 4点 + 自分自身を加えた 5回です。

プログラムでは毎フレーム迷路サイズの矩形を一回だけレンダリングしています。
例えば 512×512 なら、262144個のすべてのピクセルに対して上記の
サンプリングと遷移判定を行っていることになります。

そのため原理的にはテクスチャサイズ (迷路サイズ) だけで速度が決定し、
移動点や作業点が増えても (1つでも10万でも) 速度はほぼ変わらないことになります。
(2倍未満の若干の変化はあります。後述)

乱数は CPU で生成したものを毎フレーム GPU に渡しています。
バッファが小さいために固定パターンが目立ってしまうので、
これも GPU で生成できればもっと質の良い物が作れるかもしれません。

下記はさまざまな GPU で走らせた結果です。

              迷路生成 size                 迷路探索 size
              2048  1024   512   256   128  2048  1024   512   256   128
------------------------------------------------------------------------
1.Adreno 320  21.0  59.3  60.0  60.0  60.0  22.3  60.0  60.0  60.0  60.0
2.Mali-T604   11.1  41.3  60.0  60.0  60.0  19.0  58.5  60.0  60.0  60.0
3.Vivant GC4K  3.6  13.9  39.6  60.0  60.0   ---  13.4  41.3  60.0  60.0
4.Mali-400MP4  1.9   7.3  24.3  52.4  60.0   ---  13.8  38.1  60.0  60.0
5.Tegra 3      1.5   5.7  22.3  60.0  60.0   ---   6.0  20.3  43.8  60.0
6.PVR SGX540   0.5   5.2  21.0  60.0  60.0   ---   6.5  23.8  60.0  60.0
7.Adreno 220   ---   3.5  14.1  50.0  60.0   ---   ---  13.0  36.6  60.0※
8.Adreno 200   ---   ---   ---   ---  10.9   ---   ---   ---   ---   6.0※

・数値は FrameRate、値が大きい方が高速
・※ Adreno 220/200 は動作結果に問題あり

表示された fps 値を読み取っただけなので、あまり厳密な測定ではありません。
この中では Adreno 320 が圧倒的な速度となっています。

ほとんどの GPU では生成よりも探索の方が高速でした。
例外は Tegra3 で、探索の方が速度が落ちています。
Adreno 220/200 は一応速度を調べましたが正しく動いておりません。

● 条件分岐と条件付き代入

比較的すぐに動作する GPU と、対応のために修正が必要な GPU がありました。
一番問題だったのは Adreno 220 で、初期のコードではコンパイルが通るものの
Link Error が発生します。

// (A)
vec4 Head( vec4 color )
{
    if( isUp( color ) ){
       ~
       return  vec4( D_RESERVED, color.y, 0.0, 0.0 );
    }
    if( isDown( color ) ){
       ~
       return  vec4( D_RESERVED, color.y, 0.0, 0.0 );
    }
    if( isLeft( color ) ){
       ~
       return  vec4( D_RESERVED, color.y, 0.0, 0.0 );
    }
    if( isRight( color ) ){
       ~
       return  vec4( D_RESERVED, color.y, 0.0, 0.0 );
    }
    ~
    return  color;
}
// (B)
vec4 Head( vec4 color )
{
    if( isUp( color ) ){
       ~
       color= vec4( D_RESERVED, color.y, 0.0, 0.0 );
    }else if( isDown( color ) ){
       ~
       color= vec4( D_RESERVED, color.y, 0.0, 0.0 );
    }else if( isLeft( color ) ){
       ~
       color= vec4( D_RESERVED, color.y, 0.0, 0.0 );
    }else if( isRight( color ) ){
       ~
       color= vec4( D_RESERVED, color.y, 0.0, 0.0 );
    }else{
    	~
    }
    return  color;
}

いろいろ試した結果、(A) のように条件分岐していた命令を、
(B) のように条件代入に置き換えることでエラーを回避出来ました。
コンパイル自体は通っていたので、命令スロットやレジスタなど、何らかの
GPU リソースが Link 時にあふれていた可能性があります。

Adreno 220 でもシェーダーは動作するようになりましたが、
生成結果が意図したものになっておらずまだ問題があります。

             迷路生成                 迷路探索
------------------------------------------------------
Mali-400MP4  壁が切れることがある     正しく動作する
Adreno 220   成長が途中で止まる       ドットが動かない
Adreno 200   正しく動作するが重い     ドットが動かない

Mali-400MP4 は一見正常に見えるものの、壁が途切れている部分があります。
Adreno 200 は Adreno 220 よりまともですが処理能力が足りていません。

また (A) を (B) のように書き換えることで、
他の GPU でもパフォーマンスに影響が生じました。

(C)表              迷路生成
                   2048x2048    1024x1024    512x512   256x256
--------------------------------------------------------------
1.(A) Adreno 320   25.7~16.3   60.0~58.8   60.0         60.0 
1.(B) Adreno 320   18.6~17.7   60.0         60.0         60.0
2.(A) Mali-T604    11.9~10.3   42.8~39.9   60.0         60.0 
2.(B) Mali-T604    12.2~10.5   43.4~42.8   60.0         60.0
3.(A) Vivant GC4K   3.6~       13.9~8.8    46.8~32.5   60.0 
3.(B) Vivant GC4K   3.6~       14.6~9.3    47.6~31.2   60.0
4.(A) Mali-400MP4   1.9~        7.3~       24.6~24.0   52.4 
4.(B) Mali-400MP4   1.9~        7.4~7.3    23.8~23.5   54.0
5.(A) Tegra 3       1.5          5.7         22.3         60.0 
5.(B) Tegra 3       1.8          7.0         27.3         60.0     
6.(A) PVR SGX540    0.5          4.5~5.9    18.4~23.6   60.0
6.(B) PVR SGX540    0.5          4.5~6.0    17.8~23.8   60.0

・数値は FrameRate、値が大きい方が高速

特に Adreno 320 は、(B) に書き換えることで著しく速度が落ちました。
逆に Tegra 3 は (B) の方が高速になっています。
他の GPU でもここまで顕著ではありませんが影響が出ているようです。

予想よりも GLSL は、比較的書いたとおりにそのままコンパイルされて
いるのではないかと考えられます。
その様子は動的分岐の結果からもわかります。

●動的分岐

(C)表の fps 値で「25.7~16.3」と範囲が書かれているものがあります。
これは迷路生成初期が 25.7fps で、全部埋まる頃に 16.3fps まで
落ちていることを意味しています。

考えられる要因としてシェーダーの動的分岐があります。
迷路生成初期はほとんど全部床面の状態なので、レンダリング時は
同一ブロック(WARP)内のピクセルが同じ方向に分岐していると考えられます。
この場合他の分岐状態を実行する必要がありません。

終盤になって複雑になると、ブロック内の各ピクセルの状態がばらばらになるので
シェーダーは可能性のあるすべての分岐コードを実行していると考えられます。

Adreno 320 / Vivante / Mali-T604 などの OpenGL ES 3.0 世代の GPU は
fps 値が変化しているので、分岐の複雑さが速度に影響を与えていると考えられます。

特に Adreno 320 は変化が大きくなっています。
また (A) の分岐コードを (B) の条件代入に置き換えると、fps の変化が
大幅に少なくなることもわかります。
ここからも、記述通りに代入命令に置き換わっているのではないかと考えられます。

Adreno 320 の (B) のコードは最初は遅いものの、分岐判定のコストが
無いためか、複雑な終盤は落ち込みが少なく速度を維持しています。

Tegra 3 / Mali-400MP は速度が一定しておりほとんど変化がありませんでした。
おそらくすべての分岐を通過しているか、またはコンパイラが
分岐命令を置き換えているのではないかと思います。

Tegra 3 は (B) の方が速いので、命令置換ではなくそのまま分岐命令の分
コストが発生していると考えられます。

Adreno 220 はそもそも (B) でなければ動かないので変化が生じていません。
PowerVR SGX540 は理由はわかりませんが、条件が複雑になる終盤の方が
速度が上がっており特徴的な結果となっています。

●その他修正など

Tegra 3 は Fragment Shader で Uniform 配列に対する動的な index による
アクセスができません。
OpenGL ES 2.0 は Unified Shader が多いので忘れていましたが、
もともと Direct3D 9 ShaderModel 3.0 の仕様でも PixelShader では
index が使えませんでした。Tegra 3 の仕様で正解です。

PowerVR SGX540 では (B) の置き換えでシェーダーが動作しなくなる問題がありました。
lowp の誤差が原因で、PowerVR では mediump 以上を使用しています。

安定して動作したのは Adreno 320, Mali-T604, Vivante です。
いずれも OpenGL ES 3.0 対応 GPU です。

●アプリ

移植したシェーダーを Android の Live壁紙 にしてみました。

Google Play: GPU迷路 (作成のみ)
Google Play: GPUドット迷路 (作成+迷路探索)

上記の速度テストは、アプリのプレビュー(画面モード=ズーム)で測定しています。
GPU によっては負荷が高すぎるため 2048×2048 は除外しています。

●テスト機の詳細

   Device         OS   SoC                        GPU
-------------------------------------------------------------------
1. Nexus 7 2013   4.3  Snapdragon S4 Pro APQ8064  Adreno 320
2. Nexus 10       4.3  Exynos 5 Dual (5250)       Mali-T604
3. dtab 01        4.1  K3V2                       Immersion.16 (Vivante)
4. MOMO7 DE       4.1  RK3066                     Mali-400MP4
5. Nexus 7 2012   4.3  Tegra 3                    ULP GeForce(12)
6. Kindle Fire    4.2  OMAP4430                   PowerVR SGX540
7. EVO 3D ISW12HT 4.0  Snapdragon S3 MSM8660      Adreno 220
8. Desire X06HT   4.1  Snapdragon S1 QSD8250      Adreno 220

関連エントリ
GLSL について、互換性や問題点など
2007/09/19 Direct3D 10 ShaderModel4.0 迷路の自動探索Shader
2007/09/18 Direct3D ShaderModel4.0 Shaderで迷路作成