Hatena::ブログ(Diary)

菊やんの雑記帳

2009-03-19 優勝

[] Hack the Cell 01:02  Hack the Cell - 菊やんの雑記帳 を含むブックマーク

優勝しますた

部屋を片付けてテレビ置く場所を作ります。

2009-03-13 dddddmap

[] コード公開 02:47  コード公開 - 菊やんの雑記帳 を含むブックマーク

http://as305.dyndns.org/~kik/public/mt_mine.c

とりあえず置いてみた。実行環境がないんとasm化は大変だなあ。

2009-03-11 そろそろHack the Cellの思その6

[] 総和 00:59  総和 - 菊やんの雑記帳 を含むブックマーク

sum = 0;
for (i = 0; i < 16; i++) {
  s0 = cntb(y[i]);
  s1 = cntb(y[i+16]);
  s2 = sumb(s0, s1)
  sum += s2 << i;
}

以上。じゃなくて、ところどころシャッフルにしたけどね。

herumiさんと同じでまとめてやろうとすると、gccレジスタ割り当てに失敗して酷いことになるから、

あまりいじれなかった。

[] 結果 00:59  結果 - 菊やんの雑記帳 を含むブックマーク

ORIGNAL:         sum=3c927c56, 292970508 ticks
MINE:            sum=3c927c56, 2313630 ticks
ORIGNAL:         sum=2e987a4d, 422626291 ticks
MINE:            sum=2e987a4d, 3328071 ticks
ORIGNAL:         sum=ef1b6aef, 310977433 ticks
MINE:            sum=ef1b6aef, 2454426 ticks
ORIGNAL:         sum=eedd2516, 289009255 ticks
MINE:            sum=eedd2516, 2282352 ticks
ORIGNAL:         sum=f7e967a8, 14315023 ticks
MINE:            sum=f7e967a8, 130907 ticks
ORIGNAL:         sum=1f37a7db, 213443822 ticks
MINE:            sum=1f37a7db, 1690309 ticks
ORIGNAL:         sum=c7d41f36, 293900702 ticks
MINE:            sum=c7d41f36, 2320233 ticks
ORIGNAL:         sum=aa9d2e9f, 258629169 ticks
MINE:            sum=aa9d2e9f, 2044717 ticks
ORIGNAL:         sum=8abd398a, 249939792 ticks
MINE:            sum=8abd398a, 1975839 ticks
ORIGNAL:         sum=a374bd58, 6088262 ticks
MINE:            sum=a374bd58, 67124 ticks

126.6倍かな。ループの内側以外はまったく無視してたので、短い場合はひどいことになっとる。

そして、同じのをasmでやられたら圧倒的に負けるね。

[] 懇親会 01:04  懇親会 - 菊やんの雑記帳 を含むブックマーク

平日かー。行けるかなー。28日は行けるけど。

shinichiro_hshinichiro_h 2009/03/12 01:14 C で 126 倍ですか…どんだけ頭おかしいのかと。 asm にしたらどんくらいまでいくのかやってみたいですね。しかし PS3 が無い。

あと 28 日参加ということで良いでしょうか。

http://shinh.skr.jp/h/?HackTheCellPostMortem

2009-03-10 そろそろHack the Cellの思その5

[]更新処理 01:01 更新処理 - 菊やんの雑記帳 を含むブックマーク

普通に頭からビットを詰めていったら更新処理はこんな感じになります。

  for (; count != 0; count -= 1) {
<%= gen_update(0, 3, 4, 12, 12, "mask1") %>
<%= gen_update(1, 4, 0, 12, 29, "mask2") %>
<%= gen_update(2, 0, 1, 29, 29, "mask2") %>
<%= gen_update(3, 1, 2, 29, 29, "mask2") %>
<%= gen_update(4, 2, 3, 29, 29, "mask2", "mask3") %>
  }  

例えば mt_bs[i][0] を更新するときは 396から523番目の入ったqwordとXORしないといけません。

これらはmt_bs[i][3]とmt_bs[i][4]にまたがっていて、前者からの116ビットと後者から12ビットを

くっつけて128ビットを作らないといけません。

こういうときはrlqwとselbを使います。rlqwを使うと、回転した後の値を次の行の更新で使うことができます。

このインデックスと回転ビット数とselbのマスクを引数にしてコードを生成します。

回転ビット数とその回数を調べてみると、

ビット数回数一回当たりの命令数
151
12642
291282

となります。見れば分かるように一番多い29ビット回転に2命令かかるのは無駄です。

というわけで、29ビット回転を1命令でやります。

最初から0ビット目の隣に29ビット目、その隣に58ビット目、その隣に87ビット目……というように並べておけば、

1ビット回転しただけで29ビット回転したことになります。

これは29と128が互いに素だからできるわけで、128と互いに素な全ての数、ようするに128までの奇数に対して、

同じように並べ替えてみて、29ビット回転と12ビット回転がどのように変化していくか調べてみました。

結局、使えそうなのは29ごとに並べて

11229
新(左回転)75-41

になる場合と、99ごとに並べて

11229
新(左回転)-754-1

だけになりました。

上を採用すると、29ビット回転が1命令になりそのほかは2命令になります。

[] これは偶然 01:44  これは偶然 - 菊やんの雑記帳 を含むブックマーク

これは本当に偶然で、そうである必然性はないはずなのですが、

12 + 29 * 4 = 128

になります。この関係があるために、上の回転量は1と-4とか-1と4とかになります。

この関係をうまく使って、最初から適当にずらしておきます。

下のほうのビット並び替えを使ってmt_bsを初期化しているとして、

mt_bs2[i][0] = mt_bs[i][0];
mt_bs2[i][1] = mt_bs[i][1] rotl 1;
mt_bs2[i][2] = mt_bs[i][2] rotl 2;
mt_bs2[i][3] = mt_bs[i][3] rotl 3;
mt_bs2[i][4] = mt_bs[i][4] rotl 4;

こうずらしておきます。

各々は1ビットずつずれていて、4番目から0番目は4ビットずれているので、新しい回転量とぴったりあっています。

mt_bs[i][0]の更新にはmt_bs[i][3] rotl 4とmt_bs[i][4] rotl 4が必要だったので、

mt_bs2[i][0]の更新には mt_bs2[i][3] rotl 1とmt_bs2[i][4]を使います。

同様に

mt_bs2[i][1]にはmt_bs2[i][4] rotl 1とmt_bs2[i][0]を

mt_bs2[i][2]にはmt_bs2[i][0] rotl 1とmt_bs2[i][1]を

mt_bs2[i][3]にはmt_bs2[i][1] rotl 1とmt_bs2[i][2]を

mt_bs2[i][4]にはmt_bs2[i][2] rotl 1とmt_bs2[i][3]を

使って更新できます。なので、1ビット回転が5*32回になります。

だけど、面倒だからこれは実装せずに、29ビット回転を1ビット回転に変換まで実装しました。

2009-03-09 そろそろHack the Cellの思その4

[] ちょっとTemperingの話 01:10  ちょっとTemperingの話 - 菊やんの雑記帳 を含むブックマーク

本当は行列の計算を色々試してて気づいたんだけど

y = y >> 1;
y = y ^ (y >> 11);

y = y ^ (y >> 11);
y = y >> 1;

って、結果を見るとあまり差がないよね。

ほんの少し正確に書くと

word T1(word y) { return y ^ (y >> 11); }

って関数を考える。T1の逆関数をS1とする(簡単に作れるよね)。

こいつらは次の性質を持つ

T1(x ^ y) == T1(x) ^ T1(y)      (1)
T1(S1(x)) == S1(T1(x)) == x     (2)

まともな計算順序でやると

hi = mt[kk]&U;
lo = mt[kk+1]&L;
r = T1(mt[kk+M] ^ ((hi^lo) >> 1) ^ mag01[lo & 1]);

になるところを、(1)を駆使して

r = T1(mt[kk+M]) ^ T1(hi >> 1) ^ T1(lo >> 1) ^ T1(mag01[lo & 1]);

さっきの大体等しかったところを置き換えて

r ≒ T1(mt[kk+M]) ^ (T1(hi) >> 1) ^ (T1(lo) >> 1) ^ T1(mag01[S1(T1(lo)) & 1]);
hi = T1(mt[kk])&U;
lo = T1(mt[kk+1])&L;
r ≒ T1(mt[kk+M]) ^ ((hi^lo) >> 1) ^ T1(mag01[S1(lo) & 1]);

とかやってみると、mt[i]の代わりにT1(mt[i])を保存しといたほうがよさそうじゃん。

実際にはこんないい加減な議論じゃなくて、行列を掛けたり逆行列したりで真面目に計算して実装したんだけど、

上の計算で必要なXORが67から51に減ります。T1に必要な21回のXORが消滅して、調節用のXORが少し増えた結果です。