- 1 名前：デフォルトの名無しさん mailto:sage [2008/07/07(月) 08:55:08 ]
- 前スレ
Cellプログラミングしちゃいなよ2
pc11.2ch.net/test/read.cgi/tech/1183091522/
- 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 ばっかなのか考えようぜｗ
|
 |
