cellプログラミングしちゃいなよ3

[表示 : 全て最新50 1-99 101- 201- 301- 401- 501- 601- 701- 801- 901- 1001- 2chのread.cgiへ]
Update time : 05/09 23:35 / Filesize : 266 KB / Number-of Response : 1002
[このスレッドの書き込みを削除する]
[＋板最近立ったスレ＆熱いスレ一覧 : ＋板最近立ったスレ／記者別一覧] [類似スレッド一覧]


↑キャッシュ検索、類似スレ動作を修正しました、ご迷惑をお掛けしました

cellプログラミングしちゃいなよ3

1 名前：デフォルトの名無しさん mailto:sage [2008/07/07(月) 08:55:08 ]: 前スレ

Cellプログラミングしちゃいなよ2
pc11.2ch.net/test/read.cgi/tech/1183091522/
331 名前：デフォルトの名無しさん mailto:sage [2009/01/11(日) 23:42:30 ]: あんまり具体的な話をするのは、１～２人で参加という趣旨に反すると
思うよ。
332 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/11(日) 23:54:01 ]: >>328
Cell SDKはx86のLinuxにも入れられるぞ
シミュレータもある。
333 名前：322,324 mailto:sage [2009/01/12(月) 00:47:51 ]: あー、呑んだ。酔っぱらった。酔ったまんま unroll にとりかかるぜw
>>325,326
おいら今 unroll してない状態で 16cycle だから、近いかなぁ、と。
>>330
18ってなに？ともあれ、なんとか even をあと一つ縮めたいよなぁ…
>>331
どうせおいら申し込んでないしー。ってか名前&社名出せねぇw
334 名前：202 mailto:sage [2009/01/12(月) 00:50:14 ]: >>330
あれ、だんごさんに言われると不安になってきた。
あとで数えなおし＆理論限界の計算しなおししてみる。
335 名前：322,324 mailto:sage [2009/01/12(月) 01:05:26 ]: >>334
ってか、even 15 切ってるのが居たら神な希ガス
>>322 に書いたけど、だんごさんも 15 は切ってないよ。
どれだけ論理限界(15)に近づけるかの勝負でしょ。
それか誰かが 15 を切るかw
336 名前：322,324 mailto:sage [2009/01/12(月) 01:07:46 ]: あ、>>301 の 5.47M は間違いだと思われ
337 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/12(月) 01:43:39 ]: パイプラインの空き35位まで詰められたけど、理論性能の95%しか出てない。
>>312が99.6%出してる時点で勝てそうにないorz
338 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/12(月) 01:47:40 ]: >>312は2日前の成果。日増しに（わずかながらではあるが）性能は伸びてる
339 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/12(月) 07:40:11 ]: 理論スループット15になる方法思いついたときは俺SUGEEEEEEEEEEって思ったけど
そこまでは案外みんな気づくの早かったな。
340 名前：202 mailto:sage [2009/01/12(月) 09:00:51 ]: >>335
even? odd じゃね？ tempering 的に言って。
>>339
てっきり15サイクル切ったと思ったけど、本気で15サイクルのコードで
そのスコアを超えたのか。すげーな。
341 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/12(月) 09:40:14 ]: おいおい逆だ
pc.watch.impress.co.jp/docs/2005/0212/kaigai03l.gif
342 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/12(月) 09:41:24 ]: ＞てっきり15サイクル切ったと思ったけど、本気で15サイクルのコードで
それは秘密。

ただ、部分的に式の変形はしてる。高速化のためにどうしても必要だった。
343 名前：202 mailto:sage [2009/01/12(月) 09:54:54 ]: >>341
おおおおおおおお！
俺、v = mt[k] とかに //e って、 spu_and() とかに //o ってコメント付けてた！
恥ずかしー！
344 名前：デフォルトの名無しさん [2009/01/12(月) 12:33:46 ]: ど素人ですけど、ＣＥＬＬに悪戦苦闘してる方々に質問。
ＣＥＬＬのメモリ構成の扱いにくさって、将来ＬＳの容量が増えて
各ＳＰＵが特定の仕事に専心するようになったら、それほど
大きな足かせにならない気がするんですけど、どうでしょうか？
今はＬＳの容量が少なすぎて、頻繁に書き換えが必要だから超面倒だけど。
クタはそこまで考えて、ＬＳにしたんじゃないんでしょうか？
345 名前：デフォルトの名無しさん mailto:sage [2009/01/12(月) 13:52:21 ]: なんか書き込みがゲハ臭いから回答すべきか「帰りな」と言うべきか迷うが。
クタだけに焦点を当てるなら、PS3を設計している最中に「LSが増えたら」が無いのは考えれば分かる話だよな?
346 名前：デフォルトの名無しさん mailto:sage [2009/01/12(月) 14:19:49 ]: ほんとゲハ臭いなw
>>344
ここで Hack the Cell やるような人は扱いにくいとか思ってないんじゃん？
扱いにくいってなるのは、プロジェクトが大きくなって C# あがりの
へたれプログラマも使わなきゃいけなくなった時じゃないかな？
Hack the Cell やるような職人にとっては LS の容量が少なくて超面倒って
事はなくて(ちょっと面倒くらいw)、へたれにとっては LS の容量が増えても、
ヘテロだったり cache じゃなかったりの時点で超面倒なんだと思われ。
今だったら Larrabee みたいな方がいいに決まってるっしょ。
347 名前：346 mailto:sage [2009/01/12(月) 14:23:56 ]: 今だったら => 今から作るんだったら
348 名前：デフォルトの名無しさん mailto:sage [2009/01/12(月) 16:55:22 ]: LarrabeeってCell扱うのはマンドクセッと思ってる
ヘタレ（と言うよりPCのCPUのみ扱い慣れている）
プログラマに取ってはいかにも扱いやすそうに見えるが
キャッシュレベルで勝手に同期が取られる事を良い事に
ついスレッドのあちこちで頻繁に同期を取るプログラムを
書いてしまってそれがキャッシュ用リング？バスの帯域を
圧迫してパフォーマンスが出ないと言う罠に陥りそうな希ガス。
349 名前：デフォルトの名無しさん mailto:sage [2009/01/12(月) 17:12:05 ]: いいからゲハに帰れよ
350 名前：デフォルトの名無しさん mailto:sage [2009/01/12(月) 17:14:32 ]: >>348
何言っているんだか。まるでx86だけがPCのCPUみたいな言い方しなさんな。
つーか、LarrabeeとCellを同列で語ること自体がどうかしている。
351 名前：348 mailto:sage [2009/01/12(月) 17:19:15 ]: >349
俺は残念ながら>344じゃないしゲハから来たわけでも無いよ。
352 名前：デフォルトの名無しさん mailto:348 [2009/01/12(月) 17:30:51 ]: >350
読解力無いね、アナタ。
353 名前：デフォルトの名無しさん mailto:sage [2009/01/12(月) 19:15:57 ]: しかし、今更ながら気づいたが現在、市場で売られている
PCのCPUはもはや、ほとんど全てx86なんだよな。

Apple(Macintosh)がIntel CPUの採用を始めてからは。

と言うかx86以外のPC用（と呼べる）CPUを思いつけない。
354 名前：デフォルトの名無しさん mailto:sage [2009/01/12(月) 20:50:56 ]: CBE
355 名前：250 mailto:sage [2009/01/13(火) 03:00:47 ]: ふー、目標の 6M 突破。と思ったらすごい事になってんなw　5.47M ってwww
こっから先は spu-gcc43 の最適化特性との根比べっぽいなぁ… orz
っていうか最適化馬鹿過ぎw 不要な処理し過ぎ!! フルアセで書かせろ!!!!w
356 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/13(火) 08:21:08 ]: >>355
いっそマシン語を配列に書いたら？ｗｗｗ
SPUは厳密な実行属性管理とかしないから自己書き換えとか簡単に動いたりするよ。
実際問題オーバーレイって自己書き換えと似たようなもんだし。

いや冗談ですｗｗｗ
357 名前：202 mailto:sage [2009/01/13(火) 12:50:07 ]: どうしても0.3命令くらいはオーバーヘッドが消えない。
15.3 * 100 /15 = 102 だから、2%がオーバーヘッドか。

コンパイラに99%以上の効率のコードを吐き出させるだんごさんは神。
358 名前：202 mailto:sage [2009/01/13(火) 13:17:14 ]: >>355
ちょっと待ってろ、fixstarsにインラインアセンブラ使って良いかどうか訊いてくる。
だんごさんに勝つにはもうそれしかない希ガス。
359 名前：250 mailto:sage [2009/01/13(火) 13:34:00 ]: >>358
おぉ！よろしく頼むっす！でもさすがにダメな気がするw
おいら今 1.66% のオーバーヘッドまできた。5.54M
でもなんか全然本質じゃない事ばっかでちょっと虚しい… orz
360 名前：デフォルトの名無しさん mailto:sage [2009/01/13(火) 13:45:11 ]: これからチュートリアル読み始めるんだけど、10倍くらいならいけるかな
361 名前：202 mailto:sage [2009/01/13(火) 16:11:14 ]: 5M台何人いるのか判らなくなってきたな。
5.6M切ってるのがこのスレに4人くらい居るのかな？
362 名前：202 mailto:sage [2009/01/13(火) 17:30:57 ]: >>322,324 さん、fixstars社員ですね、わかります。
363 名前：,,・´∀｀・,,）っ-○◎○ mailto:sage [2009/01/13(火) 17:52:24 ]: VISEO MDT243Wだったら2位も悪くないなと思ってるんだぜ。
ってか、42インチのテレビなんて使わねー
PCモニタとしてつかうにはでかすぎるし。
364 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/13(火) 21:17:18 ]: 15命令切る方法思いついたかも知れない
365 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/13(火) 21:27:21 ]: うはｗｗｗｗ
みなぎってきたｗｗｗｗｗｗｗｗｗｗ

とりあえず目標修正

　　　　　　　　　　　　　　　　5Mな！
366 名前：デフォルトの名無しさん mailto:sage [2009/01/13(火) 21:28:57 ]: と思いきや、それをやるには spu_and が必要だから減らないんだなー
367 名前：202 mailto:sage [2009/01/13(火) 21:29:45 ]: wwwwwwwwww

びびらせやがって！
368 名前：デフォルトの名無しさん mailto:sage [2009/01/13(火) 21:31:56 ]: いや、>>366 は適当に書いただけだってばｗ
369 名前：202 mailto:sage [2009/01/13(火) 21:32:43 ]: 試しにインラインアセンブラつかってみたんだけど、
asm("lqr $50, mt+16")
みたいにすると、コンパイラに怒られる。 mt+ って書式は使えない？
370 名前：202 mailto:sage [2009/01/13(火) 21:33:45 ]: ちょっｗｗｗ
だんごさんに追い抜かれる！
371 名前：202 mailto:sage [2009/01/13(火) 21:35:12 ]: インラインアセンブラ無しでどうやって5M超えようか
372 名前：デフォルトの名無しさん mailto:sage [2009/01/13(火) 21:35:43 ]: 202 さんは現段階で抜いてたの？
373 名前：202 mailto:sage [2009/01/13(火) 21:42:09 ]: たぶんね。15cycle は少し前に突破してる。 >>326
だれも気づいてないっぽかったから、その後は 15cycle前提で会話してた。

gcc43に行く手を阻まれて、理論値に全然近づけてないけど、>>316 の時点で
>>312 は抜いてた。
374 名前：デフォルトの名無しさん mailto:sage [2009/01/13(火) 21:57:26 ]: って事は、>>357 は本当は 14.3 ってこと？
375 名前：202 mailto:sage [2009/01/13(火) 22:00:39 ]: >>374
それ、実は、アセンブラを自動生成する簡単なプログラム書いて、
その出力したコード（未テスト）のサイクル数の話。15はウソ。

本当のオーバーヘッドは0.3どころじゃない。もっとデカイ。

んで、アセンブラ禁止された。
... 質問しなけりゃ良かったorz
376 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/13(火) 22:15:21 ]: というわけで俺だけ次のステップに逝く予感
377 名前：デフォルトの名無しさん mailto:sage [2009/01/13(火) 22:15:31 ]: アセンブラ禁止意味不明。最早 Hack The spu-gcc43 じゃん。
378 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/13(火) 22:17:56 ]: パイプラインを埋める方策考え直さないといけないな。
379 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/13(火) 22:19:54 ]: 方策は・・・あるんだなこれが。
380 名前：デフォルトの名無しさん mailto:sage [2009/01/13(火) 22:25:49 ]: >>377 うまいｗ　まさしくそのとおりだとおも
381 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/13(火) 22:25:50 ]: これは15cycleを切れないコードの最高スコアだ。もちろんアセンブラなど使ってない。

spu-gcc43 -std=gnu99 -O3 -g -c -o mt_mine.o mt_mine.c
spu-gcc43 -Wl,-Map,mt_kadai.map mt_kadai.o mt_mine.o mt19937ar.sep/mt19937ar.o -o mt_kadai
./mt_kadai
ORIGNAL: sum=3c927c56, 294035297 ticks
MINE: sum=3c927c56, 5466192 ticks
ORIGNAL: sum=2e987a4d, 424162315 ticks
MINE: sum=2e987a4d, 7885270 ticks
ORIGNAL: sum=ef1b6aef, 312107681 ticks
MINE: sum=ef1b6aef, 5802168 ticks
ORIGNAL: sum=eedd2516, 290059639 ticks
MINE: sum=eedd2516, 5392281 ticks
ORIGNAL: sum=f7e967a8, 14367047 ticks
MINE: sum=f7e967a8, 267131 ticks
ORIGNAL: sum=1f37a7db, 214219571 ticks
MINE: sum=1f37a7db, 3982409 ticks
ORIGNAL: sum=c7d41f36, 294968868 ticks
MINE: sum=c7d41f36, 5483545 ticks
ORIGNAL: sum=aa9d2e9f, 259569157 ticks
MINE: sum=aa9d2e9f, 4825469 ticks
ORIGNAL: sum=8abd398a, 250848188 ticks
MINE: sum=8abd398a, 4663339 ticks
ORIGNAL: sum=a374bd58, 6110381 ticks
MINE: sum=a374bd58, 113635 ticks
382 名前：202 mailto:sage [2009/01/13(火) 22:29:57 ]: 多分、もう、次のステップはない。

Hack the spu-gcc 4.3 '09

優勝争いのステージに、いま、俺とだんごさんが立っている。
このステージを制するのは、俺か、だんごさんか、はたまた新たなる
チャレンジャーか！！！
383 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/13(火) 22:33:16 ]: 我ながら恐ろしい。15clk/QWORDに対する実効効率99.74％の基地外スケジューリング
俺に勝てるかなククク
384 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/13(火) 22:43:37 ]: ヒント：最適化が糞なら、無効にすればいいじゃない
385 名前：デフォルトの名無しさん mailto:sage [2009/01/13(火) 23:46:28 ]: 今更？
386 名前：デフォルトの名無しさん mailto:sage [2009/01/13(火) 23:58:15 ]: この課題説明でインラインアセンブラ禁止なら、
pragma も使用禁止でしょうな。
387 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 00:03:42 ]: それって、なんてコンパイラハッキングゲーム?w
388 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/14(水) 00:41:47 ]: わっちもようやく>>282のスタートラインに立てたので一応報告。

ちなみに、何故かコンパイラの最適化無効にしたらコードの質が良くなってるし、
コンパイラとの戦いの意味合いの方が強いような気がするなぁ…。
389 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/14(水) 01:01:21 ]: ハッキングなどしてない

spu-gcc43 -std=gnu99 -O3 -g -c -o mt_mine.o mt_mine.c
spu-gcc43 -Wl,-Map,mt_kadai.map mt_kadai.o mt_mine.o mt19937ar.sep/mt19937ar.o -o mt_kadai
./mt_kadai
ORIGNAL: sum=3c927c56, 295486875 ticks
MINE: sum=3c927c56, 5093390 ticks
ORIGNAL: sum=2e987a4d, 426256300 ticks
MINE: sum=2e987a4d, 7347483 ticks
ORIGNAL: sum=ef1b6aef, 313648483 ticks
MINE: sum=ef1b6aef, 5406455 ticks
ORIGNAL: sum=eedd2516, 291491590 ticks
MINE: sum=eedd2516, 5024518 ticks
ORIGNAL: sum=f7e967a8, 14437972 ticks
MINE: sum=f7e967a8, 248913 ticks
ORIGNAL: sum=1f37a7db, 215277119 ticks
MINE: sum=1f37a7db, 3710802 ticks
ORIGNAL: sum=c7d41f36, 296425055 ticks
MINE: sum=c7d41f36, 5109559 ticks
ORIGNAL: sum=aa9d2e9f, 260850588 ticks
MINE: sum=aa9d2e9f, 4496367 ticks
ORIGNAL: sum=8abd398a, 252086563 ticks
MINE: sum=8abd398a, 4345293 ticks
ORIGNAL: sum=a374bd58, 6140545 ticks
MINE: sum=a374bd58, 105884 ticks
390 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/14(水) 01:02:58 ]: やべぇｗｗｗ笑いがとまんねーｗｗｗｗｗ
391 名前：202 mailto:sage [2009/01/14(水) 01:17:46 ]: 抜かれた・・・完敗だorz
392 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/14(水) 01:19:03 ]: ん？まだもう一段階いけたよ
393 名前：202 mailto:sage [2009/01/14(水) 01:23:53 ]: 5M切れそう？
394 名前：202 mailto:sage [2009/01/14(水) 01:25:36 ]: ちがうか、5088682 が下限なんだな。
395 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 01:34:03 ]: >>389
逆汗しないから、その実行ファイルうpして？
396 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/14(水) 01:34:04 ]: ﾆﾔﾆﾔ
397 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/14(水) 01:35:32 ]: >>395
優勝すれば公開されるんだからそのときに見ればいいじゃないか。
種も仕掛けもない
398 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/14(水) 02:09:28 ]: >>389
さっき98%超えたけどさすがにそれは神の領域だわ。
399 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 02:14:08 ]: ttp://cell.fixstars.com/ps3linux/index.php/3.8%E3%80%80%E6%BC%94%E7%BF%92%E5%95%8F%E9%A1%8C_(3-3)_%E5%8C%BA%E5%88%86%E6%B1%82%E7%A9%8D%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0_(%E8%A7%A3%E7%AD%94)
400 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 02:17:55 ]: 途中で投稿してもうた・・・
cell.fixstars.com/ps3linux/index.php/
ここにあるプログラミングチュートリアルの演習３－３の回答で、SPEの個数を変えたいんですが
#define NUM_SPE * の*だけ変えてもだめですよね・・・
性能がどんなもんかみたいんですが…どの点を変更すればよいのかご教授いただけませんでしょうか
401 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/14(水) 02:20:52 ]: 2のべき乗ならいいんじゃないの？
テキトーに言ってみるけど。
402 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 09:07:02 ]: >>400
そこだけでいいと思うけど・・・
PS3なら個数は1~6までSPEが利用できる
403 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 12:06:10 ]: >>389
SFMTより速いんじゃね？
404 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 12:42:54 ]: >>401-402
ありがとうございます。
変更箇所はこちらであっているみたいですね
タイム関数を利用して処理時間を測定しても、逆にSPEを利用したほうが時間が延びてしまいます。
理論上ではSPE１からSPE4にしたら1/4になるはずですよね？
ppeのメイン関数にあるresultをかこって測定しているのですが適切ではないのかな
すみません、出力に要した時間を測定するにはどこが適切なのでしょう
cell.fixstars.com/pukiwiki/index.php?tips_timebase タイム関数はこれを使用しています
405 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 13:21:25 ]: >>404
そもそもこの問題ってそんな大規模な数を計算してないから
下手にSPE増やすとデータ転送時間やらその他もろもろが増えて
逆に遅くなる可能性のほうが高いよ
406 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 14:42:22 ]: そうですか…わかりました。測定するプログラム自体が間違いだったんですかｗ
性能を見るために適したプログラム・・・どっかありますかね？
探してみます。
407 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 16:03:39 ]: 質問です。
ＣＥＬＬとLarrabee ってどの程度性能差があるんですか？
大して性能差がないとしたら、仮にＰＳ４が出るとして、
ソニーがＣＥＬＬに拘る意味って、もはや無いのでは？
むしろＰＣの世界で主流になるであろう、Larrabeeに
切り替えた方がコスト的にも有利なのでは？
408 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 16:50:01 ]: ゲハ板にお帰りください。
409 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/14(水) 17:16:08 ]: >>403
逆説的だけど、並列演算を前提にした場合、実はオリジナルのMTのほうが並列度の高い
（高くしないと性能の出ない）アーキテクチャに向いてるってのはある。

MTの配列のうち、先頭から224個、残りの400個は並列演算可能だ。
これはCUDAの実装についての説明。
ソースはCUDA SDKのサンプルにも入ってる。
developer.download.nvidia.com/compute/cuda/sdk/website/projects/MersenneTwister/doc/MersenneTwister.pdf

それに対して、対してSFMTは4要素（＝128ビット）の計算をしないとその次の4要素の計算ができない。
要するに依存関係があって、128ビット性能が出ない。
各命令のレイテンシが大きいとSFMTは相対的に不向きってことになるかもね。
410 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/14(水) 17:18:53 ]: × 要するに依存関係があって、128ビット性能が出ない。
× 要するに依存関係があって、128ビットSIMD演算を低レイテンシで実行できるアーキでないとが出ない。
411 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 17:38:23 ]: つっこみたいんだが
412 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/14(水) 17:44:30 ]: どうぞ

今回の課題のMTはSFMTと比べてレイテンシを埋めるためのテクニックが使いやすいのは事実だよ。
っていうか誰かCUDAにSFMT移植してごらん？4論理スレッドしか並列実行できない悲惨なことになる。
413 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 17:45:45 ]: いや、どっちも×なところになんだがｗ
414 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/14(水) 17:48:20 ]: ○ 要するに依存関係があって、128ビットSIMD演算を低レイテンシで実行できるアーキでないと性能が出ない。

タイピングしすぎで腱鞘炎になりそう
415 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 18:36:35 ]: >407
Larrabeeはまだ世の中に出ていないので誰にも分かりません。
性能比較は用途によって変わるので今、Cellが使われている用途に
そのままLarrabeeが使われたらどうなるかなんて仮定の話は
Intelの中の人ですら分からないでしょう。

またPC用のCPUの世界でLarrabeeのような
シンプルなコアをたくさん集積したメニーコアが
すぐに流行る事も無いでしょう。

流行るとしてもだいぶ先の話（10年先か20年先か？）
416 名前：デフォルトの名無しさん mailto:sage [2009/01/14(水) 20:19:04 ]: >>409
速さもランダム性も優れているなんて虫が良すぎるんじゃないかとは思っていたんだ。
ふつーなら、どっちかのはずだもんな。元がひどくない限りは。
417 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/14(水) 22:15:12 ]: 99%超えたおー
418 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 10:44:32 ]: cell.fixstars.com/challenge/faq.html#kadai4
> インラインアセンブラは使用してもよいですか？
> インラインアセンブラは禁止としていましたが、使用していただいて構いません。(1/15 更新)
419 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 10:46:52 ]: 中の人このスレ見てるな。
420 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 11:23:12 ]: なんか、いきなり競争のルールが変わってしまったな。
421 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 11:33:29 ]: いちいちルールなんて再確認しないだろうから、このスレ見てない人が可哀想だよな。
422 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 11:38:36 ]: 迷走してるな。
アセンブラレベルでCellを熟知してない人間にはチャンスを与えない試験に成り果てた。
コンパイルオプション変更許可しない意味が既に無い。
423 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 11:58:29 ]: >アセンブラレベルでCellを熟知してない人間にはチャンスを与えない試験に成り果てた。
そのレベルの人には元々「勝つ」チャンスは無いと思います。
参加する事に意義がある。
424 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 12:05:30 ]: アセンブラ許可自体は歓迎だが、こんなことをやると

「受賞者は最初から決めてあったんだよ！」

と言われかねない。
425 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 12:11:38 ]: >>アセンブラレベルでCellを熟知してない人間にはチャンスを与えない試験に成り果てた。
>そのレベルの人には元々「勝つ」チャンスは無いと思います。

202がんがれ、超がんがれ
426 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 12:18:14 ]: >>425
いやいや、202は既に熟知「した」だろ。
427 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 12:19:00 ]: うーん、確かにコンテストを始めてからルールを変えるのはなんだかな。
再提出のチャンスがあるとは言えど。

主催者はルールが変わった事をメールなどで周知徹底すべきだろう。
428 名前：202 mailto:sage [2009/01/15(木) 12:25:20 ]: ちょ、許可になったのかよ！！

アセンブラを生成するスクリプトをCソース吐くように改変して、
どうやって最適化昨日によるデチューンから逃れるか試行錯誤してたのに！
#pragma GCC optimize ("-O0") も、 __attribute__ ((optimize(0))) も使えない、
変数をvolatileにしたらスタックにpush/popするから超遅い、etcetc、、、

俺の2日間かえせーー！
429 名前：250 mailto:sage [2009/01/15(木) 12:45:16 ]: まぁ、でも本当に Hack the spu-gcc43 になってたからな…
おいらも 4.1 だとうまくいった最適化抑制手法が、4.3 だと
使えなかったりして結構虚しくなってたからよかったかも。
430 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/15(木) 12:48:42 ]: 敢えて言う。
今までのは全部Cだ。
431 名前：250 mailto:sage [2009/01/15(木) 12:53:01 ]: あ、コンテスト終わったらでいいから、だんごさんがどうやって
最適化抑制してたのか教えてほしいかも。おいらがやってたのは
4.3 にしたら even にまで命令追加されて使えなかったっす。
432 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 12:54:18 ]: どうせ、そこまでやるんならコンパイラオプションも変更可能にして
何でもアリアリの条件で競争させて欲しい。
433 名前：202 mailto:sage [2009/01/15(木) 12:57:42 ]: >>432
インラインアセンブラ解禁=何でもアリだよ。
別のコンパイラで、別のコンパイルオプションでアセンブリソース吐かせて、
それをインラインアセンブラで埋め込めば良いんだから。
434 名前：250 mailto:sage [2009/01/15(木) 12:58:21 ]: >>431
あ、even に追加されたのは、ori $n,$n,0 ね。
even に追加することねーだろ、って叫びたいｗ
435 名前：202 mailto:sage [2009/01/15(木) 12:58:23 ]: あ、ごめん。
実質なんでもアリなら、本当に何でもアリにしてくれっていう意味ね。
436 名前：202 mailto:sage [2009/01/15(木) 12:59:15 ]: >>434
ありすぎて困るｗｗｗ
ソース破壊しない命令ばっかだから、絶対いらないのにねー。
437 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 13:00:04 ]: >433
うん、だからもはや意味の無い形式だけのコンパイルオプションを
いじるなと言う制約を外した方が分かりやすいだろ？
438 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 13:19:20 ]: やるなら mt_mine.c だけオプション分離しないと、
オリジナルの速度とかテストベンチにまで影響が…
439 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/15(木) 18:47:17 ]: SPUのアセンブリ言語はちょっとだけ読めるけどあれだけのコードをまともに書ける気がしない。
うまく飼いならせばspu-gcc43こそ最強の高級アセンブラ
440 名前：250 mailto:sage [2009/01/15(木) 19:30:29 ]: 未だに 4.3 は飼いならし方がわからんす。attribute とかじゃないんすよね？
441 名前：250 mailto:sage [2009/01/15(木) 19:47:31 ]: って、コンテスト前なんだから聞いてる場合じゃないかｗ
おいらは asm 行くけど、やり方が気になって気になって。
ちなみに 4.1 なら >>383 の率超えました!! 意味ないけどｗ
442 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/15(木) 20:54:44 ]: >>441
>>383は超えたところで意味が無い数字だぞ。
実は>>389もだけど
443 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 20:59:19 ]: なんでそういうの黙ってられないんだろう。
444 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 21:07:59 ]: 俺SUGEEEEEEEEEE だからじゃん？ｗ
445 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 21:12:55 ]: せめて締め切られてからにしたらどうかね。
446 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 21:33:05 ]: 締切後フカシだった事がばれて「俺参加してねーし」とか言いそうな感じ
447 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 21:37:21 ]: ここらで擁護がきそうな感じ
448 名前：デフォルトの名無しさん mailto:sage [2009/01/15(木) 23:48:57 ]: いやいい加減うざいと思ってただろみんな
449 名前：202 mailto:sage [2009/01/15(木) 23:53:34 ]: Cellプログラミングに関係してるだけマシだと思ってたんだけど、
ウザかった？
他になんか話題ある？
450 名前：デフォルトの名無しさん mailto:sage [2009/01/16(金) 00:34:34 ]: 糞団子に餌を与えるのはいかがなものか。もそもそ。
451 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/16(金) 03:09:49 ]: >>446
それならそれでソースコード公開できるんだけどね。

行動とは裏腹に誰にも気づかれることもなく優勝するシナリオを望んでる。
矛盾してるな。
452 名前：202 mailto:sage [2009/01/16(金) 03:28:27 ]: インラインアセンブラ版動いた。
効率はこれから詰めていくけど、とりあえず適当な詰め方でも98%行く。
デバッグが超面倒だった。

これからインラインアセンブラに手を出す人にヒント。
.balign 16
というディレクティブを使って、命令のアドレスを16byte境界にalignしないと、
Dual-issue ねらってた命令が全部single-issue になってしまう。
めっちゃ遅くなって、間違ってループカウンタ壊したかと思った。
453 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/16(金) 21:47:01 ]: 今週末は２日間とも強引に休む事にしたんで、インラインアセンブラにでも
手を付けてみます（ちなみにVCの奴は経験有るけど、GCCの奴は初）。

98%超えが４人いる事が判明しているので、まだまだチキンレース続けますよｗ

>>428
インラインアセンブラ解禁されたので、既に意味無くなった情報でも投下。

volatileによる制約は、メモリアクセスの順番を守る制約でも有ります。
組み込みプログラミングでメモリ空間が外部バスにマッピングされてると、
アクセス順番が狂う＝バグ、という死活問題に繋がってくる訳です。

>>439
gcc のコードを並び替えるだけで終わりような予感。
454 名前：202 mailto:sage [2009/01/16(金) 21:55:23 ]: >>453
俺だって元組み込み屋だ。volatileの意味くらい知ってる。

でも、ひょっとしたら、register volatile vector unsigned va; とか書いたら、vaが適当な
レジスタに固定でマッピングされてくれないかなと思って実験してみたくなるのは判るだろ。
455 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/16(金) 22:16:02 ]: >>454
その道のプロの方でしたか。これは失礼いたしました。

> vaが適当なレジスタに固定でマッピングされてくれないかな
幾らハッキングが好きなゲーム屋だからと言って、割り込みから
メインスレッドのレジスタ葬るような事はやったこと無いなぁ…。
456 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/16(金) 22:49:32 ]: SPUのABI仕様書読んでみると面白いね。
vector型をメンバに持つ構造体も、レジスタ本数に余裕がある限りレジスタ上に展開できる。
これによって複数の返値を持つことができる。

SSE(VC++)だと構造体を返値にすると無条件でスタック返しになってたような。
457 名前：デフォルトの名無しさん mailto:sage [2009/01/17(土) 02:14:37 ]: 高速化がこんなに楽しいものだとは知らなかった。
どんどん速くなっていくのは快感だね。
458 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/17(土) 02:31:13 ]: なんか手詰まりの予感orz

mt_mine.c:93: internal compiler error: Segmentation fault
Please submit a full bug report,
with preprocessed source if appropriate.
See <gcc.gnu.org/bugs.html> for instructions.
make: *** [mt_mine.o] Error 1
459 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/17(土) 03:57:00 ]: 拡張アセンブラが腐ってたっぽい感じです。レジスタの待避まで手動でやれば
大丈夫になるのかなぁ…？
460 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/17(土) 14:30:48 ]: まさにチキンレースだな。
究極的には両方のパイプを埋めきるまでやるんだろこれ。
461 名前：sage [2009/01/17(土) 14:58:35 ]: 団子さんは今どんなスコアですか？
今までの勢いだと4.5M切ってたりして…
462 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/17(土) 15:40:52 ]: そろそろ詰んだかも
463 名前：デフォルトの名無しさん mailto:sage [2009/01/17(土) 16:17:21 ]: 今まで仕事でHTCできなかったから今から本気出す
ASM禁止→解禁のごたごたの間に手を出さなかったのは逆に勝ち組なんじゃね
464 名前：デフォルトの名無しさん mailto:sage [2009/01/17(土) 16:27:20 ]: >>202 >>227>>団子厨
が優勝争ってるんでしょ～～
結局だれがいちばん強いわけ？
どれくらいとればこの人たちに勝てるかおしえて
465 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/17(土) 16:31:54 ]: たぶん一番上の項目で5Mくらい出せれば準優勝狙えると思うよ
優勝は無理だろうけどね。
466 名前：464 mailto:sage [2009/01/17(土) 16:40:34 ]: >>465
SUGEEEEEEEEEE自信だけど自分はどれくらいまで行けそうなの？
もし準優勝すらできなかったら何してくれんの？

まぁおれは7M切るので精一杯だから関係ないけど。。。
467 名前：202 mailto:sage [2009/01/17(土) 18:21:39 ]: >>465
つまり、だんごさんは5M切ったとｗ
468 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/17(土) 19:19:57 ]: さあそれはどうだか
少なくとも細かいチューンでの対決に持ち込めば勝てる自信がある・・・かもしれないね
469 名前：デフォルトの名無しさん mailto:sage [2009/01/17(土) 20:54:41 ]: 60倍越えたんですね。わかります。
470 名前：464 mailto:sage [2009/01/17(土) 21:46:34 ]: だんごさんの優勝はもう決定事項なのか。。。
471 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/18(日) 00:43:53 ]: インラインアセンブラを駆使しても>>389に勝てないという現実orz
今日一日アセンブラ触ってみて、gcc43の凄さを感じ取れました。
472 名前：202 mailto:sage [2009/01/18(日) 00:57:32 ]: アイデア出すたびにガンガン速くなってた時期と違って、5M近くにたどり着くと
苦行になってきたな。
1%未満の調整は投げ出して提出する時期かも。

下馬評では、1位だんごさんで、2位は俺と>>227の対決か。
チキンなので俺のticks数は書けない。
473 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/18(日) 01:13:21 ]: >>472
インラインアセンブラ使用前で5119021。
474 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 04:12:17 ]: 好きに使っていいレジスタって何番～何番だっけ
なんかコンパイラが予約してるとことかあった気がするんだけどどの資料を見たのか忘れてしまった
475 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 05:59:54 ]: >>474
ttp://cell.scei.co.jp/j_download.html
「SPU Application Binary Interface Specification」の「2.2.1 レジスタ」(日本語だと P8) の表
476 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 06:08:38 ]: >>475
ありがと
普通にR80～を使ってた
なんか普通に動いてるけどたまたまなのかコンパイラが退避してくれてるのか…
できるだけR10～79位を使う様にするかな
477 名前：202 mailto:sage [2009/01/18(日) 10:56:45 ]: >>476
拡張インラインアセンブリ構文を勉強すると良いよ。
コンパイラにどのレジスタ使うか教えると、変数割り当てがかぶらないように
してくれたり、必要ならレジスタ退避もやってくれる。
478 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 12:15:37 ]: 敢えて言う。
俺には無理。
479 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/18(日) 18:13:28 ]: nop/lnop を入れると早くなる謎。レジスタの依存関係は無さそうやし、
LSの帯域制限とかいう隠れ仕様でも有るのかなぁ…。
480 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 18:39:43 ]: 隠れ仕様なんかじゃないよ。もっと勉強しましょう。
481 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 19:01:48 ]: これ以上性能伸ばすにはOddパイプの命令数削減する方法を本気で考えないといけなくなった。
＃トップを目指してる人はどういう状況かわかるよな？
482 名前：202 mailto:sage [2009/01/18(日) 19:27:18 ]: >>481
ｗｗｗｗ
483 名前：202 mailto:sage [2009/01/18(日) 19:28:25 ]: >>479
dual-issueとかじゃなく？
484 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 19:29:49 ]: 策はある。足りないのはメモリ。
485 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/18(日) 19:49:31 ]: >>483
ちょっと違うっぽい。nop+lnopを入れると１クロックのロスで済むものの、
何も入れないと２クロックストールしてるような感じです。

>>481
今のところ Odd 余ってるんやけどなぁ…。まさか限界突破したとかorz
486 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 19:51:25 ]: ループ後半のどうでもいいようなところしか余ってない。
無理になんか処理入れたら逆に性能低下するし、そろそろ別の方針が必要っぽい

＃意地でもCでがんばるぞ
487 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 20:04:38 ]: >>485
ヒント欲しい？w
488 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 20:12:08 ]: 今なら言うけど、>>394は限界ではない

ラチェクラとか作った会社がまとめたSPU命令のレイテンシ一覧あったんで貼っておきますね。
なんでこういうわかりやすい資料が公式に無いのか疑問。

www.insomniacgames.com/tech/articles/0907/spu_instruction_cheat_sheet.php
489 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 20:15:02 ]: まーた、フカシが始まったよ… なんで黙ってられないんだろう。
490 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 20:24:07 ]: 別に信じなくてもいいが、現実を受け入れなきゃ優勝が無い、それだけの話だ。

↓これはまだパイプラインに余裕があったときのスコア。

spu-gcc43 -std=gnu99 -O3 -g -c -o mt_mine.o mt_mine.c
spu-gcc43 -Wl,-Map,mt_kadai.map mt_kadai.o mt_mine.o mt19937ar.sep/mt19937ar.o -o mt_kadai
./mt_kadai
ORIGNAL: sum=3c927c56, 294032967 ticks
MINE: sum=3c927c56, 4967580 ticks
ORIGNAL: sum=2e987a4d, 424158953 ticks
MINE: sum=2e987a4d, 7165990 ticks
ORIGNAL: sum=ef1b6aef, 312105208 ticks
MINE: sum=ef1b6aef, 5272912 ticks
ORIGNAL: sum=eedd2516, 290057341 ticks
MINE: sum=eedd2516, 4900408 ticks
ORIGNAL: sum=f7e967a8, 14366933 ticks
MINE: sum=f7e967a8, 242775 ticks
ORIGNAL: sum=1f37a7db, 214217873 ticks
MINE: sum=1f37a7db, 3619145 ticks
ORIGNAL: sum=c7d41f36, 294966530 ticks
MINE: sum=c7d41f36, 4983349 ticks
ORIGNAL: sum=aa9d2e9f, 259567100 ticks
MINE: sum=aa9d2e9f, 4385307 ticks
ORIGNAL: sum=8abd398a, 250846200 ticks
MINE: sum=8abd398a, 4237963 ticks
ORIGNAL: sum=a374bd58, 6110333 ticks
MINE: sum=a374bd58, 103279 ticks
491 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 20:30:40 ]: こんなとこに情報出しまくる奴にも優勝はないと思うw
492 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 20:32:00 ]: だろうね。用心深いから常に古い情報ばっかし出してる。
493 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 20:32:48 ]: それで大丈夫と思ってる井の中の蛙は負けると思うw
494 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 20:33:22 ]: お前らひがみはみっともないぜ
495 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 20:33:44 ]: いったい誰に負けるって？
496 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/18(日) 20:36:40 ]: >>490
またＣに戻って戦略練り直しかorz チキンレース面白いから大歓迎だけどｗ
497 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 20:36:47 ]: 井＝2ch
蛙＝団子
498 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 20:38:49 ]: 敢えて言う、これは出来レースだ。
499 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 20:43:09 ]: 負けた時の言い訳ですね。わかります。
500 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 20:45:33 ]: ん？俺が勝ったか負けたかをどうやって確認する気だ？ｗｗｗｗｗｗ

じゃあ予想だけしておこう。
優勝者は、13clk/qwordを、切る。
501 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 20:46:17 ]: つまり切ったんだな
502 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 20:51:00 ]: 2人参加が優勝してたらまず団子だろw
503 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 20:52:47 ]: なんか・・・インパクトに欠ける予想だな・・・
504 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/18(日) 20:53:02 ]: >>500
今の実装でも (Odd + Even) / 2 < 13clock だから否定は出来ないなぁ…。
505 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 20:54:00 ]: 2人参加が優勝したら、両方名前＆社名出すようにfixstarsに働きかけようぜw
506 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 20:55:19 ]: >>504
多いほうの命令ひとつ減らすのに、少ないほうの命令が3つくらい増える悲惨な事態に陥ってますが。
507 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 21:01:59 ]: ってか、2人参加の片割れがfixstarsの関係者かも知んなくね？
508 名前：202 mailto:sage [2009/01/18(日) 21:09:55 ]: >>506
判る判るｗ
もう、1サイクル減らすとかじゃなくて、0.3サイクルとか0.25サイクルずつ減らす
領域なんだよね。
509 名前：202 mailto:sage [2009/01/18(日) 21:13:02 ]: >>507
fixstars 関係者は参加できないよ。

中の人は、仕事の片手間に応募者より速いコードを目指して実装中。
たぶんまだ5M切れてない。
このスレみてガクブルしてるよｗ
510 名前：デフォルトの名無しさん mailto:sage [2009/01/18(日) 21:14:45 ]: 参加できないんだから、参加してない事を証明しなきゃダメだろ。
ってことは、チームの場合も両方名前＆社名出さないと。
511 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 21:45:34 ]: >>509
そんなしょーもないことしてどうすんねん
優秀な学生の確保と活力ある社会人の引き抜きが目的だろ
512 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 21:48:52 ]: うーむ・・・もはや手詰まりか
513 名前：202 mailto:sage [2009/01/18(日) 21:53:45 ]: >>511
別に非関係者装って参戦してるとかそーゆーんじゃなくて、純粋に遊びで
挑戦してるらしいよ。
Cellのプロフェッショナルとしてのプライドをかけたお遊びねw
マイミクのfixstars社員に「社内で5M切った奴いる？」って訊いてみたら？
514 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 22:08:32 ]: まあプロが俺に負けるわけにはいかんだろうがなぁ
515 名前：202 mailto:sage [2009/01/18(日) 22:21:31 ]: ちょ、だんごさん4.8M切ってるのか。スゲー！
516 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 22:31:34 ]: そこは驚くところじゃない
まだ上はいるんじゃね？何となく。
517 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/18(日) 22:52:28 ]: >>473のコードを１命令変更しただけで4.8M切れたｗ
さて、これをアセンブラに移してループの調整でも始めるかな。
518 名前：,,・´∀｀・,,）っ-○◎● mailto:でもなかったりする sage [2009/01/18(日) 22:56:16 ]: だんごやさんピーンチ
519 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/18(日) 23:02:30 ]: >>518
ちょっとﾜﾛﾀ。14cycleの時は１位との差が10000tick行くか行かないかの所まで
詰められたけど、ここまで来るとさすがに自信無いなぁ…。
520 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 00:24:58 ]: >>479
実は載ってるところ少ないんだけど8サイクル以上位連続でロード/ストアしようとするとストールした記憶がある
そこでいったんぶった切ってoddでそれ以外の事するかあけてしまった方が速くなったりとか
自分も去年かおととし気づいたことなんで厳密な事は覚えてないんだけど
521 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 00:52:56 ]: ↑の制限は８サイクルよりは長いよ。でも 227 はそんな load/store はしてないと思う。
522 名前：202 mailto:sage [2009/01/19(月) 00:53:11 ]: >>520
へぇ。
命令のバッファが空になるとLS命令をストールさせて命令をフェッチする
とかそういうのがあるのかな？
523 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 01:10:02 ]: >>520
SPEのLSはポート一個しか無いので、DMAやload,storeが頻発すると、命令フェッチができなくなる場合がある。
Handbook の 3.1.1.3 に、優先度は、 DMA > load,store > 命令フェッチと書いてある。
命令フェッチが必要な場合は、hbrp命令すると優先度が上げられる。

詳細は、
ttp://cell.scei.co.jp/j_download.html
「プロセッサにおける命令枯渇に起因する Synergistic Processor Elementの無限ストールの防止について」
あたりに書いてある気がするが、読んでもよくわからん。
524 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/19(月) 01:16:02 ]: とりあえず詰ませてみたけど、asmvis 見てもどこでストールが起きてるのか
分からない状態。片っ端から nop/lnop 入れて検証するのかぁ…orz

>>521
カンで16か20とみた。調子に乗ってループ展開しまくっていた頃だから、
知らない間にリミットを追えてしまったのかもしれませんね。
525 名前：202 mailto:sage [2009/01/19(月) 01:23:42 ]: >>524
分岐ヒント命令のレイテンシが15cycleだから、それ以下の可能性が高い。
12cycle=24命令か8cycle=16命令分でオチるんじゃないかな。
526 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 01:42:57 ]: >>523
DMA 用と load/store & ifetch 用の２ポートだった希ガス。
今回は DMA 関係ないけど、DMA は待たせられないからね。
で、load/store と ifetch でポート共有してるから、ifetch が
ストールしないように、load/store は続けちゃだめよ、と。
527 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 08:09:41 ]: 謎のデチューン（笑）で性能改善された説明になるな。
メモしておこう
528 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 12:42:42 ]: 学生でやってるけど10倍すらキツい
アセンブラ命令と複数対１命令で対応している組み込み命令は
どの程度コンパイラによる最適化の影響を受けるの？

基礎的な知識が圧倒的に足りていない件･･･orz
529 名前：,,・´∀｀・,,）っ[昼はカレー] mailto:sage [2009/01/19(月) 12:44:00 ]: 要するに128バイト分の命令（32命令）をこなす間に8サイクル以上
LSにロード・ストアしないタイミングを確保すればいいらしい。
完全にEven/Oddが同時実行されてる場合はロード・ストアが1バッファあたり8命令を越えるとアウト。
2命令同時発行できないサイクルがあったりすれば1バッファを使いきるサイクル数が17以上に延びるので、その分は延びる。
たとえばEven側20命令、ロード・ストア12命令の32命令でも、バッファのフィルに必要な8サイクルを確保できる。
530 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 14:13:31 ]: >>529
Handbook によると
「SPU instruction prefetches are 128 bytes per cycle.」
らしいので、32命令中に1サイクル空きがあればいいはず。
531 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 14:14:19 ]: >>528
結果さえ同一ならバカ正直に「SIMD版MT」を実装する必要がない
532 名前：デフォルトの名無しさん [2009/01/19(月) 14:17:58 ]: >>530
bitじゃなくてbyteかよ
533 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 14:30:33 ]: そういえばDMAと命令フェッチが同じバスなんてことが書いてあるような
534 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 15:24:33 ]: >>531ありがとうございます。>>209で言ってたようなことかな･･･
もういちど見直してみます
535 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 15:45:38 ]: >>533
>>526 じゃなくて？
536 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 16:12:20 ]: >>530,532
LS の読み書き単位が 128byte だからね、たしか。
ただ、読み込み自体は 1cycle で終わっても、SPU の pipeline は
結構深くて、15cycle くらい前に fetch されてないとダメなはず。
他にも ifetch 起動条件とか色々あるよ。どっかに資料あると
思うけど、リンクとか張らないでみんな自力で頑張ろうぜｗ
537 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 18:04:15 ]: www2.vipper.org/vip1074688.png.html

上から下までこうなってないところ捜す方がしんどい
538 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 18:47:38 ]: あ、当たり前では？
539 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 19:50:30 ]: 俺も参加したいけど、どうせなら1位2位を争いたい。
でも団子屋さんみたいな暇人じゃないから勝てるわけもないので高みの見物。
540 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 19:51:04 ]: ひまじんとはしつれいな
541 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 20:30:21 ]: >>531
それ考えてるんだけど思いつかないんだよな
アルゴリズム同じのまま使う命令の入れ替えと並び替えで15サイクルまでは来れたんだけど
しかも現状じゃ隙間は残ってるのに依存性で詰められないところがあってもったいない
ここにいる優勝候補さんたちは社会人部門だと信じてる
542 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 21:46:33 ]: __builtin_expect()使っても意味ねー
つか遅くなる
543 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 21:49:36 ]: ！！！いままで使ってなかったんか！！！ｗ
544 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 21:50:14 ]: 今さら？
__builtin_expectでぐぐりゃそんな事例出てくるだろ。
545 名前：v127251.ppp.asahi-net.or.jp mailto:sage [2009/01/19(月) 21:54:45 ]: だんごうぜー
546 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 21:59:07 ]: ふゅーじゃーねいざん？
547 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/19(月) 22:00:15 ]: ループ内側の最適化は投げ出して、外側の整形作業に移るとしますか。
知らない間にリアルが２末マイルストーンとか言う無茶苦茶な事に
なってたんで、現実逃避も程々にしとかないとマジでヤバイかも。。。
548 名前：デフォルトの名無しさん [2009/01/19(月) 22:00:49 ]: なんで、こんなところに節穴がいるの？
549 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 22:03:18 ]: 俺の日記はリアルGateKeeperがよく読んでるけどね
550 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/19(月) 22:12:55 ]: 今更になって>>389見て幻滅してきたorz メモリが無いと勝てる気がしない…。
551 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 23:17:44 ]: 15,000tick削減成功
いけるところまでやるか
552 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/20(火) 00:57:49 ]: とりあえず、>>389の一歩手前までたどり着いたのは良いんやけど、ここに
なって拡張アセンブリが使い物にならない(>>458)事がハンデになってくる
とは思わなかったorz

>>551
まだ３日ほど楽しめそうですよｗ
553 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/20(火) 01:35:27 ]: >>552
一歩手前じゃなかったっぽい。見れば見るほど>>389が神に見えてきたorz
554 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 01:38:13 ]: >>517 は何だったの？w
555 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/20(火) 01:56:24 ]: >>554
99.91%の壁の高さを痛感しているだけですよ、たぶん。
556 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 02:17:10 ]: あー、>>389 の前提がおいらとは違うのか。
>>551 を見て >>389 は最適化途中だっただけと見てたんだが。
557 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 11:58:58 ]: 素人だけど参加

命令書き換えとか、なかなか上手くいかないけど楽しいわコレｗ
558 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 16:16:18 ]: >>557
命令自己書き換え(self modification)してんの？
仕様書に書いてあるけど、その場合は sync しなきゃ
だめだからあんま早くならない気がするなぁ…
559 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/20(火) 17:53:14 ]: 【Oddの】命令数削減法思いついた
560 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 19:24:19 ]: 何命令くらいの所で頑張ってるんだろう？
自分はもうこれ以上削れる気がしないけど…
561 名前：202 mailto:sage [2009/01/20(火) 19:56:42 ]: だんごさんそのうち4M切りそうだなｗ
562 名前：202 mailto:sage [2009/01/20(火) 20:24:17 ]: いや、でも4.7Mの壁は今までの壁と比べても相当キツイな。
提出日まで頑張っても超えられない気がしてきた。
563 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/20(火) 20:45:21 ]: なんですか4.7Mの壁って
564 名前：202 mailto:sage [2009/01/20(火) 20:49:02 ]: >>563
余裕で切ってるってことかーーー！！！
マジで勝てる気がしねー。
565 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/20(火) 22:03:02 ]: 逆に遅くなったorz
566 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 22:08:50 ]: だんご優勝できなかったらブログ閉鎖の方向でよさそうなのかな？
567 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/20(火) 22:13:22 ]: なんでやねん
逆に優勝しちゃうといろいろまずいことならあるが
568 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 22:23:08 ]: 3Mの壁が・・・。イチからやり直すか・・・orz
569 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 22:30:49 ]: 16Gくらいメモリ使ったんですか？w
570 名前：202 mailto:sage [2009/01/20(火) 23:24:43 ]: >>568
3Mって、、、俺らと同じ基準なら化け物スコアだな。
571 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/20(火) 23:29:48 ]: >>557
でも今日は酔っぱらってて自己書き換えの実装出来ないんだなー。
明日時間有ったら挑戦してみる。
572 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/20(火) 23:34:44 ]: 30Mの勘違いの予感
573 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/20(火) 23:59:18 ]: いつの間にか FAQ 更新されててﾜﾛﾀ

> デクリメンタのオーバーフローを利用することは可能ですか？
> 今回の出題の趣旨に反するので不可能とします。
574 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 00:03:08 ]: 不可能ではないと思うんだ。
575 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 00:06:04 ]: 本日の捏造

spu-gcc43 -std=gnu99 -O3 -g -c -o mt_mine.o mt_mine.c
spu-gcc43 -Wl,-Map,mt_kadai.map mt_kadai.o mt_mine.o mt19937ar.sep/mt19937ar.o -o mt_kadai
./mt_kadai
ORIGNAL: sum=3c927c56, 294422087 ticks
MINE: sum=3c927c56, 4694973 ticks
ORIGNAL: sum=2e987a4d, 424720276 ticks
MINE: sum=2e987a4d, 6772739 ticks
ORIGNAL: sum=ef1b6aef, 312518235 ticks
MINE: sum=ef1b6aef, 4983550 ticks
ORIGNAL: sum=eedd2516, 290441206 ticks
MINE: sum=eedd2516, 4631487 ticks
ORIGNAL: sum=f7e967a8, 14385949 ticks
MINE: sum=f7e967a8, 229457 ticks
ORIGNAL: sum=1f37a7db, 214501370 ticks
MINE: sum=1f37a7db, 3420537 ticks
ORIGNAL: sum=c7d41f36, 295356889 ticks
MINE: sum=c7d41f36, 4709875 ticks
ORIGNAL: sum=aa9d2e9f, 259910600 ticks
MINE: sum=aa9d2e9f, 4144655 ticks
ORIGNAL: sum=8abd398a, 251178167 ticks
MINE: sum=8abd398a, 4005396 ticks
ORIGNAL: sum=a374bd58, 6118425 ticks
MINE: sum=a374bd58, 97617 ticks
576 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/21(水) 00:19:26 ]: >>575
目標修正、4.6Morz
577 名前：202 mailto:sage [2009/01/21(水) 00:54:43 ]: ああくそ、やっと正しい答えが出た。
拡張インラインアセンブラ、かなり茨の道だわ。
レジスタ多いから、どのレジスタが期待値と違うのか判らん。

誰が悪いのか判らないアセンブリのデバッグしながら命令削るより、
C言語の上で一つでも多くのアイデアを実装した方が絶対効率的だ。
578 名前：202 mailto:sage [2009/01/21(水) 00:56:33 ]: >>575
まだ4Mは切ってないようでｗ
大きな差が無くて安心した。
579 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 01:05:57 ]: 今北。

課題は、MTの最適化ではなく、合計の計算の最適化なんだな。

後段の tempering は mt[] に影響を与えないので、tempering 後の
値を合計せずに、tempering 前の「とある値」を集計する。GF(2)の中で。
すると、tempering (相当の操作)は一回で済む。

＜いまここ＞

団子「スタートライン」ってこれのことだろ？

次に、「とある値」を集計するだけの目的であれば mt[] を「真面目に」
計算する必要はなくって、かなり端折れる。(仮に、端折って計算した
mt[] を pmt[]とする)

どの計算が端折れるか、いま計算しているところ。

＜もうすぐここ＞

最後に、num_rand % 624 の端数ぶんをどう計算するかで手詰まり気味。
pmt[] から mt[] を計算し直そうとすると、mt[] を最初から計算する
のとあまりコストが変わらない方法しか思いつかない orz

いっそ、mt19937ar.c の mt[] を LS から探してしまおうか。

まず、num_rand % 624 となっている mti を探して、みつかった mt[]
から pmt[] を検定する。

どうかな。
580 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 01:07:43 ]: >>575
人間がレジスタを管理することなんて既に不可能と気づけよ。
581 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 01:12:12 ]: >>579
あーぁ、GF(2) とか出してくるなよw
団子の「スタートライン」は全然そこじゃないって。
井戸の中で満足してる奴に餌与えちゃだめだってw
582 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 01:16:35 ]: 井戸の中ｗ
583 名前：202 mailto:sage [2009/01/21(水) 01:21:54 ]: >>579
ルールブレイカー発動か？
tempering前に何かを集計して・・・ということができれば劇的に
速くなるという発想はあったんだが、多分ムリだろと思ってやってないよ。

学がないもんで、GFを今Wikipediaで調べて、やっぱり意味不明だった。
584 名前：202 mailto:sage [2009/01/21(水) 01:24:09 ]: >>580
Pythonでスクリプト組んで、アセンブラコードを半自動生成させてるから、
うまくいってるときは問題ないんだ。
一度計算結果が狂うと、どこが間違ってるのか全然判らなくなる。
585 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 01:46:28 ]: >>202
Matsutomo et al.1994 にも、MK-tempering が GF(2) 行列の掛け算だ、
と書いてあるでしょ。

それから、MTが暗号乱数として脆弱なことは Matsumoto も認めることろ。
そこをつつかなくてどーするｗ

今すぐ ACM 逝って MT に批判的な論文嫁。
586 名前：579=585 mailto:sage [2009/01/21(水) 01:50:03 ]: とかいいつつ、端数の処理が解決できなかったら俺の負け。
587 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 02:04:10 ]: >>579
団子は何もしらないってことにまだ気付いてない。。。
588 名前：デフォルトの名無しさん [2009/01/21(水) 02:07:03 ]: >>579
とりあえずそのままSIMD化しただけで放置してたんだが，
そうゆうの面白そうなんでその方向性で考えてみるわ
589 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 02:25:40 ]: ここが井戸か
590 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 03:40:48 ]: ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/TEACH/0407-2.pdf
591 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 04:11:57 ]: >>590
ポイントはここですか？w ＞「6.5.2 どこがフーリエ変換やねん」
592 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 09:33:19 ]: ま　た　勘　違　い　の　【さ　ん　す　う　や】　か
算術師の花園へようこそ
593 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 10:18:06 ]: ＞いっそ、mt19937ar.c の mt[] を LS から探してしまおうか。

このレベルのネタでいいなら、
num_randとseedの組を決めうちにして、switch(num_rand) { } で計算済みの結果返すようにしたら？
変更されるらしいけどｗｗｗ
アホの言ってることは要するにそのレベル。
螺旋の飛んださんすうやさんは計算機で如何実装するかという論点が欠けてる。

余談までに松本教授＆斎藤氏のＳＦＭＴがオリジナルのＭＴと比べて如何違うかって、最大の違いは
Temperingの結果を都度（32bit×4要素分単位で）mt[]にフィードバックしてること。
それでうまい具合にビットレベルで数値がばらけてくれる。
逆にそれで依存関係が起きて128ビットを越えるＳＩＭＤでは効率的に実行できないわけだが。

>>580
ばかだな。レジスタ管理がどうとかなんて言ってないだろ。
ここまで全部コンパイラにやらせてるし
594 名前：557 mailto:sage [2009/01/21(水) 10:29:40 ]: >>558
え、そうなの？
仕様書あんまし読んでないからわかんないけど
俺がやってるのは例えばodd命令をeven命令に置き換えたりして
同時発行を促すとかそういうのなのだけど･･･
595 名前：,,・´∀｀・,,）っ[タミフル] mailto:sage [2009/01/21(水) 10:45:30 ]: oddをevenかよ。俺様はそれをやる段階じゃないな。

てか、件のＯｄｄ側の命令数削減法、実際やろうとするとレイテンシチェインが伸びて
アンロールするレジスタ足りなくなる罠。本末転倒。

インフルエンザですが何か？
596 名前：,,・´∀｀・,,）っ[タミフル] mailto:sage [2009/01/21(水) 10:55:31 ]: >>578
俺が現在進行中のスコア貼ったことは一度も無い。
いまのところ3日前くらいのスコアばっかし貼ってる。
597 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 12:02:37 ]: >>575が3日前だとして
>>551の時点で15,000tick削減成功

だから少なくとも今は4.67M台未満ってことかな？
598 名前：202 mailto:sage [2009/01/21(水) 12:11:40 ]: やっぱりやる気でないから、数学的手法への挑戦はやめとく。
レジスタ上に一瞬とはいえ目的の乱数が出現する俺や団子さんに比べて、
数学的手法だと一瞬たりとも目的の乱数が出現しないから、
※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。
の条件に違反しているという理由で reject される恐れもあるしね。

コード整理して、レポート書いて、提出しちゃおう。
599 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 12:18:46 ]: レジスタ上に一瞬とはいえ目的の乱数が出現する俺や団子さんに比べて、

え？アレって出てるって言うのかな？
俺はデータ構造的にあやしいことやってるけど。
600 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 12:20:02 ]: >>593
結局自分で管理しないでコンパイラ任せじゃないか。
レジスタがいっぱいあるからといって自分で全て管理できるはずはないけど。
601 名前：202 mailto:sage [2009/01/21(水) 12:24:23 ]: ひょっとしてまじめに乱数作ってチェックサム取ってるの俺だけか？？
俺が団子さんに敵わないのもそのせい？？？
602 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 12:31:58 ]: >>600
だから何なんだ？管理できるとかできないとかお前は一体何を言ってるんだ？
俺にはさっぱりわからない。
603 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 12:47:36 ]: >>601
ちなみに、彼の珍理論で演算時間の短縮を図るには超次元立方体構造のレジスタや演算ユニットが必要だったりするから気にするなｗｗｗｗ
604 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 13:08:44 ]: 団子が天才。はい。だからもうだまれ
605 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 13:43:41 ]: >>604
誰だおまえ？スピード狂オタクの分際で調子に乗るな。
606 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 14:01:25 ]: MT配列は教科書通りの結果になるように都度更新してるけどtemperingをまっとうな方法でやってる自信はないな。
607 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 14:48:01 ]: >>603
おいおい、GF(2) 系の演算の高速化や簡素化はコンピュータの得意分野だぞ？
今時の暗号なら当たり前の事だろ。実装した事ないのか？
608 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 14:49:59 ]: だったら実装してみろよ
机上の空論はおなかいっぱい
609 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 14:56:08 ]: さんすうや君は端数を処理するのにチートやらないと無理だって言ってるんだろ？
ならどのみち芽がない方法だ。
610 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 15:07:30 ]: > GF(2) 系の演算の高速化や簡素化は

やってるよ。
MT[]のデータ状態に矛盾が起きない範囲でな。それが出来ないなら今回のコンテストは諦めろ。
611 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 15:21:50 ]: 青筋立てないで落ち着け。
どこのスレでも痛すぎる。正しい事を言っているかどうかじゃなくて。
答えて欲しい質問からは逃げるのに叩けるところはどうでもいいところまでしゃしゃり出てくる。
612 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 15:35:50 ]: なんだ答えて欲しい質問って？
613 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 15:35:58 ]: ゲハ厨学歴厨に何言っても手遅れ
614 名前：202 mailto:sage [2009/01/21(水) 15:38:49 ]: 話題変わるけど、spu-gdbってどうやって使うの？
elfspe使ってspe用のバイナリを直接実行できるんだけど、
spu-gdb mt_kadai とかやってもデバッグできない。

今までデバッグは全部コードインスペクションと、mt[]のダンプ取って
バグの箇所を推測するの2種類だけで全部やってた。
615 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 15:40:07 ]: 負け犬の遠吠え
616 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 15:43:17 ]: >>614
SPUの実行イメージをPPEから読み出すローダーでも作れば良いのでは？

cell.fixstars.com/ps3linux/index.php/Libspeプログラムのデバッグ
617 名前：202 mailto:sage [2009/01/21(水) 15:43:37 ]: >>612
※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。
の意味について、
1. プログラム中でmt[]の内容を計算していたら良いのか、
2. 全乱数wordについてtempering後の値も計算していないといけないのか、
3. それともチェックサムだけ合ってればなんでもアリなのか、
を質問してみて、質問して回答が2だとヤバイ？
618 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 15:46:17 ]: 俺に聞くな。

ちなみに俺はgenrand_mineを繰り返し呼んでも安全なように設計してる。
ぶっちゃけ外側の最適化はサボってる
619 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 19:26:33 ]: >>612
>>381 は本当？　>>389 == 最適化中は本当？　>>575 の捏造は本当？ｗ
620 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 19:29:02 ]: 鼻高々だな団子。
621 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 19:41:11 ]: 手元にある最新のコードよりわざと悪い結果を貼ってるのは本当。

晒す実行結果は前のバージョンだったり、わざとデチューンしたり、色々。
622 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 19:47:57 ]: なんか参加賞あるし、暇だからやってみようかな

プログラム全然書けないけど
このスレ見ながら楽しくやってみよう
623 名前：557 mailto:sage [2009/01/21(水) 20:34:12 ]: >>622
自分もそんな感じ。
勉強と思ってのんびりやろうぜ
624 名前：579 mailto:sage [2009/01/21(水) 21:15:27 ]: >>593

>switch(num_rand) { } で計算済みの結果返すようにしたら？
全然ネタのレベル同じじゃないだろｗ

>変更されるらしいけどｗｗｗ
その上でのネタなわけだが。

>最大の違いはTemperingの結果を都度（32bit×4要素分単位で）
>mt[]にフィードバックしてること。
ハズレ。

余談に余談を重ねると、MT と SFMT は GFSR である点で同一。
tempering のコストを MT の更新側に振っただけ。

>逆にそれで依存関係が起きて128ビットを越えるＳＩＭＤでは
これも違うな。

MT の漸化式は g(w)_MT = w_0 A + w_1 B + w_M なわけだが、
SFMT は g(w)_SFMT = w_0 A + w_M B + w_{N-2} C + w_{N-1} D
に変更されている。

これが効いてくるのは、レジスタ幅ではなくむしろ並列計算だろ。
625 名前：579 mailto:sage [2009/01/21(水) 21:16:53 ]: >>603
超次元立方体構造ってなんだよｗ

>>606
その教科書には、w 次 n 階の (T)GFSR も 1 階化すれば nw 次の
GFSR になって、1 階線形漸化式に帰着するとは書いてなかったかい？

>>609
>端数を処理するのにチートやらないと無理だって言ってるんだろ？
誰が無理だと言ったｗ
思いつかない＝無理なのか？

>>610
> > GF(2) 系の演算の高速化や簡素化は
>やってるよ。
MT の内側は全て GF(2) なわけだが。
それを踏まえて外側を如何に GF(2) の上に持っていくかの話だ。
626 名前：579 mailto:sage [2009/01/21(水) 21:17:46 ]: >>598=202

ヒント：外側の sum += が仮に sum ^= だとしたら？

> 同じ乱数列を生成してください。の条件に違反している
ちょｗｗｗ

だとしたら
>temperingをまっとうな方法でやってる自信はない
>MT[]のデータ状態に矛盾が起きない範囲でな。
団子道連れだな。
627 名前：579 mailto:sage [2009/01/21(水) 21:19:00 ]: 話を戻すと、課題(MTのsumを求める)は、次のように分解できる。

1. mt[] から pmt[] への線形写像を求める。
2. for (num_rand / N) 不真面目な計算。
3. pmt[] から(num_rand / N反復後の) mt[] を戻す。
4. for (num_rand % N) 真面目な計算。
5. tempering

厳密に言えば、mt[] と num_rand から不真面目な計算をして
O(1) で sum を求める事も理論的には可能。が、その理論を
解析している時間はないわけ。

が、たかが 32N 次元程度の GF(2) 上のベクトルであれば、2 の
不真面目な計算を機械的に求めることも非現実的ではない。

いまそれを解析しているところ。

問題としているのは 3 の操作で、pmt[] が mt[] の線形写像で
ある以上、完全に mt[] を元に戻すことはムリ。4 の計算も
不真面目化すればよいのだけれど、そのままでは num_rand % N に
応じて N 種類の不真面目計算方法が発生してしまってコード
サイズ的にムリ。

なので、別の方法での不真面目計算を考えているところ。

O((num_rand % N) ^ 2) であれば解は見つかった。が、これだと
条件「num_rand が 10000 以上」に対してコスト・リスク大きすぎ。

まあ、1回目の不真面目計算が解析できれば、そこから芋づる式に
求まるんじゃないかと楽観視している。

ともかく、いまは解析結果待ち。
628 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 21:30:52 ]: 妄想はいいから。

> ヒント：外側の sum += が仮に sum ^= だとしたら？

→「あり得ない仮定を持ち出す」
これは詭弁の○○箇条にもあったな

まあ珍理論持ち出しても無理だから諦めろ負け犬

くだらねーコンテストなんて目じゃねーぞ。
629 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 21:35:49 ]: > その教科書には、w 次 n 階の (T)GFSR も 1 階化すれば nw 次の
> GFSR になって、1 階線形漸化式に帰着するとは書いてなかったかい？

で、それはSPUの命令を使って何命令で実装できますか？

> 思いつかない＝無理なのか？

所詮お前は口だけだな。
ハッタリは何も出来ない人間のためにあるものだぞ。
どう足掻いてもお前にはできない。
630 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 21:38:07 ]: >>579
数学はよくわからんのだが、
自分が優勝だと勘違いしてるやつより期待してるからがんばれ！！
631 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 21:39:12 ]: ああ、ちなみに最初くらいに1ビット×128並列のビットスライス実装思いついたけど
全然速くなかったよ。
632 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 21:39:43 ]: これはどれぐらい高度な数学が必要なんだ？
633 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 21:41:31 ]: さんすうやの詭弁は聞いて呆れる
634 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 21:58:01 ]: >>632
これ読んで何書いてあるか解る程度。そのまんまだけど。
www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1441-14.pdf

1 ticks = 40clkで、PLAYSTATION 3のSPUのクロック数は3192MHz動作です。
num_rand = 58156364のとき、genrand_mineの実行時間は4.7MTicks程度かかりました。
このとき、genrand_mineの実行時間は何秒かかったでしょう？
これは簡単なさんすう（笑）の問題

でさ、pmt[]（笑）求めるのに何十秒かかるのかねぇｗｗｗ
さんすうや（笑）は計算時間がいくらかかるか、メモリがいくら必要かそういう観点が欠如してるから困る。
その上机上論ばかり並べる。できることをしない。だからできない。

まあ、時間がかかりすぎてSPU Decrementerがラップアラウンドしてくれば、見た目のTick数は（ｒｙ
635 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 21:59:50 ]: いや、だから、団子はやらんでいいから黙ってろやｗ
636 名前：579 mailto:sage [2009/01/21(水) 22:02:50 ]: >→「あり得ない仮定を持ち出す」
物事を簡単に考えるための迂回路だ。TT800から始めてろ。

>で、それはSPUの命令を使って何命令で実装できますか？
だから解析中だって言ってるだろうが。

解析結果？出てねーよ。

課題アナル(仮称)を prolog で実装した策略ミスだ。それは認める。
vsz は順調に(?)太っていってるから、あと 2,3 日ほっといてみるか。
637 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:12:27 ]: 59ms弱だよ。

前提からしてアホだろ
MT[n]のsumをTemperingしたものと TemperingFunction(MT[n])のsumは全くの別物

んで、頭弱い子は加算命令をXORとANDに分解してソフト的に加算すればいいと思ってるだろ？
レジスタ足りる？むしろメモリ足りる？

っていうか、脳みそ足りてる？
638 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:15:06 ]: >>634
なんとなく分かりました。高度な数学というよりも新鮮なアルゴリズムに気がつくかどうかの問題だし、素数を探すプロジェクトとなんか似てますね。
639 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:22:43 ]: 団子はうざいが、
>>637
>レジスタ足りる？むしろメモリ足りる？
>
>っていうか、脳みそ足りてる？

これは笑ってしまった。く、くやしい。
640 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:24:26 ]: なんにせよ10000≦num_rand＜UINT_MAXだからなぁ
何十年かかる計算を数学的解析によって短縮云々なら価値はあるが
数十ms程度で終わる計算相手にスピードを競うアプローチとしては無謀を通り越して馬鹿かと
5段階の1段階目だけで既に終わってる希ガス。

それよりUNIX crypt(3)のハッシュ値からキーをダイレクトに求めるアルゴリズムでも解明して下さいよｗｗｗ
数十年来の課題ですｗｗ
641 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:25:19 ]: fixstars側に十分な数学の知識がある人がいて
なおかつコンテストで生み出されるコードが後々の役に立つものであってほしいと願っているのなら
素直に乱数を作って加算するのが一番速くなるような問題になっているはず、
と信じたい
642 名前：579 mailto:sage [2009/01/21(水) 22:26:22 ]: >>637

頭悪いな。お前が cite した文献に書いてあるじゃん。

> MT の解像度は最大可能な解像度と比べるとかなり悪くなっている
> MT の解像度は最大可能な解像度と比べるとかなり悪くなっている
> MT の解像度は最大可能な解像度と比べるとかなり悪くなっている

> この固定されてしまった j_1,...,j_L が乱数の質を決めるのだが、これがいただけない。
> この固定されてしまった j_1,...,j_L が乱数の質を決めるのだが、これがいただけない。
> この固定されてしまった j_1,...,j_L が乱数の質を決めるのだが、これがいただけない。
643 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:30:54 ]: 負け犬は遠吠えだけは達者だな

んで、計算時間は具体的にいくらですか？
O(n)のアプローチのほうが賢明ということもありますよ。

> 1. mt[] から pmt[] への線形写像を求める。
どうせこれだけで天文学的な時間かかるんだろ？ｗ
644 名前：579 mailto:sage [2009/01/21(水) 22:34:24 ]: 線形写像求めるだけで天文学的なんて、どこまでお花畑なんだぜ？
645 名前：デフォルトの名無しさん [2009/01/21(水) 22:35:19 ]: 熱い・・・熱いぜお前ら
いいぞもっとやれ
646 名前：579 mailto:sage [2009/01/21(水) 22:36:17 ]: >>645

いや断る。俺下痢。寝る。
647 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:36:36 ]: ・メモリ210KBが使用禁止
・チャネル使用不可（メインメモリ間のDMAももちろん不可）

まあとりあえず脳内珍論はブログでやれ。
648 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:38:54 ]: 線形写像 = 実機動作、高速
解析 = 事前作業、低速
649 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:40:06 ]: 机上の空論には
「Temperingはランダムテーブルルックアップで1回の操作で行うことができますが、
4Byte×2^32 = 16GByteのメモリが必要です」
みたいなオチがつくんだよね
650 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:42:01 ]: >>648
> 線形写像 = 実機動作、高速
> 解析 = 事前作業、低速

その「線形写像」なんだけど、46KB未満のメモリ空間で確保できるLUTで
一体なにができるのｗｗｗｗ
651 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:42:56 ]: 線形写像の意味わかってる？
652 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:45:43 ]: 線形写像を実装する方法をソフトウェア工学ではLUT（ルックアップテーブル）って言うんだよ。
Cellはローカルメモリが小さいから一般的には不向きと言われる。
653 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:47:26 ]: ほうほう、じゃそれはアルゴリズムで実装することはできないんだな？ｗ
654 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:47:47 ]: おいおい団子ちゃんよ、高校の"さんすう"からやり直したらどうなのさ
655 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:50:24 ]: ＞ほうほう、じゃそれはアルゴリズムで実装することはできないんだな？ｗ

君の「アルゴリズム」が何を指すのかわかりませんが
LUTもアルゴリズムの一つです
656 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:51:42 ]: すまん、「LUT でなく、演算で求めることは、できないんだな？ｗ」だ。
657 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:53:19 ]: テーブルのオフセットをアドレスを求めて値をロードするのも「演算」です。
658 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:56:17 ]: むしろNOP系の命令以外は全て演算なんじゃないの？
659 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:58:02 ]: ま、何でもいーや。線形写像＝ＬＵＴね。tempering も LUT でやってくれｗ
660 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:04:17 ]: だんご大丈夫か？＞インフルエンザ
661 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:04:22 ]: ﾌﾟｯ

まさかビット論理演算の組み合わせだけでやろうとしてるのか？
それはそれで何もパフォーマンス上の優位性ねーし

まあ何がアホかって、結局のところ>>637なんだけど
662 名前：202 mailto:sage [2009/01/21(水) 23:04:55 ]: >>656
俺は専門卒なので難しい数学は判らないのだが、
元の計算式自体が「LUTではない方法」で、
結局難しい用語を持ち出してる数学屋の言ってることは

「元の計算式と同じ事をするより短い別の計算式を見つければおｋ」

って事？
それなら、最初に計算式とにらめっこして、「俺には無理」と判断してる。

Prologで何ができるのか知らないけど、元の計算式より計算量の少ない
式が出てくるっていう根拠が数学屋にはあるの？
663 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:05:31 ]: >>660
みなぎってきたｗｗｗｗｗｗ
とりあえず今週一杯サボるｗｗｗｗｗ
664 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:07:00 ]: >>662
結局は>>649的な実用性のない発想だから気にすることはない。知識におぼれて本質が見えてない人間が暴れてるだけ。
665 名前：202 mailto:sage [2009/01/21(水) 23:09:32 ]: MTの初期値が固定されていたら何かを打ち破る抜け口がありそうな気がするけど、
init_genrand() の引数と num_rand が未知の場合、「乱数のチェックサム」の計算を
ショートカットするのは無理そうというのがソフト屋の直感。

数学屋と違って何の根拠もないし、自分でもそんなに信じてない直感だけどな。
666 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:12:40 ]: >「元の計算式と同じ事をするより短い別の計算式を見つければおｋ」
そういうことだ。Tempering より短い写像式を見つければＯＫ。
って、Tempering も十分短いから無理っぽいけどなーｗ
667 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:13:08 ]: 暴れているのはだんごである
668 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:14:37 ]: だんごは鳥インフルエンザ
669 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:16:59 ]: 中の人二人いて煽り担当とプログラミング担当がいるコテの人はずるいと思います。
670 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:17:29 ]: >>666
たとえば
A XOR (B AND C)

これをたとえばMUXを使って式変形するとどうなる？
って、このレベルの試みは俺もとっくにやってるわけだが。
671 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:19:12 ]: >>669
３人じゃね？両方○も居た希ガス
672 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:20:22 ]: >>671
団子三兄弟ってやつか
673 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:24:56 ]: そんなに必死にならなくても大丈夫だよ、団子さんより頭の悪い人だっていっぱいいるから
674 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:28:06 ]: >>673とかな
675 名前：673 mailto:sage [2009/01/21(水) 23:30:02 ]: >>674
まぁ、本当のことだから何もいえないけどね
676 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:31:53 ]: B = A XOR D

が成立するとき

A XOR (B AND C)　＝　spu_sel(A, D, C)

これ、豆知識な
677 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:44:40 ]: 結論から言うと>>676は今回使うところはどこにもありません。

たとえるなら、RPGで毒の沼に入ってもダメージを受けない装備を手に入れたけど
この先毒沼なんてどこにもありませんって感じかな。

↑
これの元ネタ解った奴は俺のドッペルゲンガー
678 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:52:10 ]: >>676
そういうのを代数学の知識で証明できるようになりたい
679 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:52:33 ]: 知ってると思うけど団子の中の人は広大の松本研究室とメールやりとりしたことがある。
結論を言うとseedとnum_randからpmt(笑)を求めるための一意な論理式なんて存在しないよ。
あっても計算時間・メモリ容量的に実用的なモノではない。
680 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:53:34 ]: >>678
カルノー図書けば一発じゃないか
681 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:02:26 ]: >一意な論理式なんて存在しないよ。
いや、存在はするんだってば。実用的なのが見つからないってだけで。
682 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:04:44 ]: Cell使ってしらみつぶしに探しちゃえば？
683 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 00:05:41 ]: その上、端数を処理するのにチートしないと実用的な性能出ないんだろ？
しねばいいのにｗｗｗ

それに比べればこちとらまだ青天井みたいなもんだよ。
684 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:11:57 ]: どうせMT高速化やるなら、ついでに多変量正規乱数までやってくれよ
デキバイによっては金出すぜ
685 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:15:40 ]: 出来栄え?
686 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:16:46 ]: あーそれだ
日本語苦手だ許せ
687 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:21:04 ]: > こちとらまだ青天井みたいなもんだよ。
13cycle 切れた訳でもあるまいにｗ
688 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 00:26:07 ]: たとえばさ、

「genrand_mineが呼ばれる前には、必ずinit_genrand_mineされると仮定してかまわない」
とはあるが、関数を呼ぶ直前にinit_genrand_mineを呼ぶなんて言ってないんだぜ。

たとえば極端な話、

init_genrand_mine(seed);
hash = genrand_mine(num_rand) + genrand_mine(num_rand2);

みたいな鬼畜な条件での測定にしてきて、サマリ値不整合で失格続出になるかもしれないんだぜ？
俺はどう転んでも言いように丁寧な実装してるけど、
仮定して構わないって言ってること以外は仮定しちゃ駄目だと思うんだぜ。

とりあえず誰か質問してきてよ
689 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 00:27:52 ]: >>687
58156364 / 4 * 13 / 40 = 4725204.575(ticks)
だけど何か？
690 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 00:30:14 ]: 既に12clk/qword台の闘いなんだぜ？
691 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:36:13 ]: >>688
あー、それは俺も思った。

あと、num_randの期待値も。
下限10,000だけじゃ外側、内側の比重設定に困る。
692 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/22(木) 01:08:36 ]: 今日もEven13clockの壁を突破できなかった。なんか極大点に達してるような
気がするので、どこまで戻せば正しい道に戻れるか探してる所です。
693 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 01:15:57 ]: コアの部分でEven:12.5、Odd12.1サイクル位
革新がない限りこれ以上どうにもなる気がしない
694 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/22(木) 01:18:27 ]: >>580
レジスタ１２６個使えるんで、カラーリングの必要が無いから楽ですよ。

>>614
stqr + printf でデバッグしてます。バグが出たときは svn diff。
695 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 01:24:15 ]: >>693
ループの内側スカスカだったりするだろ？
696 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 01:31:34 ]: >>688
その場合って mti もちゃんと更新して、mti が０じゃない
ところからでも再開できるようにしてんの？
697 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 01:32:40 ]: 全部アセンブリで詰めてるから隙間なんて150サイクルの間にOdd4個あるだけだよ
698 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 01:36:34 ]: >>696
当然
699 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 02:13:27 ]: evenだけ12切る方法思いついたがOddが恐ろしいことになる
700 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 03:57:56 ]: 刹那な午後の人が hack the cell 始めてる～＆ここも見てるっぽい。
いやー、さんざん勉強させて貰ったんで、なんか感慨深い感じ。
701 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 04:13:25 ]: ああ、herumi氏のことか。

ここじゃないと思うよ。
リアルGoogle社員の人の日記（あそこのこと）見て真似を始めたらしい。
交流があるそうな。

去年ぐらいから一連のやり取りヲチしてるけど
東大院出身と京大院出身の頭脳バトルは見てて面白い。

素晴らしいじゃないか。
俺もherumi氏と戦えるなら負けても悔いはない。

＃妨害ついでにXbyakのAtom新命令対応パッチまた送りつけてやるかﾋﾋﾋ
702 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 04:29:35 ]: まてよ
60倍云々って・・・俺のカキコが初出の情報かもしれない・・・ｗｗｗｗ
まああの人は俺の日記読んでるからな
703 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 04:46:51 ]: んー、わからん。誰だろ？ > real google の人
&日記更新してたんね。15cycle の latency の話だけど、
6cycle なのは命令実行後 LS に反映されるまでの latency
だから、命令解釈やら register file から各演算器の latch
への転送とかの 15cycle とは別物だよー。マジ長いねw
704 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 04:51:42 ]: しょっちゅうherumi氏が日記のネタにしてるじゃないの

ヒント：「yajit」
705 名前：202 mailto:sage [2009/01/22(木) 09:29:56 ]: 俺も初めてアセンブラ触った動機がMMXで画像処理したい！で、
へるみさんのサイトに散々お世話になった。
なんか感慨深いなー。
706 名前：202 mailto:sage [2009/01/22(木) 09:31:57 ]: >>704
チーム参戦型のICFPプロコンで、個人で上位を取っちゃうあの方ですね、わかります。
707 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 16:11:09 ]: 今日もサボリのタミフルが、何故かおとなしいな
708 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 16:16:48 ]: 呼んだら出てきちまうだろ！ｗ
709 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 20:26:42 ]: くそー、13 切れねぇ orz
710 名前：202 mailto:sage [2009/01/22(木) 21:07:07 ]: 13が増えてきてるのが凄く脅威なんだが・・・
693、俺、だんごさんが13切ってて、227と709が13か
711 名前：579 mailto:sage [2009/01/22(木) 21:08:07 ]: >>640
>それよりUNIX crypt(3)のハッシュ値からキーをダイレクトに
>求めるアルゴリズムでも解明して下さいよｗｗｗ
暗号乱数とモンテカルロ乱数は別物だと何度もいっているだろバカ

>>647
>まあとりあえず脳内珍論はブログでやれ。
ブログに書くほどの内容でもないからここに書いているわけだがｗ

>>657
>テーブルのオフセットをアドレスを求めて値をロードするのも「演算」です。
これは痛すぎるだろ。tempering も線形写像なわけだが。

>>683
>それに比べればこちとらまだ青天井みたいなもんだよ。
青天井の意味知ってる？
712 名前：579 mailto:sage [2009/01/22(木) 21:10:55 ]: どうせ団子理解できないだろうから教えてやるよ。
その前に md5sum = 770e20e29056b7e5d420fc46bdc5ee6a

>>637
>んで、頭弱い子は加算命令をXORとANDに分解してソフト的に
>加算すればいいと思ってるだろ？
>レジスタ足りる？むしろメモリ足りる？
お前が挫折したからって俺と一緒にするな。

数値の表記法は n 進表記だけじゃないんだぜ？

欲しいのは 2 進表記の sum なわけだが、最終的に変換可能で
あれば途中経過の表記法は何だって構わない。交番だっていい。
問題なのは、mod 2^32 がガロア体ではないことだ。
713 名前：579 mailto:sage [2009/01/22(木) 21:11:18 ]: ループの内側がガロア体で、外側がガロア体ではなかったら、
そりゃ計数するのは非効率だろう。だったら、2^33 のガロア
拡大体の上で計数してみようという発想にはならんのかい？

33 次 M 系列の生成多項式 (33, 13) を使えば、十分実用的だ。

この系で 1 を計数する方法を考えれば明らか。
外側のループが ^= になっただろ？

>>628
>→「あり得ない仮定を持ち出す」
馬鹿が。

いくらお前でも、ガロア拡大体上での計数を前提としておけば、
tempering をループの外側に出せることも少し考えればわかるだろ？

そして、最後にシンドローム計算すれば 2 進表記に戻せる。
714 名前：579 mailto:sage [2009/01/22(木) 21:11:51 ]: >>631
>ああ、ちなみに最初くらいに1ビット×128並列のビットスライス
>実装思いついたけど全然速くなかったよ。
馬鹿はここで諦める。

ガロア拡大体上での計数は、ビットスライスで行った方が効率が
良いは明らか。が、mt[] の更新をビットスライスで行うのはいささか
非効率。これは、MT が "ビットスライスではない" 計算機での効率を
狙ったものなので当然といえば当然。

ビットスライスではない計算機で扱える効率的な線形写像は、
行列 [[0ii,0ij]T,[Iij,Ojj]T] (つまりビットシフト) の掛け算と
要素どうしの掛け算(AND)と足し算(XOR)、その組み合わせだ。

それに対して、ビットスライスで扱いやすい線形写像の条件は、
行列中に "1" の出現頻度が少ないもの。至極当然。

ならば、最初に mt[] を別の空間に写像しておいて、その空間で
更新行列の "1" が少なくなるように設計すればいくらでも
(それこそ青天井に)効率は改善される。
715 名前：579 mailto:sage [2009/01/22(木) 21:12:34 ]: しかし、これだけだとビットスライスを用いる根拠としてはまだ
少し弱い。それは、mt[] のサイズがレジスタ数と比較して大きい
(load, store をスケジュールするのが大変)のと、"1" の割合を
減らせたとしても行列自体が大きいので、必然的に計算量は多いまま。

そこで、mt[] 自体を小さくすることを考えよう。

が、残念なことに MT は mt[](19968 bit)のうち、19937 bit が
直交していることが理論的に証明されている。

さて、どうしよう？

>>640
>なんにせよ10000≦num_rand＜UINT_MAXだからなぁ
答え書いてあるじゃないかーい。INT_MAX だけどな。

つまり、32bit の seed から始まる 31bit の空間は、19937bit の
空間の中で、非常に小さな部分空間でしかない。

その小さな部分空間では、19937bit の大部分が直交していない。
直交していないビットは、それこそ計算する必要はない。

課題アナル(仮称)の正体は、直交していないビットを探索するものに
他ならない。
716 名前：デフォルトの名無しさん [2009/01/22(木) 21:23:46 ]: だンゴサんの括約で棺桶スレが成立したな
717 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 21:33:32 ]: >>579
なんでこんな大事なことばらしちゃうの？ｗ
718 名前：202 mailto:sage [2009/01/22(木) 21:36:40 ]: 一応、みんな判ってると思うが、Hack the Cell の課題が何か確認しておく。

ttp://cell.fixstars.com/challenge/challenge.html
課題は、メルセンヌ・ツイスタの最適化です。

注意事項
※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。
719 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:39:22 ]: 芽のない方法を芽がないと割り切る能力が欠落した人間の遠吠えはむなしいのう
720 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:42:03 ]: >>717
机上の空論だよ

突っ込みどころのデパート。詭弁の集大成。

まったくもって今回の課題の解法として役に立たない。
721 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 21:45:16 ]: >>710
あれ？202 も 13 切ってたの？ >>598-599 のやり取り見て、
まだ切ってないと思ってたよｗ
>>720
自分も >>599 が当てはまるとやばいんじゃないの？ｗ
722 名前：579 mailto:sage [2009/01/22(木) 21:47:43 ]: 連続投稿引っかかったｗｗ

最後に、端数をどうするかだ。

その前に、報告しておく。俺のアナルはもう検算フェーズに入ったぜ？
ざっくりと pmt[] の最悪値を見積もり始めた頃から勝算はあった
わけだが、解析結果を見ると想像以上に小さい。

これが何を意味するかわかるな？

第一に、mt[](pmt[]) の更新はほぼ O(rn^2) のコストであること。
r は線形写像行列に含まれる "1" の割合。n は行列のサイズ。

第二に、pmt[] から計数ベクトルへの写像行列を N-1 種類まるまる
用意してもメモリサイズ的に余裕ができたこと。

いまからマネしようとしても、解析の方法なんて想像もつかないだろ？
お前はご自慢の 59ms アナルでおとなしく全数探索でもしていろｗ

さーて、そろそろ実装でも始めますかｗｗｗ
723 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:50:46 ]: >>721
単純にMTの式をMTを32ビット×4並列化したものではないということだよ。
配列状態とサマリの値が等価になる範囲で高速化出来る方法は全て駆使してる。

もうやることは終わってさじ加減次第かな。
部分的にスカスカな部分があったりするのでループ全体を見て命令数が減るようにバランス調整が必要だ。
724 名前：579 mailto:sage [2009/01/22(木) 21:51:09 ]: >>719
自分に自信がないやつほど声がでかいってのは本当だったんだな。
725 名前：579 mailto:sage [2009/01/22(木) 21:52:11 ]: >もうやることは終わってさじ加減次第かな。
青天井じゃなかったのかよ
726 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:52:40 ]: >>722
机上の空論は結果を出してから言うことだ
727 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:53:13 ]: >>724←これとかな
728 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 21:53:27 ]: >>579
アンタ、糞団子と接するのは初めてかい?
まあ力抜いてアナル(r
729 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:00:14 ]: だんごも>>579もすごいぜ
少なくとも議論の台に乗れるんだから
俺も工学系だから少なくとも理系ではあるんだが何を言ってるのか全くわからんｗ

とりあえずサイクルの話はあんまりしない方がいいとおもた
サイクルの話見ただけでどこの最適化やっててどこの最適化やってないか想像できるし
730 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:00:24 ]: 負け犬579をアボーンリストに追加しとけばいい
彼は全然役に立たないことしか言ってない。

まあ見えない敵と戦ってる馬鹿だから相手にするな
731 名前：579 mailto:sage [2009/01/22(木) 22:05:16 ]: >>717
どうせ団子理解できないだろ？

>>718
>※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ
>乱数列を生成してください。

何をもって「同じ」とするか、だ。

tempering 前の数値も tempering 後の数値も、表記法が
異なるだけで、同じ数値なわけだ。tempering した方が
モンテカルロに用いる上では好都合な事が多いので
しているだけ。

>3. それともチェックサムだけ合ってればなんでもアリなのか、
>1. プログラム中でmt[]の内容を計算していたら良いのか、
>2. 全乱数wordについてtempering後の値も計算していないといけないのか、

これが 2 だったら、出題者が問題の意図理解していないよ orz
1 の判断は微妙だが、仮に 1 だとするとできる事は限られてくる、
つまりそんなコンテ誰が出ても結果は一緒。ツマンネ。
732 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:06:35 ]: ハイ　おさらい。
pc11.2ch.net/test/read.cgi/tech/1158559031/l50

SSE実行できないCellでSSEの実測をしたという捏造の瞬間ｗｗｗｗｗ

864 名前：・∀・）っ-○◎● [sage] 投稿日： 2007/06/17(日) 16:22:27
movd xmm0, eax
movd eax, xmm0
movd xmm0, eax
movd eax, xmm0
movd xmm0, eax
movd eax, xmm0
movd xmm0, eax
movd eax, xmm0

こんな感じで繰り返せば一応往復のレイテンシは計測できるよね
で、何クロックかかるのかな？

答えてね。俺より頭いい子ならすぐわかるはず。

もっとも俺は実測結果あるけど

866 名前：デフォルトの名無しさん [sage] 投稿日： 2007/06/17(日) 16:26:12
CellでSSEって
733 名前：202 mailto:sage [2009/01/22(木) 22:08:13 ]: >>721
>>689は超えたよ。
結構苦労してアセンブラ書いたしね。

>>721(=>>693?)もだんごさんも、tempering後の値をまじめに計算して
add を繰り返してる訳じゃないのか・・・
とりあえず、チェックサムだけ合ってればOKなのか訊いてみて、
OKならまただんごさん超えに挑戦してみるよ。
734 名前：579 mailto:sage [2009/01/22(木) 22:09:04 ]: >>728
アナルの力抜いておくよ。

>>730
ｶﾞｸﾌﾞﾙしている姿が見えて楽しいよｗ
735 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:09:26 ]: 693だけどtemperingは毎回やってる
というか処理の7割がtempering
泣きそう
736 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:15:59 ]: 話の腰をもんで悪いんだが
temperingってなんだ？
737 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:17:17 ]: 揉むな!ｗ
738 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:20:06 ]: 勘で出てきた乱数を32bit空間で偏りが無い様に再マッピングしてるんだと勝手に思ってた
739 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:21:20 ]: マージャン用語です

テンパイ＝【聴牌】
麻雀で、あと一枚必要な牌がくればあがることのできる状態。

これが、転じて何か事を成し遂げようとしたときの最終段階、、待ちの状態になったときに使うケースがあります。

てんぱる、てんぱってる。

スタンばる（スタンバイする）、、などと同じ和製語ですね。
740 名前：579 mailto:sage [2009/01/22(木) 22:22:14 ]: さてさて。

一日静かだと思っていた矢先、団子登場。団子はよっほど俺の
アナルが好きなんだなｗ　頼むから寝込み襲ってくるなよ。

この手の作戦だと実装を後回しにした方が効率いいわけだが、
結果出せ出せウルセーやつがいるから、俺はそろそろ実装始める
ことにするよ。

その前にクソして寝る。
741 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:23:20 ]: >>739
そうだったのか…
勘とはいえすごい的外れな嘘を教えてしまった
ごめんよ>>736
742 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:27:12 ]: おおざっぱに、MTで乱数生成の為に行うアルゴリズムでビットシフトを行う操作のことだな
tempering
743 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:30:00 ]: >>729
暗号論の世界にも差分解読法なんてのがあって、ビットの並びの特徴から演算をショートカットする
方法に関しては俺自身もいろいろ試したことがあってね。
んで、今回はそういうショートカットは全くもって役に立たない。

MTのTemperingはフェイステイル型暗号でいうところの一種のS-boxみたいなもんだ。
RISCオペレーションで10命令程度のビット論理演算で構成できるとはいえ、
けっこううまい具合にビットがばらけるように考えてある。

加算ってさ、簡易的にはXORとANDの組み合わせで作れるわけだけど、
キャリーアップ先は、1ビット隣じゃん。
Tempering前と後じゃその1ビット隣すら全然別物になっちゃうんだよね。
だからTempering前の値をいくら「加算」しても無意味なんだ。

Temperingは少ない命令数ながら、うまく考えてあると思うよ。

暗号の実装の話になるけど、AltiVecのVPERMやSPUのSHUFBはAESのS-Boxを16並列で処理する
ことができるけど、SSEだと同様のシャッフル命令であるpshufb命令なんかを使うより別の方法のほうが速い。
今回の課題はそう言う観点で何が最適なアルゴリズムかを考えられる人でないと難しいと思う。
744 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:31:58 ]: > フェイステイル型暗号でいうところの一種のS-boxみたいなもんだ。
ち・が・う
745 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:34:09 ]: >>739
(y << 15)んとこが16だったらアレしてこうして・・・とか思ったけど
なかなかうまくいかないもんだね
746 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:36:08 ]: >>744
あらゆるフェイステイル型暗号のS-boxはビット論理演算の組み合わせだけで実装できるの知ってる？
747 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:37:44 ]: お得意の bitslice か？　それと s-box の意義は全然別物だぞ？
748 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:39:16 ]: フェイステイル型暗号におけるS-boxの役割は、簡単に言うと前後のビットの並びの相関性を破壊するための仕組み。
MTのTemperingも、Temperingを省いて合計値を計算しようとしても出来ないようにする程度には相関性を破壊できてる。
749 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:45:37 ]: そりゃ、暗号も擬似乱数も拡散って意味ではなんだって拡散だし、
ほとんどが論理演算の組み合わせで実装できるだろうよ。
その程度の意味で、feistel の s-box と同じって言ったのか？
750 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:53:59 ]: Tempering＝「調律」
スイーツ（笑）用語でいうとチョコレートコーティングの表面を滑らかにするための行程。

もちろん、そのまんまの意味で解釈しても意味はない。
ビットの並びの相関性をある程度破壊することに意味がある。
MTにおいては、相関を破壊することが、ビットの出現確率の均一化（Tempering）になる。

S-BoxのSはsubstitution
ようするにテーブルルックアップなわけだが。

たしかにTemperingとS-boxは別の単語だが、言葉をそのまま捉えても意味はない。
本質を理解しないといけない。

テーブルルックアップを使わない暗号・ハッシュアルゴリズムの実装では
ほとんどMTのTemperingみたいな簡単なシフト＋ビット論理演算をやってる。
だから本質的に同じだって言ったんだよ。
751 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 23:07:52 ]: >テーブルルックアップを使わない暗号・ハッシュアルゴリズムの実装では
>ほとんどMTのTemperingみたいな簡単なシフト＋ビット論理演算をやってる。
へー、すごいなｗ。いや、LUT を使わない実装が標準とか思わないほうがいいぞ？
暗号作ってる方は簡単なシフト＋ビット論理演算で求められないように sbox を
導入してるのに、なんか可哀想になってきちゃうよ。

まぁ確かに本質的には両方拡散だから同じだしなｗ
752 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 23:30:18 ]: >>751
RSAのRivest Cipher(RC)シリーズとかMD5なんてS-boxを使わずにスワップを繰り返す
暗号・ハッシュアルゴリズムの代表格なわけだが？
RC6はAESの最終候補まで残ったぞ。
753 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 23:36:19 ]: なんで軒並み落ちてって、今 feistel ばっかなのか考えようぜｗ
754 名前：デフォルトの名無しさん [2009/01/22(木) 23:37:45 ]: >>743
よわかりませんが、M系列で「加算」する場合もキャリーは１ット隣なのでしょうか？
755 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 23:42:56 ]: >>754
最低限言えることは、SPUには任意の位置のビットにキャリーアップしてくれるような特殊な算術加算命令はないということだ。

まあそういうことだ。
ハードウェアに不向きなことをやらせて性能を出そうという方が間違い。
756 名前：デフォルトの名無しさん [2009/01/22(木) 23:49:49 ]: なんだかよくわかりませんが、よくわかりました。
ありがとうございました。
757 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 23:55:21 ]: 関係ないけどJNBのトークンって暗号形式なんだったっけ？
758 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 23:59:44 ]: そろそろ詭弁の○○ヶ条で〆てくれ
759 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:06:08 ]: >>753
そこはAESばっか、に訂正しろよ。
AESが世界的に選ばれてるのはAESがAESだからだ。
AESに選ばれなかったfeistel暗号の信頼性を保証する根拠にするのは間違いだな。

とっくに死んだはずのDESが何故かワンタイムパスワードとして現役で使われてたりするくらいだし。
そのレベルで言うならMD5やRC4だって未だに使われてるんだぜ。
iがつかないニンテンドーDSだとWi-FiはWEP（RC4）強制だしｗｗｗｗｗ

それに比べれば国産暗号のMISTYとかCamelliaなんてまだまだマイナー杉。
松井さんには悪いが。
760 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:11:09 ]: ん？ DES も Feistel だろ？ MISTY1 も Camellia も NESSIE とってるが。
＆ MD5 と RC4 をこれから新規に採用する規格があったら驚きだが？
761 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:17:04 ]: ちなみに、SHA-3 コンペでも feistel 使われてるぞｗ
762 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:18:28 ]: 当たり前のこと言ってどうすんだ。鍵長考えてものを言え。
引き合いに出すならRC6あたりだろ。

RijndaelがAESに選ばれたのはその一つとしてDESみたいな複雑なビットシャッフル演算がなくて
専用ハードウェアでなくても実装コストが軽いからだ。
別にRC6の暗号強度が否定されたわけではない。
763 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:30:55 ]: すまん、ちょっと読み違えてた。が、時間がない。また今度w
あ、俺も RC6 の暗号強度を否定するつもりは毛頭ないよ。
764 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:33:43 ]: そもそも別にLUTよりビット演算のほうがコストパフォーマンスが優れてるなんて言う気はない。
不毛すぎ

今回のTemperingを通す前にサマリ計算が出来るかどうかだが
実用的な計算時間をはじき出すのは「無理」と言えるレベルの相関性の破壊は達成できてるというのが
俺の見解。

俺個人は国産暗号マンセーの立場なので君に付き合ってRSAの腐れの擁護する気もない。

ちなみにSHA-3候補として俺が注目してるのはこれ
ehash.iaik.tugraz.at/uploads/5/5c/Lesamnta.pdf

＃あとAESは厳密にはSPNSであってFeistelには分類されない。
765 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:37:12 ]: 日本語でおｋ
766 名前：デフォルトの名無しさん [2009/01/23(金) 00:39:15 ]: 当たり前のこと言ってどうすんだ。
767 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:43:44 ]: 個人的にCamelliaのSSE4向け実装とか開発中
おれ松井さん好きだし

＞Fixstarsさん
来年の課題はCamelliaでお願いします。
768 名前：復活 mailto:sage [2009/01/23(金) 01:17:25 ]: >>764
俺の見解は、拡散って意味では tempering も sbox も同じってのには同意。
だが、シフト＋ビット論理演算ではできない substitution を実現するために
sbox を導入してんだから、それを安易に同列に扱うのは理解できん。

あ、国産マンセーは俺も一緒。来年 Camellia いいねぇw
769 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 02:09:19 ]: ま、とりあえず俺の情報源のひとつ晒しておくわ。

暗号アルゴリズム及び関連技術の評価報告
cryptrec.nict.go.jp/cryptrec_03_0424_outrep.htm

S-boxを使わないRC6はかなり高い評価を得てるよ。

一般的なバイトマシン・ワードマシンでビット演算でやったらめちゃくちゃコストかかる演算を
LUTなら簡単に実装出来たりする。S-boxの多くは、RISCプロセッサのビット演算にそのまんま展開すると
とんでもない演算数がかかったりするんだが、それは暗号理論的な堅牢性の根拠としては弱いと思うよ。

バイトマシン・ワードマシンじゃなくて、ビットマシンとかASIC・FPGAだったら？
たとえばDESのS-boxはAND/OR/NOT/XORの基本的な1ビット論理演算で
たったの平均56ゲートで構成出来る。
これは具体的にいうと32ビットワードの全加算回路に必要なトランジスタ数よりもかなり少ない。

AESのS-boxは・・・実装についての論文あったけど、いくらだったか忘れた。
（総当たりで最短を検索するプログラムが手元にあるけど8ビット×8ビットのS-boxは計算時間的に流石にきつい）

見方を変えようか
AESやCamelliaはS-boxを除けば、DESのIP・E・P・FPでやってるような複雑なビット単位の
攪拌処理をやらずに、世界最高水準の安全性を実現してるわけだ。
更にいうと、CamelliaはS-boxは実質的に8ビット入力×8ビット出力のものがたった1つだけしかない。
その点でみてソフトウェアでの実装の複雑さと暗号的な強度は別モノと考えてる。
770 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/23(金) 02:17:31 ]: >>710
とりあえず13clock切れた。けど謎のストールに阻まれ停滞中orz
771 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 02:34:03 ]: 本命：団子
対抗：>>202,>>227
大穴：>>579
772 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 02:44:12 ]: Camelliaの教科書的実装より引用。
俺はなんでこれでAESなみの強度が得られるのか疑問だったよ。

#define SBOX1(n) SBOX[(n)]
#define SBOX2(n) (Byte)((SBOX[(n)]>>7^SBOX[(n)]<<1)&0xff)
#define SBOX3(n) (Byte)((SBOX[(n)]>>1^SBOX[(n)]<<7)&0xff)
#define SBOX4(n) SBOX[((n)<<1^(n)>>7)&0xff]

2と3は1の出力値をローテートしてるだけ。4は入力値をローテートしてるだけ。
なんでこれで「AESなみの暗号強度を実現できる」（中の人談）のか

>>771
というか、どうやら俺が見つけた最適化方法は既にこのスレで13clk切った連中は見つけてると思うよ。
あとは実装勝負なわけだが、アセンブラ相手にCで勝てる気はしない。
具体的にいうと現時点では>>693よりは遅い。ガチ。
（てかこの人が最速っぽい）

ただ俺にとっては今回の挑戦はどこまでもHack the spu-gcc43なのだ。
アセンブラ使わないと優勝できないのはわかってるが、アセンブラを使うのは俺的に負けなのである。
Cのみで挑戦する人向けに特別賞でも用意してくれるなら俺は喜んで表彰台にあがってやるぜ。
（herumi氏も参戦してきたことで、それですら負ける気がしてきた）
773 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 02:47:12 ]: まあ、どうやってコンパイラの副作用を抑え込んだのかっていうのはソースにびっしり書いてたりするから
俺が上位に残ってたら参考にしてくれ、的な。
774 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 02:55:35 ]: >>769
俺の言いたい事は >>768 で言ったが、「今 feistel ばっか」とかが
気に食わないんかな？ sbox ＝堅牢と言ってるんではなくて、堅牢さと
速度を両立するのに sbox が向いてると言いたいだけなんだが。
シフト＋ビット論理演算だけで同等の堅牢さを実現するよりも、
sbox の方が早くし易いし、小さくもし易いって理解なんだけど。
だから NIST にしろ NESSIE にしろ、feistel 系ばっかなんでしょ。
それだけ別物だから俺には tempering と sbox を同列には扱えん。
以上。
775 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 02:55:47 ]: >>772
俺はアセンブリじゃないと絶対に出来ないことをやってるから他の点の実装が一緒なら有利かもしれん
正直な話このスレで結構な数のヒント貰ったからこれがないと負けてた
776 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 03:46:15 ]: この程度ならあんまり影響っていうレベルで、Cで組む人にアドバイス。
（というかC＋組み込み関数で俺に挑もうと考えてる奴は流石にいないだろう）

特にイライラしたのは、even側の命令減らしたいのに値のロードにimmidiate load（evenロード)に勝手に展開しやがること。
qword型でしてるのにimmidiate load。
どうやらQWORDの全要素が同一の値だと勝手にimm loadに展開しやがるらしい。

んで、volatileにしたらアドレスからロード（Odd）に展開してくれるようになった。
とか、いろいろ。
あと、AND/OR/XORなどで使う値はhalfwordに即値指定すれば命令数を減らせる。

俺としてはまた方針を変えてパイプラインを詰め直そうと思っている。
現時点で片方のパイプが全部埋まるところまでCで詰めることができてるわけで

>>774
残念だが同意できない。
標準規格においてダントツのトップに君臨するAESはFeistel系アルゴリズムとちょっと似てるが分類上別物。

あと示したとおり、Camelliaは普通のFeistel型暗号で従来4つ以上のLUT（S-Box）が必要な処理を
1つのLUTとローテートで水増ししてるけど、その点で強度に問題があるといわれたことは無い。
単一のS-boxにビット演算を少し組み合わせるだけで、強度を得るのに必要なS-boxの数を
実質的に減らすことができるのだから、シフト・論理演算・定数の組み合わせでS-boxを使わずに
性能と強度を得るのが不可能とは思わん。
実際問題、S-boxを使わないRC6は多くのFeistel暗号より高速で、なおかつ十分な堅牢性がある。

S-boxがハードウェアの負担が小さいってこと自体同意できない。
モバイル向けのプロセッサにはAESのS-boxすらデータキャッシュに収まりきらないくらい小さいものもある。
CamelliaがSBOXを最小の実装でたったの256バイトのLUTだけで構成出来るように配慮されてるのは
ミリワットクラスの組み込みCPUでの実装を視野に入れてるからだ。
CamelliaのS-boxが小さいことは、キャッシュメモリが小さいアーキテクチャにやさしいということでもある
で、それでいて十分な強度という評価を得ている。
777 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 04:24:16 ]: うーん、論点がどこなんだかイマイチ解らん。
feistel の sbox と spn の sbox は別物なのか？
俺も不可能とは思ってないし否定もしないよ＞RC6
負担が小さいとも思ってない。堅牢性と共に、早く
出来ることも小さくする事も可能なのが重要なだけ。
AES の sbox も 256 だったと思うのだが違うのか？
俺には tempering と sbox を同列に扱うのは理解
できないし、「みたいなもん」なんて説明には到底
同意できんから異は唱えるが、別に団子がそれで
間違ってないって思うのはどーでもいーよ。

ってか、こんな話誰もついてこねーよなw

でもさー、団子も sbox 系とシフト・論理演算系を
綺麗に別けてねーかw　やっぱ別なんじゃね？w
778 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 05:11:28 ]: >>770
みんなすげぇなぁ。
おいら even -1 したら、odd +3 = total +1 で意味なかったよ orz
779 名前：202 mailto:sage [2009/01/23(金) 09:21:02 ]: >>778
wwwwwwwwwwwww
すっげーヒントあげたいけど、その壁は自分で超えろ。
780 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 09:41:39 ]: >>778
大丈夫、私もその辺で挫折した。つーか、飽きたw
781 名前：202 mailto:sage [2009/01/23(金) 09:42:23 ]: >>693が、58156364 / 4 * 12.5 / 40 = 4543466 か。
この数値が出せてたら俺より速い。
>>775 の意味も判る。

現時点でこのスレだと、
優勝、準優勝候補 : >>693 , 俺
優勝候補を抜く可能性のあるヒト: >>568, >>579

だんごさんと >>579 の話にはついていけなかったんだが、
とりあえず >>579 の Prolog が導き出した解法のサイクル数が
出るまではインラインアセンブラで限界まで行った者勝ちっぽいな。
782 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 11:13:19 ]: まー普通に考えても、ここに書き込んでないやつで優れた奴もいるだろ～から
優勝候補をこのスレ内で絞るってのも無理があると思うんだけどな
783 名前：202 mailto:sage [2009/01/23(金) 11:46:04 ]: >>782
もちろんその可能性は否定しない。このスレを読まないと、「命令数どこまで減らせる」という
指標がない状態でチキンレースに参加しないといけないからキツイけど、このスレをROMってるなら
命令数がどこまで減らせるか判るね。
784 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 11:59:48 ]: >>781
おい、俺様を優勝・準優勝の可能性からはずすな！

いや外してもいいや。こっから先の手の内は明かすわけにはいかない

とりあえずカードは残してる。
785 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 12:06:20 ]: >784
だって亀田兄弟的ポジションじゃんｗ
786 名前：202 mailto:sage [2009/01/23(金) 12:08:22 ]: >>784
まじかよ・・・
>>693の12.5がもう限界だと思ってた。
787 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 12:16:58 ]: >>786
全然関係ないけどさ
Oddへの置き換えなしだとEven側は18くらいかかるわけだけど、これを17に減らす方法って気づいた？
788 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 12:27:55 ]: mt[n] = mt[m] ^ (x >> 1) ^ (((x & 1) == 1)? 0x9908b0dfUL : 0);

↓

x = rotr(x, 1);
mt[n] = mt[m] ^ x ^ ((x > 0x7FFFFFFF)? (0x1908b0dfUL) : 0);

※これを使ってもチキンレースには参加できません。課題が別モノなら有用だったかも

これ問題公開されてから3日くらいで考えたネタだけど、最終的に高速化の候補としては外れた方法だから敢えて紹介しておく。
あとブロック単位じゃなくてスカラ単位で取り出す場合はこっちのほうが速いかもしれない。レイテンシ的な意味で。
789 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 12:44:24 ]: ^ x ^

↑このへんがむかつく
790 名前：202 mailto:sage [2009/01/23(金) 13:24:28 ]: >>787
evenの命令数削減は無意識だから、どうやったら even18 になるか悩んだ。
andc ともう一つ命令を使うヤツか？
もう一つの命令で予約違反してるけど、将来のSPUで動かなくなっても
構わないと判断したよ。
791 名前：202 mailto:sage [2009/01/23(金) 13:26:21 ]: andcじゃなくてselでも良いのか。
792 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 13:48:27 ]: >>202 なに言ってんだ？w
793 名前：202 mailto:sage [2009/01/23(金) 13:54:00 ]: いっか、トップランカーには無意味な情報だからバラしちゃえ。
spu_and( matrix_a, spu_cmpeq( spu_and( x , 1 ) , 1 ) )
↓
spu_andc( matrix_a, spu_subx( z, z, x ) )
794 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 13:58:00 ]: コンテスト参加してんのお前らだけじゃねーぞ
少しは考えろ
795 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 14:00:30 ]: ってか、202 には >>788 の答えは見えてないのか？
796 名前：202 mailto:sage [2009/01/23(金) 14:00:57 ]: >>794
悪い。調子乗りすぎた。
締め切りまで黙ってる。
797 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 14:03:11 ]: >>793
そ　　ん　　な　　方　　法　　も　　あ　　っ　　た　　の　　か
第一オペランド破壊する命令はうまく考えて使わないと困るんだよね。

>>788見つけたときは俺SUGEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEって思った
798 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 14:06:19 ]: >>797 こんなので思うな!w
799 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 21:14:51 ]: 8bit×4の水平加算とかあるけど何に使うんだコレ

SSEのPSADBW/MPSADBWと同じく、動画の動き検出とかに使うんだろ？
それしか思いつかない。

悲しいことに今回の課題でも役に立たない。
如何あがいても垂直加算のほうが性能出る。
これがもしもOddで処理されるならまた使い方も違ったんだけど。
800 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 21:23:56 ]: absdb/avgb/sumb あたりは動画のためだぁな。
801 名前：579 mailto:sage [2009/01/23(金) 21:43:31 ]: 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アナルに決めたよ。ついでに処理系と実装も変えたけど。
802 名前：579 mailto:sage [2009/01/23(金) 21:44:09 ]: $ 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

ですが、何か？
803 名前：579 mailto:sage [2009/01/23(金) 21:45:05 ]: ちなみに、実装は C99 な。本当の意味でのな。altivec も使っていない。
32bit ビットスライスｗでこの程度。端数の処理はまったく最適化していない。

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

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

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

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

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

>>781=202
俺？優勝する可能性？ないよ。出ないしｗ
804 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 21:56:21 ]: >>801
おいORIGANALが本来のターゲットより一桁以上速いぞw
でも、多項式取り違えてたとはいえ、すげえ伸び率だね。
805 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 22:05:25 ]: よくできた捏造だな
でもターゲットはＰｏｗｅｒPCじゃなくて「SPU」
806 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:08:25 ]: よ、よく出来てるのか？ｗ
807 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:09:26 ]: > 俺？優勝する可能性？ないよ。出ないしｗ
これを書くのはもうちょっとあとの方が面白かったかなｗ
808 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:09:33 ]: >>805
たしかに>>732より、よくできてるのは間違いないな
809 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 22:11:27 ]: ゲハ板で発狂してるアスペル君が勝手に勘違いしただけだろそれ
810 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:12:40 ]: さすがに俺もそう思う。団子はウザイけど >>732 は無罪。
811 名前：808 mailto:sage [2009/01/23(金) 22:15:00 ]: そうだったのか。団子ごめん
812 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 22:16:23 ]: PPUとSPUが同じコードシーケンスで実行できるとかアホなこと言いやがんだもん
ＰＰＵに18issueの命令帯域が必要になるぞって言ったら、十分とかいいやがるし

しまいには、SSEがｘ86のフォーマットとはかけ離れてるとかｗｗｗ
あの命令フォーマットがｘ86でなくてなんなんだよ
813 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:37:38 ]: 大丈夫だよ。あのコピペで団子は間違ってないってみんな分かってるから。

団子が間違いを認めなくてウザい事もかなりあるがな。
あと接頭辞のように付いてくる「知り合いに誰々がいる」って下りもウザい。
知り合いが有名なだけで、別にスネ夫が偉いわけじゃないだろう。
814 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:38:02 ]: 「サマリだけ求めるショートサーキット禁止」
とか胴元が慌てて言い出したら爽快だな。
つか出題者があたまわるいってことになるが。
815 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 22:45:01 ]: 俺もそろそろトランザム（笑）発動しちゃおうかな
そろそろ勘のいい人は愚直な方法がいくらばかばかしいことに気づいてるかも知れない頃だし

>>814
関数抜ける前にMTの配列に書き戻しさえすれば等価な実装でもかまわないのでは？
816 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:59:23 ]: ルールを根本変更されると正直悲しい。そしてキツい。
単なるチキンレースなら降りる。
817 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 23:18:26 ]: 課題見直しで延期とかになったら面白い。

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

コアループ抜けてからMT配列に書き戻せばちゃんと再実行も可能。
818 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 23:32:24 ]: >>734の言うとおりになったな
819 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 23:39:57 ]: 俺もロジックジェネレータ改造したそろそろ走らせようかな
テキトーに当たり付けたパターンを再帰で全部試す馬鹿な方法使ってるから最適に近い方法見つけるのに1ヶ月くらいかかる。
俺の試算だと
820 名前：202 mailto:sage [2009/01/24(土) 00:00:50 ]: ごめん、もうプログラムは書かないから、言わせてくれ。

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

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

俺はHack the Cellに参加したんだ。単なる数学コンテストなら降りる。
821 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 00:18:10 ]: 様々な分野に対する知見が求められる、それだけのことじゃないか?
822 名前：202 mailto:sage [2009/01/24(土) 00:22:59 ]: >>821
課題を100回読んでよ。　つ cell.fixstars.com/challenge/challenge.html
どこに「乱数のチェックサムを計算してください」って書いてある？

「課題は、メルセンヌ・ツイスタの最適化です。」
「メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。」
823 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 00:25:25 ]: しかしCellって本当に早い？使ったことないけど
フィクターのサイトにあるパフォーマス例と同じ処理をXeonで組んでみたら
10倍速いのできたんだが・・・
824 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 00:29:55 ]: >>693だけど
なんか裏で本気出してる間にお通夜モードになっとる
とりあえず12.0まではきた
まだ0.3位は詰めれるかもしれない
で、大会中止とかルール変更とかなったらおれはどうすればいいんだ
825 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 00:30:33 ]: >>820
おちつけ

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

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

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

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

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

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

どこまでが王道でどこからが邪道なのか、無用な線引きを脳内で作ってしまっても「勝ち」はないわけで
とりあえず中の人に明確化してもらいたいところだ。
俺はgcc43って指定してあるのにアセンブラ使用可になった時点で最早ルールなんてないもんだと思ったが。
826 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 00:33:09 ]: ごめん文が微妙に抜けてた

×そんなことをSPUで実際やれば56本固定で食っちまう。
○224要素くらいまでを割り当てるにしても、そんなことをSPUで実際やれば56本固定で食っちまう。
827 名前：202 mailto:sage [2009/01/24(土) 00:38:54 ]: >>825
別に、mt[] をいじるなとは言ってないし、一部の計算をメモリ上じゃなくてレジスタ上で
やるのは俺もやってる。

だが、>>579はそもそもMT擬似乱数の生成自体全くやってないように思えた。
mt[]を変形してMT擬似乱数を生成しているだけなら俺の勘違いだ。噛み付いてスマン。
828 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 00:41:37 ]: ネタばらししちゃうけど13切った奴はみんな部分的に8並列とか16並列とかやってるだろ？
spu_shuffle使ってパック・アンパックしてやってるだろ？
それがアリなら何でもアリだよ。

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

それが速いかどうかは別にして（っていうかcarryの計算が増える分速くない）
829 名前：202 mailto:sage [2009/01/24(土) 00:46:45 ]: >>828
ごめん、それ気づかなかったわｗｗｗｗ

てか、コンテスト参加者でまだ13cycle切ってない、これから頑張る人も居るんだから、
ネタばらしは止めようぜ。
830 名前：202 mailto:sage [2009/01/24(土) 00:51:07 ]: 俺は、 >>598 や >>601 でいってるとおり、まじめに genrand_int32() の戻り値を
計算した上でチェックサムをとってる。

乱数を複数のレジスタに分割するのはどうなんだろうな？
たまたま場所が離れているだけで、ビット単位では元の乱数を生成しているんだし、
別にいい気もするが、、、グレーだな。
831 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 00:58:17 ]: じゃあそのグレーな方法を使わせてもらうよ。

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

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

なあに、genrand_int32()の形式で要素を抽出するAPIを別途用意すれば問題ない
832 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/24(土) 01:26:29 ]: とりあえずストール地獄からの脱出に成功。
明日も出勤だけど>>824目指して頑張る。

ところで、
for (int i = 0; i < num_rand; i+=2) {
sum += genrand_int32();
sum -= genrand_int32();
}
とかやってみたらチート対策になったりしないのかな？かな？
833 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 01:27:20 ]: 俺はチートはしないよ
834 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 01:56:42 ]: init_genrand_mine を変更するなとは書いてあるけど、
init_genrand_mine で初期化されたベクタでテストするとは
書いてないわけだが。
835 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 02:00:54 ]: トランザム＝通常の3倍の性能
あとはわかるな？
836 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 02:00:58 ]: だんごいい加減ネタばれひどいだろ
13は切ってるけど、>>828の方法は使ってない
あんたが天才なのは結構だけど、コンテスト終わってからにしろよ
837 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 02:04:33 ]: 残念だがその方法には芽は無いようだ。
散々罵倒したけど彼には感謝しないといけない。

なあに、単純な理屈だったよ。
838 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 02:25:51 ]: Hack the Cell と見せ掛けて Hack the spu-gcc43、
と思ったら Hack the MT だったでござる。
839 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 02:32:37 ]: ツンデレ？
840 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 02:34:18 ]: おう
841 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 02:46:25 ]: このブレイクスルーは、ある意味でCellの特性を最大限生かしたものになる。
もちろんMTの互換性・再実行性も保障できる。

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

いや、それでも詰めるには必要だけど
842 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 02:48:32 ]: 実装するのと極めるのは別物だからな
843 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 03:01:18 ]: いいや、最後にはSIMDerだからこそできるテクニックがものを言うと思うよ。
844 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 03:28:16 ]: なんか色々台無しだね。>>321 の予想通りという事かね。
845 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 03:44:22 ]: どのみち最速で無い（愚直にmt[]を舐めるだけ）の方法は近々俺の日記で公開してやろうと思っている。

Fixstarsはなんでmt[]をvec_uint4との共用体にしといてくれなかったのか？
実はそこに答えがあったのだ。
846 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 03:49:22 ]: >>845
既に気付いてる人間からしたら、滅茶苦茶迷惑なんですけど。
847 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 03:50:25 ]: おいおい
あんまりいらんことするな
12サイクルに到達してない人間の努力は全否定か
ついでに10倍速で参加賞出さなきゃいけないFixstersの身にもなれと
848 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 03:55:15 ]: >>847
10倍到達した人が多い場合は上位からってルールがあったはず
どのみち優勝不可能なコードなんだから文句無いだろ？

俺がやらなきゃどうせ上位者（BSDライセンスでソース公開）はアセンブラばっかしのコードになるんだろ？
アセンブラのコードなんて公開されてもソースの再利用性という面では意味が無いんだよ。
高速化のテクニックを、アイディアを再利用性の高い形で世に出す必要がある。
俺は俺の信念で、アセンブラ許可したFixstarsをこき下ろす
849 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 05:55:21 ]: アセンブラ無しなら自分が最速で、もっとも優れたテクニックやアイディアを持ってると思ってるあたりが痛いよな……
850 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 06:14:29 ]: 新しいコードだとTempering相当処理は0.5命令/Word切った。
別のところが増えちゃってるんですけどね。

言ったろ？トランザム発動するって。
851 名前：,,・´∀｀・,,）っ-○◎● mailto:ということにしておきたい sage [2009/01/24(土) 06:48:26 ]: すまん、黙っておく。
実は何も思いついてません。ﾋﾋﾋﾋﾋ
852 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 07:47:25 ]: 土日でエネルギー使い果たして失速するんですね、分かります
853 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 07:53:17 ]: ホント今回「も」呆れる。団子痛すぎ。
でも今回は珍しく本人が非を認めたから許す。
もっとやれ。
854 名前：557 mailto:sage [2009/01/24(土) 08:00:42 ]: 本当に迷惑するから公開はやめてくれ
何故そんなことをする
855 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 08:04:54 ]: じゃあ締切後に公開するよ。
どうせ提出しないコードだ。
856 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 08:22:01 ]: >>848に述べられているところの必要性から公開するというなら
まずはフィックスターズに直接文句言ってくれよ
その後でコンテスト終了後に非アセンブラのコードを公開すればいい
それによってあなたの言う「再利用性」の要求は達成されるのでは？

確かに再利用可能なコードとアイディアの公開は必要な要素だと思うし賛同するけど
別にコンテスト中にそれを行って競技を潰さなければ達成できない目的ではないと思う
純粋に自分の信念から公開に踏み切ろうとするのならば、理解して欲しい
また、そんな可能性は無いとは思うが悪意や自己顕示欲からそれを行おうとするのは止めて欲しい
そんなことは分別のない子供のすることだし、恐らく貴方は子供ではないので。
857 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 08:24:13 ]: >>855
あ、そうなのか。ありがとう
必死こいて>>856みたいな長文書いたのが恥ずかしい
気分を害してしまったら申し訳ないです
858 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 08:35:03 ]: まあ、コンテストの上位を狙うにはどっちにしろ「役に立たない」と思うけどね。
公開予定のコードはもう開発凍結するよ。

無駄だとわかったことはやらない。
859 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 09:34:56 ]: 無駄でも挑戦するのがロマンだろ?
まぁ、コンテスト潰しはお勧めしない。
# 今回については、「もっとやれ」とは思わなくもないがw
860 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 10:48:45 ]: まあ万人にフェアであるべきだよな
861 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 12:11:49 ]: >>848
>俺がやらなきゃどうせ上位者（BSDライセンスでソース公開）はアセンブラばっかしのコードになるんだろ？
>アセンブラのコードなんて公開されてもソースの再利用性という面では意味が無いんだよ。

痛いやつだなｗ
参加者全員がソース公開の許可をしているんだから、運営側の判断で
全員のソースコードが取得可能になるとか、最速のコードの他にも十分早くて可読性の良いソースが
公開されるとかも可能性もあるだろ。

>高速化のテクニックを、アイディアを再利用性の高い形で世に出す必要がある。
これも大事だが、他の参加者が”自分で考えて”スキルを磨く事も大事なことだろ？

おまえが凄いのは認めてるやるから、人の”考える”楽しみを奪うなよ。
862 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 16:32:27 ]: ＞全員のソースコードが取得可能になるとか、最速のコードの他にも十分早くて可読性の良いソースが
＞公開されるとかも可能性もあるだろ。
おめでたいこって。

＞おまえが凄いのは認めてるやるから、人の”考える”楽しみを奪うなよ。
考える能力の低い奴に限ってそう言うよね。
充分能力があるなら、目の前にゴールへの地図があってもその過程を楽しむことができるのに。
863 名前：579 mailto:sage [2009/01/24(土) 16:44:32 ]: >>838
俺は最初から Hack the MT だとおもてたよ。

真面目に乱数列を生成する方法については、IBM か SCE が最速のコードを
(しかも証明つきで)持っているのではないかと思えるわけだ。CELL の設計を
する際にそのくらいの検討はしているだろう。

それから、これは当てずっぽうだけれど、Folding@Home の乱数も MT では？
だとすると、SCE は広告費を掛けて最適化しているはず。勝ち目ないね。

ならば、C だけで(SIMD 使わずに)最速だしたら面白いんじゃね？と思った。
実際問題、それを行うには「課題」をかなり曲解しないと無理なわけだが、
そこは数学屋と物理屋のスタンスの違いであるわけだ。

最初はそう思っていたけど、興味が変化したのは良くも悪くも >>628。

数学は演繹の学問。全ては真実であると証明されたことから導かれなければ
ならない。という意味では、
>→「あり得ない仮定を持ち出す」これは詭弁の○○箇条にもあったな
この指摘は正しい。

片や、物理は帰納の学問。全ては観測に基づく。もっともらしいと評価された
「事実」は、それを反証する観測がなされない限り「事実」であるとする。
そして時には妥協もする。物理屋は、「ありえない仮定」はよく用いる。
「仮想仕事」言葉くらいは聞いたことあるだろ？
864 名前：579 mailto:sage [2009/01/24(土) 16:45:31 ]: 数学屋と物理屋、どちらが上だ下だと論じるつもりは毛頭ないが、>>628 で
自ら「算術師」と名乗り、人を「さんすう屋」と呼ぶ「団子」に興味が移った。

「あり得ない仮定」が「あり得ない」とするのは、団子の「仮定」でしかない。
この仮定は、演繹の学問としては正しい方法ではない。

だから、>>713 でその仮定が間違えていることを証明した。それでも団子は
「机上の空論」といって譲らない。

ここで完全に興味を失った。

団子という人物を知った気になっていた。「数学屋＞さんすう屋＞＞＞算術師」
という事実が「観測された」と思っていた。

が、ここに来てどうだろう。最近の団子、俺と同じこと言っていないか？
つまり、最初から俺は団子に乗せられていたんだな。

完敗。

コードは団子同様、締め切り後に公開することにするよ。似たようなロジックで
SIMD 使われたら勝てる気がしない。

ごめんな。
865 名前：579 mailto:sage [2009/01/24(土) 16:59:59 ]: >>820
>メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。
mt19937ar.c は、線形合同法で生成した最初の種からしか数列生成できないだろ？
課題としては、mt19937ar.c と同じ数列が生成できれば良い、と読める。
だって、mt[] の初期値を投入する関数削除されちゃっているんだもん。

>>834
init_genrand_mine() の内容を勝手に変更されたら、それは mt19937ar.c が
生成する(できる)乱数列じゃないよね。そんな風にルール変更されたら
それこそアンフェアじゃないかい？

それから、任意の数だけ生成した乱数列の合計が計算できるということは、
任意の箇所で生成される乱数を計算できる(num_rand - 1 で計算した合計を
引き算すればよい)。つまり、「乱数列が生成できる」のと同じ意味になる。

そして、コンテストは sum を計算する速さで競う、と書いてある。

>>825
>乱数なんて所詮擬似的なモノです。
まさに。

そして、擬似乱数は「使う側」の資質も問われます。
今回は、「合計を計算するために」擬似乱数をつかった。
それだけの事だ。

>>830
ある程度真面目に計算するにしても、水平加算は最後の1回だろ？
866 名前：579 mailto:sage [2009/01/24(土) 17:29:39 ]: >>837
>残念だがその方法には芽は無いようだ。
>散々罵倒したけど彼には感謝しないといけない。
>なあに、単純な理屈だったよ。

最後に捨て台詞吐いておくよ。

俺の発言には所々「嘘」が盛り込まれている。思考の過程で
「こりゃだめだ」と行き詰ったものな。

嘘を混ぜ込むのが団子の常套手段だろ？

そこを起点として少し考えれば、団子以外のやつは気づくと
思っていた。そして、団子は気づかないだろうと思っていた。

なあに、単純な理屈だよ。
867 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 17:36:51 ]: 俺は疑わしきは罰せよ、０か１かの代数ばっかし扱う畑育ちだから
数学記号とか読んでもモナー板専用の特殊文字の羅列にしか見えないわけで
最も愚かな解法で再実装してみてるが

各処理の演算コストモデルが完全に逆転してしまった。
マジでXORとシフトだけしかない世界だな
868 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 17:39:41 ]: > 俺の発言には所々「嘘」が盛り込まれている。思考の過程で
> 「こりゃだめだ」と行き詰ったものな。
ああまさに俺の常套手段だ
869 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 19:40:59 ]: なんちゅう厨房の会話だw
870 名前：202 mailto:sage [2009/01/24(土) 19:41:14 ]: 「同じ乱数列」が何を意味するのかは、Fixstarsに質問投げたから回答待ち。

>>865
>課題としては、mt19937ar.c と同じ数列が生成できれば良い、と読める。
うん、同じ乱数列を生成する速度を競ってるんだよね。
で、>>579の方法では、同じ数列を生成してるの？
「○○すれば同じ数列が取り出せる」というんだったら、○○も加えた時間を出してね？

>ある程度真面目に計算するにしても、水平加算は最後の1回だろ？
だから？
同じ乱数列を生成するのが課題で、課題を満たした上でチェックサムを取る順番なんて自由だろ？
871 名前：202 mailto:sage [2009/01/24(土) 19:48:05 ]: 何度も言うけど、課題は同じ乱数列の生成で、チェックサムはあくまでも同じ乱数列を
生成しているかを確認する手段に過ぎない。
デクリメンタが時間を計測する手段にしか過ぎないのと同じ。

>デクリメンタのオーバーフローを利用することは可能ですか？
>今回の出題の趣旨に反するので不可とします。

このFAQと同じ。
スタック解析してORIGINALの計算結果を探すとか、genrand_mine() を呼び出す前のデクリメンタの
値を書き換えるとか、 mt_kadai の動作に対するハックは幾つかあるけど、それが今回の課題の
回答として認められる訳ではない。

乱数生成しないでチェックサムだけ計算しようとしてるヤツは、ネットゲームでバグ技見つけて、
「バグも仕様のうち」とかぬかしてゲームを滅茶苦茶にするタイプか？
872 名前：579 mailto:sage [2009/01/24(土) 20:05:22 ]: >>870
悪いけどな。

sum が計算できることと、数列が生成できることは >>865 に書いた通り
数学的には合同なんだ。

そして、mt19937ar.c の capability はかなり限られている。

>mt19937ar.c と同じ乱数列を生成してください。
つまり、mt19937ar.c が生成できない乱数は生成する必要がない。

仮に、>>688 のような評価方法が採られたとしても、最後の seed と mti
さえ保存しておけば、端数ぶんの sum をキャンセルして続きの sum を
計算すればおｋ。

もちろん、キャンセルするぶんのコストは掛かるが、num_rand >= 100000
とかいう条件を加味すれば十分にコストは回収できる。

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

俺が考えたチートは、全て課題を熟考した上でのことだ。

この段階で、mt19937ar.c の capability を変更することがあれば、それは
fixtars の勝手なルール変更であって、それこそ根本的なルール変更だ。

ごめんな。団子に入れ知恵しちまったのは俺だ。
873 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:06:45 ]: 優勝狙ってるならともかく、自分の好きな方法で好きに組めばいいじゃん

別に公的組織が開いてる大会ってわけじゃないから、心配なら純粋な最適化と数学的な方法の２バージョンだすとかもありじゃね？
ダメかもしれんが・・（確認は必要だな）
874 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:13:04 ]: 熱くなりすぎだ
回答待てば万事解決
流石にデクリメンタを書き換えてなんとかとは同列には出来んだろう
きちんと数学的に証明されたアルゴリズムを実装してるだけなんだから

それはそうと11.6まではいった
俺は当分もとのアルゴリズムのままで愚直に乱数列を生成しつつ10↓を目指して頑張るぜ
875 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 20:14:37 ]: >>871
逆に聞こう
mt[]のデータレイアウトはmt19937ar.cと完全互換である必要あるか？

mt[]の配列見て思ったんだけど、こうやりたくて仕方がなかったよ。

union {
　　　vec_uint vec[N/4];
　　　unsigned int scl[N];
} MT_Array;

#define mt MT_Array.scl

結局別の方法考えたんでどうでも良くなった。
それはさておき、何がやって良くて何をやったらいけないか？その線引きって誰がやるの？
あまりに固定観念に縛られすぎてるんじゃないかと？

＞デクリメンタのオーバーフローを利用することは可能ですか？

みたいな論外な質問だってFAQにあがってるんだし、何ができるかどうかは
聞いたらいいんじゃないの？
自分だけの無用な追加ルールを作ってしまっても損でしかない
876 名前：202 mailto:sage [2009/01/24(土) 20:16:35 ]: >>872
>sum が計算できることと、数列が生成できることは >>865 に書いた通り
>数学的には合同なんだ。
数学的に等価であるから何？これは数学コンテストじゃなくて最適化コンテストだよ？
同じ乱数列が作れるなら、実際に同じ乱数列を作って、その時間を計測して。

ただし、 >>579 はコンテストに参加しないらしいから、数学的な興味から課題とは違う解法を
見つけるのは別に問題ないよ。

でも、参加するヤツは、ちゃんと課題どおり乱数生成しようぜ。
877 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:19:26 ]: 回答どうなるかね。回答する側も悩んでるんじゃね？ｗ

プログラムの最適化を競う大会で、気が付いたら非常に高度な数学知識を持った人しか
上位入賞できないっていうのもなんだかなぁ
878 名前：579 mailto:sage [2009/01/24(土) 20:19:39 ]: >「同じ乱数列」が何を意味するのかは、Fixstarsに質問投げたから回答待ち。

本当にごめんな。今回のは、そもそもは fixstars の「設問ミス」なんだよ。
>>865 に書いた「擬似乱数は『使う側』の資質も問われます」はそういう意味。

この段階で設問を変更するためには、センター試験同様「全員に参加賞出します」
くらいの覚悟が必要。

例えば、「ウォール街のランダムウォーク」を仮定して「株ロボ」コンテストが
行われる。しかし、乱数生成は線形合同法と宣言されている。

もちろん、みんな線形合同法をつついたチートをするわけだ。そしたら突然、
「乱数生成を MT にします」。そんな感じ。
879 名前：202 mailto:sage [2009/01/24(土) 20:24:31 ]: >>874
たしかに>>579の考えた方法は、数学的に正しいらしいし、その方法を求められるのは凄いと思う。

でも、方法が凄くても凄くなくても、「同じ乱数列を生成する」という課題を満たしてない以上、
今回のコンテストの回答としては不適切だろ？
デクリメンタのオーバーフローと同列に扱って何の問題がある？
880 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 20:25:11 ]: 論理演算を最適化するためのブール代数学も数学の一つだよ。
「^ x ^」のアレだって数学的知識に基づくモノだけど、チートなの？

乱数を変形状態で生成したら駄目だなんて書いてないと思うんだぜ。
その辺の融通がきかないと、閉区間内の浮動小数を正規形でダイレクトに生成するdSFMTは、乱数じゃないみたいな話になっちまう。
881 名前：579 mailto:sage [2009/01/24(土) 20:25:37 ]: >>877
>プログラムの最適化を競う大会で、気が付いたら非常に高度な数学知識を持った人しか
>上位入賞できないっていうのもなんだかなぁ

たぶんね、
>>819
>テキトーに当たり付けたパターンを再帰で全部試す馬鹿な方法使ってるから
>最適に近い方法見つけるのに1ヶ月くらいかかる。
に書いてある通り。

クラスタ計算機持っているやつが優勝する。
俺はかなり妥協した。
882 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:28:18 ]: よし、Cellのクラスターをつくって勝負しよう！
883 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 20:31:41 ]: 【内輪話】
Twisted-GFSRのループ内で何かしら集計できるのはTempering後にMSBに相当するビット以外思い当たらなかった。
加算をXOR 1個で置き換えられるのはMSBしかないだろ？キャリーの計算とかめんどいよ。

んでもってUnslicingはTempering＋加算のサイクルに織り込んで一気にやっちまったほうがエレガントかつ速いと言う結論に達した。
SPUにはそれを高速にやるために有用な命令が存在する。
884 名前：202 mailto:sage [2009/01/24(土) 20:33:57 ]: >>880
>論理演算を最適化するためのブール代数学も数学の一つだよ。
>「^ x ^」のアレだって数学的知識に基づくモノだけど、チートなの？

「同じ乱数列を生成してください」という課題なんだから、間でどんな数学を使っても、
同じ乱数列を生成していればOKだろ。

> 乱数を変形状態で生成したら駄目だなんて書いてないと思うんだぜ。
変形の程度によるだろうけど、明らかに違うビット列になってたら、「数学的に等価だから
同じ乱数列だ」なんてのは詭弁に聞こえる。

> その辺の融通がきかないと、閉区間内の浮動小数を正規形でダイレクトに生成するdSFMTは、乱数じゃないみたいな話になっちまう。
いや、今回のコンテストとどういう関係があるのかぜんぜん意味不明なんだが？
dSFMT は同じ乱数列じゃないから、今回の課題の回答としては明らかにアウトだけど、
回答としてアウトだということと乱数であるか否かとは全く関係ない話だ。
885 名前：579 mailto:sage [2009/01/24(土) 20:35:28 ]: 残念だけど、数学的に「同じ乱数列」である以上は、どうあがいても
「同じ乱数列」なんだよ。

2 進表記 32 ビットで計数しても GF(2^33) で計数しても同じであるのと一緒。

もっと分かりやすく言うと、ethernet を情報が流れるときに変調される
わけだけれど、その変調によって値が変化するわけではない。計算した
乱数をレジスタに格納するとき、CMOS のキャパシタのポテンシャルに
変換されるわけだけれど、それによって値が変化するわけではない。

ついでに、極論すると MT は GF(2^19937) の「カウンタ」でしかない。
886 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 20:35:30 ]: おっと、「unslicing」の意味がわかってる人間はここには殆どいないか
887 名前：202 mailto:sage [2009/01/24(土) 20:38:47 ]: なんか、根本的にみんなと感覚が違う気がしてきたな。。。

プログラマとして、「同じ乱数列」という言葉を聴くと、「同じ (ワード|バイト|ビット) 列」という意味だと
解釈するのが当然だと思っていたんだが、数学屋は「数学的に等価」と解釈するのか？
888 名前：579 mailto:sage [2009/01/24(土) 20:40:38 ]: >>884
>明らかに違うビット列になってたら

ビット列で数値を表現する方法も、数学的に考えられた一つの方法でしか
ないんだよ。
889 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:41:23 ]: 仮に１０００番目の乱数を取り出してといわれたときに、オリジナルと同じ値が取り出せるなら同じ乱数列ってことでいいんじゃね？
890 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 20:42:41 ]: Tempering＋加算が爆速になったのはいいとしてGFSRの処理のほうがめんどいことになってる。なんとかサイクルを減らせないものか
ミスアラインロード・ストアがボトルネックになるのは結局同じだった。何かしら方策を考えないといけない。

>>887
BCDでも2進数でも浮動小数方式でも数値的に値を表してれば十分でないの？
データ構造なんて抽象化してナンボだよ。C++屋の考えだけど。
891 名前：202 mailto:sage [2009/01/24(土) 20:45:47 ]: >>888
そんなこと100も承知で、>>887のように解釈してるんだよ。
どっちの解釈を求められていたかは、公式の回答待ちだ。

とりあえず、暗黙の了解が違いすぎるのはよく判った。
>>579 とは絶対に一緒にプログラム書きたくない。
「utf-8で文字列返して」って言ったら、平気でutf-8をbase64エンコードして返してきそうだ。
892 名前：579 mailto:sage [2009/01/24(土) 20:47:33 ]: >>887
>数学屋は「数学的に等価」と解釈するのか？
数学屋も物理屋もプログラマも、目的のためには手段は選ばないと思うのだが。

例えにするのも憚られるが、IBM は契約書に書いてある以上の仕事は絶対に
しない。日本人的思考からすると、「もうこんな所と契約するか」と思う
だろうし、実際、俺もそう思ったけど、実社会では契約書に穴がある方が
馬鹿。それを認めないと、今のままの日本人的思考では、これから先、
日本は衰退する一方。

>「○○すれば同じ数列が取り出せる」というんだったら、
>○○も加えた時間を出してね？

逆に、これは意味がない。

フェルマーの最終定理が証明されたところで、それを応用できる分野は今のところ
見当たらない。しかし、それを証明する過程で得られた知見は何事にも代えがたい
大切なものである。
893 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:47:37 ]: 整数型の値を期待しているところでfloatで値を渡されるもの嫌だなｗ
１０．０も１０と変わらないとか言って
894 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:51:19 ]: ひとつの掲示板でこうなんだから、他にも同じようなことやっているやつがいるだろう。
結局、グローバルスタンダードは、そこになるのかもね。
895 名前：202 mailto:sage [2009/01/24(土) 20:51:43 ]: >>893
7進数でその数値を表した文字列を渡されるかもな。
896 名前：579 mailto:sage [2009/01/24(土) 20:51:47 ]: >>891

return "utf-8";
897 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:52:47 ]: まあ不満もあるけども
>データ構造なんて抽象化してナンボだよ。C++屋の考えだけど。
には100%同意だ
既定のインプットから既定のアウトプットを出してる以上文句は言えんとおもうね
元はと言えばfixstersが実装する関数をgenrand_int32と同じにしなかったのが問題なんだろうけどそれじゃあ速度は出ないからなぁ
それに定数時間じゃない以上まだ負けると決まったわけじゃないさ
実装レベルで出来ることだっていくらでもあるんだぜ？
まだまだきついが多分10サイクルは切れる
898 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 20:53:10 ]: >>893
返すのは整数型の「合計値」だろ？

MTで得られた疑似乱数値なんて今回の値では中間値でしかないじゃん。
どのみち中間値なんて公開する必要ないんだから、データ構造がどうなってるかは

当のオリジナルのMTは、得られる乱数がビッグエンディアンかリトルエンディアンかすら規定してないぜ。
899 名前：579 mailto:sage [2009/01/24(土) 21:05:16 ]: >>891
> >>579 とは絶対に一緒にプログラム書きたくない。

いや、マジな話ね。

そう言ってもらえるのは嬉しくて、「じゃ、後はお前に任せた」とかいって
意気揚々とハナクソほじっていると、締日 3 日位前に泣きつかれるんだよね。
勘弁してほしいのだが。
900 名前：デフォルトの名無しさん [2009/01/24(土) 21:09:48 ]: > 一緒にプログラム書きたくない。
の対象は今回のケースではfixtersの面々なんじゃないか？
FAQの"趣旨"なんて曖昧な表現で一体何がわかるってんだ．
fixtersは普段からこんな表現使って仕事してんのか？
契約書，仕様書にも厳密な記述無しで"趣旨"って書くのか？
901 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:10:47 ]: 面白くなってきたな
物事を様々な側面から捉える力ってのは大事だと思う
902 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 21:13:23 ]: Cellのスケールメリット上重要な位置づけだったPS3があの惨状なのに
Cellオンリーのリーディングカンパニーの時点で、どうやろなと思ってる。

決算報告書とか意味不明だし。
黒字なのか赤字なのかすら読めない。
903 名前：579 mailto:sage [2009/01/24(土) 21:14:41 ]: >契約書，仕様書にも厳密な記述無しで"趣旨"って書くのか？

ネトゲには「こちらが想定したのと違う方法で...」って書いてあるんだろ？
やったことないから詳しくは知らんが。

想定なんて、後付でどうにでもなる。

そんなレベルのコンテストだとしたら、始めから出る価値ないよ。
904 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:16:26 ]: >>875
おまえが捨てたやり方は全部公開ってか？
調子乗りすぎ。
905 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:20:27 ]: ,,・´∀｀・,,）っ-○◎●

このＡＡ、[ ´ ｀ ]の部分と[, ・・ ]の部分、どっちが目なんだよ？
前から気になってしょうがない。
あいまいな事をするなよな
906 名前：579 mailto:sage [2009/01/24(土) 21:22:30 ]: 579って、「こんにゃく」って読めるよね。
907 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:23:10 ]: >>902
面白そうだから決算書見てみたよ
当期純利益が34百万とあるから黒字だな

しかし大雑把な決算書だな
株式会社の要件満たすため、とりあえず出してるだけといったところだ
908 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 21:23:58 ]: ×リーディングカンパニー
○自称リーディングカンパニー

ｘ86とかTeslaとか手広くやります、とかなら俺も心揺れた
909 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:26:52 ]: >>906
こん　な　くそ　って呼んでた
910 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:27:13 ]: Cellは家電やゲームのほうだと微妙だが
スパコンの方だとかなり活躍しているじゃない
911 名前：579 mailto:sage [2009/01/24(土) 21:29:20 ]: 906 は 579 ではありません。

アナルコンニャクより。
912 名前：579 mailto:sage [2009/01/24(土) 21:35:09 ]: >>911 は俺だが、話を戻すとして。

>>877
>非常に高度な数学知識を持った人しか

プログラマという人種は高度な数学的知識を持っていたらいけないの?
数学的知識のないプログラマは、ただの奴隷だよ orz
913 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:43:42 ]: >>912
もちろん数学知識は必要だし、他にも英語やらいろいろ求められる。

ただ、今回のコンテストに話をしぼったときに、ｓｕｍの計算の数学的な解法にたどり着けない人に
入賞の機会すら与えられないのはどうなのって話。
まあ、参加者の半数が納得できるなら問題ないと思うけどね。
914 名前：579 mailto:sage [2009/01/24(土) 21:52:42 ]: >>913
Cマガ電脳倶楽部で、どれだけ数学的知識の差に泣かされたことか。
当時中学生～高校生。
915 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:57:32 ]: なんだ？
高卒が暴れてんのか？ｗ
916 名前：579 mailto:sage [2009/01/24(土) 22:05:11 ]: >>915
そうだね。高校は間違いなく卒業したよ。いやガチで。
お前が末期癌で担ぎ込まれたときの主治医が俺かも知れないけどな。
917 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 22:15:53 ]: SPUのアセンブラを自分で書くのが億劫（レジスタが多すぎて混乱しまくりんぐ）な俺が勝つには
極限られた人間しか思いつかないようなブレイクスルーが必要だったわけだが。

逆に、いつから「フォーマット」が決まった上でのアセンブラチキンレースになったんだ？
918 名前：579 mailto:sage [2009/01/24(土) 22:16:01 ]: お前が包茎手術をする時の執刀医が俺かも知れない。
が、そんなことはどうでも良い。

アイソトープを使う上で、物理屋諸君には大変お世話になった。
物理を理解する上で、数学屋諸君の知見は非常に役に立った。
シミュレーションを進める上で、松本先生(の開発されたMT)には
大変お世話になった。

その上で、今回の設問は、松本先生を馬鹿にしているようにしか
思えないわけだ。
919 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 22:17:38 ]: たとえば、Cellのパイプラインをよく回す最適化という点では、
なにもしていない579のコードが、他のよく最適化したコードの10倍速いとなったとき、
Cellとは関係ないけど、アルゴリズムを考えた579さん優勝～というのは、非常に変な話だ。
でも、実際に速いなら無視できない。特別賞でもなんでもいいからあげればいいかな？

579のコードで、しかもCell特有の最適化を多少してあったら、文句ないだろうか？
920 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 22:20:50 ]: そんなのは中の人が判断すること。けちつけるくらいなら精進しる
921 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 22:26:14 ]: >>919
ちなみに俺はCell特有と言ってもいい命令を駆使して再設計してるよ。
今まで全くつかってなかった命令だ。

逆に従来のやり方だとSSEでもできることしかやってない。
922 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 22:29:46 ]: >>921
再設計するのは勝手だが、大会終わるまで古い方法はさらすなよｗ
大丈夫だと思うけど、一応な
923 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 22:32:07 ]: >>922に一票
924 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 22:35:57 ]: 古い方法もブレイクスルー来たんだけどね。
今やってる方法がアリならこれもありじゃんって感じで。

晒しちゃうと手の内を一部明かすことになるのでやらない。スコアも一切出さない。
ただ一ついえるのは12とか13とかとは全く意味の無い数字になってしまった。
何もかも方法が違う。
925 名前：579 mailto:sage [2009/01/24(土) 22:40:25 ]: >>924

スコア明かすことは、そのまんま pmt[] のサイズを晒すことに
なっちゃうんだよねｗ
926 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 22:42:57 ]: >>925
あんま団子にエサやるなって。
めちゃくちゃ釣れやすいんだから
927 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 22:49:12 ]: >>925
そんなものは無いから。
おもっくそ泥っ臭い方法でやってるし。それこそSIMDのパワーにものいわせた頭の悪い方法で。

配列なんてレイアウトが変わったくらいでmt[]のサイズとほとんど変わらん
敢えて言っちゃうけど、160 qword分
928 名前：579 mailto:sage [2009/01/24(土) 22:57:54 ]: >>927
レイアウト変えただけで、mt[] とは等次元空間ですな。

そのやり方ができるのであれば、(演繹的には)それに越したことは
ないと思います。俺は自信なかったからチートしたけど。それとて、
fixstars に文句言われる筋合いはないけどな(帰納的には)。

脱帽です。
929 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:04:02 ]: 別に数学的なんちゃら考えなくてもだんごの言うくらいには命令減らせるよ
データレイアウトが思いっきり変わるから和を出すときは別として
乱数列を出す時に毎回展開とかやってられんけどな
930 名前：579 mailto:sage [2009/01/24(土) 23:09:03 ]: >>929
12 とか 13cycle の 1/3 まで減らせるの？
それとも、俺また釣られているの？

もう誰もちんじれない
931 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 23:09:22 ]: 全加算じゃなきゃ馬鹿らしすぎてやっとられんわ
しかしこの配列構造は大好きです
932 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 23:15:04 ]: というか>>929には気づかれたようだ
933 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:16:06 ]: 試算だとその方法でtemperingにかかるのはQWORD当たり大体0.6サイクルを切る位
残念ながらだんごよりは2～3割遅いけどな
俺はとりあえずもとの方法で最適化を続けるけど後はFixsters次第
934 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:17:13 ]: すまん
×QWORD当たり大体0.6サイクルを切る位
○WORD当たり大体0.6サイクルを切る位
935 名前：202 mailto:sage [2009/01/24(土) 23:18:07 ]: 俺も、Fixstarsの回答しだいでは両方出すかも。。。
936 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 23:21:52 ]: >>933
GFのほうを作り込んでるけどシャッフルによるパッキングのサイクル数を抑えられないので
トータルだと似たり寄ったりな性能になりそうな予感。

しかし最後の加算は美しすぎてアドレナリン出てくるぜｗｗｗｗ
937 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:30:08 ]: 579の思い置き去りの展開かよw
938 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:31:34 ]: 0.6は計算ミス
どうやら0.5位だなぁ
殆ど同じ方法かもしれん
939 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 23:31:42 ]: 当たり前だ。1割も理解してない。
力業 is Justice.
940 名前：202 mailto:sage [2009/01/24(土) 23:57:59 ]: やべぇ、俺もチートの方実装したくなってきた。
まだ12.5cycle切ってないんだが、、、
941 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 00:00:17 ]: チートじゃねぇ

【邪道】だ
942 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 00:09:26 ]: うーん。

3倍はﾌｶｼでした。サーセンｗｗｗｗｗ
943 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 00:40:32 ]: Fixstersから返事があるまでCell Challengeやろうぜ！
944 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:05:59 ]: 枯渇でストールするのは単なるバグなので、それを考慮してアセンブラチューン
するのはあまり生産的では無いね。90nm版のCellでしか発生しないんだから。
ま、90nm版以外を身近に手にする事は将来にも無いかもしれないけどね。(ｗ
945 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:11:05 ]: 散々罵って結局だんごも579の方法でやってるのか？
946 名前：202 mailto:sage [2009/01/25(日) 01:16:06 ]: >>945
ちがうよ、数学できない俺でもできる方法。
947 名前：202 mailto:sage [2009/01/25(日) 01:16:55 ]: ちがうか、だんごさんは2種類やってるのか。
948 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 01:21:16 ]: 3種類だ。
949 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:26:45 ]: >>984
579のやり方は机上の空論だって言ってたのは？
950 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:38:25 ]: 950
951 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 01:38:31 ]: 俺は都度擬似乱数の生成を行ってから加算してる。そこだけは拘る。
952 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:42:17 ]: 579に謝れよ団子
953 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 01:47:13 ]: 繰り返す
【俺は都度擬似乱数の生成を行ってから加算してる】

どんな方法にせよTempering前にサマリ求めるのがアリだとは思わないからな
954 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:51:31 ]: ありとかなしとか話題すげ替えんなよ
579はオツムがよわいとか能無しだとか言ってたろ？
机上の空論じゃなかったんだから否を認めろよ
955 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/25(日) 01:56:23 ]: やっと12clockになる方法思いついた。けど、そこから先のEvenを減らす道が
見えなくて困ってる所です。やっぱりレイアウト葬らないと壁を越えられない
のかなぁ…。

>>912
数学の教養が無くても、転職してから１．５週で数十万行の構造把握して、
そこからバグ率を低く保って行く位の事なら出来てますよ。

つーか、今日になって（マイルストーン一ヶ月前なのに）コアな部分の
動作変更するとか言い出す上司がいて、バグの対処諸々考えてたら頭が
回らなくなってきました。初回からコケないことを祈るしか無いですｗ
956 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 01:57:46 ]: 本物の頭の弱い子だね。
俺の意図とは無関係に本人が煽りだと思ってないわけでそれ以上は何も言うことは無いだろう。
「カード」そのものは彼が登場する前から用意してたものだよ。
957 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 02:00:59 ]: 否を認めろよ
ってくらいだからな
958 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 02:05:59 ]: 頭が弱いのを認めとくとして
>>俺の意図とは無関係に本人が煽りだと思ってない
ってどう有意味だ？いやまじめに。
959 名前：デフォルトの名無しさん [2009/01/25(日) 02:16:49 ]: 次
pc11.2ch.net/test/read.cgi/tech/1232817361/l50
960 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 02:23:21 ]: >>958
ようするに団子は本当はできるのわかってて煽ってたってことだよ。

よく恥ずかしげもなくそんな言い訳できるわ。さすが糞団子だな！
961 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 02:40:23 ]: GF(2)の解法が全然別物ということが判明したので俺も俺で思い過ごしだったということだ
962 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 09:57:55 ]: 拡大体
963 名前：579 mailto:sage [2009/01/25(日) 13:19:30 ]: >>949 >>952 >>954
今回は俺の負ということで、もう、ゆるして。

>>955
冬山の知識が無くても、入隊してから１．５週で一個中隊の編成把握して、
そこから致死率を低く保って行く位の事なら出来てますよ。

つーか、今日になって（三本木までもうすぐなのに）コアな部分の
編成変更するとか言い出す少佐がいて、凍死の対処諸々考えてたら頭が
回らなくなってきました。初回からコケないことを祈るしか無いですｗ

いかだ作って川を下るとか言い始めるんですね。わかります。
964 名前：579 mailto:sage [2009/01/25(日) 13:24:09 ]: ×三本木
○田代元湯
965 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:23:05 ]: うーむ、もはや何の話をしてるのかすら外野の俺には分からなくなってきたｗ。
966 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:25:08 ]: 八甲田山死の彷徨だろ
陸軍史くらい勉強しとけよ
967 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:32:29 ]: >>966
確かに、プログラマにはデスマーチの知識も必要だな。
968 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:35:35 ]: ああ、そういう意味なのか、やっと分かった。
（そういう比喩を持ち出した訳は）
969 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:36:20 ]: なんか、学歴厨と学歴僻み厨の争いみたいな展開だな。
正直、どっちもどっち。

数学や哲学が分からん奴は、勉強してから発言しなきゃ不毛だしただの馬鹿野郎。
頭の中の話を主として話をしてる奴は、とりあえず現実とのスリ合わせが下手な駄目人間。
970 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:50:22 ]: >579
MATRIX_Aの変更が重要なん？
971 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 19:54:16 ]: MATRIX_Aの変形って意味なら>>788の方法でもやってるね。

MATRIX_AとのXORはMersenne TwisterのTwisterたる所以だ。
ビット単位の行列問題に帰着すれば、なぜMATRIX_Aなのかわかるかもしれない。
972 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 20:04:30 ]: 拡大体云々はRSA暗号のクラックにも有用視されてる方法だな
ちょっとモチベーション低下気味なんで文献あさってるけど面白すぎる
973 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 20:30:21 ]: 早くFixstarsには答えを出して欲しいところだな
俺はどっちになっても続けるけど脱落する奴もいそうだ
974 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 22:45:03 ]: >971
そうじゃなくて、579が>>801-802で書いたのはMATRIX_Aを変えたMTと、彼の方法の速度比較じゃん。
(だからsumも変わってる)

オリジナルMTのsumを高速化するのは結局無理だったんじゃないの？と。
975 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 22:55:03 ]: Twist抜いたMTなんてMTじゃないですわ。
MATRIX_Aはビットストリームを改変する一種のsaltとして機能してるらすぃ

余談だが「Saltを加えたDES」（2chのトリップで使われてるcrypt(3)のそれ）は差分解読がやりにくいなんて
現役の数学者が言ってたよ。
976 名前：デフォルトの名無しさん [2009/01/26(月) 17:33:50 ]: ↑こいつ何者？
977 名前：デフォルトの名無しさん mailto:sage [2009/01/26(月) 18:24:59 ]: アイちゃん
978 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/26(月) 22:32:55 ]: とりあえず公式見解が出るまでコーディング作業はお休み。

>>967
デスマに巻き込まれるとゆとりが無い分行動が不安定になってくるんですね。
# ４日連続勤務時間中にFPSやってる上司とか見て発狂しそうになってますｗ
979 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/26(月) 23:19:02 ]: saltをとは何かを考える、
日本語でいえば「お塩学」
ファッキンライト

ﾃﾝｷｭｰ
980 名前：579 mailto:sage [2009/01/27(火) 01:09:23 ]: >>970
>>974
アナルに突っ込んだ行列が間違えていただけの話。
ハックtheアナルの結果でたから、再トライした結果がこれ。

ORIGNAL: sum=3c927c56, 20051002 ticks
MINE: sum=3c927c56, 480600 ticks
ORIGNAL: sum=2e987a4d, 28979324 ticks
MINE: sum=2e987a4d, 680855 ticks
ORIGNAL: sum=ef1b6aef, 21517023 ticks
MINE: sum=ef1b6aef, 573675 ticks
ORIGNAL: sum=eedd2516, 19761023 ticks
MINE: sum=eedd2516, 446886 ticks
ORIGNAL: sum=f7e967a8, 981473 ticks
MINE: sum=f7e967a8, 116481 ticks
ORIGNAL: sum=1f37a7db, 14592172 ticks
MINE: sum=1f37a7db, 365659 ticks
ORIGNAL: sum=c7d41f36, 20085705 ticks
MINE: sum=c7d41f36, 465866 ticks
ORIGNAL: sum=aa9d2e9f, 17899900 ticks
MINE: sum=aa9d2e9f, 495607 ticks
ORIGNAL: sum=8abd398a, 17074673 ticks
MINE: sum=8abd398a, 434344 ticks
ORIGNAL: sum=a374bd58, 415390 ticks
MINE: sum=a374bd58, 86607 ticks
981 名前：579 mailto:sage [2009/01/27(火) 01:09:50 ]: >>722
>ざっくりと pmt[] の最悪値を見積もり始めた頃から勝算はあった
>わけだが、解析結果を見ると想像以上に小さい。
大口たたいたものの、MATRIX_A 直したら、ごらんこのザマだ。
最後の評価なんて最低合格ラインの 10 倍満たしていない。

ぶっちゃけ、46KiB の制約に収まるかも怪しい。

SIMD 化すればまだ可能性はあるかもしれないけど、俺は燃え尽きた。
団子にはかなわないよ。悔しいけどな。
982 名前：579 mailto:sage [2009/01/27(火) 01:21:13 ]: >>978
上司の気持ちもわからんでもないな。

>>202 >>227 まだ若いみたいだから教えておくけど、開発の現場で
一番必要とされているスキルは何だかわかるかい？

ウンコみたいなコードを読み取るスキルでもなく、バグの少ない良質な
コードを生産するスキルでもない。

正しい日本語と、寛容な気持ちだよ。

そのうちわかる日が来るさ。頼むから、俺みたいなクサレジジィには
ならないでくれ。

"Der Alte wuerfelt nicht."
983 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/27(火) 01:25:37 ]: ん？シミュと実機じゃTick値の意味が違うのか？？？？？？
984 名前：579 mailto:sage [2009/01/27(火) 01:33:35 ]: 先週5日間連続＋今日1日、勤務時間中にLBPやっていた俺が言うのもなんだが。
985 名前：579 mailto:sage [2009/01/27(火) 01:35:14 ]: >>983
つか、PowerPC なんで。SPU への移植性なんて考えていないよｗ
tb_get(get_tbだっけ?)は /usr/include/asm/time.h からかっぱらってきた。
986 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 01:47:54 ]: 結果出してから大口叩けばよかったのに
987 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/27(火) 01:49:14 ]: びびらせんなｗｗｗｗｗｗ
988 名前：デフォルトの名無しさん [2009/01/27(火) 07:47:08 ]: 579の欺瞞によりダンゴさん始まったな
989 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 10:41:15 ]: >>988
まてまて、スカラと最適化済みベクタで差の出にくい
普通の PowerPC で >>980 だとしたら、SPU じゃさらに
４倍差開くと見ていいだろ。
>>287 >>288 の通りなんじゃねーの？
990 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 14:50:11 ]: >>989
PPC970だろ？ちょっとコードの書き方変えるだけでも差は出るよ。

ループはあまり得意ではなくて、タイトな部分があればアウトオブオーダで並列実行できるから
アルゴリズムレベルでたいしたことは無くてもそれだけで性能が伸びてしまうこともある。
991 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 14:53:04 ]: SIMD化で性能単純4倍と考えるのも愚かだ。
ミスアラインロードの連発で性能出ないことだってある。オリジナルMTがそうであるようにね。
テーブルも16バイトアラインしたら容量オーバーかもしれないね。
992 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 17:24:41 ]: そろそろ皆さんハッタリのネタが無くなって静かになっちゃいましたねｗ
993 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 17:39:59 ]: 10cycを切ることはありえない
994 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/27(火) 18:58:49 ]: >>993
ﾆﾔﾆﾔ
995 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 19:15:53 ]: >>981
ってかさぁ、１０倍満たしてないし、どうせ参加しないんだったら
コードさらしてみてよ。ハッタリじゃないんだったらさｗ
996 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/27(火) 19:39:44 ]: 「Hack the 579コード」のはじまりです
997 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 19:43:25 ]: 推測するに>>802はミスにより既約でなくなったんジャマイカ?
つか64ビット整数で処理したら速くならない?
998 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/27(火) 19:50:02 ]: >>997
実は、PPC970は64bit ALU×2で、かつAltiVecの並列演算できるユニット少ないから
ALUでやったほうが小回りが利いて速いことがある。
999 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 20:03:39 ]: よっしゃ!! 8.5 cycle 切った!!!
1000 名前：1000 mailto:let's transpose! sage [2009/01/27(火) 20:04:06 ]: 「Hack the ハッタリ」第２章 -> pc11.2ch.net/test/read.cgi/tech/1232817361/l50
1001 名前：１００１ [Over 1000 Thread]: このスレッドは１０００を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef