ORIGNAL: sum=26842941, 20235458 ticks
MINE: sum=26842941, 296432 ticks
ORIGNAL: sum=ff298dc7, 29209150 ticks
MINE: sum=ff298dc7, 416484 ticks
ORIGNAL: sum=e41976b4, 21287451 ticks
MINE: sum=e41976b4, 359310 ticks
ORIGNAL: sum=1d20a3cf, 19895914 ticks
MINE: sum=1d20a3cf, 271577 ticks
ORIGNAL: sum=7ab6f153, 1012083 ticks
MINE: sum=7ab6f153, 80442 ticks
ORIGNAL: sum=d528faae, 14662211 ticks
MINE: sum=d528faae, 226395 ticks
ORIGNAL: sum=f2e9b16f, 20421921 ticks
MINE: sum=f2e9b16f, 285473 ticks
ORIGNAL: sum=c38c3ffb, 17745083 ticks
MINE: sum=c38c3ffb, 312869 ticks
ORIGNAL: sum=4a476dd4, 17155127 ticks
MINE: sum=4a476dd4, 268986 ticks
ORIGNAL: sum=817388cd, 412802 ticks
MINE: sum=817388cd, 60522 ticks

課題アナル(仮称)間違えていたよ orz

ところで、いつまでも仮称だとアナルが可愛そうなので、正式名称を
ハックtheアナルに決めたよ。ついでに処理系と実装も変えたけど。

$ diff mt19937ar.sep/mt19937ar.c~ mt19937ar.sep/mt19937ar.c
52c52
< #define MATRIX_A 0x9908b0dfUL /* constant vector a */
---
> #define MATRIX_A 0x9908b0cfUL /* constant vector a */

$ uname -mrsv
Linux 2.6.18-6-powerpc64 #1 SMP Fri Dec 12 23:54:31 UTC 2008 ppc64

$ cat /proc/cpuinfo
processor : 0
cpu : PPC970FX, altivec supported
clock : 2700.000000MHz
revision : 3.1 (pvr 003c 0301)

processor : 1
cpu : PPC970FX, altivec supported
clock : 2700.000000MHz
revision : 3.1 (pvr 003c 0301)

timebase : 33333333
platform : PowerMac
machine : PowerMac7,3
motherboard : PowerMac7,3 MacRISC4 Power Macintosh
detected as : 336 (PowerMac G5)
pmac flags : 00000000
L2 cache : 512K unified
pmac-generation : NewWorld

ですが、何か？

ちなみに、実装は C99 な。本当の意味でのな。altivec も使っていない。
32bit ビットスライスｗでこの程度。端数の処理はまったく最適化していない。

SIMD 化したらもっと早くなるかなぁ（棒

>>720
>突っ込みどころのデパート。詭弁の集大成。
で、
>>729
>だからTempering前の値をいくら「加算」しても無意味なんだ。
言いたいことはそれだけ？

>>579
>tempering 前の「とある値」を集計する。GF(2)の中で。
>すると、tempering (相当の操作)は一回で済む。
誰も tempering 前の値を「そのまま」加算するとは言っていないぜ？
加算するとも言っていない。首尾一貫してるだろ？

>>730
>彼は全然役に立たないことしか言ってない。
ｵﾏｴﾓﾅｰ

>>771
そんなに俺のアナル大きい？

>>781=202
俺？優勝する可能性？ないよ。出ないしｗ

>>801
おいORIGANALが本来のターゲットより一桁以上速いぞw
でも、多項式取り違えてたとはいえ、すげえ伸び率だね。

よくできた捏造だな
でもターゲットはＰｏｗｅｒPCじゃなくて「SPU」

よ、よく出来てるのか？ｗ

> 俺？優勝する可能性？ないよ。出ないしｗ
これを書くのはもうちょっとあとの方が面白かったかなｗ

>>805
たしかに>>732より、よくできてるのは間違いないな

ゲハ板で発狂してるアスペル君が勝手に勘違いしただけだろそれ

さすがに俺もそう思う。団子はウザイけど >>732 は無罪。

そうだったのか。団子ごめん

PPUとSPUが同じコードシーケンスで実行できるとかアホなこと言いやがんだもん
ＰＰＵに18issueの命令帯域が必要になるぞって言ったら、十分とかいいやがるし

しまいには、SSEがｘ86のフォーマットとはかけ離れてるとかｗｗｗ
あの命令フォーマットがｘ86でなくてなんなんだよ

大丈夫だよ。あのコピペで団子は間違ってないってみんな分かってるから。

団子が間違いを認めなくてウザい事もかなりあるがな。
あと接頭辞のように付いてくる「知り合いに誰々がいる」って下りもウザい。
知り合いが有名なだけで、別にスネ夫が偉いわけじゃないだろう。

「サマリだけ求めるショートサーキット禁止」
とか胴元が慌てて言い出したら爽快だな。
つか出題者があたまわるいってことになるが。

俺もそろそろトランザム（笑）発動しちゃおうかな
そろそろ勘のいい人は愚直な方法がいくらばかばかしいことに気づいてるかも知れない頃だし

>>814
関数抜ける前にMTの配列に書き戻しさえすれば等価な実装でもかまわないのでは？

ルールを根本変更されると正直悲しい。そしてキツい。
単なるチキンレースなら降りる。

課題見直しで延期とかになったら面白い。

MTの配列を毎回舐める必要がない前提ならトランザム（笑）可能なことは気づいてた。
それをやるとアルゴリズムが根本から変わるけど

コアループ抜けてからMT配列に書き戻せばちゃんと再実行も可能。

>>734の言うとおりになったな

俺もロジックジェネレータ改造したそろそろ走らせようかな
テキトーに当たり付けたパターンを再帰で全部試す馬鹿な方法使ってるから最適に近い方法見つけるのに1ヶ月くらいかかる。
俺の試算だと

ごめん、もうプログラムは書かないから、言わせてくれ。

>>816
そもそも、課題は乱数生成を最適化しろというもので、最初からどこまでサイクル数を
減らせるかというチキンレースなんだぞ？

>>579の方法はただのチートで、ルールが「チェックサム合ってれば乱数生成しなくても良い」
ってなったらそれこそ根本的なルール変更だ。

俺はHack the Cellに参加したんだ。単なる数学コンテストなら降りる。

様々な分野に対する知見が求められる、それだけのことじゃないか?

>>821
課題を100回読んでよ。　つhttp://cell.fixstars.com/challenge/challenge.html
どこに「乱数のチェックサムを計算してください」って書いてある？

「課題は、メルセンヌ・ツイスタの最適化です。」
「メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。」

しかしCellって本当に早い？使ったことないけど
フィクターのサイトにあるパフォーマス例と同じ処理をXeonで組んでみたら
10倍速いのできたんだが・・・

>>693だけど
なんか裏で本気出してる間にお通夜モードになっとる
とりあえず12.0まではきた
まだ0.3位は詰めれるかもしれない
で、大会中止とかルール変更とかなったらおれはどうすればいいんだ

>>820
おちつけ

> ルールが「チェックサム合ってれば乱数生成しなくても良い」

乱数なんて所詮擬似的なモノです。
mt[]の配列以外のワークメモリを別に確保して、その上で乱数生成もやる
それが認められるなら高速化はいくらでもやりようがある。

CUDAの1SMあたりのレジスタ本数は32ビット×8192＝32KB
配列の要素を全部レジスタに割り当てて計算し、あとでメモリ上のmt[]に書き戻した方が効率がいい。
mt[]の配列をレジスタに割り当てて計算したらMT互換ではないのか？決してそんなことではない。
レジスタに余裕があるアーキテクチャでは、最適化の過程でそんなことは自動でやってくれる
処理系も存在する。

【というわけで】
mt[]を舐めることさえやめれば、いくらかは高速化の余地があるよ。

たとえば、コアループの内側でmt[]のいくつかレジスタに割り当ててしまって、
全部レジスタ上でこね回すとすれば、128ビット×156本のレジスタが必要になり、SPUの128本本数では足りない。
そんなことをSPUで実際やれば56本固定で食っちまう。せいぜいロード・ストア回数が減るくらいしか実用性はないし
アンロールに使えるワークレジスタが実質的に減ってしまって逆に性能低下になりかねない。

そこでだ、レジスタを節約しつつ、スループットを稼げるように、データのレイアウトそのものを弄ってしまえばいいんじゃないかと。
ワークメモリはレジスタに割当て続ける必要はなく、LS上の空きにスワップしていい。
もちろん、これはさんすうやではなく、計算機屋としての理屈だ。


どこまでが王道でどこからが邪道なのか、無用な線引きを脳内で作ってしまっても「勝ち」はないわけで
とりあえず中の人に明確化してもらいたいところだ。
俺はgcc43って指定してあるのにアセンブラ使用可になった時点で最早ルールなんてないもんだと思ったが。

ごめん文が微妙に抜けてた

×そんなことをSPUで実際やれば56本固定で食っちまう。
○224要素くらいまでを割り当てるにしても、そんなことをSPUで実際やれば56本固定で食っちまう。

>>825
別に、mt[] をいじるなとは言ってないし、一部の計算をメモリ上じゃなくてレジスタ上で
やるのは俺もやってる。

だが、>>579はそもそもMT擬似乱数の生成自体全くやってないように思えた。
mt[]を変形してMT擬似乱数を生成しているだけなら俺の勘違いだ。噛み付いてスマン。

ネタばらししちゃうけど13切った奴はみんな部分的に8並列とか16並列とかやってるだろ？
spu_shuffle使ってパック・アンパックしてやってるだろ？
それがアリなら何でもアリだよ。

たとえばさ、32ビットの疑似乱数の上位16ビットと下位16ビットが別々のレジスタ上に分かれてたら、乱数じゃないの？
んで、上下が分かれた状態で別々に合計値の計算してもいいよね？

それが速いかどうかは別にして（っていうかcarryの計算が増える分速くない）

>>828
ごめん、それ気づかなかったわｗｗｗｗ

てか、コンテスト参加者でまだ13cycle切ってない、これから頑張る人も居るんだから、
ネタばらしは止めようぜ。

俺は、 >>598 や >>601 でいってるとおり、まじめに genrand_int32() の戻り値を
計算した上でチェックサムをとってる。

乱数を複数のレジスタに分割するのはどうなんだろうな？
たまたま場所が離れているだけで、ビット単位では元の乱数を生成しているんだし、
別にいい気もするが、、、グレーだな。

じゃあそのグレーな方法を使わせてもらうよ。

x86で64ビット整数をどうやって扱ってるか知ってる？
下位32ビットがeax、上位がedxだ。

整数を扱うのは2進でなくともたとえばBCDでもｲｲと思うわけ
浮動小数の仮数部で23ビットを表現してもいい。

なあに、genrand_int32()の形式で要素を抽出するAPIを別途用意すれば問題ない

とりあえずストール地獄からの脱出に成功。
明日も出勤だけど>>824目指して頑張る。

ところで、
for (int i = 0; i < num_rand; i+=2) {
sum += genrand_int32();
sum -= genrand_int32();
}
とかやってみたらチート対策になったりしないのかな？かな？

俺はチートはしないよ

init_genrand_mine を変更するなとは書いてあるけど、
init_genrand_mine で初期化されたベクタでテストするとは
書いてないわけだが。

トランザム＝通常の3倍の性能
あとはわかるな？

だんごいい加減ネタばれひどいだろ
13は切ってるけど、>>828の方法は使ってない
あんたが天才なのは結構だけど、コンテスト終わってからにしろよ

残念だがその方法には芽は無いようだ。
散々罵倒したけど彼には感謝しないといけない。

なあに、単純な理屈だったよ。

Hack the Cell と見せ掛けて Hack the spu-gcc43、
と思ったら Hack the MT だったでござる。

ツンデレ？

おう

このブレイクスルーは、ある意味でCellの特性を最大限生かしたものになる。
もちろんMTの互換性・再実行性も保障できる。

つまり、アセンブラなんて最初から必要なかったんだよ。

いや、それでも詰めるには必要だけど

実装するのと極めるのは別物だからな

いいや、最後にはSIMDerだからこそできるテクニックがものを言うと思うよ。

なんか色々台無しだね。>>321 の予想通りという事かね。

どのみち最速で無い（愚直にmt[]を舐めるだけ）の方法は近々俺の日記で公開してやろうと思っている。

Fixstarsはなんでmt[]をvec_uint4との共用体にしといてくれなかったのか？
実はそこに答えがあったのだ。

>>845
既に気付いてる人間からしたら、滅茶苦茶迷惑なんですけど。

おいおい
あんまりいらんことするな
12サイクルに到達してない人間の努力は全否定か
ついでに10倍速で参加賞出さなきゃいけないFixstersの身にもなれと

>>847
10倍到達した人が多い場合は上位からってルールがあったはず
どのみち優勝不可能なコードなんだから文句無いだろ？

俺がやらなきゃどうせ上位者（BSDライセンスでソース公開）はアセンブラばっかしのコードになるんだろ？
アセンブラのコードなんて公開されてもソースの再利用性という面では意味が無いんだよ。
高速化のテクニックを、アイディアを再利用性の高い形で世に出す必要がある。
俺は俺の信念で、アセンブラ許可したFixstarsをこき下ろす

アセンブラ無しなら自分が最速で、もっとも優れたテクニックやアイディアを持ってると思ってるあたりが痛いよな……

新しいコードだとTempering相当処理は0.5命令/Word切った。
別のところが増えちゃってるんですけどね。

言ったろ？トランザム発動するって。