- 1 名前：デフォルトの名無しさん mailto:sage [2008/07/07(月) 08:55:08 ]
- 前スレ
Cellプログラミングしちゃいなよ2
pc11.2ch.net/test/read.cgi/tech/1183091522/
- 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 はコンテストに参加しないらしいから、数学的な興味から課題とは違う解法を
見つけるのは別に問題ないよ。
でも、参加するヤツは、ちゃんと課題どおり乱数生成しようぜ。
|
 |
