[B! cell] TAKESAKOのブックマーク

Hack the Cell - Hack the Cell

1/66 >> First Last Hack the Cell

TAKESAKO 2009/06/02

cell

リンク

bitsliceによる超高速ビット演算 : DSAS開発者の部屋

bitslice とは Hack the Cell '09 に参加して知った、Cellに限らず一般的に使えるビット演算の高速化手法について紹介します。 Bitslice と呼ばれる手法では、ビット順を90度回転します。言葉で説明するよりもコードを見たほうが早いので、回転させるコードの例を見てください int x[32], y[32]; // x が元のデータ、y が回転後のデータ. for (int i = 0; i < 32; ++i) { int t = 0; for (int j = 0; j < 32; ++j) t |= ((x[j] >> i) & 1) << j; // x[j] の i ビット目を y[i] = t; // y[i] の j ビット目にする } この変換をすることで、y[0] には x[0] - x[31] の最下位ビットが、 y[1] には 2番目のビット

TAKESAKO 2009/03/11

リンク

Hack the Cell '09 課題提出しました : 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,

TAKESAKO 2009/03/11

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

リンク

2009-03-10

普通に頭からビットを詰めていったら更新処理はこんな感じになります。 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]にまたがっていて、前者からの11

TAKESAKO 2009/03/11

>最初から0ビット目の隣に29ビット目、その隣に58ビット目、その隣に87ビット目……というように並べておけば、 1ビット回転しただけで29ビット回転したことになります。

リンク

はじめてのにき(2009-03-07)

_ TCO Algorithm Qualification Round 3 寝過ごした。予戦落ちとかウケますね忘れてた→酔っ払って寝てた→寝過ごしたとか僕の能力を全て出し切った感じである。その結果が予戦落ちなのだから、まぁ順当な結果なのだと思う。 (01:50) _ ぼくの村の話 http://www.fukkan.com/fk/VoteDetail?no=3761 復刊されたらしい。らしいっていうか知らせが来るってことはなんかの拍子でリクエストボタン押したんだろうなぁ。でも買わないと思うんだな。読むと成田使いたくなくなるけど、まぁなかなか使わないのも難しいよねというような。 (01:56)

TAKESAKO 2009/03/09

「hack the cell にかこつけて CPU の今後と最適化について僕に教える会」

リンク

2009-03-08

みんなそうだと思うけど、even命令が大幅に過剰になっちまった。しかも、僕のコードは1ワード1ロードシャッフル無しだから、それはもう多すぎて http://d.hatena.ne.jp/kikx/20090120 これはループのアンロール前で内側に14回のループが残ってたんだけど、こんなんで44倍だったからアンロールしてoddに移動できるのを順番に移動してったんですよ。 (y >> 1) ^ mag01[y & 1] y << 7 y << 15これらは上から、 even*1 + odd*3 odd*1 odd*2を全部やってもまだ余ってて、しかたがないから y >> 11の半分くらいをodd*3で置き換えて、69倍速になったのです。バイト単位じゃないともったいない。 z = si_lqx(spu_slqw(spu_gather(y), 4), mag_lut); r = spu_x

TAKESAKO 2009/03/09

「69倍になったあとは、一ヶ月ずっとビット転置のやり方を考えてました」→「これを元に実装すると、1ビットシフトは31回も必要なくて、最上位ビット1回だけになります」

リンク