- 1 名前：デフォルトの名無しさん mailto:sage [2008/07/07(月) 08:55:08 ]
- 前スレ
Cellプログラミングしちゃいなよ2
pc11.2ch.net/test/read.cgi/tech/1183091522/
- 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() の戻り値を
計算した上でチェックサムをとってる。
乱数を複数のレジスタに分割するのはどうなんだろうな？
たまたま場所が離れているだけで、ビット単位では元の乱数を生成しているんだし、
別にいい気もするが、、、グレーだな。
|
 |
