Download Report

GPGPU による
生体軟組織の実時間変形・破壊シミュレーション
佐瀬一弥
[email protected] 北海道大学大学院情報科学研究科博士課程後期
Tumor
Aspirator
脳腫瘍摘出シミュレーション（約 10 [FPS], 節点数 9184, 四面体要素数 34050）
0
有限要素法ベースの力覚作用可能な脳外科手術シミュレータの実
現を目指す．課題は膨大な計算量を実時間で処理することである．
1
2
0
0
1
1
n j
E(e, 1) = n
0
1
2
2
アプローチ：
生体組織を等方性弾性体と仮定．四面体要素を用いた共回転系定式
化による非線形有限要素法を採用し，それに適した GPGPU 実装を
開発する．
Methods
( 佐瀬他，GPGPUを活用した実時間脳腫瘍摘出シミュレーション，
ロボティクス・メカトロニクス講演会2014予稿集，富山，2014. )
E(e,3) E(e,1) E(e,2) E(e,0)
E(e,3)
E(e,1)
0
1
2
3
0
1
2
Nnode
3
E(e,2)
E(e,0)
Ke
K (E(e, 0), E(e, 1)) += Ke(0,1)
K
剛性行列の組み立て（1 マスは 3×3 の部分行列）
疎行列形式ではコストの高いランダムアクセスを避けたい．
そこで，縮約配列を用いる．下記①-③を一度行い，計算ループでは
④を実行する．( Cecka, et al., GPU Computing Gem, 2012)
① 全総和元行列 (Ke) 一次元化．
Element data (
② 総和先行列 (K) 格納先 *1 を確保．
③ 非ゼロエントリごとに
総和元インデックスのリスト
（縮約配列）を作成．
④ 非ゼロエントリ / スレッドで右
図の処理を並列実行．
)
① Read
② Sum Reduction
array
=
K (csrValues)
縮約配列
*1 CSR 形式の場合，非ゼロ要素配列，列オフセット配列，行インデックス配列
Conclusion
③ Write
+
3
E(e, 3) = i, E(e, 1) = j
0
1
2
3
0
1
2
Global matrix
3
E(e, 2) = n
Element stiffness matrices
of tetras which share node n
E(e, 1) = i, E(e, 0) = j
Element stiffness matrices of tetras
which share an edge (i, j), (i > j)
剛性行列の対称性を考慮した縮約配列の作成
剛性行列の対称行列となるため，
行列成分の半分のみを計算する
（上図）．
全体のフローチャートを右図に
示す．
共回転系定式化による有限要素
法では，初期配置における Ke に
現配置における回転 Re を作用さ
せた行列を作成し，その総和に
より全体剛性行列を得る．
破壊表現のためには削除する要
素の Re を零行列として GPU に
送信する．
連立一次方程式の求解には共役
勾配 (CG) 法を用いた．
ボトルネックのひとつは剛性行列の組み立てである．
剛性行列 K は要素剛性行列 Ke の総和により得る．
K：3 Nnode × 3 Nnode 疎行列 , Ke：12 × 12 密行列（×Ntetra）
2
3
i
1
3
n
3
0
1
2
2
3
脳外科手術シミュレータ
0
3
Host (CPU)
Device (GPU)
Precomputing
Reduction array
Ke
Calc. R
Re
Re Ke ReT
K(CSR)
Reduction
Apply
boundary
condition
Solve Av = b
A, b
v
Other func..
フローチャート
Results
最上部の図に示すシミュレーション
において，CPU のみの場合，と
GPU を併用した場合の結果を右図
に示す．GPU を用いることで 43
[ms] 削減することができた．
+
コンピュータ構成
160
Time per flame [ms]
Introduction
120
80
148
105
40
0
・Intel Core i7-3960X
CPU
GPU
4.8 [GHz](Over-clocked), 6 cores
1
ステップあたりの計算時間
・NVIDIA Tesla K20c, 2496 cores, 706MHz
・OpenMP および CUDA を利用．
縮約配列を用いた剛性行列組み立て，および，CG 法による連立方程式の求解を GPGPU 実装することに
より，約 10000 節点を持つ有限要素モデルに対し 1 ステップ 100 [ms] のほぼ実時間計算を実現した．