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

Slides:



Advertisements
Similar presentations
1 広島大学 理学研究科 尾崎 裕介 石川 健一. 1. Graphic Processing Unit (GPU) とは? 2. Nvidia CUDA programming model 3. GPU の高速化 4. QCD with CUDA 5. 結果 6. まとめ 2.
Advertisements

G ゼミ 2010/5/14 渡辺健人. パフォーマンスの測定 CUDA Visual Profiler CUDA の SDK に標準でついているパフォーマン ス測定用のツール 使い方: exe ファイルのパスと作業ディレクトリ指定して実 行するだけ 注意点 : GPU のコード実行後にプログラム終了前に,
HBSP モデル上での 行列積を求めるアルゴリ ム 情報論理工学 吉岡健太.
Imagire Day CEDEC 2009続・レンダリスト養成講座 田村 尚希 川瀬 正樹 シリコンスタジオ株式会社.
ゲーム開発者向け最新技術論文の解説・実装講座
【事例演習5】  字句解析     解 説  “ハッシュを用いた字句解析の方法”.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
情報理工学系研究科 コンピュータ科学専攻 上嶋裕樹
プログラミング演習3 李 亜民クラス 第2回 ラスタライズ.
07. 値予測 五島 正裕.
計算理工学基礎 「ハイパフォーマンスコンピューティングの基礎」
07. 値予測 五島 正裕.
ヘテロジニアスマルチコアプロセッサ 環境を対象としたキャッシュシステム 自動生成ツールの開発
基本情報技術概論(第10回) 埼玉大学 理工学研究科 堀山 貴史
Ibaraki Univ. Dept of Electrical & Electronic Eng.
パノラマ動画像モデルによる 仮想空間表現システムの研究
A Q R QR分解とは? → × ◆QR分解 QTQ = I (単位行列) ◆応用例 ◆主な計算方法 n m 今回はこの方法に注目
11章 ボリュームレンダリングを学ぶ 本来は目に見えない内部情報をレンダリングし可視化する技術
3DCG技法についての 調査報告 ○○県立○○高等学校 1年は組 グループ0.
三重対角化アルゴリズムの性能評価 早戸拓也・廣田悠輔.
IaaS 仮想マシン(VM)をネットワーク経由で提供 負荷に応じてVM数や性能を変更できる ハードウェアの導入・管理・維持コストの削減
オペレーティングシステム 第11回 仮想記憶管理(2)
Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化
画像処理工学 2011年10月27日 担当教員 北川 輝彦.
情報工学基礎(改訂版) 岡崎裕之.
AllReduce アルゴリズムによる QR 分解の精度について
地理情報システム論 第3回 コンピュータシステムおける データ表現(1)
P,Q比が変更可能なScaLAPACKの コスト見積もり関数の開発
岩井 儀雄 コンピュータ基礎演習  ー探索、整列ー 岩井 儀雄
第7章 データベース管理システム 7.1 データベース管理システムの概要 7.2 データベースの格納方式 7.3 問合せ処理.
首都大学東京 都市教養学部数理科学コース 関谷博之
ピクセル レス サンプリング 高桑昌男 国際情報科学芸術アカデミー.
第5回 CPUの役割と仕組み3 割り込み、パイプライン、並列処理
階層的境界ボリュームを用いた 陰関数曲面の高速なレイトレーシング法
基本情報技術概論(第8回) 埼玉大学 理工学研究科 堀山 貴史
3次元剛体運動の理論と シミュレーション技法
演算/メモリ性能バランスを考慮した マルチコア向けオンチップメモリ貸与法
Yuri Y. Boykov Marie-Pierre Jolly
画像のディジタル化 1 A/D変換器 光強度のアナログ情報をディジタル信号に変換する 標本化:sampling
正方行列向け特異値分解の CUDAによる高速化
オーサリングツール&ブラウザの 技術的トピック
文献名 “Performance Tuning of a CFD Code on the Earth Simulator”
サポートベクターマシン によるパターン認識
過負荷時の分散ソフトウェアの 性能劣化を改善する スケジューリングの提案
Advanced Computer Architecture
画像処理 基礎.
コンピュータを知る 1E16M009-1 梅津たくみ 1E16M017-8 小沢あきら 1E16M035-0 柴田かいと
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
大阪電気通信大学 工学部 電子機械工学科 入部正継
Advanced Computer Architecture
3次元構築アプリケーションにおける3D表示(2)
オペレーティングシステムJ/K (仮想記憶管理)
第7回 授業計画の修正 中間テストの解説・復習 前回の補足(クロックアルゴリズム・PFF) 仮想記憶方式のまとめ 特別課題について
動的データ依存関係解析を用いた Javaプログラムスライス手法
可視面・不可視面の判定方法と隠れ面(不可視面)の消去法について述べる.
先進的計算基盤システムシンポジウム SACSIS2007併設企画 マルチコアプログラミングコンテスト 「Cellスピードチャレンジ2007」
2012年度 情報数理 ~ 様々なデジタル情報(1) ~.
バイトコードを単位とするJavaスライスシステムの試作
情報処理Ⅱ 第2回:2003年10月14日(火).
地理情報システム論(総)/ 国民経済計算論(商)
第4回 メモリ管理 主記憶(メインメモリ)の管理 固定区画方式と可変区画方式 空き領域の管理 スワッピング.
アルゴリズムとデータ構造1 2009年6月15日
アルゴリズムとデータ構造 2010年6月17日
情報処理Ⅱ 第2回 2004年10月12日(火).
分散メモリ型並列計算機上での行列演算の並列化
2019年度 情報数理特論B ~ 様々なデジタル情報(1) ~.
プログラミング基礎a 第5回 C言語によるプログラミング入門 配列と文字列
Ibaraki Univ. Dept of Electrical & Electronic Eng.
2008年 7月17日 応用数理工学特論 期末発表 鈴木綾華,程飛
Presentation transcript:

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

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

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

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

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

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

ピクセル値の計算 ―― α-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 を,画面奥から順に 処理.

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 の処理順序と キャッシュ ベスト・ケース 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

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

SP の処理順序と キャッシュ ワースト・ケース Cache 3 5 7 4 8 6 1 5 2 6 3 7 4 8 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 の処理順序と キャッシュ 提案手法 Cache 1 3 2 4 1 3 2 4 Screen

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

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

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

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

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

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

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

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

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

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

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

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

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

評価環境 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

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

ピクセル順 (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. 並列化 応用 連続モデル 非構造格子