Multicore Programming Contest GPU Challenge 2009 ツールキット解説書 ver.1.0 対応版 GPU Challenge 2009 実行委員会 Cell Challenge 2009 併設企画 GPU Challenge 2009.

Presentation on theme: "Multicore Programming Contest GPU Challenge 2009 ツールキット解説書 ver.1.0 対応版 GPU Challenge 2009 実行委員会 Cell Challenge 2009 併設企画 GPU Challenge 2009."— Presentation transcript:

1 Multicore Programming Contest GPU Challenge 2009 ツールキット解説書 ver.1.0 対応版 GPU Challenge 2009 実行委員会 Cell Challenge 2009 併設企画 GPU Challenge 2009

2 これはなに？ GPU Challenge 2009 規定課題に取り組む際 のベースとなるツールキットの解説です Cell Challenge 2009 ツールキット解説書 (Cell Challenge 2009 実行委員会による ) を、許諾 を得て転載・一部改変したものです

3 規定課題 「文字列の編集距離計算」 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 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

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

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

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

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

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

9 ツールキット 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 を生成する

10 実行方法 (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

11 実行方法 (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 [CPU] : 19168 [GPU] : 19168 SUCCESSFUL. さまざまな練習問題を実行する， run1.sh ～ run9.sh が用意されています GPU を用いた計算時間 ２つの文字列の長さ GPU を用いた計算結果 ( 編集距離 )

12 実行方法 (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 [CPU] : 19168 [GPU] : 19168 SUCCESSFUL. 文字列長 GPU を用いた計算時間 ２つの文字列の長さ GPU を用いた計算結果 ( 編集距離 ) 巨大な文字列を対象にした場合，計 算時間が非常に長くなることがあり ます 「答え」を与えないと CPU で検算を行います 。 検算の時間は計算時間には含まれません 第一ファイル 第二ファイル 答え ( 省略可 )

13 規定課題への取り組み方 規定課題では， CPU プログラムおよび GPU のプログ ラム (device.cu) を実装する – 以下のプログラムを実装してください CUDA で記述された，編集距離を計算するプログラム (device.cu) device_user() 関数を実装してください．ツールキットの device_user() を基に改造を行うのは，もちろん ok です – 以下のファイルは変更が許可されません main 関数などを含むプログラム (main_host.cpp) – device.cu に加え，新たにプログラムファイル (*.c, *.cpp, *.cu, *.h など ) を追加することは ok それに応じて， Makefile を変更すること

14 参加者が実装する 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) 以下です 計算結果は返り値としてかえすこと

15 参加者が実装する device_user 関数について (2) 参加者のプログラムは 1 つの GPU のみを用いること． device_user 関数の中で cudaSetDevice 関数などを呼んでは いけない． – 委員会の準備する計算機には 2 つずつ GPU が搭載されていますが ，各チームはそのうちの 1 つだけを使うことになります ) 参加者のプログラムは CPU コアを高々 1 つだけ用いること ．ホストと GPU の間の通信や GPU カーネル関数の終了待 ちなどにも CPU コアが使われるので注意のこと．

16 メモリについて 参加者はホストメモリ (malloc などによる ) ， GPU 上の Global memory(cudaMalloc などによる ) を自由に利用でき ます – GPU 上の shared memory, texture memory なども ok メモリ容量に注意してください – ホスト : 32GB – GPU (Global memory): 4GB 特に， lenStr1 * lenStr2 のサイズの int 二次元配列は，最大 (2 の 34 乗 ) の場合にはホストにも GPU にも乗りません  ツールキットで行っているような，使用メモリ量を抑 える工夫が必要

17 プログラムの実行時の注意 複数の参加者が，計算機を紳士協定で共用しま す (2009/02/03 現在 ) – 各チーム ( 偶数・奇数 ) が許可されている方のマシンだ けにログイン可能です． – 一度のプログラム実行は， 10 分までとしてください ．また，一チームが連続して複数回プログラムを実 行することはできますが，長期間占有することは避 けてください． プログラムの実行前には， ps コマンドや top コマンド でマシン利用状況を確認することをおすすめします ．

18 ツールキット ver1.0 の計算手順 複数のスレッドブロックおよび，それぞれ複数スレ ッドを用いて並列に編集距離を計算するコードの例 並列化できる部分は，前述の「アルゴリズムの並列 化」を参照 – ( 表上で ) 斜めに並んだセルは並列化可能 – 効率化のため ( アクセスの coalescing) ，同時にアクセスす る部分がまとまるように表を作成

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

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

21 おわり