CUDAの基本事項
作成日 2008/6/5 最終更新日 2008/7/18
CUDAには日本語のプログラミングガイド（以下、PG)がついていますが、機械翻訳らしく意味が通らないところがたくさんあります。
そこで、自分の備忘録としての意味も含めて、CUDAにおける基本概念についてまとめてみたいと思います。
1.スレッドとブロック（PG第2章）
PG2.1節、「メインCPUかホストのコプロセッサ」というくだりは、原文では"in main CPU, or host"
となっており、
CPU側での処理やCPUのメインメモリなどを「ホスト」と呼ぶ、という意味。これはプログラム上の___host___修飾子の意味づけになっていま
す。
スレッドとは、普通のCPUと同じく、ひとつの処理の流れに相当します。
ブロックはスレッドの集まりで、ひとつのブロックに属するスレッドは「共有メモリ(shared
memory)」と呼ばれるキャッシュのようなものを通して、
高速なメモリアクセスを行うことができる。VRAM(gloabl memoryあるいはdevice
memoryと呼ばれる）からそのブロックが使用する部分を
共有メモリにコピーした上で処理を行うことで高速な処理ができます。
１ブロックには最大で512のスレッドをいれることができます（Appendix.A)。
プログラマは問題を複数のブロックに分割し、それを並行に処理することによって並列プログラムを実行することになります。
PG日本語版p.8、「同じ次数とサイズのブロックの場合は、複数のブロックから一つのブロックに集めた同じカーネルで実行します」
は、
「次数とサイズが同じブロックで同じカーネル（処理）を実行する場合は、複数のブロックがグリッドにまとめられて同時実行されます」という意味。
カーネルとは各スレッドで実行されるプログラムのこと。
グリッドにまとめることによって、512以上のスレッドを同時実行することができます。
ただし、ブロックをこえたメモリ共有や同期はできません。
グリッドに含まれるブロックが逐次実行されるか、並行処理されるかは、デバイスの処理能力に依存しますが、
それをあまり意識せずにプログラムを組むことができることが利点とされています。
実際どの程度のスレッドが同時に実行できるのかはグラフィックボードのスペックによりちがいます。
たとえば、同時実行可能なスレッド数が128（4つのマルチプロセッサがある場合）ならば、
1ブロックに含まれるスレッドが64でも、2つのブロックを同時に実行することができますので、
ブロックを小さいな単位にすることによってパフォーマンスが落ちるということはありません。
おそらく、1ブロックに含まれるスレッドをいくつにすべきかということは、
1つのスレッドがいくつのレジスタと共有メモリを消費するかということによって決まるのではないでしょうか。
ただし、後述のワープ単位の実行という制限があるため、32の倍数にすべきでしょう。
グラフィックカード上には6種類のメモリが存在します。
・レジスタ（スレッド単位）
・ローカル・メモリ（スレッド単位）
・共有メモリ（ブロック単位）
・グローバル・メモリ（アプリケーション共通）、カーネルから読み書き可能、キャッシュなし
・定数用メモリ（アプリケーション共通）、カーネルからは読み込みのみ、キャッシュあり
・テクスチャ・メモリ（アプリケーション共通）、カーネルからは読み込みのみ、キャッシュあり
最後の３つはホスト側から設定することが可能です。
ローカルメモリについては、第2章の図2-2ではプロセッサごとに存在することになっていますが、
すぐ後の第3章の図3-1では記述がありません。これについてはもうちょっと調べます。
これらはそれぞれで効率的な使い方がことなります。（後述）
2.マルチプロセッサとワープ（PG 第3章）
並行処理の単位はマルチプロセッサと呼ばれるプロセッサの集合によって行われます。マルチプロセッサは8つのプロセッサを持ちます。
共有メモリはマルチプロセッサごとになっていますので、１つのブロックは１つのマルチプロセッサ上で実行されます。
１つのブロック内のスレッドは32個のずつに「ワープ」という単位にまとめられて実行されます。
つまり、32のスレッドは常に一度に実行されることになります。
マルチプロセッサは8個のプロセッサを持ちますから、4クロックを使って32スレッド＝1ワープを処理します。
ワープは連続したスレッドIDごとにまとめられます。(0-31,32-63,64-95.....）
ただし、現在の実装では、実行のスケジューリングは半ワープ(16スレッド）単位で行われているようです。
1つのマルチプロセッサに複数のブロックが割り当てられた場合、タイムスライスによるスケジューリングが行われますが、
どのような順番でブロックが実行されるかは不定です。
よって、ブロックをまたいだメモリ共有や同期、およびグローバルメモリを通した通信などはできません。
限られた条件下では、メモリへの書き込みにタグを付与することによって、
同時アクセスによる値の不定性を回避することが可能なようです。
これは、サンプルのHistogramで解説されていますので、のちのちこのサイトでも触れたいと思います。
3．共有メモリのバンク衝突回避について
共有メモリは、1つのブロック内において共有できるキャッシュのようなもの
で、
非常に高速なアクセスを行うことができます。
一般的な処理は、
1)グローバルから共有メモリへの値の読み込み
2)共有メモリを用いて演算を行う
3)共有メモリからグローバルへ結果を書き出す
というステップで行われることになるでしょう。
この共有メモリは、マルチスレッド下でアクセスされることが前提となっているために、
同時にメモリの複数個所をアクセスすることがサポートされているわけですが、
どのような場合にも高速なアクセスができるわけではありません。
共有メモリは16個のバンクという塊に分割されており、
それぞれのスレッドが別々のバンクにアクセスしているときのみ同時アクセスが可能となり、
複数のスレッドが同じバンクを同時にアクセスしようとすると、
アクセスがシリアル化されてしまうため、実行が遅くなります。
その実験を実際にしてみましたので、詳細はこちら。
この結果、共有メモリのバンク番号nは、共有メモリのアドレス（バイト単位）addrから
n = (addr mod 64) / 4
で求められることが確認できました。
(以下、執筆予定）