参照の空間局所性を最大化する
ボリューム・レンダリング・
アルゴリズム
額田 匡則 小西 将人 五島 正裕
中島 康彦 富田 真治
京都大学
ボリューム・レンダリング
► 半透明な3次元のオブジェクトを
ポリゴンに変換したりしないで
直接2次元画像に変換する方法の総称
► 応用分野:
 科学技術計算の結果
 CT,MRI などの医用画像
 エンターテインメント
ボリューム (正方格子,離散モデル)
: Voxel
N = 128 ~ 4K
ボリューム・レンダリング
►記憶量,計算量:O(N3)
 主記憶容量,計算速度:最近,満たされつつある.
 データの供給能力:
依然,不足.
►従来手法には,参照の局所性がほとんどない!
►参照の空間局所性を最大化するアルゴリズム
 キューボイド順 レイ・キャスティング法
を提案
発表内容
1. 従来手法:
ピクセル順 レイ・キャスティング法
2. 提案手法:
キューボイド順 レイ・キャスティング法
3. 性能評価
レイ・キャスティング (RC) 法

ボリューム・レンダリングの一般的な方法
1. 視点からピクセルに 視線 (Ray)を 飛ばす (Cast)
2. 視線上に等間隔に サンプリング点 (SP) をとる
3. 視線上の SP を,画面奥から順に処理.
SP のボクセルの値をサンプリングし,
ピクセル値を更新する.
ピクセル値の計算 ―― α-Blending
n-th Sampling Point
Viewpoint
Ray
Voxel
(in , tn)
Pixel
in : Intensity (RGB)
tn : Transparency
tn × I n
In-1
In = tn×In-1 + in
in
視線上の SP を,画面奥から順に 処理.
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];
// ボリューム
// カラーマップ
// スクリーン
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;
}
RC 法の要求バンド幅
►要求バンド幅:1FLOPあたりのデータ転送量
►RC 法
 1B ÷ 12FLOP = 1/12 B/FLOP
►参考:Itanium 2
 6.4GB/s ÷ 4GFLOPS = 1.6 B/FLOP
►RC 法は,計算バウンド ?
SP の処理順序 ―― ピクセル順
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Screen
SP の処理順序と
キャッシュ
ベスト・ケース
13
951
10
14
62
15
11
37
12
16
48
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Cache
Screen
SP の処理順序と
キャッシュ
ワースト・ケース
31
42
Cache
1
2
3
4
Screen
SP の処理順序と
キャッシュ
ワースト・ケース
3
75
1
5
2
6
3
7
4
8
4
86
Cache
Screen
ピクセル順 RC 法の問題点
►ワースト・ケースでは,
フェッチしたラインの1Bしか使えない!
►フェッチするラインの数は,
ライン・サイズ倍 ―― ex. 64~128倍に!
RC 法の要求バンド幅 (ベスト・ケース)
►要求バンド幅:1FLOPあたりのデータ転送量
►RC 法
 1B ÷ 12FLOP = 1/12 (B/FLOP)
►参考: Itanium 2
 6.4GB/s ÷ 4GFLOPS = 1.6 B/FLOP
►RC 法は,計算バウンド
RC 法の要求バンド幅(ワースト・ケース)
►要求バンド幅:1FLOPあたりのデータ転送量
►RC 法
 128B ÷ 12FLOP =
10 B/FLOP
►参考: Itanium 2
 6.4GB/s ÷ 4GFLOPS = 1.6 B/FLOP
►RC 法は,メモリ・バウンド!
SP の処理順序と
キャッシュ
提案手法
1
3
1
3
2
4
2
4
Cache
Screen
基本的なアイディア
►要は,タイリングすればよい.
『ライン内のすべての SP を一気に処理』
 フェッチするライン数:
最小
 参照の空間局所性:
最大
►ただし ,メモリ・アクセス・パタンが:
 通常の数値処理: 静的,固定
 RC法:
動的,変化
►視点,スクリーンの位置に依存
キューボイド (Cuboid)
►キャッシュ・ラインは小さい
 オーバヘッド大
►いくつかのラインをまとめた3次元のブロック:
キューボイド (Cuboid) = 直方体
►サイズ:1次キャッシュの1/2 ~ 1/4
►『キューボイド内のすべての SP を一気に処理』
キャッシュ・ラインと
キューボイド
Cache Line
128
8
8
Cuboid
8 x 8 x 128 = 8K
SP の処理順序と
キャッシュ
キューボイド順
Cuboid
51
73
1
3
2
4
5
7
6
8
62
84
Cache
Screen
キューボイド順処理の2条件
► この例なら簡単だけど,いつでもできるの?
► キューボイド順処理の2条件
1. 1つのキューボイド内の SP は一気に.
2. 1本の視線上の SP は画面奥から順に.
1. キューボイド間の処理順序は,必ず存在するか?
2. キューボイド内の全 SP を効率よく探せるか?
キューボイド間の処理順序
► キューボイド順処理の2条件 (再び)
1. 1つのキューボイド内の SP は一気に.
2. 1本の視線上の SP は画面奥から順に.
► この2条件を満たす処理順序は,必ず
―― 視点,スクリーンの位置に依らず ――
存在するか?
► 結論:存在する.
 x,y,z,各軸ごとに,
視点から遠いキューボイドから処理すればよい.
キューボイド間の処理順序
y
O
x
1
5
13
9
2
6
14
10
3
7
15
11
4
8
16
12
Cuboid
キューボイド間の処理順序
y
O
x
1
2
4
3
5
6
8
7
9
10
12
11
13
14
16
15
Cuboid
キューボイド順処理の条件 (再び)
► この例なら簡単だけど,いつでもできるの?
► キューボイド順処理の条件
1. 1つのキューボイド内の SP は一気に.
2. 1本の視線上の SP は 画面奥から順 に.
1. キューボイド間の処理順序は,必ず存在するか?
2. キューボイド内の全 SP を効率よく探せるか?
キューボイド内の全 SP の探索
► キューボイド内の全 SP を探す.
► 1本の視線上では画面奥から順に.
► 手順:
1. キューボイドを通過するすべての視線を求め,
2. 各視線上,
最奥の SP から順に,最手前の SP まで処理.
キューボイド内の
全 SP の探索
y
Cuboid
Screen
O
►各ピクセルごとに,
 最近処理した SP の座標
 視線ベクトル
を格納.
►O(N2) で,問題にならない.
x
Viewpoint
Screen
キューボイド順 RC 法のまとめ
► キューボイド内の全ての SP を一気に処理
 参照の空間局所性,キャッシュ・ヒット率は最大
 いつでも,ピクセル順のベスト・ケースと同じ
► オーバヘッド
1. キューボイドの面のレンダリング
► O(N2) ではある
2. ベクトル長の短縮
► ピクセル順:
N (128 ~ 4K)
► キューボイド順 ベスト: 128
► キューボイド順 ワースト:
8 (!)
性能評価
► 評価項目:
 キャッシュ・ヒット率
 提案手法のオーバヘッド
1. キューボイドの面のレンダリング
2. ベクトル長の短縮

評価環境
 Itanium 2 サーバ
 gcc –O4
評価環境 Itanium 2 サーバの諸元
動作周波数
1GHz
浮動小数点命令発行数
2命令/cycle
ピーク演算性能
2GMACS, 4GFLOPS
システム・バス・バンド幅
6.4GB/s
キャッシュ
L1D
L2
L3
16KB
256KB
3MB
64B
128B
128B
4
8
12
INT
1
5
12
FP
NA
6
12
サイズ
ライン・サイズ
ウェイ数
レイテンシ
load to use (cycles)
実効FLOPS値:16N 3FLOP ÷ 描画時間
350
300
250
200
PO
PO
CO
CO
150
100
50
0
128
256
512
Worst
Best
Worst
Best
ピクセル順 (PO) と キューボイド順(CO)
►PO Best : PO Worst
 キャッシュ・ヒット率悪化による性能低下
►PO Best : CO Best
 主に,スキャン変換のオーバヘッド
►CO Best : CO Worst
 主に,ベクトル長短縮によるオーバヘッド
►PO Worst : CO Worst
 提案手法による性能向上
まとめ
►キューボイド順レイ・キャスティング法を提案
 視点,スクリーンの位置に依らず,
ボリューム参照の空間局所性を最大化.
►Itanium 2 サーバを用いた評価
 ワースト・ケースでも,ベスト・ケースの 5/6
 ピクセル順に対し,実質 5倍の速度向上
►ボリューム・レンダリングにおけるメモリの問題は
解決!
今後の課題
►プログラムのチューニング
 評価結果は gcc まかせ
 理論最大性能の1割未満 (300M/4GFLOPS)
 ハンドチューニングにより:
►2.4GFLOPS.
►2563 で,10 frames/sec.
►並列化
►応用
 連続モデル
 非構造格子
ダウンロード

ppt