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

1 名前：デフォルトの名無しさん mailto:sage [2008/07/07(月) 08:55:08 ] 前スレ Cellプログラミングしちゃいなよ2 pc11.2ch.net/test/read.cgi/tech/1183091522/ 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 ] すまん、黙っておく。 実は何も思いついてません。ﾋﾋﾋﾋﾋ

---

---

[ 続きを読む ] / [ 携帯版 ]

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