規定課題

GPU Challenge 2009の規定課題は Cell Challengeと同様， 「文字列の編集距離計算」です．

GPU Challenge 2009実行委員会が用意する，NVIDIA社GPU(Tesla S1070-500) を搭載した計算機で，CUDAプログラミング環境を用いてプログラムを 作成していただきます．

※Cell Challenge 2009の課題webページの内容を引用・一部改変し 掲示させていただいておりますが，本ページについてのお問い合わせは GPU Challenge実行委員会あてにお願いいたします．

概要

2つの文字列の近さを計るために片方に次の操作を繰り返し適用して， もう一方の文字列を得るための操作回数の最小値が，その2つの文字列の 編集距離です。使用可能な操作は以下の3種類です。
  1. 削除：1つの文字を取り除く
  2. 挿入：1つの文字を新たに付け加える
  3. 置換：1つの文字を別の文字で置き換える
例えば「weight」と「write」の編集距離を考えるとき，次のように 操作を繰り返し適用すると，この2つの編集距離が 4以下 であることが分かります。 また，3回以下の操作の適用では「weight」を「write」にすることが 実はできないので，「weight」と「write」の編集距離は 4 になります。 削除，挿入，置換は文字列の中のどの位置で行ってもよいです。

予選課題詳細

具体的に解いていただくのは以下形式で出題される問題です．
ユーザの実装する関数
unsigned int device_user(char *str1, int lenStr1, char *str2, int lenStr2);
引数として与えられるポインタはすべてホスト(CPU)上のメモリを指すもので あるため， ホストとGPUの間のデータ転送(cudaMemcpyなど)は，device_user関数内 で行う必要があります．
文字列
1文字は1バイトで1〜255の値を持つ．(char)0が終端．
2つの文字列はstr1, str2の指す領域に保存される．
それぞれの長さはlenStr1, lenStr2．
文字列の長さは128の倍数．
文字列の最大長はそれぞれ1048448文字(1M-128)．
2つの文字列長の積(lenStr1*lenStr2)は最大で2の34乗(=17,179,869,184)．
編集距離
1回の挿入，削除，置換の編集距離はすべて1．
回答
2つの文字列の編集距離を，device_user関数の返り値として返すこと．
実行時間の測定
device_user関数の実行時間が測定され，順位決定に用いられます．

プログラム作成ルール