DSAS開発者の部屋

Hack the Cell '09 に参戦していました。Fixstars社からの結果発表を待ってから成績報告をしようと思っていたのですが、他の参加者の皆さんがどんどんとスコアや素晴らしいテクニックを披露されているので、予定を前倒しして私のスコアとソースコードを公開します。（中身に関してはまた別の記事に書きます）

提出物とスコア

ソースコード (試行錯誤の跡が整理されていません)

スコア

ORIGNAL:         sum=3c927c56, 294030647 ticks
MINE:            sum=3c927c56, 4464381 ticks
ORIGNAL:         sum=2e987a4d, 424155603 ticks
MINE:            sum=2e987a4d, 6440068 ticks
ORIGNAL:         sum=ef1b6aef, 312102737 ticks
MINE:            sum=ef1b6aef, 4738888 ticks
ORIGNAL:         sum=eedd2516, 290055058 ticks
MINE:            sum=eedd2516, 4403913 ticks
ORIGNAL:         sum=f7e967a8, 14366822 ticks
MINE:            sum=f7e967a8, 218363 ticks
ORIGNAL:         sum=1f37a7db, 214216185 ticks
MINE:            sum=1f37a7db, 3252580 ticks
ORIGNAL:         sum=c7d41f36, 294964206 ticks
MINE:            sum=c7d41f36, 4478494 ticks
ORIGNAL:         sum=aa9d2e9f, 259565045 ticks
MINE:            sum=aa9d2e9f, 3941212 ticks
ORIGNAL:         sum=8abd398a, 250844221 ticks
MINE:            sum=8abd398a, 3808729 ticks
ORIGNAL:         sum=a374bd58, 6110290 ticks
MINE:            sum=a374bd58, 92978 ticks

倍率としては、約66倍といったところです。ただし、ORIGINALの速度が安定しない(プログラムのアライメントによって実行速度が変化する)ので、倍率は参考程度にとどめておいてください。

今回のコンテストの内容について

課題は、メルセンヌツイスターという乱数生成機の高速化でした。

最適化する対象となる関数はこちらです(一部省略)

#define N 624
#define M 397
#define MATRIX_A 0x9908b0dfUL   /* constant vector a */
#define UPPER_MASK 0x80000000UL /* most significant w-r bits */
#define LOWER_MASK 0x7fffffffUL /* least significant r bits */

static unsigned long mt[N]; /* the array for the state vector  */
static int mti=N+1; /* mti==N+1 means mt[N] is not initialized */

/* ... */

unsigned long genrand_int32(void)
{
    unsigned long y;
    static unsigned long mag01[2]={0x0UL, MATRIX_A};
    /* mag01[x] = x * MATRIX_A  for x=0,1 */

    if (mti >= N) { /* generate N words at one time */
        int kk;

        for (kk=0;kk<N-M;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
        }
        for (;kk<N-1;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
        }
        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];

        mti = 0;
    }

    y = mt[mti++];

    /* Tempering */
    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680UL;
    y ^= (y << 15) & 0xefc60000UL;
    y ^= (y >> 18);

    return y;
}

しかし、最適化したコードを実装する側のスケルトンとなる関数は次のような定義になっていました

unsigned int
genrand_mine(int num_rand)
{
  int r = 0;
  /* r = num_rand 個の乱数のチェックサム */
  return r;
}

この関数は戻り値として、 num_rand 個の生成された乱数のチェックサムを返す必要があります。

もともとの課題では、「※疑似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。」となっていたのですが、参加者によって以下のように異なった解釈がされていました。

• 同じ32bit整数としての乱数を求められている (私はこの解釈をしていました)
• 乱数のビット順がどうなっていても良い
• そもそも配布されているプログラムがチェックサムしか見ていないのだから、チェックサムだけ合ってれば何をしてもOK

この解釈の違いが問題になっていたのですが、最終的には現在課題のページにあるように、一番ゆるい「チェックサムが合っていれば何をしてもOK」というルールで優勝・準優勝を決め、きちんと乱数を生成していた人にはFixstars社の判断で「フィックススターズ賞」が送られることになりました。

結果として、今回のコンテストにおいて最適化の方針として3つが生まれました。

1. 元のコードをそのままSIMD化する

   基本は元のプログラムのまま、mt[] の要素を4つひとまとめに処理する。 その後、命令数を削減したりパイプラインを埋めて速度を稼いでいく。 この方法だと、60倍〜70倍程度までを目指せます。

   元の乱数生成器と同じ32bit整数で乱数を生成するので、フィックススターズ賞ねらいになります。

2. ビット順を90度入れ替えた bitsliece と呼ばれる構造で乱数を計算する

   SPUの128bitレジスタを、32bit整数4つとしてではなくて、1bitが128個あると考えて最適化していきます。命令の組み合わせだけでなくデータ構造をどうするのかにも工夫が必要になります。この方法で100倍を超えた参加者もおられるようです。

   この方法では乱数が32bit整数の形では出現しないので、優勝・準優勝ねらいになります。

3. 乱数を生成しないで直接チェックサムを計算する

   mt[] の値は 32bit整数を乱数の種として初期化されるので、種と num_rand と組み合わせた 64bitの情報から結果のチェックサム32bitを求めるということが究極的な目標になります。 極端な例を言えば 32bit * 2^64 分のテーブルを用意すれば、O(1) でチェックサムの計算ができる事になります。

   私には全く思いつかなかったのですが、 この計算をメモリ制約の中で O(n) 未満で実行する方法が存在するかもしれません。

私は2月は忙しくて全く高速化できなかったので、ルール確定前までに書いていた 1 の方法のプログラムのまま提出しました。 提出締め切り後、同じ1の方法でもあと5%以上高速化する方法が他の参加者のブログで紹介されていて悔しい思いをしています。 次回があればまた参加したいと思います。