トップ «前の日記(2009-03-21) 最新 次の日記(2009-03-25)» 編集

はじめてのにき

ここの位置付け

2004|11|
2005|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|07|08|09|10|11|12|
2020|01|02|03|04|05|06|07|08|09|10|11|12|
2021|01|02|03|04|05|06|07|08|09|10|11|12|
2022|01|02|03|04|05|06|07|

ToDo:


2009-03-22

_ わーぷ

普通に log(n) 回の行列計算でいけるかなーとか思ったら kik さんが書いてた上に諦めていた。

http://d.hatena.ne.jp/kikx/20090321#1237632002

でぱっと見 kodera さんのがそれ実際にやってる感じに見えるけど、 えーと違うのかな。

http://longlong.way-nifty.com/blog/2009/03/hack-the-cell-0.html

なんか違う気がした。

ああそうか、たぶん、分割数が 4 なら、

  • 0...624, 4*624...5*624, 8*624...9*624, ...
  • 624...2*624, 5*624...6*624, 9*624...10*624, ...
  • 2*624...3*624, 6*624...7*624, 10*624...11*624, ...
  • 3*624...4*624, 7*624...8*624, 11*624...12*624, ...

と担当すればいいって話か。 ただこれは mt の更新行列がそれなりに複雑になっちゃうだろうから、 log(n) べき乗ができるならそっちの方が良さそうだなぁ。

次元の3乗のオーダーを log(n) 回ってそんなに大きくないんじゃないかな… とか思ったけど、 20000次元**3 を 128 並列でできるので、 62ギガ単位の話。 積和命令とかあった気がするし 62G clock でいけるの? よーわからんけど悪くて 124G clock だろう。 8コア使うって前提の話なので、 15G clock か。 今回の mt_kadai のサンプルくらいだと現実的じゃないけど、 もっと激しく大きければ案外いけるくらい?

眠いので根本的に色々まちがっていそうだ。

(03:00)

_ あと

まあこの手のは基本的にはパズルでしかないので cell 自体の経験はあんま関係ないんじゃないかなぁ。

  • bitslice: 思いつき勝負
  • うまく命令数減らす: kikさんは天才
  • アセンブリ: __asm__ を書いたことがあるか、命令スケジューリングをある程度自動化する程度のプログラムを書けるか
  • spu-gcc とうまくつきあう: 基本的には try-and-error しか無い?

あたりがどっちかというとメインだった気がする。 even-odd の量をうまく散らすとかは重要だけど、 命令数たいして多くないから おおまかに把握するのにそんなに時間はかからないしなあ。 命令をうまく使って命令数減らすのも重要っちゃ重要だけど kik さん以外はたくさん減るのは見つけてない感じだよねたぶん。

一方 x86 とか経験がすごい生きそうだよなぁ。 herumi さんに勝てる気とか全然しない。

と書いてみて x86-64 でこいうコンテストとかも 割と面白いかもなーとか思った。 Core 2 Duo あたりで。 僕自信は勝負になる気がしないが。 誰かやらんかな。

(03:15)

_ こう

分割数が 8 として、 num_rand が 8*10**7 だとして、 800 程度進める行列を普通に(log(n)とか考えずに)作るのは たぶん 640000 回ループ回す程度のコストでできて、

  • 0...100, 800...900, 1600...1700, ...
  • 100...200, 900...1000, ...
  • 200...300, ...
  • ...
  • 700...800, ...

とかいう感じで分割すれば、 通常のループを 10**7 回と、 800 進める行列を 10**5 回かける時間で計算できるんじゃないかなぁ。 そしたら 10**7 回のループが律速な感じだから だいたい 8 倍になってる気がするなぁ、 とか思ったけど定かではない。

(03:30)

_ つか

これで8倍になるんだったら SIMD ったら shufb, selb, rotqw* あたりが消えたりするのかな。 というかそれが

http://pc11.2ch.net/test/read.cgi/tech/1232817361/581

が言っていたことか。やっとわかった。

shufb とかも減れば odd も減りそうだけど、どうなんかな。 だとすると SPU 1個でももっとフザけた倍率出たりするのかな?

(03:37)

_ メアド

http://d.hatena.ne.jp/firewood/20090322/1237659723

いいかげんな正規表現がそれなりに有効というのはとても同意… 元の正規表現で実用上一番問題なのはプラスが入ってないこと、かなぁ?

とかはいいとして、

http://blog.livedoor.jp/dankogai/archives/51189905.html

の From: Anonymous <nobody@example.com> を Perl の正規表現ならできる…っていうのは 実物がもしあるんなら見てみたいな。 自分では全然知らんけど、聞きかじった知識を元に考えると大変そうで、 結構とんでもないことになってそう。

(04:27)

お名前:
E-mail:
コメント:
人生、宇宙、すべての答え
本日のリンク元

2009年
3月
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
1.shinh(2014-05-24 10:42) 2.団子厨(2014-05-24 10:42) 3.shinh(2014-05-24 10:42)
search / home / index

全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。

shinichiro.hamaji _at_ gmail.com / shinichiro.h