参照の空間局所性を最大化する ボリューム・レンダリング・ アルゴリズム

Presentation on theme: "参照の空間局所性を最大化する ボリューム・レンダリング・ アルゴリズム"— Presentation transcript:

1 参照の空間局所性を最大化する ボリューム・レンダリング・ アルゴリズム
額田 匡則 小西 将人 五島 正裕 中島 康彦 富田 真治 京都大学　

2 ボリューム・レンダリング 半透明な3次元のオブジェクトを ポリゴンに変換したりしないで 直接2次元画像に変換する方法の総称 応用分野：
科学技術計算の結果 CT，MRI などの医用画像 エンターテインメント

3 ボリューム (正方格子，離散モデル) : Voxel N = 128 ～ 4K

4 ボリューム・レンダリング 記憶量，計算量：O(N3) 主記憶容量，計算速度：最近，満たされつつある． データの供給能力： 依然，不足．
データの供給能力： 依然，不足． 従来手法には，参照の局所性がほとんどない！ 参照の空間局所性を最大化するアルゴリズム キューボイド順 レイ・キャスティング法 を提案

5 発表内容 従来手法： ピクセル順 レイ・キャスティング法 提案手法： キューボイド順 レイ・キャスティング法 性能評価

6 レイ・キャスティング (RC) 法 ボリューム・レンダリングの一般的な方法 視点からピクセルに 視線 (Ray)を 飛ばす (Cast)
視線上に等間隔に サンプリング点 (SP) をとる 視線上の SP を，画面奥から順に処理． SP のボクセルの値をサンプリングし， ピクセル値を更新する．

7 ピクセル値の計算 ―― α-Blending
n-th Sampling Point Viewpoint Ray Pixel Voxel in : Intensity (RGB) (in , tn) tn : Transparency tn × In In-1 In = tn×In-1 + in in 視線上の SP を，画面奥から順に 処理．

8 RC 法のコード (1/2) struct Pixel { float r, g, b; }; // ピクセル値
struct Voxel { float r, g, b, t; }; // ボクセル値 unsigned char vlm[N][N][N]; // ボリューム Voxel map[UCHAR_MAX+1]; // カラーマップ Pixel pxl[N][N]; // スクリーン

9 RC 法のコード (2/2) for (int v = 0; v < N; ++v)
for (int u = 0; u < N; ++u) while (IS_IN_VOLUME(x, y, z)) { // サンプリング (3FLOP) unsigned char ind = vlm[(int)x][(int)y][(int)z]; Voxel vxl = map[ind]; // ピクセル値の更新 (6FLOP) pxl[u][v].r = vxl.t * pxl[u][v].r + vxl.r; pxl[u][v].g = vxl.t * pxl[u][v].g + vxl.g; pxl[u][v].b = vxl.t * pxl[u][v].b + vxl.b; // SP の更新 (3FLOP) x += dx; y += dy; z += dz; }

10 RC 法の要求バンド幅 要求バンド幅：1FLOPあたりのデータ転送量 RC 法 1B ÷ 12FLOP = 1/12 B/FLOP
参考：Itanium 2 6.4GB/s ÷ 4GFLOPS = 1.6 B/FLOP RC 法は，計算バウンド ？

11 SP の処理順序 ―― ピクセル順 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Screen

12 SP の処理順序と キャッシュ ベスト・ケース
Cache 13 9 5 1 10 14 6 2 11 15 3 7 12 16 4 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Screen

13 SP の処理順序と キャッシュ ワースト・ケース
Cache 3 1 2 4 1 2 3 4 Screen

14 SP の処理順序と キャッシュ ワースト・ケース
Cache 3 5 7 4 8 6 1 5 2 6 3 7 4 8 Screen

15 ピクセル順 RC 法の問題点 ワースト・ケースでは， フェッチしたラインの1Bしか使えない！ フェッチするラインの数は，
ライン・サイズ倍 ―― ex. 64～128倍に！

16 RC 法の要求バンド幅 (ベスト・ケース) 要求バンド幅：1FLOPあたりのデータ転送量 RC 法
1B ÷ 12FLOP = 1/12 (B/FLOP) 参考： Itanium 2 6.4GB/s ÷ 4GFLOPS = 1.6 B/FLOP RC 法は，計算バウンド

17 RC 法の要求バンド幅(ワースト・ケース)
要求バンド幅：1FLOPあたりのデータ転送量 RC 法 128B ÷ 12FLOP = 10 B/FLOP 参考： Itanium 2 6.4GB/s ÷ 4GFLOPS = 1.6 B/FLOP RC 法は，メモリ・バウンド！

18 SP の処理順序と キャッシュ 提案手法 Cache 1 3 2 4 1 3 2 4 Screen

19 基本的なアイディア 要は，タイリングすればよい． 『ライン内のすべての SP を一気に処理』 フェッチするライン数： 最小
フェッチするライン数： 最小 参照の空間局所性： 最大 ただし ，メモリ・アクセス・パタンが： 通常の数値処理： 静的，固定 RC法： 動的，変化 視点，スクリーンの位置に依存

20 キューボイド (Cuboid) キャッシュ・ラインは小さい オーバヘッド大 いくつかのラインをまとめた3次元のブロック：
サイズ：１次キャッシュの1/2 ～ 1/４ 『キューボイド内のすべての SP を一気に処理』

21 キャッシュ・ラインと キューボイド Cache Line 8 128 Cuboid 8 x 8 x 128 = 8K

22 SP の処理順序と キャッシュ キューボイド順
Cache 1 5 7 3 6 2 4 8 1 3 2 4 Cuboid 5 7 6 8 Screen

23 キューボイド順処理の2条件 この例なら簡単だけど，いつでもできるの？ キューボイド順処理の2条件 1つのキューボイド内の SP は一気に．
キューボイド間の処理順序は，必ず存在するか？ キューボイド内の全 SP を効率よく探せるか？

24 キューボイド間の処理順序 キューボイド順処理の2条件 (再び) 1つのキューボイド内の SP は一気に．
この2条件を満たす処理順序は，必ず ―― 視点，スクリーンの位置に依らず ―― 存在するか？ 結論：存在する． x，y，z，各軸ごとに， 視点から遠いキューボイドから処理すればよい．

25 キューボイド間の処理順序 1 5 13 9 2 6 14 10 3 7 15 11 Cuboid 4 8 16 12 y x O

26 キューボイド間の処理順序 1 2 4 3 5 6 8 7 9 10 12 11 Cuboid 13 14 16 15 y x O

27 キューボイド順処理の条件 (再び) この例なら簡単だけど，いつでもできるの？ キューボイド順処理の条件
1つのキューボイド内の SP は一気に． 1本の視線上の SP は 画面奥から順 に． キューボイド間の処理順序は，必ず存在するか？ キューボイド内の全 SP を効率よく探せるか？

28 キューボイド内の全 SP の探索 キューボイド内の全 SP を探す． 1本の視線上では画面奥から順に． 手順：
キューボイドを通過するすべての視線を求め， 各視線上， 最奥の SP から順に，最手前の SP まで処理．

29 キューボイド内の 全 SP の探索 y 各ピクセルごとに， 最近処理した SP の座標 視線ベクトル x を格納． O
Cuboid 各ピクセルごとに， 最近処理した SP の座標 視線ベクトル を格納． O(N2) で，問題にならない． Screen x O Viewpoint Screen

30 キューボイド順 RC 法のまとめ キューボイド内の全ての SP を一気に処理 参照の空間局所性，キャッシュ・ヒット率は最大
いつでも，ピクセル順のベスト・ケースと同じ オーバヘッド キューボイドの面のレンダリング O(N2) ではある ベクトル長の短縮 ピクセル順： N (128 ~ 4K) キューボイド順 ベスト： 128 キューボイド順 ワースト： 8 (！)

31 性能評価 評価項目： キャッシュ・ヒット率 提案手法のオーバヘッド キューボイドの面のレンダリング ベクトル長の短縮 評価環境
Itanium 2 サーバ gcc –O4

32 評価環境 Itanium 2 サーバの諸元 動作周波数 1GHz 浮動小数点命令発行数 2命令/cycle ピーク演算性能
2GMACS, 4GFLOPS システム・バス・バンド幅 6.4GB/s キャッシュ L1D L2 L3 サイズ 16KB 256KB 3MB ライン・サイズ 64B 128B ウェイ数 4 8 12 レイテンシ load to use (cycles) INT 1 5 FP NA 6

33 実効FLOPS値：16N 3FLOP ÷ 描画時間

34 ピクセル順 (PO) と キューボイド順(CO)
PO Best : PO Worst キャッシュ・ヒット率悪化による性能低下 PO Best : CO Best 主に，スキャン変換のオーバヘッド CO Best : CO Worst 主に，ベクトル長短縮によるオーバヘッド PO Worst : CO Worst 提案手法による性能向上

35 まとめ キューボイド順レイ・キャスティング法を提案 視点，スクリーンの位置に依らず， ボリューム参照の空間局所性を最大化．
Itanium ２ サーバを用いた評価 ワースト・ケースでも，ベスト・ケースの 5/6 ピクセル順に対し，実質 5倍の速度向上 ボリューム・レンダリングにおけるメモリの問題は解決！

36 今後の課題 プログラムのチューニング 評価結果は gcc まかせ 理論最大性能の1割未満 (300M/4GFLOPS)
ハンドチューニングにより： 2.4GFLOPS． 2563 で，10 frames/sec． 並列化 応用 連続モデル 非構造格子