- 2009-02-27 (金) 16:02
- 大会/イベント
何を思ったかCell Challenge 2009に出ています．CellってPS3(PlayStation 3)に積んであるということぐらいしか知らない状況だったけど，先輩に言われ勢いで凸をした，という感じです．Cellは並列化ももちろん重要ですが，ベクトル化も重要なわけです．ベクトル化といえばSX-8でプログラムを書いた時はfor文が勝手にベクトル化されていてあまり実感がわきませんでした．その点，Cellは自分でベクトル化する分実感がわくというかなんというか，ある程度計画性を持ってプログラムを書いておかないとすぐに待ちが発生する点で苦労苦労．でも，これが実感をわかせてくれていると思うので醍醐味なわけです．まぁそんなこんなで初めての概念に色々戸惑いつつ，どうにか予選ラウンドに関しての提出はさきほどしてきました．バグが怖いけど，あとoxyさんが出るらしいのでそれも怖いけど，うまくいくと良いな！
進捗状況ですが，だいたい131072文字×131072文字の編集距離を1秒以内で求められるようになったので結構満足しています．手元のMacBook Pro (Core2 Duo 2.53GHz)で単純に組んだら(以下のコード参照)200秒近くかかるのでそれを考えると大進歩．だいたいこれは31クロック/セルなので無駄がかなりありますが，x86系はメモリの読み書きが非常に多いので仕方がない出来事なのではないかと予測．
002: #include <stdio.h>
003: #include <stdlib.h>
004: #include <algorithm>
005: using namespace std;
006:
007: char *str[2]; int len[2]; int *map[2];
008:
009: int main(int argc, char **argv) {
010: if (argc != 3) return printf("Usage: levenshtein file1 file2\n"), 0;
011: // 引数二つ分読み取り
012: for (int i = 0; i < 2; i++) {
013: // ファイルのオープン
014: FILE *fp = fopen(argv[i + 1], "r");
015: if (!fp) { perror(argv[i + 1]); return 0; }
016: // ファイルの長さの取得
017: fseek(fp, 0, SEEK_END); len[i] = ftell(fp); rewind(fp);
018: // 内容の読み取り
019: str[i] = (char *)malloc(len[i] + 1);
020: fread(str[i], 1, len[i] + 1, fp);
021: // ファイルのクローズ
022: fclose(fp);
023: }
024: // レーベンシュタイン距離を出力
025: printf("The length of the 1st string is %d.\n", len[0]);
026: printf("The length of the 2nd string is %d.\n", len[1]);
027: // 作業用配列の取得
028: map[0] = (int *)malloc((len[0] + 1) * sizeof(int));
029: map[1] = (int *)malloc((len[0] + 1) * sizeof(int));
030: // 初期状態(一番上の行)の設定
031: for (int x = 0; x <= len[0]; x++) map[0][x] = x;
032: // 探索処理
033: for (int y = 0; y < len[1]; y++) {
034: // 左端の値の設定
035: map[1][0] = y + 1;
036: // 次の状態を計算する
037: for (int x = 0; x < len[0]; x++) {
038: map[1][x + 1] = min(map[1][x] + 1, min(
039: map[0][x] + ((str[0][x] == str[1][y]) ? 0 : 1),
040: map[0][x + 1] + 1));
041: }
042: // 次の状態を現在の状態に入れ替える
043: swap(map[0], map[1]);
044: }
045: printf("The distance of Levenshtein is %d.\n", map[0][len[0]]);
046: // 終了
047: return 0;
048: }
なんというか，この大会を通じて将来のCPUの先が実感できたような気がします．将来もしかすると情報系の大会はオーダーが一段違っても実はSIMD化すれば勝てるとかあり得そう．でも逆にスペックがあがってNが大きくできるから問題はないとか？うーむ．
- Newer: TopCoder Open Round 1
- Older: TopCoder Open Qualification Round 1
Comments:1
- oxy 09-02-28 (土) 15:52
-
あら結構速いすね。>1秒以内
Trackbacks:0
- Trackback URL for this entry
- http://imoz.jp/2009/02/cell-challenge-2009-pre/trackback/
- Listed below are links to weblogs that reference
- Cell Challenge 2009 予選ラウンド from 超現実いもす(imos)の日記