Multicore Programming Contest GPU Challenge 2009 ツールキット解説書 ver.1.0対応版 GPU Challenge 2009 実行委員会 Cell Challenge 2009併設企画 GPU Challenge 2009 これはなに？ • GPU Challenge 2009規定課題に取り組む際のベースとなるツールキットの解説です • Cell Challenge 2009ツールキット解説書(Cell Challenge 2009実行委員会による)を、許諾を得て転載・一部改変したものです規定課題「文字列の編集距離計算」 • 2つの文字列の近さを計る方法 • かな漢字変換エンジンや，DNAの相同性検索などに利用される • 2つの文字列の編集距離 – 片方の文字列から，もう一方の文字列を得るための操作回数の最小値 – 使用可能な操作は以下の3種類 • 削除：1つの文字を取り除く • 挿入：1つの文字を新たに付け加える • 置換：1つの文字を別の文字で置き換える – 参考になるURI「wikipedia:レーベンシュタイン距離」 http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A 5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2 編集距離の操作例 • 「weight」と「write」の編集距離 • 以下の操作で「weight」から「write」になる  1. 2. 3. 4. weight weighte (挿入：e) wrighte (置換：e → r) wrihte (削除：g) write (削除：h) • 3回以下の操作では「weight」を「write」できない • よって編集距離は「4」 • 削除，挿入，置換は文字列の中のどの位置で行ってもよい編集距離計算のアルゴリズム(概要) • 「動的計画法(Dynamic Programming)」が有名 weight 文字列1 write 文字列2 • 操作回数を表を作って求める w weight write w r i t e e i g h t 操作回数を格納するテーブル編集距離計算のアルゴリズム(手順) このスライドにはアニメーションが設定されています 1. 最左列，最上行のセルは1～N， 1～Mの値と仮定 2. 上，左上，左のセル値と，当該の行と列の文字列を使い，以下の方法で各セルの値を計算する N 1 2 3 4 5 6 0 w e i g h t 1 w 0 1 2 3 4 5 2 r 1 1 2 3 4 5 3 i 2 2 1 2 3 4 4 t 3 3 2 2 3 3 5 M e 4 4 3 3 3 4 アニメーションでは列ごとに計算しているが，「上，左上，左のセル値」が決定しているセルならば計算手順は任意 A) B) C) D) E) 3. 4. 文字列が同一ならば左上セルの値異なるならば左上セルの値+1(置換) 左セルの値+1(挿入) 上セルの値+1(削除) (A)-(E)の最小値をセルの値に設定テーブルの左上から値を求める右下端のセル値が最終的な編集距離となるアルゴリズムの並列化 (1) • 以下のデータがあれば，各セルの計算が可能このスライドにはアニメーションが設定されています w r i t e w e i g h t 0 1 2 3 4 1 1 2 3 4 2 2 1 2 3 3 2 2 4 4 3 3 3 3 3 5 5 4 3 4 – 文字列 – 左上セル，左セル，上セルの値 ⇒ 図中の同じ文字色のセルどうしは，並列に実行可能！しかしこの並びを素直に配列で表現すると，GPUではメモリアクセス性能が低下 ⇒”Coalesced access”を可能としたい Coalesced accessについては，NVIDIA CUDA Programming Guide 2.0の5.1.2.1を参照「Compute Capability 1.2 and Higher」の部分です．(利用するGPUは1.3なので) アルゴリズムの並列化(2) w w r 0 1 2 3 4 i t e e 1 1 2 3 4 i 2 2 1 2 3 g h 3 3 2 2 4 4 3 3 3 3 t 5 5 4 3 4 • GPUのスレッド達が同時にアクセスする領域は，メモリ上で固まっていた方が効率的(coalesced access) ⇒ツールキットでは，左図のように表配置を「ずらす」ことにより，同じ文字色のセルを，メモリ上で固めて配置 • 計算は左図の上から下へ順に行われる • ツールキットでは，メモリを節約するため，最新の三行だけをGPUのメモリ(Global memory)に保持しているツールキット ver1.0 • 2つのテキストファイルを入力すると，それらの中の文字列を読み込んで編集距離を求める • GPU内で複数のスレッドブロック・複数のスレッドを起動する ⇒複数のStreaming Multiprocessor(SM)およびSPを使用する • 制約：各文字列の文字数は128の倍数 – いろいろなサイズの例題ファイル付き (file1, file2, … , file20) • getrndstr.c を使用すると，任意長のランダム文字列を生成できる $ gcc -O3 -o getrndstr getrndstr.c $ ./getrndstr 128 13 > file9999 乱数種13で生成される128文字の文字列を格納したファイルfile9999を生成する実行方法(1/3) • Toolkitのディレクトリ内でコンパイル gt901@gpuc1:~/toolkit-1.0> make nvcc -c -O2 main_host.cpp nvcc -c -O2 -g device.cu nvcc -O2 -o ldistance main_host.o device.o 実行方法(2/3) • 練習問題の実行 gt901@gpuc1:~/toolkit-1.0> ./run3.sh answer = 19168 strnum(a)= 20480 ２つの文字列の長さ strnum(b)= 20480 Initializing CUDA: 3.97771811 seconds GPU eclock : 0.41952395 seconds GPUを用いた計算時間 [CPU] : 19168 [GPU] : 19168 GPUを用いた計算結果(編集距離) SUCCESSFUL. さまざまな練習問題を実行する，run1.sh ～ run9.shが用意されています実行方法(3/3) • 自作問題(getrndstrなどによる)の実行 gt901@gpuc1:~/toolkit-1.0> ./ldistance file7 file8 19168 answer = 19168 第一ファイル第二ファイル答え strnum(a)= 20480 (省略可) ２つの文字列の長さ strnum(b)= 20480 Initializing CUDA: 3.97771811 seconds GPU eclock : 0.41952395 seconds GPUを用いた計算時間 [CPU] : 19168 [GPU] : 19168 GPUを用いた計算結果(編集距離) SUCCESSFUL. 文字列長「答え」を与えないとCPUで検算を行います。検算の時間は計算時間には含まれません巨大な文字列を対象にした場合，計算時間が非常に長くなることがあります規定課題への取り組み方 • 規定課題では，CPUプログラムおよびGPUのプログラム (device.cu)を実装する – 以下のプログラムを実装してください • CUDAで記述された，編集距離を計算するプログラム(device.cu) • device_user()関数を実装してください．ツールキットのdevice_user()を基に改造を行うのは，もちろんokです – 以下のファイルは変更が許可されません • main関数などを含むプログラム(main_host.cpp) – device.cuに加え，新たにプログラムファイル(*.c, *.cpp, *.cu, *.hなど)を追加することはok • それに応じて，Makefileを変更すること参加者が実装する device_user関数について(1) unsigned int device_user (char *str1, int lenStr1, char *str2, int lenStr2) • device_user関数はCPU上で呼ばれます • この関数に与えられるポインタ引数は全て，CPUのメモリ(ホストメモリ)を指します – GPU上のメモリへのコピー(cudaMemcpy)などは，device_user関数内で行う必要があります • 各入力文字列の先頭ポインタ: str1, str2 • 各入力文字列の長さ: lenStr1, lenStr2 – lenStr1, lenStr2はそれぞれ1M-128(=1,048,448)以下です – lenStr1, lenStr2はそれぞれ128の倍数です – lenStr1とlenStr2の積は2の34乗(=17,179,869,184)以下です • 計算結果は返り値としてかえすこと参加者が実装する device_user関数について(2) • 参加者のプログラムは1つのGPUのみを用いること． device_user関数の中でcudaSetDevice関数などを呼んではいけない． – 委員会の準備する計算機には2つずつGPUが搭載されていますが，各チームはそのうちの1つだけを使うことになります) • 参加者のプログラムはCPUコアを高々1つだけ用いること．ホストとGPUの間の通信やGPUカーネル関数の終了待ちなどにも CPUコアが使われるので注意のこと．メモリについて • 参加者はホストメモリ(mallocなどによる)，GPU上のGlobal memory(cudaMallocなどによる)を自由に利用できます – GPU上のshared memory, texture memoryなどもok • メモリ容量に注意してください – ホスト: 32GB – GPU (Global memory): 4GB • 特に，lenStr1 * lenStr2のサイズのint二次元配列は，最大(2 の34乗)の場合にはホストにもGPUにも乗りません  ツールキットで行っているような，使用メモリ量を抑える工夫が必要プログラムの実行時の注意 • 複数の参加者が，計算機を紳士協定で共用します (2009/02/03現在) – 各チーム(偶数・奇数)が許可されている方のマシンだけにログイン可能です． – 一度のプログラム実行は，10分までとしてください．また，一チームが連続して複数回プログラムを実行することはできますが，長期間占有することは避けてください．プログラムの実行前には，psコマンドやtopコマンドでマシン利用状況を確認することをおすすめします．ツールキットver1.0の計算手順 • 複数のスレッドブロックおよび，それぞれ複数スレッドを用いて並列に編集距離を計算するコードの例 • 並列化できる部分は，前述の「アルゴリズムの並列化」を参照 – (表上で)斜めに並んだセルは並列化可能 – 効率化のため(アクセスのcoalescing)，同時にアクセスする部分がまとまるように表を作成ツールキットのメモリ利用 lenStr2 w w r 0 1 2 i t e 3 4 e 1 1 2 3 4 i 2 2 1 2 3 g 3 3 2 2 3 h 4 4 3 3 3 t 5 5 4 3 4 • 左図は実際には全てがメモリにおかれることはなく，最新の三行だけがGPUの Global memoryにおかれる • あるステップでは，p[1], p[2] から読み込んでp[0]に書き込み • 次のステップでは，p[2], p[0] から読み込んでp[1]に書き込み・・・3つのバッファを順繰りに利用並列処理の方法 • ずらした表において，横に並んだセルを並列に実行したい – 最大1M-128個のセル – GPUでは，一度に65535個までのスレッドブロック，スレッドブロック内には512個までのスレッドを起動可能 (y方向， z方向を使えばよりたくさん) 合計1M-128個のスレッドの同時起動は可能 – 実際のStreaming multiprocessor数より多くのスレッドブロックを起動すると，一般的にはメモリアクセスコストを隠せて性能上有利  ツールキットでは最大lenStr2個のスレッドを起動し，一スレッドが一セルを計算するおわり