• トップ
  • G-DEPについて
  • ご購入ガイド
  • サポート
  • お問い合わせ

G-DEPトップ  >  G-DEPの高速演算記  >  高速演算記 第20回 glueon合同会社 井沼安広様

高速演算記 第20回 glueon合同会社 井沼安広様

高速演算記 第20回は glueon合同会社 井沼安広様より、GPUにおけるランダムアクセスの確率論的解析についてご寄稿頂きました。(指導教員:小柳滋様(立命館大学 情報理工学部))

GPUにおけるランダムアクセスの確率論的解析 

1. 研究背景

GPUコンピューティングでは、特にグローバル(大域)メモリに対するアクセスがボトルネックになりがちであり、高速化にはアプリケーション毎に最適化を施す必要がある。最適化手法にはいくつかあるが、代表的なものとしてマルチスレッディングによるアクセスレイテンシの隠ぺいが挙げられる。この手法によって最大限の性能を発揮するためには、
アクセスレイテンシを予め見積もっておき、そのレイテンシを隠ぺい出来るだけのスレッドを立ち上げる必要がある。ここで重要となるのがレイテンシの見積もりである。

ラインアクセスのような規則正しいメモリアクセスの場合、レイテンシの見積もりは比較的容易である。ところが、ランダムアクセスのような不規則なメモリアクセスの場合、決定的なレイテンシの解析は困難である。
ハッシュテーブル、進化計算、シミュレーションなど、GPGPU用途においてランダムアクセスは頻出なものであり重要度が高い。

本稿では、このようなグローバルメモリに対するランダムアクセスに着目し、確率論的なアプローチをとることによって定量的解析を試みる。
 

2. CUDAアーキテクチャ

GPGPUのソフトウェア開発環境としては,NVIDIA社が提供するCUDA(Compute Unified Device Architecture)フレームワークが一般的である.
CUDAはC言語をベースとし,比較的容易にGPGPUプログラミングが行える.
本稿では,CUDAを対象に説明を行う.

2.1. プログラミングモデル
実行の最小単位がスレッドである.
このスレッドの集合体がブロックで,ブロックサイズは1~3次元で指定できる.
さらにブロックの集合体がグリッドで,グリッドサイズは1~2次元で指定できる.
このように,CUDAのプログラミングモデルは階層構造を取っている.
実際には,次で説明するWarp単位でスケジューリングされる.

2.2. Warp
GPUでは,立ち上げたすべてのスレッドが同時並列的に処理されるのではなく,32スレッドずつの塊に分割され,それらをクロック単位で切り替えながら処理を進めていく.
この32スレッドの塊をWarp(ワープ)と呼ぶ.

2.3. Compute Capability
デバイスが対応する機能などは,Compute Capability(CC)と呼ばれるバージョンに依存する.FermiアーキテクチャはCC2.xにあたり,それより以前のデバイスはCC1.xとなる.

2.4. グローバルメモリ
グローバルメモリは大容量であるが,オフチップメモリのためアクセスレイテンシが400~600クロックサイクルと非常に大きい.
グローバルメモリでは,連続したアドレスの要素をまとめたセグメント単位で転送が行われる.以下に示すように,要素の大きさによってセグメントの大きさは異なる.
● 要素サイズ=1Byte → セグメントサイズ=32Byte
● 要素サイズ=2Byte → セグメントサイズ=64Byte
● 要素サイズ=4,8,16Byte → セグメントサイズ=128Byte
このセグメント単位のバーストアクセスを活用するために,複数スレッドのメモリアクセスを一括して処理するコアレッシング(Coalescing)が行われる.CC1.2ではHalfWarp(16スレッド),CC2.0では1Warp(32スレッド)単位で一括処理される.
さらに,あるWarpがグローバルメモリにアクセスしている間に,別のWarpの処理を行うことでレイテンシの隠蔽が行われる.
グローバルメモリはレイテンシが大きいため,これらをうまく利用してオーバーヘッドを抑えることが重要である. 

2.5. キャッシュメモリ
2009年に発表されたFermiアーキテクチャ以降のGPUには、グローバルメモリの2階層キャッシュが搭載されている.
L1キャッシュは物理的にはシェアードメモリと同じであり,シェアードメモリとL1キャッシュの容量比は変更できる.
さらに,グローバルメモリの近くに768KBもの広大なL2キャッシュが配置されている.
どちらもキャッシュラインは128Byteである.
この2階層キャッシュにより,グローバルメモリに対するアクセスオーバーヘッドが以前のアーキテクチャに比べ大幅に改善された.
 

3. グローバルメモリに対するランダムアクセスのモデル化

グローバルメモリに対するランダムアクセスのモデル化を行う。
モデル化にあたり、以下のように仮定する。 

● [仮定1] ランダムアクセス対象の配列要素はInt型(4Byte)
● [仮定2] ランダムアクセス対象の配列要素数は32の倍数
● [仮定3] スレッド数は32の倍数
● [仮定4] アクセス先要素は一様ランダムに決定

3.1. バースト転送とコアレッシングのモデル化
まずバースト転送とコアレッシングのモデル化を行う。
図1は、一括処理されるDスレッドがランダムアクセス対象であるm個のセグメント集合に対してランダムアクセスする様子を表している。図においてアクセスが当たっているセグメントの数が、すなわちアクセス回数である。
 

図1:セグメント集合に対するランダムアクセス

 式(1)は、一括処理されるDスレッドがm個のセグメント集合に対してランダムアクセスし、結果としてn個のセグメントにアクセスが当たる確率である。

  

式(1)より、確率分布(図2)、さらにWarpあたりの平均アクセス回数を得ることができる。

図2: F(32, m, n)の確率分布


3.2. キャッシュ効果のモデル化
CC2.0以降では、キャッシュの効果を考慮に入れる必要がある。
一度アクセスされたセグメントはキャッシュされ、以降は高速にアクセスできる。さらに処理が進むにつれてキャッシュ済みセグメントが単調的に増加していく。このようなキャッシュの効果を吸収的マルコフ連鎖によってモデル化する。これにより任意の時間におけるキャッシュのヒット率(ミス率)を求めることが可能になる。

以下、ランダムアクセス対象のセグメントの数をm、キャッシュ容量をC(単位はセグメント)、キャッシュ飽和点をM=min(m,C)とする。

図3は、キャッシュ済みセグメント数を状態とした状態遷移図である。初期状態S0でキャッシュは空とし、SMが吸収状態となる。



図3:キャッシュの状態遷移図

ある状態Siからある状態Sjへの遷移確率G(i,j)を式(2)に示す。

 マルコフ連鎖の定義を式(3)(4)(5)に示す。

 

表1は、任意の時間tでのキャッシュ済みセグメント数の分布を表している。初期状態W(0)ではキャッシュは空で、4Warp目W(4)ですべてキャッシュされることがわかる。

表1:適用例(M=16)

3.3. モデルの検証
キャッシュ済みセグメント数の理論期待値と実測平均値を比較することで、モデルの正しさを検証する。
実測値の算出方法は以下の通りである。

● CUDAでランダムアクセスモデル(図1)を実装
   ☆ アクセス先の決定に、2種類の疑似乱数生成アルゴリズムを使用
● CUDA Visual Profilerのl1_cached_missを1,000回サンプリング、平均値を算出

M=54とした場合の検証結果を図4に示す。

図4:理論値と実測値の比較(M=54)

図4より、モデルと実測値は高い相関関係にあることがわかる。

4. レイテンシの見積もり

本章では、3章で構築したモデルに基づいたレイテンシの見積もり手法について述べる。
以下、ランダムアクセス対象のセグメント数をm、立ち上げるWarpの数をdとする。
また、L1キャッシュアクセスにかかるレイテンシをLL1、L2キャッシュアクセスにかかるレイテンシをLL2、グローバルメモリアクセスにかかるレイテンシをLGlobalとする。

以下、Compute Capability別にレイテンシの見積もり手法について述べる。

4.1. Compute Capability 1.2
CC1.2では、ランダムアクセスレイテンシを式(6)によって求めることができる。


4.2. Compute Capability 2.0以降
CC2.0以降ではキャッシュの効果を考慮に入れる必要があるため、CC1.2と比べ複雑になる。
L1キャッシュに関するパラメータを以下のように定義する。

L2キャッシュに関するパラメータを以下のように定義する。

任意の時間tにおけるL1キャッシュのヒット率とミス率を式(7)(8)のように表すことができる。

同様に、任意の時間tにおけるL2キャッシュのヒット率とミス率を式(9)(10)のように表すことができる。

 

CC2.0以降では、ランダムアクセスレイテンシを式(12)によって求めることができる。

5. まとめ

本稿では、GPUのグローバルメモリに対するランダムアクセスに着目し、アクセスレイテンシの定量的な解析手法について提案を行った。
3章でランダムアクセスの確率論的モデル化を行い、4章でモデルに基づいたレイテンシの解析手法について述べた。  

 
[参考文献]
1. NVIDIA: NVIDIA CUDA C Programming Guide 4.0 (2011).
2. Ronald L. Graham 他著, 有澤誠 他訳: コンピュータの数学, 共立出版 (1993).

[参考]
本稿で登場する定数 

D 一括処理されるスレッド数 CC1.2では16 (HalfWarp)
CC2.0では32 (1Warp)
C キャッシュ容量 L1は16KB or 48KB(本稿仮定下では、128セグメント or 384セグメント)
L2キャッシュ容量は768KB(本稿仮定下では6144セグメント)
LL1 L1 キャッシュアクセスに
かかるレイテンシ
40 Clock Cycles
LL2 L2 キャッシュアクセスに
かかるレイテンシ
~200 Clock Cycles
LGlobal グローバルメモリアクセス
にかかるレイテンシ
200~ Clock Cycles