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: レーベンシュタイン距離」 5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2 5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2

編集距離の操作例 「 weight 」と「 write 」の編集距離 以下の操作で「 weight 」から「 write 」になる  weight 1.weighte ( 挿入： e) 2.wrighte ( 置換： e → r) 3.wrihte ( 削除： g) 4.write ( 削除： h) 3 回以下の操作では「 weight 」を「 write 」できな い よって編集距離は 「 4 」 削除，挿入，置換は文字列の中のどの位置で行 ってもよい

weight w r i t e 編集距離計算のアルゴリズム ( 概 要 ) 「動的計画法 (Dynamic Programming) 」が有 名 操作回数を表を作って求める weight write 文字列 1 文字列 2 write weight 操作回数を 格納する テーブル

編集距離計算のアルゴリズム ( 手順 ) 1. 最左列，最上行のセルは 1 ～ N ， 1 ～ M の値と仮定 2. 上，左上，左のセル値と，当該の 行と列の文字列を使い，以下の方 法で各セルの値を計算する A) 文字列が同一ならば左上セルの値 B) 異なるならば左上セルの値 +1( 置 換 ) C) 左セルの値 +1( 挿入 ) D) 上セルの値 +1( 削除 ) E)(A)-(E) の最小値をセルの値に設定 3. テーブルの左上から値を求める 4. 右下端のセル値が最終的な 編集距離となる 0weight w r i t e このスライドには アニメーションが設定されてい ます アニメーションでは列ごとに計算しているが， 「上，左上，左のセル値」が決定しているセル ならば計算手順は任意 N M

アルゴリズムの並列化 (1) 以下のデータがあれば，各セル の 計算が可能 – 文字列 – 左上セル，左セル，上セルの値 ⇒ 図中の同じ文字色のセルどう しは，並列に実行可能！ しかしこの並びを素直に配列で表 現すると， GPU ではメモリアク セス性能が低下 ⇒ ”Coalesced access” を可能とした い weight w r i t e このスライドには アニメーションが設定されてい ます Coalesced access については， NVIDIA CUDA Programming Guide 2.0 の を参 照 「 Compute Capability 1.2 and Higher 」の部分です． ( 利用する GPU は 1.3 なので )

アルゴリズムの並列化 (2) GPU のスレッド達が同時にアク セスする領域は，メモリ上で固 まっていた方が効率的 (coalesced access) ⇒ツールキットでは，左図のように 表配置を「ずらす」ことにより ，同じ文字色のセルを，メモリ 上で固めて配置 計算は左図の上から下へ順に行 われる ツールキットでは，メモリを節 約するため，最新の三行だけを GPU のメモリ (Global memory) に 保持している wweight r i t e

ツールキット ver1.0 2 つのテキストファイルを入力すると，それらの中の文 字列を読み込んで編集距離を求める GPU 内で複数のスレッドブロック・複数のスレッドを起 動する⇒複数の Streaming Multiprocessor(SM) および SP を使 用する 制約：各文字列の文字数は 128 の倍数 – いろいろなサイズの例題ファイル付き (file1, file2, …, file20) getrndstr.c を使用すると，任意長のランダム文字列を生 成できる $ gcc -O3 -o getrndstr getrndstr.c $./getrndstr > file9999 乱数種 13 で生成される 128 文字の文字列を格納したファイル file9999 を生成する

実行方法 (1/3) Toolkit のディレクトリ内でコンパイル make nvcc -c -O2 main_host.cpp nvcc -c -O2 -g device.cu nvcc -O2 -o ldistance main_host.o device.o

実行方法 (2/3) 練習問題の実行 answer = strnum(a)= strnum(b)= Initializing CUDA: seconds GPU eclock : seconds [CPU] : [GPU] : SUCCESSFUL. さまざまな練習問題を実行する， run1.sh ～ run9.sh が用意されています GPU を用いた計算時間 ２つの文字列の長さ GPU を用いた計算結果 ( 編集距離 )

実行方法 (3/3) 自作問題 (getrndstr などによる ) の実行 file7 file answer = strnum(a)= strnum(b)= Initializing CUDA: seconds GPU eclock : seconds [CPU] : [GPU] : SUCCESSFUL. 文字列長 GPU を用いた計算時間 ２つの文字列の長さ GPU を用いた計算結果 ( 編集距離 ) 巨大な文字列を対象にした場合，計 算時間が非常に長くなることがあり ます 「答え」を与えないと 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) ，同時にアクセスす る部分がまとまるように表を作成

ツールキットのメモリ利用 左図は実際には全てがメモ リにおかれることはなく， 最新の三行だけが GPU の Global memory におかれる あるステップでは， p[1], p[2] から読み込んで p[0] に 書き込み 次のステップでは， p[2], p[0] から読み込んで p[1] に 書き込み ・・・ 3 つのバッファを順 繰りに利用 wweight r i t e lenStr2

並列処理の方法 ずらした表において，横に並んだセルを並列に 実行したい – 最大 1M-128 個のセル – GPU では，一度に 個までのスレッドブロック， スレッドブロック内には 512 個までのスレッドを起動 可能 (y 方向， z 方向を使えばよりたくさん )  合計 1M-128 個のスレッドの同時起動は可能 – 実際の Streaming multiprocessor 数より多くのスレッド ブロックを起動すると，一般的にはメモリアクセス コストを隠せて性能上有利  ツールキットでは最大 lenStr2 個のスレッドを起動し ，一スレッドが一セルを計算する

おわり