3.4.1 コアレッシング
各スレッドがグローバルメモリにランダムアクセスするとアクセスの効率が悪 く、400〜600クロックサイクルのレイテンシがかかる。しかし、グローバルメモ リのコアレッシング（Coalescing）を利用することで、メモリへのアクセスを高速 化することができる。コアレッシングとは連続したメモリ領域をまとめて転送す るという機能である。図22のように、ハーフワープの各スレッドが同一のデータ サイズにアクセスし、それぞれのアクセスする先が一定サイズのセグメント内に 収まる場合にコアレッシングが発生する。具体的には、グローバルメモリへのア
図 21: メモリのアクセス速度とアクセス経路[18]
クセスは32バイト、64バイト、128バイト単位で、更に先頭のスレッド（スレッ
ド0）がそれぞれ32、64、128の倍数のアドレスを先頭にしてアクセスする必要が
ある。領域のデータサイズは1、2、4、8、16バイトに対応している。他にも、一 部のスレッドがメモリにアクセスしない場合でも、条件が揃えばコアレッシング が発生する（図23）。
図24のようなアクセスでは、アクセス先が一定サイズのセグメントに収まって いてもメモリのアライメントを跨ぎ、別セグメントにアクセスが起きコアレッシ ングが発生しない。また、図25の順番に沿っていないメモリアクセスもコアレッ シングが発生しない。
これらのコアレッシングされる条件の他に、古い世代のGPUではさらに制限が ある。新しい世代のGPUになると、コアレッシングを利用しない場合のアクセス の速度が、L1キャッシュ、L2キャッシュによって改善されている。
3.4.2 バンクコンフリクト
シェアードメモリは高速にアクセスが可能であり、このメモリを効率的に利用 すると性能が飛躍的に向上するが、逆に速度が低下してしまうアクセスパターン が存在する。シェアードメモリは16個のバンクによって構成されている。アクセ スはハーフワープ単位で行われ、各バンクはシェアードメモリを4バイト単位で 管理している。バンク0では、シェアードメモリのアドレスの0、64、128・・・を管 理していることになる。ハーフワープの16スレッドがそれぞれ別個のバンクにア クセスすると、16個のバンクをすべて使い並列処理が可能になる（図26、図27）。
図 22: コアレッシングが発生するメモリ アクセス
図23: アクセスを行わない領域があるが、
コアレッシングが発生するメモリアクセ ス
図 24: 別セグメントにアクセスがあり、
コアレッシングが発生しないメモリアク セス
図25: 順番に沿っていないので、コアレッ シングが発生しないメモリアクセス
図 26: バンクコンフリクトが発生しない メモリアクセス
図 27: 順番に沿っていないが、バンクコ ンフリクトが発生しないメモリアクセス
しかし、複数スレッドが同一のアドレスにアクセスすると、アクセス先のバン クに衝突が発生する(図28)。これをバンクコンフリクトという。バンクコンフリ クトが発生したバンクでは1度に1つのアクセスしか処理できす、逐次処理を行う ことになりプログラム上のボトルネックとなる。また、同一アドレスでなくても ４バイトのデータを1つおきにアクセスした場合も、偶数番目のバンクに2回の アクセスが発生し、奇数番目のバンクにはアクセスがない状況になり、すべての バンクを使ったアクセスに比べて倍の時間がかかることになる(図29)。
例外として、すべてのスレッドが同じデータにアクセスした場合はバンクコン フリクトが発生しない。
3.4.3 Divergent分岐
GPUの分岐命令は1ワープ単位で実行される。よって、ワープ内のスレッドの 分岐先が一致するか、しないかで動作が変わる。すべてのスレッドが同じ分岐な らば、分岐先の処理のみ実行される。しかし、スレッドによって分岐が異なる場 合は、最初にthenのスレッドの処理が実行され、その間elseのスレッドは命令を 実行せずに休止する。次にelseのスレッドの処理が実行され、thenのスレッドは 休止する。これをDivergent分岐と呼ぶ(図30)。CPUでは、if文は片方の分岐先 の処理しか実行しないが、Divergent分岐があるGPUでは、そのワープがthenと elseの両方の処理をするため時間がかかってしまう。できるだけ、ワープ内で異な る分岐が起きないようにプログラミングする必要がある。
図 28: 同じバンクにアクセスがあり、バ ンクコンフリクトが発生するメモリアク セス
図 29: 偶数番目のバンクにのみアクセス が有り、バンクコンフリクトが発生する メモリアクセス
図 30: Divergent分岐
図 31: NVIDIA Visual Profilerの動作画面
3.4.4 CUDA Visual Profiler
CUDAでより速いプログラムを書くためには、プログラムを解析し、ボトルネッ クとなっている部分を確認してから、プログラムの最適化を行う必要がある。 自 分でプログラムを解析するのは簡単なことではない。そこで使用するのが、プロ ファイリングツールのCUDA Visual Profilerである。 CUDA Visual Profilerは、
プログラムを実行し、GPUに組み込まれているパフォーマンスカウンタを調べ、
これらのカウンタに基づいてデータを集計し、そのデータに基いてレポートを表 示する。カーネルを実行するのにかかった時間だけでなく、レジスタやメモリの 使用状況、コアレスアクセスかどうか、バンクコンフリクトやDivergent分岐の発 生状況なども確認できる。様々な形式でグラフ化してプロファイリング結果を見 られるようになっており、また最適化すべき部分も指摘してくれる。CUDAプロ グラミングにおいて非常に重要なツールである。
4 流体シミュレーションの高速化
4.1 プログラムの主要な関数における計算量
表4に、CPUのシミュレーションプログラムの主要な関数についての説明を載 せた。CPUとGPUでは関数の構成が異なるが、処理の流れは基本的に図7の計 算アルゴリズムに沿って行われる。Uniform Gridに関する処理は、最初に計算さ れる重力項と粘性項の計算の前に入る。
MPS法では半陰的アルゴリズムを用いているため、最も計算時間のかかる処理 は圧力のポアソン方程式を解く部分となる。粒子数Nの場合、N×Nの係数行列 が作られる。しかし、行列の非零要素数がN×(近傍の粒子数)となる疎行列で、か つ対称行列になる。例として、2次元のシミュレーションにおいてラプラシアンモ デルの重み関数の半径reを3.1とした時、近傍の粒子数は20∼ 30個になり、行 列の要素数はN ×(20 ∼ 30)となる。このことから、プログラム全体の計算量は ラプラシアンモデルの重み関数の半径によって大きく変わることになる。よって、
シミュレーションの際、大きすぎる値を使わないように注意が必要である。この シミュレーションプログラムでは、共役勾配法(CG法)を用いて方程式を解いて いる。この時、CG法の1ステップあたりの計算量は疎行列なのでO(N)、反復回 数はO(N0.5)となるため、CG法全体の計算量はO(N1.5)となる。
次に計算時間がかかる処理は、重み関数の計算で必要となる近傍の粒子の探索 である。効率化する方法を適用せずに探索を行うと、計算量はO(N2)となり粒子 数が増えると爆発的に計算量が増加していく。そこで、Uniform Gridを使い領域 分割を行うことで、計算量はO(N)となる(2.3.1節参照)。
表5に主要な関数についての計算量のオーダーを載せた。重み関数をともなわな い関数は、すでにO(N)なのでUniform Gridの適用による計算量の改善はない。
表4の中で、Uniform Gridによる計算量の改善が期待できるのは、重み関数の計 算をともなう「cal viscosity」、「set coefficient matrix」、「cal pressure gradient」、
圧力の最低値の探索を行う「set minimum pressure」の4つの関数である。以上よ り、プログラム全体の計算時間がUniform Grid適用後では、O(N1.5)でスケーリ ングされると期待できる。