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

前スレ

Cellプログラミングしちゃいなよ2
http://pc11.2ch.net/test/read.cgi/tech/1183091522/

Cell Broadband Engine 技術情報公開
http://cell.scei.co.jp/

PLAYSTATION3 Linux Information Site
http://cell.fixstars.com/ps3linux/index.php

The Cell Processor - PukiWiki
http://cell.fixstars.com/pukiwiki/index.php

developerWorks : Cell Broadband Engine resource center(IBMのCell技術情報)
http://www-128.ibm.com/developerworks/power/cell/

Cell Broadband Engine Architecture forum (Cellプログラミングの掲示板)
http://www.ibm.com/developerworks/forums/dw_forum.jsp?forum=739&cat=46

Multicore Programming Primer: PS3 Cell Programming
(マサチューセッツ工科大学のPS3を使ったマルチコアプログラム演習。ソースコードなど有り)
http://cag.csail.mit.edu/ps3/

CellPerformance
http://www.cellperformance.com/articles/

一応たててみたもののスレタイみすった／（＾o＾）＼

>>1 乙。久しぶりに話題投下してみる。

あるshort値の配列があって、それをlog2()するような感じで指数が欲しい。
指数未満の値、つまり仮数部は四捨五入する。

また、マイナス値とプラス値は連続させて結果をコンパクトにしたい。
趣味で作ってるプログラムだから結果のフォーマットはこれ以外に変わっても構わない。
疑似コードで書くと、いまのところこんな感じの実装にしてある。

(short)round(log(abs(a))/log(2)) + (a > 0 ? 16 : 0);

で、これを最適化できないかなという話。
とりあえず2つ程考えてみたので貼ってみる。

vec_short8 log2_1(vec_short8 v) {
  static const vec_uchar16 vPack = (vec_uchar16)
  { 2,  3,  18, 19,   6,  7,  22, 23,
   10, 11,  26, 27,  14, 15,  30, 31};

  vec_short8 v1      = spu_splats((int16_t)1);
  vec_short8 v0x100  = spu_splats((int16_t)0x100);
  vec_uint4  vEven   = (vec_uint4)spu_convtf(spu_mule(v, v1), 0);
  vec_uint4  vOdd    = (vec_uint4)spu_convtf(spu_mulo(v,  1), 0);
  vec_uint4  vExpE   = spu_rlmask(vEven, -22);
  vec_uint4  vExpO   = spu_rlmask(vOdd,  -22);
  vec_short8 vExp    = (vec_short8)spu_shuffle(vExpE, vExpO, vPack);
  vExp = spu_rlmask(vExp + spu_and(vExp, 1), -1); // round
  vExp = spu_add(spu_and(vExp, 0xff), -126)
       + spu_rlmask(spu_andc(v0x100, vExp), -4); // sign
  vExp = spu_andc(vExp, (vec_short8)spu_cmpeq(v, 0));
  
  return vExp;
}

vec_short8 log2_2(vec_short8 v) {
  static const vec_uchar16 vPack = (vec_uchar16)
  { 2,  3,  18, 19,   6,  7,  22, 23,
   10, 11,  26, 27,  14, 15,  30, 31};

  vec_ushort8 v1     = spu_splats((uint16_t)1);
  vec_ushort8 vIsPos = spu_cmpgt(v, 0);
  vec_ushort8 vAbs   = (vec_ushort8)spu_sel(-v, v, vIsPos);
  vec_ushort8 vRound = (vAbs & ~spu_rlmask(vAbs, -2)) + spu_rlmask(vAbs, -1);
  vec_uint4   vEven  = spu_mule(vRound, v1);
  vec_uint4   vOdd   = spu_mulo(vRound,  1);
  vec_uint4   vExpE  = spu_sub(32, spu_cntlz(vEven));
  vec_uint4   vExpO  = spu_sub(32, spu_cntlz(vOdd));
  vec_short8  vExp   = (vec_short8)spu_shuffle(vExpE, vExpO, vPack);
  vExp += (vec_short8)spu_and(vIsPos, 16); // sign
  
  return vExp;
}

>>6
同時に32個以上突っ込めるなら後者の方が良いな

音声圧縮かな？

nop / lq
nop / shufb
csflt / shufb
csflt / shufb
nop / shufb
rlmaskbyte

とか妄想してみた

>>7
その心は？

>>8
鋭いです。
ところでそのコード、シャッフルが一回多いような気が。
アンパックx2、パック、後は何？

>>9
パック一回で十分だね

CUDA本格的になってなんたらエンジン窮地に立たされる

>>11
よくわかんねーよｗ

>>11
大丈夫、スパースエンジンなんて最初っから立場がないから。

Cell が GPU に敵う進化を続けられるかは別だが。

そもそもの HPC 的視点が、Cell は超並列プロセッサであり、GPU はハイパーSIMD/MIMD なわけだ。
それぞれに得意な分野があるから、どちらが滅んでどちらが栄えるという話ではない。


滅ばないとも言わないが。

実際問題、超並列プロセッサっていっても、ハイパーSIMD/MIMDと変わらないような用途でしか使ってないだろう。
プロセッサがいくつかあって、すごいことがいつできるんだ。LinuxがSPEに仕事割り振れるようにでもなればなあ。

ブロードバンドエンジンは内蔵されたホストCPUがPen4程度の低性能、
スパースエンジンは並列度が落ちた挙句にホストCPUが外付け。
某芝の目指す方向はどこなんだか。

>>15
> 実際問題、超並列プロセッサっていっても、ハイパーSIMD/MIMDと変わらないような用途でしか使ってないだろう。
俺には単に、GPU での処理に向いたアプリケーションの、並列コンピュータからの置き換えが、まだまだ進んでいないだけのようの思える。
そいういう意味で無いなら、俺の知らない分野のことを言っているようだから、教えてくれると有り難い。

つーか超並列はMIMDでしか作らない訳だが。

Cellプログラミングをやろうと思い
PS3にｘUbuntuをいれSynapticパッケージマネージャでCell-sdkとbinfbinfmts-supportを入れました。
spu-gcc でhello world

途中で送信してしまいました

Cellプログラミングをやろうと思い
PS3にｘUbuntuをいれSynapticパッケージマネージャでCell-sdkとbinfbinfmts-supportを入れました。
spu-gcc でhello worldを表示するプログラムをつくりコンパイルをするところまではできたのですが

いざ実行してみると
spu_create(): no such file or directory
spe_create_single: Bad address
とでてしまい実行できませんでした。

いろいろ調べても見たのですがこれといった解決策も見つからず途方にくれています。
原因をご存知の方がいらっしゃいましたら教えていただけないでしょうか。

素直にfedoraかYellowdogにしれ。

レス有難うございます
ｘUbuntuだと結局Cellやるのには問題多いんですかね・・・
軽いって話を聞いたんですけど。無理そうならFedoraにしときます。

PS3で開発って辺りが結構無茶っぽい。
いいクロス開発環境ないのかねぇ。

SPU用のバイナリのファイル名が違ってるか作られてないのでは？
俺のとこはxじゃないUbuntu7.10だけど問題なくセルフ開発できてる

>>23
そうだよな
開発成果をＢＤまたは仮想ＢＤで出力する環境が欲しい

素直に一旦ゲーム屋に行けよｗ

>> 20
うちはxubuntuで上手く行ってる。24の指摘通りではないでしょうか。

>>24,27
レスありがとうございます。
はじめに実行したときcannot execute binary file と表示されたのでSPU用のバイナリが原因かもしれません。
それを解決するためにbinfbinfmts-supportを入れてみたのですが・・・解決にはなってなかったかもしれないですね。
SPU用のバイナリについて勉強不足であまりよくわからないので調べてみたいと思います。

SPU のは普通は直接起動できず，起動するのは PPU 用のバイナリ．
そこから spe_image_open と spe_program_load 使って load する．
さらに thread を 6つ創って spe_context_create, spe_context_run する．
SPU 用のバイナリを埋め込んじゃえば _open の方は要らない．
後，spu-gcc のオプションに -standalone を指定すれば，
直接起動できるプログラムを生成してくれたはず．

本当にSPUを活用したいなら、
使える立場にいるならSPURSとか、
MARS,Ctk,そのほかの
SPU自律カーネルみたいなのを立てて
それにジョブを投げた方が楽だよ。

仕事でやるんならそうだね

ftp://ftp.infradead.org/pub/Sony-PS3/mars
どうなんだい？

追記
ftp://ftp.infradead.org/pub/Sony-PS3/mars/MARS-GATECH-20080711-final.pdf

自分も是非感想を聞きたい。

誰かファイル操作についてのCの制御文？（printfのようなもの）知らない？
知ってる分だけ伝授してほしいです

>>35
スレ違い。

MARSってコンテキスト量減らせるだけ？

MARSでやれるようなことは、GPGPUだとたぶん無理だと思う。こういうことにこそ、Cellの強みがあるんじゃないかな。
実際どれだけ使えるようになっているのかが問題だ。

データの入れ替えには対応してないみたいだな。(まだ)

CPUの省エネ、後編(CELL、BG/Lを参考に考える。)
http://www.ne.jp/asahi/comp/tarusan/main190.htm

電力消費量的にLSはよいと。うまくつかえればの話だけど。


それじゃあ、キャッシュとLSを二つ持って、使い分ければいいのかとも思うけど、
２つの使い分けを把握しないといけないから、煩わしさが増えると。

「5年は追いつけないでしょう」──東芝が作るAVノートの新しい未来形・Qosmio G50の革新性とは
ttp://journal.mycom.co.jp/articles/2008/07/30/qosmio/001.html

通常
ttp://journal.mycom.co.jp/photo/articles/2008/07/30/qosmio/images/005l.jpg
supers engine
ttp://journal.mycom.co.jp/photo/articles/2008/07/30/qosmio/images/006l.jpg

これは結構いいな。

問題はノートでここまでの要求があるかだが

映画好きの人とか、結構、本気で欲しがるんじゃないか？
自宅で使うデスクノートとして。まあ、あくまでマニア需要かな。

でも、世間的に意外とこんなんで火がついたりとかありえそうな気もするが。

QosmioのSupersは直接いじれないらしから、すれ違いだけどね。

アプリは自作用のカードに乗らないから色々なメーカーに期待するって……
自作用カード出しても、エコシステムが回るほどアプリが出てくる思えないな。

Qosmio G50新兵器、SpursEngineがスゴすぎる件【前編】
http://ascii.jp/elem/000/000/157/157525/

NvidiaのGPUまわせば、SpursEngineいらないんじゃ…。

The Barcelona Supercomputing Center has a new prototype
to investigate the supercomputing of the future
http://www.bsc.es/media/1762.pdf

Roadrunnerを超えるCellスパコンができるらしい。

ついにベールを脱いだIntelのCPU&GPUハイブリッド「Larrabee」
http://pc.watch.impress.co.jp/docs/2008/0804/kaigai457.htm

Intel版Cellといろんなところで騒がれていますな。Cellとがちだけど、GPUとして
登場するところは大きな違いであり、？でもある。

そろそろCellも次世代のバージョンの詳細がでてくるだろうか。2PPE+32SPEがでる
っていう情報はでてるけど、それ以上の話はまだなくて、今まさに検討中なんだろう。

Sonyが腰が引け気味で、Toshibaが違った方向に進みつつあり、IBMはHPC路線で突き進んでいる。

また、PS3の状況は、次世代Cellに大きく関わってくるんだろう。PS3の状況はよくなりつつあるが、
まだ厳しそうだ。次世代に向けて動き出すときこのときに、今のような不透明な状況であることが、
次世代のCellに一体どう作用するか…。Sonyの求心力が弱まることで、よりIBM主導のアーキテクチャに
進むのだろうか？果たして…。

>>45
> Qosmio G50新兵器、SpursEngineがスゴすぎる件【前編】
> http://ascii.jp/elem/000/000/157/157525/
>
> NvidiaのGPUまわせば、SpursEngineいらないんじゃ…。

GPUでまっとうなC/C++使える日が来たらそうかもね。

MSが次のXBOXにLarrabee使うんじゃ

>>49
CUDAでいいんじゃね。

>>51
> >>49
> CUDAでいいんじゃね。

「まっとうなC/C++」というのはCUDAへの皮肉だよw
Cellの方がはるかに作りやすい。
まぁ作りやすい以上の動機があるからCUDAが使われているわけだけど。

三角関数も全く使えなくても、最適化が馬鹿でも、メモリ転送命令が低レベルでしか実装されていなくても、
それでもCellの方がはるかに作りやすいんですね、判ります。

超越関数使えるのは便利だわな。
それ以外のツッコミは的外れ。

超越関数なんて（細かい注文付けなきゃ）簡単に実装できるだろ？
何が問題なんだ？

そりゃハードで超越関数の演算器持ってくれてた方がうれしいだろ。

ハードウェアの超越関数ってスループットが5サイクルくらいなんでしょ？
4要素計算しても20サイクル、馬鹿っ速いじゃないか。

超越関数つーかsqrtがあれば十分だな。1/sqrtでも良いけど。

>>52
LSの容量制限でC++はやりにくかろう。結果的にCellもCUDAもそんなに変わらんと思うが。

>>59
そういうことはどっちもやってみてから言ってくれ。

どっちもCとちょっとの拡張で書ける程度だからねえ。書くだけならどっちもそこまで大差ないさ。
問題は最適化の段階だな。でも、これもコツを覚えて、そこそこの最適化でいいんならそんなには苦労しないと思う。
個人的な感想では、CUDAのメモリ周りの最適化がちょっと難ありか。Cellは最初からアラインメントとらないとそもそも
DMA転送できないようになっているから、あんまり考える必要ないが、CUDAの場合は、スレッドごとのDRAMへのアクセスパターンを
考えないと駄目というのが、う〜ん。あとshared memoryのバンクコンフリクトを考えないと、とんでもないことに
なるときがある。ここらへんを、コンパイラかハードでなんとかしてくれるといんだけど。

Qosmio G50新兵器、SpursEngineがスゴすぎる件【後編】
http://ascii.jp/elem/000/000/162/162488/index-3.html
円弧職人の夢がここに

ググってたらこんなんめっけた

http://www.ibm.com/developerworks/jp/power/library/j_pa-asmvis/
第 1 回 asmVis を試してみよう
http://www.ibm.com/developerworks/jp/power/library/j_pa-asmvis2/
第 2 回 パイプラインを最適化する

リードテック、東芝のメディアプロセッサ
「SpursEngine」搭載PCIe拡張カード
http://pc.watch.impress.co.jp/docs/2008/0910/leadtek.htm

（ﾟ�听）ｲﾗﾈ

いくらくらいになるんだ？

東芝、'09秋に発売のCell TVの高速映像処理をデモ
http://av.watch.impress.co.jp/docs/20080918/toshiba7.htm
45nmを積むんだろな。

次世代CELLは4PPE+32SPEか

368: 2008/09/22 22:10:38 RPIGcU63O [sage]
>>364
MACｵﾀｿｰｽですけど､次世代CELLのｸﾛｯｸは3.8GHz止まりです｡

> 6/10のｾﾐﾅｰ資料､もう少し掘っていたら次世代CELLについて言及した別のがあったす｡
> http://www-06.ibm.com/jp/solutions/deepcomputing/events/pdf/080610_Cell_Strat_JHC_Japan.pdf
> 　･従来型Cell/B.E.わ2009年に45nmﾌﾟﾛｾｽ化
> 　･以前のﾛｰﾄﾞﾏｯﾌﾟにあった2*PPE + 32*SPEの"PowerXCell 32ii"わｷｬﾝｾﾙ｡代わりに
> 　　4*PPE + 32*SPEの"PowerXCell 32iv"へ｡
> 　･PowerXCell 32ivの世代でPPEに手を入れる -> PPE' へ
> 　･同じくSPEわ"eSPE"に進化
> 　･ｸﾛｯｸも上げる､〜3.8GHz
> 　･その他PowerXCell 32iv世代の特徴わ､下記の通り
> 　　- 100% backward compatible
> 　　- PPE性能わ大幅向上
> 　　- SPEわ新命令追加以外わ現状並 (新命令ｾｯﾄを使用するｿﾌﾄわ大幅に性能向上)
> 　　- SPE間の通信ﾚｲﾃﾝｼ削減
> 　　- More on-chip memory (LS増量か?)
> 　　- ﾒｲﾝﾒﾓﾘｱｸｾｽの大域幅増強とﾚｲﾃﾝｼ削減

marsが微妙にバージョンUp

>>68
それ何時出るんだ？
何プロセスで作ったら現実的なんだよ。
んな金があったら、拡張ボードを出すか、現状のアレな点を修正した
マイナーアップバージョン出した方が良いと思うんだが。

拡張ボードってなんだ？
あれな点とは？

>>70
微細化が進んだら規模を拡大するのは当たり前の話。サーバ用のCPUなんだから。

それに従来のCellの改良版なら、既に製品化されてるよ。

>>68が出たらPS3みたいに不良コアをいくらか殺してくれて構わないから安く手に入らないかなあ。

ああ、初代 Cell.B.E は 90nm だったのか。
だったら、4倍増(+LS増量)+αならありえる話か。ごめん。

どちらにしろ、PS3 限定状態じゃ流行らんだろな。
Atom + GeForce の方がやりやすそう。

そりゃAtomの方が数は出るだろうけど、そもそも競合してないだろ。

ttp://www-06.ibm.com/systems/jp/bladecenter/hardware/qs22/

Cellの将来はSonyとIBMと東芝がそれぞれ違う分野での使い方を想定し
異なる開発計画を持ってるから、「どの会社の計画なのか？」を
指定しないと話がスレ違いしまくりなんだよな。

Sony:ゲーム機（PS3及びその後継）
東芝：家電（画像処理）＆ノートPC用コプロセッサ（SpursEngine）
IBM：ブレードサーバー＆HPC用CPU

BDエンコーダとか、BDエンコーダとか・・・

Cell触ってみたいな
仕事では絶対やだけど

>>78
仕事でSuperEngine触るかもしれん

そいつはSuperですね

helloworldプログラムを作ったのですが、実行させると。
spu_create(): Invalid argument
spe_context_create: Bad addressとでます。
プログラムソースはfixstarsのチュートリアルどおりで、
PS3にはFedora7、SDKは3.0を導入しました。
ここの>>20さんの質問とほぼかぶっているのはわかるのですが、解決策がわかりません。
>>24さんのいう、バイナリのファイルが違っている、もしくは作られていない場合はどうしたらよろしいのでしょうか？

>>76
> Sony:ゲーム機（PS3及びその後継）
SCEではなくSonyでなんでゲーム機限定？
音響も視野に入ってくるだろ。

ヒント: 事業部の壁

>>81
fixstarsのチュートリアルの3.2章にあるソース（PPE/SPE用）をコンパイルしたということですよね。
私の環境では、Fedora7 + SDK3(厳密には3.0.0.3ですが関係ないでしょう）、で問題なく実行できます。

PS3 linux上でmountを実行した際に、spufsはマウントされていますか？
Linux環境周りの問題のような気がします。

GT200とかLarrabeeとかのニュースもひと段落して、最近、新しい話がなくて退屈だ。
そろそろ、つぎのCellの話がでてきていいはずだよな。

初代Cellは出たころは、9コアをいきなり実現して、業界にそれなりのインパクト、影響を与えたと思う。

次のCellは2010年後半で36コアだけど、どうなるだろうか。

さすがに32個もSPEがあると、本質的に今までと変わってくることが出てくる。

まず、一番問題なのはメモリの帯域だろう。現状でも帯域は演算に追いついていないが、
そこまで厳しい要求があるアプリケーションばかりでないので、実用には問題ない。
しかし、次のCellではコア数増で、帯域不足がより問題になるんじゃないだろうか。

IBMはもちろんそこら辺は考えた上で設計してるから、解決してるのだろう。その解決の
仕方がどうやっているのかが聞いてみたい。

次に、性能のスケーラビリティは32SPEでも問題なく保てるのかどうかだ。
これはメモリの話とも関係してくることではあるけど。初代Cellでは8コアで
ほぼリニアにスケールするという話がよく聞かれ、Cellの一つの売りになっていた。
2Cellで16SPEでもスケールするなんて話もあったような気がするが、次のCellでは
どうだろうか。

これが、32SPEくらいまでだったらスケールしたから、32SPEに設計しました
とかっていうのか、もっと100くらいまでいけることを確認しているのか、20個くらいが
限界で、あとは別用途で同時実行してくださいっていうのか、非常に重要だ。

Cellのスケーラビリティがよいというのは、他の半導体メーカーも注目しているはずで、
30個ぐらいでも性能でるめどがあるとなったら、他も真似して追従したくてしょうがないだろう。
8コアくらいまでが実用の上限なんて話もあるから、ここら辺の見極めをしたいはずだ。
まあ、アプリケーションによるけど。でもMARSが32SPEで効果的に働くってなったら、ちょっと
いいんじゃないだろうか？

このCellのスケール性がLSのコヒーレンシを考える必要がないことが本質だったら、
次のCell、その次のCell(120コアくらい?)で、その効果が指数関数的に出てくるはず。
そうすると、LSの再評価みたいなのが起きてくるんじゃないだろうか。
このLSに相当するGPUのshared memoryはその先取りかもしれないし、もしくは
メニーコアの必然として同じアーキテクチャにたどりついたといえるのかもしれない？
まあ、スクラッチパッドなんて昔からあったから、そんなに偉いもんかわからないけど。

LSといえば、プログラマはみんな容量を増えることを、次のCellでは期待しているだろう。
Cellのスピードチャレンジで今年優勝した人は、LSの容量が本質的に計算の高速化
と関係するようなことをいってた。プログラムが楽とかいうことではなく。
LSの容量が許せば、SPEごとのローカリティの高いアルゴリズムに変更できることがある
というようなことらしい。

Cellがでてだいぶみなが人柱になることで、LSの容量はこれくらいあるべきというのが、
ユーザーからあがりつつある。LSの増加は当然トランジスタ予算を食うわけで、SPE数を増やす
ほうがいいのか、LSを増やすほうがいいのかの天秤につるして、次のLSの容量もきまるんだろう。

次世代のCellで面白いのは、競合するGPUが存在するなかでのデビューになり、Larrabeeとの競争は
激しいものになるだろうことだ。

PPE：3
SPE：21
LS容量：12MB
これくらいがいい。

>>84さん　ありがとうございました。
エラーの原因は>>84さんの記述どおり、spufsがmountされていなかったためでした。

mars1.0.0にバージョンアップ

とりあえずロックフリーキューで全部差し替えないとmutex大杉

SDK3.1
http://www-128.ibm.com/developerworks/forums/thread.jspa?threadID=231196&tstart=0

質問なんですが、SDK3.0を入れても、コンパイルエラーが出て、
gccはインストールされていませんとでたのですが、
どこで入手したらよいのでしょうか？

パスはちゃんと設定してあるのか? いずれにしても、cellプログラミングと関係ないじゃん。

何この態度でかそうな奴

お前が言うなｗ

Fedora9にSDK3.1とシミュレータをインストールしました。
SDK付属のeclipse上から、シミュレータを実行すると、カーネルを読み込んで
立ち上がったところで、コマンド入力待ちになり、先に進まなくなってしまいます。
何か設定しなければならない項目等があるのでしょうか？

コマンド入力待ちになるなら、コマンドを入力すればいいんじゃね?

Run→Open Run Dialog...ウインドウのTargetタブで、起動したシミュレータを指定すればいいですよ

http://www.ibm.com/developerworks/jp/power/library/j_pa-sdk31/

フィックスターズ、Yellow Dog Linuxの米Terra Softを買収
http://journal.mycom.co.jp/news/2008/11/11/052/

http://www.ie.u-ryukyu.ac.jp/~kono/papers/kono/2008/gongo-sigos2008.pdf
http://www.ie.u-ryukyu.ac.jp/~kono/papers/kono/2008/akira-vld.pdf
こんなのあった

>>102
ワラタ。Cellの開発に東芝の名前が無い。

Hack the Cell 2009に参加しようかな
ほんとに図書券もらえるならやる気出すんだけど

社員乙

レス早いな
結局図書カードじゃね？って話なだけだったんだが

応募したらHack the Cell 2008に参加ありがとうって言われたけどいいのだろうか

>>102
揚げ足だけど、一つの文章内でCell Broadband Engineの説明がSPEが7つとか6個とか書いちゃってる時点でアイタタタ。
統一取れてない上にPS3に限定しない一般的な説明としてはどっちも間違ってるw

PS3をOpenCV on the Cellとして
顔認識のサンプルプログラムを動かしてみたいのですが、
fixstarsの通りにインストールしても巧く動作しません。
（SPEが動いている気配なし）

http://cell.fixstars.com/opencv/index.php/How_to_Build

たぶんパスがちゃんと通ってません。
どなたか解決法を教えてください！！！

Hack the Cell 2009ってこれのことか。
cellプログラミングのコンテンスか
http://cell.fixstars.com/challenge/index.html

なんで>>107は2008に参加ありがとうって言われたんだｗ

学生と社会人で部門分かれてるけど・・
どちらにも当てはまらない場合にはどうなるんだ？

もりあがってまいりました。

最近Ｃ言語の勉強始めたばっかりだけど、Hack the Cellって参加して大丈夫かな？
ＰＨＰならかなり得意なんだけど。

でも、優勝しても一緒に海外旅行に行くような友人いないなぁ。

どーせなら ioccc で笑いをとれ

PHPが得意でCが出来ない人間ってオブジェクト指向とか知ってるのか気になる

Cellの知識っていわゆるトリビアだよね。

2年近く最先端でいられたのである意味役立った。

これ、家賃収入で食ってる人や無職でも参加できるんだろうか？
学生以外は全部社怪人部門ってなってるけど、会社名とか部署名とか必須項目を埋められないんだが。
素直に会社名「親の家」部署「自宅警備」って書いていいのか？

なぜおまえはそう卑屈なんだ
自宅警備員に誇りを持て

ＰＨＰならほんとかなり得意だよ
お前らのＰＣハックくらいは全然余裕
Ｃｅｌｌも多分簡単に使いこなせると思う

釣りは他所でやれ

>>118
あの登録フォームみてると「何らかの組織に所属してる人間以外は参加禁止」って風に見えるんだ。

http://www.amazon.co.jp/Programming-Cell-Processor-Graphics-Computation/dp/0136008860

>>121

自宅警備員代表としてがんばってくれ。
時間が味方をしてくれるはず。

俺はだめみたいだ・・ＤＭＡとか良く分からん

>>110
>社会人部門
>
>学生部門に該当しない人すべての方が対象となります。
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
>個人もしくは2名でのチーム応募が可能です。

少しは説明読めよｗ

Cell2 Broadband Engine
･ 3PPE (Power Processor Element)
･4.2Ghz
　･2 threads (can run at same time)
･L1 cache:32KB data + 32KB instruction
･L2 cache:512KB
･Memory bus width:64bit (serial)
･VMX (Altivec) instruction set support
･Full IEEE-745 compliant
･18 SPE (Synergistic Processing Element)
･4.2Ghz
･2 SPE disabled to improve chip yield
･1 SPE dedicated for hypervisor security
･256KB local store per SPE
･128 registers per SPE
･Dual Issue (Each SPE can execute 2 instructions per clock)
･IEEE-754 compliant in double precision (single precision round-towards-zero instead of round-towards-even)

PS4のｽﾍﾟｯｸ予想
http://www.edepot.com/playstation4.html

120%ありえない

>126
そう？ Cellに関してはそんなにぶっ飛んでもいない、
むしろ穏当な予測だと思うが。
PPEを3つも積むかはちょっと疑問だけど。

SPEのローカルストアはやはり256KBが限界なのかなあ？
アーキテクチャ上はもっと増やせるように思うが、
ダイの面積的に苦しいだろうか？

>>127
●Cell B.E.にeDRAMの大容量メモリ搭載の道も開ける
ttp://pc.watch.impress.co.jp/docs/2007/0216/kaigai338.htm

http://www.fixstars.com/company/press/20081119.html

SpursEngineのSDKの解説があるらしい

SpursEngineのイベントを東芝が来週実施、SDKの解説やソフト各社のアピールも
http://www.watch.impress.co.jp/akiba/hotline/20081129/etc_toshiba.html

XLC で行こう！: 第 3 回 いくらかの手入れはやっぱり必要
ttp://www.ibm.com/developerworks/jp/power/library/j_pa-xlc03/

ソニーからこんなん出てますな。
ttp://pc.watch.impress.co.jp/docs/2008/1205/sony.htm
ttp://www.ecat.sony.co.jp/business/video_production/products/index.cfm?PD=33164&KM=BCU-100

映像編集用機器扱いだけどどんな使い方を想定してるんだろうか？　OS別だし。
こういうのも悪くは無いかも知れないが、PC用拡張ボードの形で
メモリ（XDR-DRAM)をある程度積めてそこそこ安い奴を早く出して欲しい。

PS3よりもっとメモリがたくさん欲しいと思うといきなり100万円コースに
なるのはそろそろ勘弁してください。

>>132 いまいち、わからんなぁ・・・・・・
結局それって幾らぐらいのしろもので、どの程度の事まで手が回せるんだろう？？？

なんか、情報がどうでもいい事しかでてなくてなぁ。
たんなるPS3の在庫処分としてなんだろうか？

Cell派生のSpursEngineのPCIeボードが発売されているがSDKを年内に無料配布するそうだ
なんだSpursEngineか、と思ったらSPEの開発環境(eclipse)ごとの提供でデバッガも付くらしい
http://www.watch.impress.co.jp/akiba/hotline/20081206/image/sstod8.jpg
ホスト側(PC側)はVisual Studioで日本語ドキュメントも用意されるらしい
http://www.watch.impress.co.jp/akiba/hotline/20081206/image/sstod7.jpg
SpursEngineのボード自体が3万くらいだからPS3買えよって話もあるけどね

>134
SpursEngine搭載カードはいろいろ出てきたが、肝心のCell搭載カードは
いくら待っても出て来ないな（100マソコースのボッタクリCardは除く）

XDR-DRAM容量を256MBから1GBくらいまで選べてついでにDDR2-DRAMを
1GBくらい搭載できて5万から20万程度のカードがなぜ出せん？
もちろんインターフェースはPCI-Express x 16で。
冷却ファンはゴツイ物が要りそうではあるな。
RSXは使いようが無いんで要らない。

アマチュアプログラマの関心はもっぱらGPGPUに向かってしまうぞ。
あらゆる実験をすべてPS3上でやれってか？FixStarsさん。

http://cellbe-cygwin.cvs.sourceforge.net/viewvc/cellbe-cygwin/cellbe-cygwin/ppu-gcc-c%2B%2B-4.1.1-5.cygwin.i686.rpm?view=log

PPE側も含めてWindowsでクロス開発はできる状況になりつつあるんだけどね。

>>135
ごもっとも。PCにさせるということが、実は一番気軽な近い手段なんだと、実感させられる。
ゲーム機にインストールできるってのは、手軽そうで実はバリアがある。

Nvidiaはそこらへんを知ってか知らずか、かなり本気で環境出しているのがすごい。いくらサポート
がひどいとはいえ、WindowsPCで使えて、VCまで使える環境をそろえるだけで十分強力すぎる。
ひどい日本語とはいえドキュメントもそろえて、開発者用公式の掲示板も作って、やれることをやっている。

Cellはなぜ3社もあるのに、そういうのができないのか…。3社がねじれているからって気もするな。

nVidiaが必死なだけ

成果は出てる分マシだろ。

GPUで単精度で500GFLOPS出るビデオカードが2万程度で買えるご時世に
頑張っても200GFLOPS出るかでないかの代物に4万も出して買う奇特な人間もそうそういないからな。
SpursEngineだってMPEG2/H.264のエンコーダ・デコーダと既製ライブラリがあるからこそのもので
SPEだけだったらいくらSDK用意しても誰も食いつかなかったろうよ。
実際問題、リードテックのアレは食いつきがいいのかどうかは知らん。



言語処理系としてCUDAが優れてるのは、SIMDとマルチコアという概念をSPMDモデルにおける
スレッドの概念でうまく隠蔽してること。並列化言語としては非常にシンプルでわかりやすい。

最後の二行、残念ながら団子に同意。とは言うものの、スレ違いだなw

SCEはこれぐらいやってもいいんじゃね？
・PLAYSTATION公式ページで「PS3でできること」にLinuxのことをちゃんと書く
とにかく今だにPS3にLinuxをインストールできることがPS3ユーザーにすら知られてない。公式にアナウンスしないから。
サポート対象外の機能です、でいいから。「へーそんなこともできるんだ」と思ってもらったらそれだけで付加価値2万円分ぐらいアップすると思う。

フィックスターズはYDLのリリースに合わせてインストールDVD付きのムック本を出して欲しい。
定期的に。内容は毎回ほとんど同じでもいいから。そういうディスク付きのHOWTO本が出ないと新規ユーザーは増えていかない。
エンドユーザーが増えないとCellビジネスも加速しないよ？

東芝とソニーはCellパソコン作ってよOSはLinuxで。GPUはチップセット内蔵レベルでいい。グラフィックはSPEでやればいいから。ローコスト重視で、細く長く売るタイプの商品にして欲しい。

せっかくいいもん作ったんだから、どんどん前出していこうぜ。

nVidiaが頑張っている事もCUDAが良くできている事も同意なんだが
日進月歩で且つレンジの違うものにご時世とか言ってるのが痛すぎる。

Cellに未来があるかはともかく。

＞フィックスターズはYDLのリリースに合わせてインストールDVD付きのムック本を出して欲しい。

フィックスターズ（旧Terrasoft）としては有償サポートを売りたいだろうからこれは無いだろ。
ぶっちゃけ、【Linuxインストールディスクに広告付きの紙の束を売る商売】は今世紀始まって
2年くらいでビジネスモデルとして破綻した。

スポンサー不在というか、スポンサーに対する消費者不在。
Software Designみたいな硬派な雑誌とは違って、ノンサポートのLinuxのCD-ROM付録
楽しみにしてるのはせいぜい個人ユーザーくらいだった。
企業ユーザー向けのカラーを強めると、あくまでクライアントOSとして楽しみたい
個人が置いてけぼり食らう。はなから企業ユーザーはあまりついてきてなかった。
ルータとか仮想化ソリューションとか売りにしても消費者が付いてこないわけよ。
で、広告が取れないからどんどん薄く高くなっていった。

追い討ちをかけるようにブロードバンドやCD-Rが普及しちゃったから、雑誌で
買う意味もなくなっちゃった。
Linux Magagineのまつもとゆきひろ氏の連載は好きだったけどさ。
連載打ち切られてから買う楽しみもなくなったな。

まあPC雑誌全般に言えることだけど。
どういうわけかMac雑誌だけは根強い人気を誇ってる。あれだけは理解不能。


>>143
浮動小数の額面だけに注目した性能・コストパフォーマンスに関してはGeForce 8800シリーズ登場時点で
既に微妙だったよ。つまり初っ端から微妙。その上ゲーム事業がいまあの様だし。
厳密に言えばGPUでやれることはCellのSPEのそれよりも用途を選ぶしメモリの制約も厳しい。
だが言語処理系としてのとっつきやすさの面ではCUDAはそれなりには良いものだ。

要するにCellが訴求力弱いのはその辺だね。
まあ、OpenCLに対応したからっていまさらどうなるもんでもないがな。

PS3も日進月歩で価格落ちてくれれば良かったんだがね。2万円台くらいに。
最初から製造原価割れ。
更にダンピング規制法ができて、無茶な値下げができなくなった。
ソフトメーカーがついてきてないのにハード売っても仕方ない面もある。

最近のNVIDIAもハード先行の感はあるが、なにげに昔からゲームソフト開発に対する支援は手厚かった。
機材やライブラリの提供とかな。
メジャーなPC向けゲームタイトルには必ずNVIDIAの広告があるだろ？
CUDAでも同じように技術支援やってるよ。それこそ個人開発のソフトにまで。

一方でSCEはPS3向けソフトの無料体験版をダウンロード数に応じてソフトメーカーに課金とか、
あり得ない資金回収法を実施中。
そういうことは市場掌握して有無を言わせない状態にしてからするもんだ。
DSとかWiiとか360とか他に逃げ場がある状態でやってるからな。これでは逃げるばかり。
打算的な悪行は他にもあるが。
「PS3を中心としたCellベースのエコシステム」の可能性を自ら潰してしまった。

ムック本自体で儲からなくてもいいんだよ。
エンドユーザーを増やすことが目的だから。
エンドユーザーが増えればCell自体の知名度や注目度も上がってビジネスでの採用も増えるだろうし、
将来の社員の養成、技術者のレベルの底上げもできる。
だからフィックスターズはやるべきだよ。

これぐらいだなやってるの
ttp://www.playstation.com/ps3-openplatform/jp/index.html
ttp://cell.fixstars.com/ps3linux/index.php/MARS

OpenCLの策定にはIBMもかなり入っててCellに対応するっぽいから生暖かく見守ってる。

OpenCLが正式にリリースされていつでも使えるようになった後でも
CellだけリーズナブルなPC用拡張カードが出なくて、誰もCell用
OpenCLを使えなかったとしたらなかなか笑える状況だな。

Cellが生き残るかはアレだけどIBMのOpteron+Cellってのは悪くないと思う。
それぞれ得意分野が全く違うわけで。

理想的にはCPU+Cell+GPUになるべき。
そのためのOpenCLだと思うしね。
CPUでもDSPでもGPUでも同じように記述できて、簡単に切り替え/同時使用出来るようになってる。

当然得意分野が違うわけだからフローまで同じように記述したら性能は生かせないが、
同じ言語で記述できて、とりあえず動くいうのは大きい。

今AMDとSTIって仲間なの？

STI?
スバルテクニカインターナショナルとAMDが何か関係があるとは
聞いた事無いな。

>>150
>理想的にはCPU+Cell+GPUになるべき。
この理想っていうのは何に使うつもりなの？たしかに、GPUで得意なところとCellで得意なところが
補えるという意味では理想かもしれないが、そんな複雑なシステムを使おうっていう人や状況は
本当に限られていると思う。
計算機センターで、いろんな人に対応する共有計算機ならまだわかるが、そんなん使う人いるかどうか…。

ATIはAMDが買った。良い買い物だったと思うよ。

>>151の言ってるSTIってちょにー・とーしば（笑）・IBMのことじゃ？
45nmプロセスの開発で協力とか何とかがなかったっけ。

Sony Toshiba IBMの三社をまとめてSTIと略すのは初めて聞くな。

AMDとIBM(他にも何社か)が半導体プロセス開発
（特にSOIプロセス）でアライアンスを組んでるのは有名だが。

ttp://en.wikipedia.org/wiki/Cell_(microprocessor)

Cell is a microprocessor architecture jointly developed by Sony Computer Entertainment, Toshiba, and IBM, an alliance known as "STI".

ヘーヘーヘー！　初めて知ったｗ。

そういえばSTIは今回の金融危機でかなりの痛手を負っててリストラを余儀なくされてるけど、
MicrosoftとIntelだけはなぜか不自然なほど傷が浅いんだ。。。

IntelはAtom馬鹿売れだったからな。小さくて歩留まりもいい製品だから、数さえ捌ければ儲かる。

MSのVista不人気は今に始まったことじゃない。
ソフト事業自体、もともと利益率がすさまじいし。
十分な利益率で十分な労働者を雇えるだけの貯蓄がある。
日本企業だと任天堂がリストラ知らずなのと同じ。

Xbox事業が今期から黒字計上してるのも大きいね（累積だとまだまだ赤だけど）
ドル安は短期的には外貨稼ぎにプラスに働く。

しかし、STIでも
一番おいしいところはIBMが持っていくと。PC部門の売り時もうまかったし
HDDも・・・IBMはすげーよ。

/proc/cpuinfoのtimebaseってsysctlとかで読めないのでしょうか？

今更Cell用のコード書いてみたんだ
ttp://tripper.kousaku.in/20081217.html#p01

Hack the Cellの課題発表された
http://cell.fixstars.com/challenge/challenge.html

課題はメルセンヌ・ツイスタの最適化
使用SPE1基、LS256KBのうち210KBが使用禁止。

あんまり工夫のしどころが無い気が…

ttp://ftp.uk.linux.org/pub/linux/Sony-PS3/mars/latest/
バージョン1.1

>>164
もち団子さんに期待

まるでだんごのために用意したような課題
前書いてたしな
だんご入賞したら尊敬してやる

だが断る

さすが団子さん！

質問なのですが、Cell SDK のインストールされているFedora 9 にて、
SPE用のＣソースプログラム上からpthread_create関数でスレッド生成出来ますか？
要するにSPEのプログラムはマルチスレッドが出来るかどうかと言うことなのですが、
手元にCell環境がないので教えてください。

>>171
SPEで、まともなプログラミングができると言う甘い幻想はとっとと捨てましょう。
POSIXはおろか、C標準の関数でさえ殆ど使えませんから。

つーか、なんでスレッド生成なんて発想に?
そんなのは、PPEにやらせてSPEは計算に専念するのがCBEの基本ですぜ。

>>172
ある処理を行う裏側で、SPEからPPEに書き込むデータが50区画ぐらいありまして、
tag番号が32までしかないので、別スレッドでデータを送ろうと思ったのですが・・・。
データの配置を連続的になるように考え直したいと思います。

>>173
DMAタグをローテーションさせて転送させたらいいと思う

>>173
あ、裏側でか。
関数を交互に呼んで疑似マルチスレッド、かな。

そーいえばSPEで簡単なベンチマークとろうとしてtime.hがなくて吹いた

そりゃ当たり前だな。

パソコン上のCでtime関係の関数が普通に使えるのはPCが
ハードウェアでリアルタイム・クロックを持ってるからだ。
で、CPUから直接読める空間にレジスタを置いている。

ハードウェアのリアルタイム・クロックがなけりゃ
例えPCのCPUであってもどうしようも無い。

まあ使いたいのは時刻よりは時間計測なんだけどな
そこはSPU Decrementerうまく使って代用して欲しかったね
PS3のCellはベースクロックが79.8MHzだっけ
いちおうLinux上からはとれてるみたいだけど

たかだか数分しか計測できないDecrementerを上手く使えとか。

clock()でも実装しておいてくれれば楽なんだけどねぇ。
まぁ、所要時間計測はどっちみち環境依存するものと思っているから未だいいのだけれど。

>>164
ちょっと弄ったら4倍速くらいになった。
ここまでは当然として、締切ぎりぎりまで粘るかな

>>181
応募するには最低10倍速だな。さてさて。

>>182
実行結果見せてみ？ｗ
コードみせろとは言わない。

どっちかというとコードサイズ制限の中でどれだけアンロールするかっていうテーマになりそう

いやいや、俺は参加してないよ。応募条件だったか、入賞の条件かが、Fixstarsのサイトに10倍速って書いなかった？

>>184
SFMTをそのまま移植してる？

>>184
あれは生成式が別物だからそもそも使い物にならない。
しかし意外と並列化できるね。それこそアンロールしまくれば。
Makefileは弄っちゃ駄目だけど#pragmaは使っていいんだろ？

>>186ね

movdquみたいな気の利いたミスアラインデータを処理するユーティリティ関数がなくてうぜーと思いました
shufbですませたけど。

7倍までいけた。
コンパイラの指定とかあるの？俺が使ってるのはSDK3.1


IBMが出してるトレースツールでも使おうかな

乱数の種と生成する乱数列の長さを決めるseed_tableに含まれるデータは例です。 実際の計測時は変更する場合があります。任意の値で動作するようにしてください。
ただし、以下の二点は仮定して構いません。
- num_randは4の倍数
- num_randは10000以上


なーんだ、仮定して良かったのか

GCC4.3とXLCってどっちがはやいんだろう。俺はいろいろあってXLC派。

しかし、コンテストが2つもあるのにこの過疎りよう…。もうちょっと盛り上がっても
いいような気がするぜい。

GCC4.3の吐くコードはたまに神がかった最適化をやってくれるんだけどピーキーだな。
速くなったり遅くなったり。
最適化フラグの指定方法によって変わるから、1関数毎に細かく最適化オプションを指定していく必要がある。
これはCellに限らずだけど。

>>164
これの
＞使用SPE1基、LS256KBのうち210KBが使用禁止。

ってどこに書いてある？

あーなるほど、壊れるのか

>>193
もう一つのコンテストって何？

やべー俺優勝しちゃうかも

Cell Challenge 2009
http://www.hpcc.jp/sacsis/2009/cell/

こっちの方が〆切近いな

>>198
大丈夫、きっとみんながそう思っている。

劇的ではないものの、ちょっと弄ってみただけでも1割くらい平気で性能伸びるな

一個目、7Mticks切った。
だんごさんに勝てる気はしないけど、準優勝を目指す。

そこまでは軽くいけるのか。やっぱり。
俺も自分の変態テクニックがどこまで通用するのかはわからん。

本格的に壁にぶち当たったから使える命令がないか手当たり次第に探ってるところ。
収穫がないようならとりあえず提出一番乗りさせてもらうよ。
暫定だけどレポート書いちゃったし。

これ以上は時間かけても無駄かもと思っている。
マイクロ秒単位の勝負に持ってこられると正直きつい。いろいろ手抜きしてる部分が響いてきそう

>>203
なんかもう行き詰った。
>>202のあともいろいろやったんだけど、あれからどうしても 7M 切れない。
何を工夫しても逆に遅くなる。

アセンブラで書けば >>202 を超えられるかもしれないけど、そこまでする気力は無いや。
odd パイプがきついよね。 even パイプが add と shift だけでも受け付けてくれると助かるのに。

また7Mtics切れるようになった。
ループ一回をマクロにして十数個並べたりとか、お決まりだな。
こっちも、もうそろそろレポート書くか。

早く提出した方がいいとかあるの？？？

ないね。
考えて答えが見つかるモンでもないし

考えすぎて仕事が手に付かなくなるくらいなら諦めた方がいい。

7Mticsていうと30倍以上かすげーな
アルゴリズムは基本のままでそこまでいけるの？

>>208
アルゴリズムはそのままだけど、生成した乱数をチェックサム計算だけして直ぐに
捨たりと、実用性を削って速度を稼いでる。

いいこと思いついたぞ！
ビットスライスして処理すればいいんじゃね？




（混乱させようとしてるからあぼーん推奨）

ぶっちゃけCellって将来性はどうなの？
なんかPCのGPUでトリップ計算がCellの10倍の性能たたき出したとか
聞いたんだけど

45nmで32コア＋PPE2コアのCellが出てるね
自作の改良版Bitslice DESを使うと、PS3でSPE 6コアだけ使って12MTrips/sec程度はいける。
32コア全部使えば64MTrips/sec程度は出る



でもその32コアCellはアホみたいに高いおｗｗｗｗｗｗ

当分安くはなりそうもないしねぇ。

>>210
spu_sel() ?
もう使ってるよ (謎笑

7Mまで苦労したのに、「そこまでは軽く」とか言っちゃう人が、さらに速くなるのか・・・
ひょっとして6M切ってる？

>>202
ミスリードしているぞ。「そこまでは軽くいっちゃう」のはあんたのことだろ。団子は自分のことだとは書いてないぞ。

流石にヒントはやれん

>>214
当然

>>215
だんごさんは、 1/4 に ttp://tripper.kousaku.in/20090104.html#p01 までいってて、
1/5 に >>201 とかいってるから、 7M は切ってるハズ。

という前提の元に、 7M 切れた！ と言ったら、「そこまでは軽く」と返されたので、
6Mまでいってるのかな、と。
6M逝かれると、逆立ちしても勝てる気がしない。

32コア版も新型GPUも8〜10億トランジスタ、
ダイサイズは同じくらいになるだろ
歩留まり率はまあアレで同じとして、
SPEだけでも本当に5〜6GHzで動かせるならアドバンテージになるな
メモリ帯域も拡張しないとあんまり意味ないけど

メモリ拡張した際の端子数考えるとXDRも広帯域実装向けなんだよな

業界の問題児RAMBUS

>>218
それって本当？
じゃあ、32コアCellはGPUとトランジスタ資源は同じで、現行の周波数でも同性能になるの？

感覚的に、GPUのほうが単純な構造だから、同じトランジスタ数ならピークの性能はGPUが上かと思っていた。

もし同等なら、LSの容量の大きさが結構あるってだけで、Cellの強みはすでにあるよね。あと倍精度も上になる。
価格は全然だめだめだろうけど。

初代の改良ということで、LS1MBとか、SPEのスカラ性能アップとか、PPEの強化とか実現したら結構いいものになるだろうな。
でも、PPEが強化ぐらいしか現実的に無理だろうけど。

まあ、IBMのことだからそういう反省点はちゃっかりPowerに反映してくるだろうなと予測。

>>222
LSは256KBのままでその分SPE数を増やしてもらった方が嬉しいな。
LS増やしたら確実にSPE載せられる数減るし。

>>223
>>128

odd命令をeven命令に切り替えた。
というか、あの命令がeven命令だと知らなかった。
俺にも6Mが見えてきた。

spu-gcc43 に変更されてる ＆ FAQ追加されとる。

oddとevenの違いが分かってきて、何とか7Mtick切れた@gcc43。

# 課題の再提出って出来るんだろうか…。フライングしすぎて失敗してもうたorz

はやく提出して得することなんてあるのか？
フィックスターズからのスカウトでも狙ってるの？

つーか、何の意図があってspu-gcc43なんだ？
おかげで50倍超えたおｗｗｗ
なぜならオリジナルのほうが遅くなったから

spu-gcc43 にしたら、ORIGINALが遅くなって、40倍以上平気で出るなｗ

・・・よし、6M

再提出可になってる。＠FAQ
っていうおいらはリモート開発環境に scp できない次元で奮闘中。
みんな出来てんのかなぁ？？？

>>228
フィックスターズからのスカウトでも狙ってるの？

どっちにしろ再提出何度もできるなら、しないよりはした方が得だな

50倍超えたおwww
もう削れる気がしねぇ。だんごさんに並べてたら嬉しいな。

234=202

そもそもORIGINAL側がコロコロ変わるからなぁ
まあ、やることはコンパイラの機嫌取りの作業だな

次はCUDAに取りかかるかな

ところで顔と名前晒して表彰台に立つの？

ってか、社名も晒されるのかなぁ…

>>239
会社名で申し込んだのか？

さすがに必須項目で嘘書くのも憚られるっしょ。

どうせだんごの50倍とかフカシだろ？
なんだかんだ理由付けて結局は提出しないと見た。
コンテスト終了後にだんごがソース公開しなかったらフカシ確定

俺の中の人も本質を求める人間だ
たとえばさ、学生部門の優勝者って奨学金を年60万円もらえるでしょ。
社会人枠でたかだか42インチのテレビっていうか15万円相当のギフト券優勝狙うよりは、
より額が大きい学生枠で聞き分けのいい後輩に入れ知恵したほうが得

ってのは極論。しかし、特に勝つことには拘ってない。
ちなみに優勝候補は5x倍の圧倒的な性能をたたき出した上で既に提出済みって情報ならあるよ。
ビット演算の論理式レベルで最適化したレポートをひっさげて、ね。

＃だんごやさんのマイミクにガチのフィックスターズ社員さんがいます。今回の出題者かもね？

>>238-239はたぶんCell Speed Challengeのほうだろ。あれは大学・企業対決の意味合いが強いから当然だ。
フィックスターズのほうは会社の名義を書く必要がないので自宅警備員ですら応募可能です。

なんか心理戦になってるｗ
圧倒的な性能って、、、だんごさんも 5x倍でしょーに。

だんごさんが優勝候補でないとすると、俺は準優勝すらムリポだが、
一応50倍逝ったので終了後ソース公開するよ。

っていうかIPC上限考えれば論理式レベルで手を入れない限り限界突破は不可能

ちなみに「団子厨」は優勝云々以前に参加登録すらしてませんので。
偽名はまずいらしいからね。

2人までのチーム参加OKなの知ってた？
今回はだんごやさんではない代表名義で、実質俺だけでやってます。
優勝か準優勝になったらPS3を彼にあげるってことで手を打った。

っていうか、優秀者のコードはBSDライセンスで公開されることになってるから
終了後に公開ってのも無意味だと思うんだ。

アセンブリ出力と実行形式一式を暗号化ZIPでアップロードして
コンテスト終了後にパスワード公開するってのはどうかな？

で、みんなで pikazip challenge ですね。わかります。

おいらまだ普通に並列化しただけで１０倍の状態… orz
５０倍はしんどそうだなぁ。あ、今 gcc 4.1 なんだけど、
4.3 にしたらどんくらい違うんだろ? 4.3 のオリジナルって
何 ticks くらい？

4.3でやれ。

一番上が29Mticksくらい

何とか6MTick突破。spu_timing 見る限りもっと詰められそうな気もする…。
これからドルアーガの中継見て寝る。

>>228
今は3Dプログラミングだけに集中したいと思っていたりもします。

spu_timing ってなんですか？とググらずに聞いてみるテスト。

もっと画期的なモン使えよ
http://up2.viploader.net/pic3/src/vl2_092246.gif

>>252
ども。29M って事は、50 倍だとやっぱとりあえずの目標が 6M なのね。
いま、ちょっとやったら [email protected] にはなった。さっきは 20M。
さらに半減かぁ。だんだん最適化できる所が減ってきたなぁ。

アンローリングしまくったら遅くなって、アセンブラ見るとローカル変数をLSに読み書きしてる・・・
コンパイラがバカなのか、レジスタ128個じゃパイプライン詰められないのか、よく判らん。

5.6M切ったよ

うぁー、5M台増えてきたな。
みんなすげー。

現在確認されている5M台は、だんごさん、俺、>>227、>>258 と、リーク情報の提出者か。
提出者 = >>258 だったりしないのかな？

トリップ付けて、コードのコメントにトリップパスつけるという手もあるな。

団子先生(笑)と同じチームだったりします。

>>262
名前貸してPS3をゲットを狙ってる人か
>>247の書き込みみると，学生部門じゃなく社会人部門で参加してるのね


ところでCellチャレやってる人はいないのかな
ここ学生少ないんかね？

トリップで mt_mine.c の sha1sum 書き込んどきゃいいじゃん

証明する気など更々ないんだが

中の人は中の人名義で別の活動やってるからこっちの名前で技術的名声得ても何のメリットもないし。
だんごやさんとは所詮「記号」だ。tanasinnなみに退廃的な概念だ。
なによりでしゃばりすぎだ、だんごやさんは

>>264
一度トリップ付けたら、その後ソース改変できなくなるじゃん。

ん？？改変したらまた新しいの書き込めばいんじゃん？

>212
「45nmで32コア＋PPE2コアのCell」がどこかで発表されたの？
論理設計してみただけとか言う話じゃなく、試作チップくらい作られた？

検索したけど見つからなかったので差し支えなければソースを教えてくれ。

>>268
http://www-06.ibm.com/jp/solutions/deepcomputing/events/pdf/ibm.pdf

勘違いだった。投入は来年（2010年）ごろらしいよ。

今日と月曜休日出勤命令が出たと言うのに、こんな時間まで現実逃避して
しまって良いのだろうか…。

>>255
何この芸術的な画面。こっちは一画面分片側無しとか有るんですがｗ

>>258
ようやく追いつけた、けど次にやるべき事が見えてこない罠。

一番綺麗なところ見せてるに決まってるじゃんか。

Odd側でレイテンシ1なのはlnopかhbrだと思っていいよ。

5.6M切ったところに壁があるのかな？

なんで速くなったのかわかんねーが理論限界にまた一歩近づいた

>>273
1％上げるのすら絶対無理な境地に達した。

>>275
mjd!? 優勝候補ブチ抜けるんじゃない？
俺も準優勝以上目指して頑張ろう。

プライベートがゴタゴタしまくってて、せっかくの休みなのに殆ど弄れねー。

っていうかね

コアループの内側の片方パイプ側が全部隙間無く埋まっちゃって
これ以上どうしようもないんだよね

外側をどうにかするとかいうレベルでのチューンしかできない。

とはいってもTick数が10とか20変わるレベルなんだけど

優勝候補ってのはオレのチームに決まってるだろ

>>278
ちょｗ、>>243の優勝候補って団子さん自身だったのかよｗｗｗ

他人のスコアをリークするfixstars社員がいるのかと思ったよ。

っていうか>>271見て焦った
だが、普通無理だろっていう境地に達した

敢えて言う
spu-gcc43の特性見切った

>>280
のちの団子氏によると、ここが真のスタートラインだったという。

スタートラインに立ってる人間いくらいるんだろうな？
ループ内で片方のパイプ全部埋まってる状態なんだが。
埋めるのしんどかった。アセンブラ使わずにだからな。

というコメントを書き込み、団子氏はふと気付いた。
「アセンブラを使ったら…」

じゃあ質問してきてよ。
アセンブラ使っていいかどうか

っていうか変数おっかけるのめんどくせぇ

というコメントを残しており、
動機は未だに不明。
では、次のニュースです。

まさか、そこまで普通しないだろう。
そう、普通はしない。
しかし、Cellをいじる様な人種に常識は通用しないのだ。

今までなんとなく、心にぼんやりとあった、疑問が脳裏をよぎる。

"なぜ、MTの限られた最適化で、LSの容量も制限するという、こんなにもきつい制限の課題なのか。"

そう。実は要求レベルは、その領域にあったのだ。

スタート地点に立てた人間は、そうは多くない。しかし、そこまで行きついたものは確実に、"次"に気づいた。
だが、それらの人間とは別に、ごく一部、初めからその道を進んでいたものもいた。

そして、その先には、さらなる波乱が待っていた。

ってかさぁ、1 tick って何 cycle くらいなの？
そっから逆算すると、5.6 M の時って平均何 cycle / 32bit 生成くらい？

>270
納得した。

>>289
知ってるが、教えたくない情報の一つだなｗ

ヒント: cpuinfo

ちなみに、壁を超える方法も思いついたぞ。

１．先に実行されたはずのORIGINALの結果をレジスタから探してくる
2. チャネルに書き込めないなら、関数呼び出し前に保存したデクリメンタの値を
　　書き換える。

だれかネタでやってくれないかなｗ

>>289, 291
40cycle/1tickだろ。5.6Mだと3.85cycle/32bitくらいか。
最低限SIMD化したとして15.4cycle/128bit。
unroll効いてるとして16〜7cycle/128bitくらいか。
ホントにそんなんで出来るんか？？？

>>282
少ない方が100ぐらい空いてるので、全部詰められれば0.25MTickか…。
コンパイラが糞なら asm volatile を使って手動スケジューリングでも
しようかと考え中です。

>>292
while( spu_read_decrementer() < ~16384 ) rand();

SPU_Decrementerは内部的にチャンネル使ってます。

配列にマシン語記述ってのどうかな？

ありがちな方法だな。
いけないプログラマ丸出し

>>293
unrollするとってくだりからアレだが、そこまでの推測は正しいと思うよ。

15.4という数値がでてきたとすると、15cycle+0.4cycleで0.4がオーバーヘッドになる。
オーバーヘッドは1%くらいに抑えたいから、目標は5.51Mticksを切ること。
トップクラスはそのあたりにある壁にどこまで近づけるかというチキンレース中。

というところまで推測できちゃうから、みんなticks数は有効数字一桁しか出さなかったんだけど、
だんごさんが有効数字二桁の情報を出してきたのは、「cycle数で並ばれても壁までの近さなら
負けない」という意思表示かな。カッコイイ。

普段使ってるのと違うPCで書き込みしたらsage忘れた。スマソ。

＞unroll効いてるとして16〜7cycle/128bitくらいか。
これが意味不明なんだけどね。

アンロールしようが何しようが演算ユニットが増えるわけじゃない。
演算ユニットの稼働率をいくらまで詰めるかって課題なわけで。

っていうか
「15サイクル」って具体的な数字が出てきたけど、本当にそれでいいのか、そこから考えないといけない。

128bitあたり、15サイクルのスループットで済むと仮定して、オーバーヘッド抜きのスループットは5.47M切るくらい？でいいのかな？


えーと、絶望させちゃっていいかな？

【とっくに切ってるよ】
逆にどこに限界があるのかわからなくなってきたよ。

だんごに勝つにはtemperingの命令数減らすことを本気で考えたほうが良い。
そこから道が開けると思う。
アンロールしてタイミング詰めるのはそれからでも遅くない。

>>301
底知れねーな。でも大丈夫、その程度で絶望しないよ。
5.5Mを切る戦いに参戦する敵を増やしたくなかったから、>>297では>>293の数値をもとに話してた。
まだgccの吐くコードに翻弄されてるけど、5.5の壁の先の世界があることは理解している。

・・・でも、俺より先に>>227がだんごさんに追いつきそうなんだよな・・・
昨日一日物件探しまくって、良い物件見つけたと思ったら今朝「もう申し込まれてました」と連絡がorz
早く休日を丸一日使ってだんごさんと同じ世界に行きたい。

>>302
敵増やしたくないから具体的な話はしたく無いんだけどさ。
俺もだんごさんも>>227さんも、とっくにそのレベルで出来る事はやってる。
その程度では勝てないよ。

で、一位がこのスレからでるのは確定状態か

団子3兄弟

スレで情報をホイホイ書き込むような人がトップとれるんだろうか…

具体的な方法論は誰も公開してないんだぜ。
5M台叩き出してる人はアルゴリズムレベルでは殆ど同じコードになってると思う。必然的に。

あとは0.1パーセント単位のチューンってことになるわけだが
最後まで粘ったもん勝ちになりそうだな。

ってかさぁ、15cycle とかホントに出来んの？
ってか、みんなマジでこんなとこに書いてんの？w

とりあえず、良くも悪くもこのスレに書き込まれたことで、ここら辺の性能が
スタンダードになってしまったな。

まだ2か月近くあるしね。

こうならないと面白くないだろ？

ORIGNAL: sum=3c927c56, 294426736 ticks
MINE: sum=3c927c56, 5470853 ticks
ORIGNAL: sum=2e987a4d, 424726988 ticks
MINE: sum=2e987a4d, 7891991 ticks
ORIGNAL: sum=ef1b6aef, 312523179 ticks
MINE: sum=ef1b6aef, 5807115 ticks
ORIGNAL: sum=eedd2516, 290445788 ticks
MINE: sum=eedd2516, 5396877 ticks
ORIGNAL: sum=f7e967a8, 14386174 ticks
MINE: sum=f7e967a8, 267359 ticks
ORIGNAL: sum=1f37a7db, 214504754 ticks
MINE: sum=1f37a7db, 3985803 ticks
ORIGNAL: sum=c7d41f36, 295361550 ticks
MINE: sum=c7d41f36, 5488220 ticks
ORIGNAL: sum=aa9d2e9f, 259914712 ticks
MINE: sum=aa9d2e9f, 4829583 ticks
ORIGNAL: sum=8abd398a, 251182134 ticks
MINE: sum=8abd398a, 4667315 ticks
ORIGNAL: sum=a374bd58, 6118517 ticks
MINE: sum=a374bd58, 113731 ticks

このスコアをここに晒せるって意味を理解してくれ。

ちょっとそのソース晒してくれる？
嘘くさいから。

晒せるかボケ

あれからパイプラインの空きを半分くらいまで詰められたけど、
コンパイラが糞でどうにもならない状態。

.L9: ; メインループの先頭
lqr $81,mt+X
lqr $84,mt+X
lqr $53,mt+X
lqr $41,mt+X
lqr $47,mt+X
lqr $48,mt+X
lqr $59,mt+X
lqr $68,mt+X
lqr $24,mt+X
lqr $71,mt+X
lqr $113,mt+X
lqr $42,mt+X
lqr $43,mt+X
lqr $45,mt+X
lqr $46,mt+X
lqr $58,mt+X
lqr $55,mt+X
lqr $93,mt+X
lqr $104,mt+X
shufb $106,$73,$81,$127

>>312
数日前のスコアですか？

>>313
ちょｗｗｗそれはやりすぎだろｗ
>>312がスタンダードになってしまうｗ

>>312 なら追いつける自信があるけど、そっから先どこまで行ったんだろうね。。。

>>316
自信あるのかよ！
ハッキリ言ってなんでこれで性能上がるのか理解不能っていう（デ？）チューンをしてる

15clkが本当なら>>312は99％突破してるわけだが

虚虚実実ですなw

再提出上等
スコア更新する度にフィックスターズに送りつけてやるぜﾍﾍﾍ

このスレで期限前に最速コードを公開して、コンテストを無効化して、そして伝説へ…
なんてストーリーがあるのかなと妄想してたよ。2chっぽくさ。いやいや、全然勧めてないからやらないでね。

いや、でも、なかなか燃える展開だな。がんばれ、団子３兄弟。

58156364 / 4(SIMD) * 15(cycle) / 40(ticks) = 5452159.125 か。
だれか 15cycle の壁をやぶってくれw

temperingをテーブル参照で・・・


って、数十GBメモリが必要になりますよ

じゃぁ、それを計算で求めるようにしよう！！！

ってのはおいといて、おいらも>>312が視野に入ってきたかな。。。

9%→90%→99%→99.9$→・・・

ですね。わかります

>>322
だんごさんが15を破れることバラしちゃったから俺もバラすけど、
15は数日前にもう破ってるよ。
コンパイラの吐くコードがよろしくなくて、調整の時間が取れてないだけ。

>>325
99.9$ ・・・ 9000円くらい？

未だかつてこのスレでこんなにCellプログラミングが流行ったことがあっただろうか、いやない

きそう、この週末丁度暇になったのにPS3は会社のだから事務所に置きっぱなしだ……
尤も、半年以上放置しているから今更勘が戻らないけどね。

>>328
大丈夫、俺なんてCellプログラミングは初めてだ。
リモートの開発環境も用意してくれるよ。

・・・べ、別に誘ってるわけじゃないんだからねっ！
どっちかっていうとライバルが増えると困るんだからねっ！

>>326
切ったのは16（っていうか18）じゃなくて？

どうせ4要素毎にspu_addして最後に合計を水平加算してるっしょ？
加算はEvenパイプだよ。

あんまり具体的な話をするのは、１〜２人で参加という趣旨に反すると
思うよ。

>>328
Cell SDKはx86のLinuxにも入れられるぞ
シミュレータもある。

あー、呑んだ。酔っぱらった。酔ったまんま unroll にとりかかるぜw
>>325,326
おいら今 unroll してない状態で 16cycle だから、近いかなぁ、と。
>>330
18ってなに？ともあれ、なんとか even をあと一つ縮めたいよなぁ…
>>331
どうせおいら申し込んでないしー。ってか名前&社名出せねぇw

>>330
あれ、だんごさんに言われると不安になってきた。
あとで数えなおし＆理論限界の計算しなおししてみる。

>>334
ってか、even 15 切ってるのが居たら神な希ガス
>>322 に書いたけど、だんごさんも 15 は切ってないよ。
どれだけ論理限界(15)に近づけるかの勝負でしょ。
それか誰かが 15 を切るかw

あ、>>301 の 5.47M は間違いだと思われ

パイプラインの空き35位まで詰められたけど、理論性能の95%しか出てない。
>>312が99.6%出してる時点で勝てそうにないorz

>>312は2日前の成果。日増しに（わずかながらではあるが）性能は伸びてる

理論スループット15になる方法思いついたときは俺SUGEEEEEEEEEEって思ったけど
そこまでは案外みんな気づくの早かったな。

>>335
even? odd じゃね？ tempering 的に言って。
>>339
てっきり15サイクル切ったと思ったけど、本気で15サイクルのコードで
そのスコアを超えたのか。すげーな。

おいおい逆だ
http://pc.watch.impress.co.jp/docs/2005/0212/kaigai03l.gif

＞てっきり15サイクル切ったと思ったけど、本気で15サイクルのコードで
それは秘密。

ただ、部分的に式の変形はしてる。高速化のためにどうしても必要だった。

>>341
おおおおおおおお！
俺、v = mt[k] とかに //e って、 spu_and() とかに //o ってコメント付けてた！
恥ずかしー！

ど素人ですけど、ＣＥＬＬに悪戦苦闘してる方々に質問。
ＣＥＬＬのメモリ構成の扱いにくさって、将来ＬＳの容量が増えて
各ＳＰＵが特定の仕事に専心するようになったら、それほど
大きな足かせにならない気がするんですけど、どうでしょうか？
今はＬＳの容量が少なすぎて、頻繁に書き換えが必要だから超面倒だけど。
クタはそこまで考えて、ＬＳにしたんじゃないんでしょうか？

なんか書き込みがゲハ臭いから回答すべきか「帰りな」と言うべきか迷うが。
クタだけに焦点を当てるなら、PS3を設計している最中に「LSが増えたら」が無いのは考えれば分かる話だよな?

ほんとゲハ臭いなw
>>344
ここで Hack the Cell やるような人は扱いにくいとか思ってないんじゃん？
扱いにくいってなるのは、プロジェクトが大きくなって C# あがりの
へたれプログラマも使わなきゃいけなくなった時じゃないかな？
Hack the Cell やるような職人にとっては LS の容量が少なくて超面倒って
事はなくて(ちょっと面倒くらいw)、へたれにとっては LS の容量が増えても、
ヘテロだったり cache じゃなかったりの時点で超面倒なんだと思われ。
今だったら Larrabee みたいな方がいいに決まってるっしょ。

今だったら => 今から作るんだったら

LarrabeeってCell扱うのはマンドクセッと思ってる
ヘタレ（と言うよりPCのCPUのみ扱い慣れている）
プログラマに取ってはいかにも扱いやすそうに見えるが
キャッシュレベルで勝手に同期が取られる事を良い事に
ついスレッドのあちこちで頻繁に同期を取るプログラムを
書いてしまってそれがキャッシュ用リング？バスの帯域を
圧迫してパフォーマンスが出ないと言う罠に陥りそうな希ガス。

いいからゲハに帰れよ

>>348
何言っているんだか。まるでx86だけがPCのCPUみたいな言い方しなさんな。
つーか、LarrabeeとCellを同列で語ること自体がどうかしている。

>349
俺は残念ながら>344じゃないしゲハから来たわけでも無いよ。

>350
読解力無いね、アナタ。

しかし、今更ながら気づいたが現在、市場で売られている
PCのCPUはもはや、ほとんど全てx86なんだよな。

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

と言うかx86以外のPC用（と呼べる）CPUを思いつけない。

CBE

ふー、目標の 6M 突破。と思ったらすごい事になってんなw　5.47M ってwww
こっから先は spu-gcc43 の最適化特性との根比べっぽいなぁ… orz
っていうか最適化馬鹿過ぎw 不要な処理し過ぎ!! フルアセで書かせろ!!!!w

>>355
いっそマシン語を配列に書いたら？ｗｗｗ
SPUは厳密な実行属性管理とかしないから自己書き換えとか簡単に動いたりするよ。
実際問題オーバーレイって自己書き換えと似たようなもんだし。

いや冗談ですｗｗｗ

どうしても0.3命令くらいはオーバーヘッドが消えない。
15.3 * 100 /15 = 102 だから、2%がオーバーヘッドか。

コンパイラに99%以上の効率のコードを吐き出させるだんごさんは神。

>>355
ちょっと待ってろ、fixstarsにインラインアセンブラ使って良いかどうか訊いてくる。
だんごさんに勝つにはもうそれしかない希ガス。

>>358
おぉ！よろしく頼むっす！でもさすがにダメな気がするw
おいら今 1.66% のオーバーヘッドまできた。5.54M
でもなんか全然本質じゃない事ばっかでちょっと虚しい… orz

これからチュートリアル読み始めるんだけど、10倍くらいならいけるかな

5M台何人いるのか判らなくなってきたな。
5.6M切ってるのがこのスレに4人くらい居るのかな？

>>322,324 さん、fixstars社員ですね、わかります。

VISEO MDT243Wだったら2位も悪くないなと思ってるんだぜ。
ってか、42インチのテレビなんて使わねー
PCモニタとしてつかうにはでかすぎるし。

15命令切る方法思いついたかも知れない

うはｗｗｗｗ
みなぎってきたｗｗｗｗｗｗｗｗｗｗ





とりあえず目標修正

　　　　　　　　　　　　　　　　5Mな！

と思いきや、それをやるには spu_and が必要だから減らないんだなー

wwwwwwwwww

びびらせやがって！

いや、>>366 は適当に書いただけだってばｗ

試しにインラインアセンブラつかってみたんだけど、
asm("lqr $50, mt+16")
みたいにすると、コンパイラに怒られる。 mt+ って書式は使えない？

ちょっｗｗｗ
だんごさんに追い抜かれる！

インラインアセンブラ無しでどうやって5M超えようか

202 さんは現段階で抜いてたの？

たぶんね。15cycle は少し前に突破してる。 >>326
だれも気づいてないっぽかったから、その後は 15cycle前提で会話してた。

gcc43に行く手を阻まれて、理論値に全然近づけてないけど、>>316 の時点で
>>312 は抜いてた。

って事は、>>357 は本当は 14.3 ってこと？

>>374
それ、実は、アセンブラを自動生成する簡単なプログラム書いて、
その出力したコード（未テスト）のサイクル数の話。15はウソ。

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

んで、アセンブラ禁止された。
... 質問しなけりゃ良かったorz

というわけで俺だけ次のステップに逝く予感

アセンブラ禁止意味不明。最早 Hack The spu-gcc43 じゃん。

パイプラインを埋める方策考え直さないといけないな。

方策は・・・あるんだなこれが。

>>377 うまいｗ　まさしくそのとおりだとおも

これは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

多分、もう、次のステップはない。

Hack the spu-gcc 4.3 '09

優勝争いのステージに、いま、俺とだんごさんが立っている。
このステージを制するのは、俺か、だんごさんか、はたまた新たなる
チャレンジャーか！！！

我ながら恐ろしい。15clk/QWORDに対する実効効率99.74％の基地外スケジューリング
俺に勝てるかなククク

ヒント：最適化が糞なら、無効にすればいいじゃない

今更？

この課題説明でインラインアセンブラ禁止なら、
pragma も使用禁止でしょうな。

それって、なんてコンパイラハッキングゲーム?w

わっちもようやく>>282のスタートラインに立てたので一応報告。

ちなみに、何故かコンパイラの最適化無効にしたらコードの質が良くなってるし、
コンパイラとの戦いの意味合いの方が強いような気がするなぁ…。

ハッキングなどしてない

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

やべぇｗｗｗ笑いがとまんねーｗｗｗｗｗ

抜かれた・・・完敗だorz

ん？まだもう一段階いけたよ

5M切れそう？

ちがうか、5088682 が下限なんだな。

>>389
逆汗しないから、その実行ファイルうpして？

ﾆﾔﾆﾔ

>>395
優勝すれば公開されるんだからそのときに見ればいいじゃないか。
種も仕掛けもない

>>389
さっき98%超えたけどさすがにそれは神の領域だわ。

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)

途中で投稿してもうた・・・
http://cell.fixstars.com/ps3linux/index.php/
ここにあるプログラミングチュートリアルの演習３−３の回答で、SPEの個数を変えたいんですが
#define NUM_SPE * の*だけ変えてもだめですよね・・・
性能がどんなもんかみたいんですが…どの点を変更すればよいのかご教授いただけませんでしょうか

2のべき乗ならいいんじゃないの？
テキトーに言ってみるけど。

>>400
そこだけでいいと思うけど・・・
PS3なら個数は1~6までSPEが利用できる

>>389
SFMTより速いんじゃね？

>>401-402
ありがとうございます。
変更箇所はこちらであっているみたいですね
タイム関数を利用して処理時間を測定しても、逆にSPEを利用したほうが時間が延びてしまいます。
理論上ではSPE１からSPE4にしたら1/4になるはずですよね？
ppeのメイン関数にあるresultをかこって測定しているのですが適切ではないのかな
すみません、出力に要した時間を測定するにはどこが適切なのでしょう
http://cell.fixstars.com/pukiwiki/index.php?tips_timebase タイム関数はこれを使用しています

>>404
そもそもこの問題ってそんな大規模な数を計算してないから
下手にSPE増やすとデータ転送時間やらその他もろもろが増えて
逆に遅くなる可能性のほうが高いよ

そうですか…わかりました。測定するプログラム自体が間違いだったんですかｗ
性能を見るために適したプログラム・・・どっかありますかね？
探してみます。

質問です。
ＣＥＬＬとLarrabee ってどの程度性能差があるんですか？
大して性能差がないとしたら、仮にＰＳ４が出るとして、
ソニーがＣＥＬＬに拘る意味って、もはや無いのでは？
むしろＰＣの世界で主流になるであろう、Larrabeeに
切り替えた方がコスト的にも有利なのでは？

ゲハ板にお帰りください。

>>403
逆説的だけど、並列演算を前提にした場合、実はオリジナルのMTのほうが並列度の高い
（高くしないと性能の出ない）アーキテクチャに向いてるってのはある。

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

それに対して、対してSFMTは4要素（＝128ビット）の計算をしないとその次の4要素の計算ができない。
要するに依存関係があって、128ビット性能が出ない。
各命令のレイテンシが大きいとSFMTは相対的に不向きってことになるかもね。

× 要するに依存関係があって、128ビット性能が出ない。
× 要するに依存関係があって、128ビットSIMD演算を低レイテンシで実行できるアーキでないとが出ない。

つっこみたいんだが

どうぞ


今回の課題のMTはSFMTと比べてレイテンシを埋めるためのテクニックが使いやすいのは事実だよ。
っていうか誰かCUDAにSFMT移植してごらん？4論理スレッドしか並列実行できない悲惨なことになる。

いや、どっちも×なところになんだがｗ

○ 要するに依存関係があって、128ビットSIMD演算を低レイテンシで実行できるアーキでないと性能が出ない。

タイピングしすぎで腱鞘炎になりそう

>407
Larrabeeはまだ世の中に出ていないので誰にも分かりません。
性能比較は用途によって変わるので今、Cellが使われている用途に
そのままLarrabeeが使われたらどうなるかなんて仮定の話は
Intelの中の人ですら分からないでしょう。

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

流行るとしてもだいぶ先の話（10年先か20年先か？）

>>409
速さもランダム性も優れているなんて虫が良すぎるんじゃないかとは思っていたんだ。
ふつーなら、どっちかのはずだもんな。元がひどくない限りは。

99%超えたおー

http://cell.fixstars.com/challenge/faq.html#kadai4
> インラインアセンブラは使用してもよいですか？
> インラインアセンブラは禁止としていましたが、使用していただいて構いません。(1/15 更新)

中の人このスレ見てるな。

なんか、いきなり競争のルールが変わってしまったな。

いちいちルールなんて再確認しないだろうから、このスレ見てない人が可哀想だよな。

迷走してるな。
アセンブラレベルでCellを熟知してない人間にはチャンスを与えない試験に成り果てた。
コンパイルオプション変更許可しない意味が既に無い。

>アセンブラレベルでCellを熟知してない人間にはチャンスを与えない試験に成り果てた。
そのレベルの人には元々「勝つ」チャンスは無いと思います。
参加する事に意義がある。

アセンブラ許可自体は歓迎だが、こんなことをやると

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

と言われかねない。

>>アセンブラレベルでCellを熟知してない人間にはチャンスを与えない試験に成り果てた。
>そのレベルの人には元々「勝つ」チャンスは無いと思います。

202がんがれ、超がんがれ

>>425
いやいや、202は既に熟知「した」だろ。

うーん、確かにコンテストを始めてからルールを変えるのはなんだかな。
再提出のチャンスがあるとは言えど。

主催者はルールが変わった事をメールなどで周知徹底すべきだろう。

ちょ、許可になったのかよ！！

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

俺の2日間かえせーー！

まぁ、でも本当に Hack the spu-gcc43 になってたからな…
おいらも 4.1 だとうまくいった最適化抑制手法が、4.3 だと
使えなかったりして結構虚しくなってたからよかったかも。

敢えて言う。
今までのは全部Cだ。

あ、コンテスト終わったらでいいから、だんごさんがどうやって
最適化抑制してたのか教えてほしいかも。おいらがやってたのは
4.3 にしたら even にまで命令追加されて使えなかったっす。

どうせ、そこまでやるんならコンパイラオプションも変更可能にして
何でもアリアリの条件で競争させて欲しい。

>>432
インラインアセンブラ解禁=何でもアリだよ。
別のコンパイラで、別のコンパイルオプションでアセンブリソース吐かせて、
それをインラインアセンブラで埋め込めば良いんだから。

>>431
あ、even に追加されたのは、ori $n,$n,0 ね。
even に追加することねーだろ、って叫びたいｗ

あ、ごめん。
実質なんでもアリなら、本当に何でもアリにしてくれっていう意味ね。

>>434
ありすぎて困るｗｗｗ
ソース破壊しない命令ばっかだから、絶対いらないのにねー。

>433
うん、だからもはや意味の無い形式だけのコンパイルオプションを
いじるなと言う制約を外した方が分かりやすいだろ？

やるなら mt_mine.c だけオプション分離しないと、
オリジナルの速度とかテストベンチにまで影響が…

SPUのアセンブリ言語はちょっとだけ読めるけどあれだけのコードをまともに書ける気がしない。
うまく飼いならせばspu-gcc43こそ最強の高級アセンブラ

未だに 4.3 は飼いならし方がわからんす。attribute とかじゃないんすよね？

って、コンテスト前なんだから聞いてる場合じゃないかｗ
おいらは asm 行くけど、やり方が気になって気になって。
ちなみに 4.1 なら >>383 の率超えました!! 意味ないけどｗ

>>441
>>383は超えたところで意味が無い数字だぞ。
実は>>389もだけど

なんでそういうの黙ってられないんだろう。

俺SUGEEEEEEEEEE だからじゃん？ｗ

せめて締め切られてからにしたらどうかね。

締切後フカシだった事がばれて「俺参加してねーし」とか言いそうな感じ

ここらで擁護がきそうな感じ

いやいい加減うざいと思ってただろみんな

Cellプログラミングに関係してるだけマシだと思ってたんだけど、
ウザかった？
他になんか話題ある？

糞団子に餌を与えるのはいかがなものか。もそもそ。

>>446
それならそれでソースコード公開できるんだけどね。

行動とは裏腹に誰にも気づかれることもなく優勝するシナリオを望んでる。
矛盾してるな。

インラインアセンブラ版動いた。
効率はこれから詰めていくけど、とりあえず適当な詰め方でも98%行く。
デバッグが超面倒だった。

これからインラインアセンブラに手を出す人にヒント。
.balign 16
というディレクティブを使って、命令のアドレスを16byte境界にalignしないと、
Dual-issue ねらってた命令が全部single-issue になってしまう。
めっちゃ遅くなって、間違ってループカウンタ壊したかと思った。

今週末は２日間とも強引に休む事にしたんで、インラインアセンブラにでも
手を付けてみます（ちなみにVCの奴は経験有るけど、GCCの奴は初）。

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

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

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

>>439
gcc のコードを並び替えるだけで終わりような予感。

>>453
俺だって元組み込み屋だ。volatileの意味くらい知ってる。

でも、ひょっとしたら、register volatile vector unsigned va; とか書いたら、vaが適当な
レジスタに固定でマッピングされてくれないかなと思って実験してみたくなるのは判るだろ。

>>454
その道のプロの方でしたか。これは失礼いたしました。

> vaが適当なレジスタに固定でマッピングされてくれないかな
幾らハッキングが好きなゲーム屋だからと言って、割り込みから
メインスレッドのレジスタ葬るような事はやったこと無いなぁ…。

SPUのABI仕様書読んでみると面白いね。
vector型をメンバに持つ構造体も、レジスタ本数に余裕がある限りレジスタ上に展開できる。
これによって複数の返値を持つことができる。

SSE(VC++)だと構造体を返値にすると無条件でスタック返しになってたような。

高速化がこんなに楽しいものだとは知らなかった。
どんどん速くなっていくのは快感だね。

なんか手詰まりの予感orz

mt_mine.c:93: internal compiler error: Segmentation fault
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.
make: *** [mt_mine.o] Error 1

拡張アセンブラが腐ってたっぽい感じです。レジスタの待避まで手動でやれば
大丈夫になるのかなぁ…？

まさにチキンレースだな。
究極的には両方のパイプを埋めきるまでやるんだろこれ。

団子さんは今どんなスコアですか？
今までの勢いだと4.5M切ってたりして…

そろそろ詰んだかも

今まで仕事でHTCできなかったから今から本気出す
ASM禁止→解禁のごたごたの間に手を出さなかったのは逆に勝ち組なんじゃね

>>202>>227>>団子厨
が優勝争ってるんでしょ〜〜
結局だれがいちばん強いわけ？
どれくらいとればこの人たちに勝てるかおしえて

たぶん一番上の項目で5Mくらい出せれば準優勝狙えると思うよ
優勝は無理だろうけどね。

>>465
SUGEEEEEEEEEE自信だけど自分はどれくらいまで行けそうなの？
もし準優勝すらできなかったら何してくれんの？


まぁおれは7M切るので精一杯だから関係ないけど。。。

>>465
つまり、だんごさんは5M切ったとｗ

さあそれはどうだか
少なくとも細かいチューンでの対決に持ち込めば勝てる自信がある・・・かもしれないね

60倍越えたんですね。わかります。

だんごさんの優勝はもう決定事項なのか。。。

インラインアセンブラを駆使しても>>389に勝てないという現実orz
今日一日アセンブラ触ってみて、gcc43の凄さを感じ取れました。

アイデア出すたびにガンガン速くなってた時期と違って、5M近くにたどり着くと
苦行になってきたな。
1%未満の調整は投げ出して提出する時期かも。

下馬評では、1位だんごさんで、2位は俺と>>227の対決か。
チキンなので俺のticks数は書けない。

>>472
インラインアセンブラ使用前で5119021。

好きに使っていいレジスタって何番〜何番だっけ
なんかコンパイラが予約してるとことかあった気がするんだけどどの資料を見たのか忘れてしまった

>>474
ttp://cell.scei.co.jp/j_download.html
「SPU Application Binary Interface Specification」の 「2.2.1 レジスタ」(日本語だと P8) の表

>>475
ありがと
普通にR80〜を使ってた
なんか普通に動いてるけどたまたまなのかコンパイラが退避してくれてるのか…
できるだけR10〜79位を使う様にするかな

>>476
拡張インラインアセンブリ構文を勉強すると良いよ。
コンパイラにどのレジスタ使うか教えると、変数割り当てがかぶらないように
してくれたり、必要ならレジスタ退避もやってくれる。

敢えて言う。
俺には無理。

nop/lnop を入れると早くなる謎。レジスタの依存関係は無さそうやし、
LSの帯域制限とかいう隠れ仕様でも有るのかなぁ…。

隠れ仕様なんかじゃないよ。もっと勉強しましょう。

これ以上性能伸ばすにはOddパイプの命令数削減する方法を本気で考えないといけなくなった。
＃トップを目指してる人はどういう状況かわかるよな？

>>481
ｗｗｗｗ

>>479
dual-issueとかじゃなく？

策はある。足りないのはメモリ。

>>483
ちょっと違うっぽい。nop+lnopを入れると１クロックのロスで済むものの、
何も入れないと２クロックストールしてるような感じです。

>>481
今のところ Odd 余ってるんやけどなぁ…。まさか限界突破したとかorz

ループ後半のどうでもいいようなところしか余ってない。
無理になんか処理入れたら逆に性能低下するし、そろそろ別の方針が必要っぽい


＃意地でもCでがんばるぞ

>>485
ヒント欲しい？w

今なら言うけど、>>394は限界ではない

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

http://www.insomniacgames.com/tech/articles/0907/spu_instruction_cheat_sheet.php

まーた、フカシが始まったよ… なんで黙ってられないんだろう。

別に信じなくてもいいが、現実を受け入れなきゃ優勝が無い、それだけの話だ。

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

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

こんなとこに情報出しまくる奴にも優勝はないと思うw

だろうね。用心深いから常に古い情報ばっかし出してる。

それで大丈夫と思ってる井の中の蛙は負けると思うw

お前らひがみはみっともないぜ

いったい誰に負けるって？

>>490
またＣに戻って戦略練り直しかorz チキンレース面白いから大歓迎だけどｗ

井＝2ch
蛙＝団子

敢えて言う、これは出来レースだ。

負けた時の言い訳ですね。わかります。

ん？俺が勝ったか負けたかをどうやって確認する気だ？ｗｗｗｗｗｗ

じゃあ予想だけしておこう。
優勝者は、13clk/qwordを、切る。

つまり切ったんだな

2人参加が優勝してたらまず団子だろw

なんか・・・インパクトに欠ける予想だな・・・

>>500
今の実装でも (Odd + Even) / 2 < 13clock だから否定は出来ないなぁ…。

2人参加が優勝したら、両方名前＆社名出すようにfixstarsに働きかけようぜw

>>504
多いほうの命令ひとつ減らすのに、少ないほうの命令が3つくらい増える悲惨な事態に陥ってますが。

ってか、2人参加の片割れがfixstarsの関係者かも知んなくね？

>>506
判る判るｗ
もう、1サイクル減らすとかじゃなくて、0.3サイクルとか0.25サイクルずつ減らす
領域なんだよね。

>>507
fixstars 関係者は参加できないよ。

中の人は、仕事の片手間に応募者より速いコードを目指して実装中。
たぶんまだ5M切れてない。
このスレみてガクブルしてるよｗ

参加できないんだから、参加してない事を証明しなきゃダメだろ。
ってことは、チームの場合も両方名前＆社名出さないと。

>>509
そんなしょーもないことしてどうすんねん
優秀な学生の確保と活力ある社会人の引き抜きが目的だろ

うーむ・・・もはや手詰まりか

>>511
別に非関係者装って参戦してるとかそーゆーんじゃなくて、純粋に遊びで
挑戦してるらしいよ。
Cellのプロフェッショナルとしてのプライドをかけたお遊びねw
マイミクのfixstars社員に「社内で5M切った奴いる？」って訊いてみたら？

まあプロが俺に負けるわけにはいかんだろうがなぁ

ちょ、だんごさん4.8M切ってるのか。スゲー！

そこは驚くところじゃない
まだ上はいるんじゃね？何となく。

>>473のコードを１命令変更しただけで4.8M切れたｗ
さて、これをアセンブラに移してループの調整でも始めるかな。

だんごやさんピーンチ

>>518
ちょっとﾜﾛﾀ。14cycleの時は１位との差が10000tick行くか行かないかの所まで
詰められたけど、ここまで来るとさすがに自信無いなぁ…。

>>479
実は載ってるところ少ないんだけど8サイクル以上位連続でロード/ストアしようとするとストールした記憶がある
そこでいったんぶった切ってoddでそれ以外の事するかあけてしまった方が速くなったりとか
自分も去年かおととし気づいたことなんで厳密な事は覚えてないんだけど

↑の制限は８サイクルよりは長いよ。でも 227 はそんな load/store はしてないと思う。

>>520
へぇ。
命令のバッファが空になるとLS命令をストールさせて命令をフェッチする
とかそういうのがあるのかな？

>>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の無限ストールの防止について」
あたりに書いてある気がするが、読んでもよくわからん。

とりあえず詰ませてみたけど、asmvis 見てもどこでストールが起きてるのか
分からない状態。片っ端から nop/lnop 入れて検証するのかぁ…orz

>>521
カンで16か20とみた。調子に乗ってループ展開しまくっていた頃だから、
知らない間にリミットを追えてしまったのかもしれませんね。

>>524
分岐ヒント命令のレイテンシが15cycleだから、それ以下の可能性が高い。
12cycle=24命令か8cycle=16命令分でオチるんじゃないかな。

>>523
DMA 用と load/store & ifetch 用の２ポートだった希ガス。
今回は DMA 関係ないけど、DMA は待たせられないからね。
で、load/store と ifetch でポート共有してるから、ifetch が
ストールしないように、load/store は続けちゃだめよ、と。

謎のデチューン（笑）で性能改善された説明になるな。
メモしておこう

学生でやってるけど10倍すらキツい
アセンブラ命令と複数対１命令で対応している組み込み命令は
どの程度コンパイラによる最適化の影響を受けるの？

基礎的な知識が圧倒的に足りていない件･･･orz

要するに128バイト分の命令（32命令）をこなす間に8サイクル以上
LSにロード・ストアしないタイミングを確保すればいいらしい。
完全にEven/Oddが同時実行されてる場合はロード・ストアが1バッファあたり8命令を越えるとアウト。
2命令同時発行できないサイクルがあったりすれば1バッファを使いきるサイクル数が17以上に延びるので、その分は延びる。
たとえばEven側20命令、ロード・ストア12命令の32命令でも、バッファのフィルに必要な8サイクルを確保できる。

>>529
Handbook によると
「SPU instruction prefetches are 128 bytes per cycle.」
らしいので、32命令中に1サイクル空きがあればいいはず。

>>528
結果さえ同一ならバカ正直に「SIMD版MT」を実装する必要がない

>>530
bitじゃなくてbyteかよ

そういえばDMAと命令フェッチが同じバスなんてことが書いてあるような

>>531ありがとうございます。>>209で言ってたようなことかな･･･
もういちど見直してみます

>>533
>>526 じゃなくて？

>>530,532
LS の読み書き単位が 128byte だからね、たしか。
ただ、読み込み自体は 1cycle で終わっても、SPU の pipeline は
結構深くて、15cycle くらい前に fetch されてないとダメなはず。
他にも ifetch 起動条件とか色々あるよ。どっかに資料あると
思うけど、リンクとか張らないでみんな自力で頑張ろうぜｗ

http://www2.vipper.org/vip1074688.png.html

上から下までこうなってないところ捜す方がしんどい

あ、当たり前では？

俺も参加したいけど、どうせなら1位2位を争いたい。
でも団子屋さんみたいな暇人じゃないから勝てるわけもないので高みの見物。

ひまじんとはしつれいな

>>531
それ考えてるんだけど思いつかないんだよな
アルゴリズム同じのまま使う命令の入れ替えと並び替えで15サイクルまでは来れたんだけど
しかも現状じゃ隙間は残ってるのに依存性で詰められないところがあってもったいない
ここにいる優勝候補さんたちは社会人部門だと信じてる

__builtin_expect()使っても意味ねー
つか遅くなる

！！！いままで使ってなかったんか！！！ｗ

今さら？
__builtin_expectでぐぐりゃそんな事例出てくるだろ。

だんごうぜー

ふゅーじゃーねいざん？

ループ内側の最適化は投げ出して、外側の整形作業に移るとしますか。
知らない間にリアルが２末マイルストーンとか言う無茶苦茶な事に
なってたんで、現実逃避も程々にしとかないとマジでヤバイかも。。。

なんで、こんなところに節穴がいるの？

俺の日記はリアルGateKeeperがよく読んでるけどね

今更になって>>389見て幻滅してきたorz メモリが無いと勝てる気がしない…。

15,000tick削減成功
いけるところまでやるか

とりあえず、>>389の一歩手前までたどり着いたのは良いんやけど、ここに
なって拡張アセンブリが使い物にならない(>>458)事がハンデになってくる
とは思わなかったorz

>>551
まだ３日ほど楽しめそうですよｗ

>>552
一歩手前じゃなかったっぽい。見れば見るほど>>389が神に見えてきたorz

>>517 は何だったの？w

>>554
99.91%の壁の高さを痛感しているだけですよ、たぶん。

あー、>>389 の前提がおいらとは違うのか。
>>551 を見て >>389 は最適化途中だっただけと見てたんだが。

素人だけど参加

命令書き換えとか、なかなか上手くいかないけど楽しいわコレｗ

>>557
命令自己書き換え(self modification)してんの？
仕様書に書いてあるけど、その場合は sync しなきゃ
だめだからあんま早くならない気がするなぁ…

【Oddの】命令数削減法思いついた

何命令くらいの所で頑張ってるんだろう？
自分はもうこれ以上削れる気がしないけど…

だんごさんそのうち4M切りそうだなｗ

いや、でも4.7Mの壁は今までの壁と比べても相当キツイな。
提出日まで頑張っても超えられない気がしてきた。

なんですか4.7Mの壁って

>>563
余裕で切ってるってことかーーー！！！
マジで勝てる気がしねー。

逆に遅くなったorz

だんご優勝できなかったらブログ閉鎖の方向でよさそうなのかな？

なんでやねん
逆に優勝しちゃうといろいろまずいことならあるが

3Mの壁が・・・。イチからやり直すか・・・orz

16Gくらいメモリ使ったんですか？w

>>568
3Mって、、、俺らと同じ基準なら化け物スコアだな。

>>557
でも今日は酔っぱらってて自己書き換えの実装出来ないんだなー。
明日時間有ったら挑戦してみる。

30Mの勘違いの予感

いつの間にか FAQ 更新されててﾜﾛﾀ

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

不可能ではないと思うんだ。

本日の捏造

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

>>575
目標修正、4.6Morz

ああくそ、やっと正しい答えが出た。
拡張インラインアセンブラ、かなり茨の道だわ。
レジスタ多いから、どのレジスタが期待値と違うのか判らん。

誰が悪いのか判らないアセンブリのデバッグしながら命令削るより、
C言語の上で一つでも多くのアイデアを実装した方が絶対効率的だ。

>>575
まだ4Mは切ってないようでｗ
大きな差が無くて安心した。

今北。

課題は、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[] を検定する。

どうかな。

>>575
人間がレジスタを管理することなんて既に不可能と気づけよ。

>>579
あーぁ、GF(2) とか出してくるなよw
団子の「スタートライン」は全然そこじゃないって。
井戸の中で満足してる奴に餌与えちゃだめだってw

井戸の中ｗ

>>579
ルールブレイカー発動か？
tempering前に何かを集計して・・・ということができれば劇的に
速くなるという発想はあったんだが、多分ムリだろと思ってやってないよ。

学がないもんで、GFを今Wikipediaで調べて、やっぱり意味不明だった。

>>580
Pythonでスクリプト組んで、アセンブラコードを半自動生成させてるから、
うまくいってるときは問題ないんだ。
一度計算結果が狂うと、どこが間違ってるのか全然判らなくなる。

>>202
Matsutomo et al.1994 にも、MK-tempering が GF(2) 行列の掛け算だ、
と書いてあるでしょ。

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

今すぐ ACM 逝って MT に批判的な論文嫁。

とかいいつつ、端数の処理が解決できなかったら俺の負け。

>>579
団子は何もしらないってことにまだ気付いてない。。。

>>579
とりあえずそのままSIMD化しただけで放置してたんだが，
そうゆうの面白そうなんでその方向性で考えてみるわ

ここが井戸か

ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/TEACH/0407-2.pdf

>>590
ポイントはここですか？w ＞ 「6.5.2 どこがフーリエ変換やねん」

ま　た　勘　違　い　の　【さ　ん　す　う　や】　か
算術師の花園へようこそ

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

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

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


>>580
ばかだな。レジスタ管理がどうとかなんて言ってないだろ。
ここまで全部コンパイラにやらせてるし

>>558
え、そうなの？
仕様書あんまし読んでないからわかんないけど
俺がやってるのは例えばodd命令をeven命令に置き換えたりして
同時発行を促すとかそういうのなのだけど･･･

oddをevenかよ。俺様はそれをやる段階じゃないな。


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








インフルエンザですが何か？

>>578
俺が現在進行中のスコア貼ったことは一度も無い。
いまのところ3日前くらいのスコアばっかし貼ってる。

>>575が3日前だとして
>>551の時点で15,000tick削減成功

だから少なくとも今は4.67M台未満ってことかな？

やっぱりやる気でないから、数学的手法への挑戦はやめとく。
レジスタ上に一瞬とはいえ目的の乱数が出現する俺や団子さんに比べて、
数学的手法だと一瞬たりとも目的の乱数が出現しないから、
※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。
の条件に違反しているという理由で reject される恐れもあるしね。

コード整理して、レポート書いて、提出しちゃおう。

レジスタ上に一瞬とはいえ目的の乱数が出現する俺や団子さんに比べて、

え？アレって出てるって言うのかな？
俺はデータ構造的にあやしいことやってるけど。

>>593
結局自分で管理しないでコンパイラ任せじゃないか。
レジスタがいっぱいあるからといって自分で全て管理できるはずはないけど。

ひょっとしてまじめに乱数作ってチェックサム取ってるの俺だけか？？
俺が団子さんに敵わないのもそのせい？？？

>>600
だから何なんだ？管理できるとかできないとかお前は一体何を言ってるんだ？
俺にはさっぱりわからない。

>>601
ちなみに、彼の珍理論で演算時間の短縮を図るには超次元立方体構造のレジスタや演算ユニットが必要だったりするから気にするなｗｗｗｗ

団子が天才。はい。だからもうだまれ

>>604
誰だおまえ？スピード狂オタクの分際で調子に乗るな。

MT配列は教科書通りの結果になるように都度更新してるけどtemperingをまっとうな方法でやってる自信はないな。

>>603
おいおい、GF(2) 系の演算の高速化や簡素化はコンピュータの得意分野だぞ？
今時の暗号なら当たり前の事だろ。実装した事ないのか？

だったら実装してみろよ
机上の空論はおなかいっぱい

さんすうや君は端数を処理するのにチートやらないと無理だって言ってるんだろ？
ならどのみち芽がない方法だ。

> GF(2) 系の演算の高速化や簡素化は

やってるよ。
MT[]のデータ状態に矛盾が起きない範囲でな。それが出来ないなら今回のコンテストは諦めろ。

青筋立てないで落ち着け。
どこのスレでも痛すぎる。正しい事を言っているかどうかじゃなくて。
答えて欲しい質問からは逃げるのに叩けるところはどうでもいいところまでしゃしゃり出てくる。

なんだ答えて欲しい質問って？

ゲハ厨学歴厨に何言っても手遅れ

話題変わるけど、spu-gdbってどうやって使うの？
elfspe使ってspe用のバイナリを直接実行できるんだけど、
spu-gdb mt_kadai とかやってもデバッグできない。

今までデバッグは全部コードインスペクションと、mt[]のダンプ取って
バグの箇所を推測するの2種類だけで全部やってた。

負け犬の遠吠え

>>614
SPUの実行イメージをPPEから読み出すローダーでも作れば良いのでは？

http://cell.fixstars.com/ps3linux/index.php/Libspeプログラムのデバッグ

>>612
※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。
の意味について、
1. プログラム中でmt[]の内容を計算していたら良いのか、
2. 全乱数wordについてtempering後の値も計算していないといけないのか、
3. それともチェックサムだけ合ってればなんでもアリなのか、
を質問してみて、質問して回答が2だとヤバイ？

俺に聞くな。

ちなみに俺はgenrand_mineを繰り返し呼んでも安全なように設計してる。
ぶっちゃけ外側の最適化はサボってる

>>612
>>381 は本当？　>>389 == 最適化中は本当？　>>575 の捏造は本当？ｗ

鼻高々だな団子。

手元にある最新のコードよりわざと悪い結果を貼ってるのは本当。

晒す実行結果は前のバージョンだったり、わざとデチューンしたり、色々。

なんか参加賞あるし、暇だからやってみようかな

プログラム全然書けないけど
このスレ見ながら楽しくやってみよう

>>622
自分もそんな感じ。
勉強と思ってのんびりやろうぜ

>>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
に変更されている。

これが効いてくるのは、レジスタ幅ではなくむしろ並列計算だろ。

>>603
超次元立方体構造ってなんだよｗ

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

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

>>610
> > GF(2) 系の演算の高速化や簡素化は
>やってるよ。
MT の内側は全て GF(2) なわけだが。
それを踏まえて外側を如何に GF(2) の上に持っていくかの話だ。

>>598=202

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

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

だとしたら
>temperingをまっとうな方法でやってる自信はない
>MT[]のデータ状態に矛盾が起きない範囲でな。
団子道連れだな。

話を戻すと、課題(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回目の不真面目計算が解析できれば、そこから芋づる式に
求まるんじゃないかと楽観視している。

ともかく、いまは解析結果待ち。

妄想はいいから。


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

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

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

くだらねーコンテストなんて目じゃねーぞ。

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

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

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

所詮お前は口だけだな。
ハッタリは何も出来ない人間のためにあるものだぞ。
どう足掻いてもお前にはできない。

>>579
数学はよくわからんのだが、
自分が優勝だと勘違いしてるやつより期待してるからがんばれ！！

ああ、ちなみに最初くらいに1ビット×128並列のビットスライス実装思いついたけど
全然速くなかったよ。

これはどれぐらい高度な数学が必要なんだ？

さんすうやの詭弁は聞いて呆れる

>>632
これ読んで何書いてあるか解る程度。そのまんまだけど。
http://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数は（ｒｙ

いや、だから、団子はやらんでいいから黙ってろやｗ

>→「あり得ない仮定を持ち出す」
物事を簡単に考えるための迂回路だ。TT800から始めてろ。

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

解析結果？出てねーよ。

課題アナル(仮称)を prolog で実装した策略ミスだ。それは認める。
vsz は順調に(?)太っていってるから、あと 2,3 日ほっといてみるか。

59ms弱だよ。

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

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

っていうか、脳みそ足りてる？

>>634
なんとなく分かりました。高度な数学というよりも新鮮なアルゴリズムに気がつくかどうかの問題だし、素数を探すプロジェクトとなんか似てますね。

団子はうざいが、
>>637
>レジスタ足りる？むしろメモリ足りる？
>
>っていうか、脳みそ足りてる？

これは笑ってしまった。く、くやしい。

なんにせよ10000≦num_rand＜UINT_MAXだからなぁ
何十年かかる計算を数学的解析によって短縮云々なら価値はあるが
数十ms程度で終わる計算相手にスピードを競うアプローチとしては無謀を通り越して馬鹿かと
5段階の1段階目だけで既に終わってる希ガス。



それよりUNIX crypt(3)のハッシュ値からキーをダイレクトに求めるアルゴリズムでも解明して下さいよｗｗｗ
数十年来の課題ですｗｗ

fixstars側に十分な数学の知識がある人がいて
なおかつコンテストで生み出されるコードが後々の役に立つものであってほしいと願っているのなら
素直に乱数を作って加算するのが一番速くなるような問題になっているはず、
と信じたい

>>637

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

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

> この固定されてしまった j_1,...,j_L が乱数の質を決めるのだが、これがいただけない。
> この固定されてしまった j_1,...,j_L が乱数の質を決めるのだが、これがいただけない。
> この固定されてしまった j_1,...,j_L が乱数の質を決めるのだが、これがいただけない。

負け犬は遠吠えだけは達者だな

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


> 1. mt[] から pmt[] への線形写像を求める。
どうせこれだけで天文学的な時間かかるんだろ？ｗ

線形写像求めるだけで天文学的なんて、どこまでお花畑なんだぜ？

熱い・・・熱いぜお前ら
いいぞもっとやれ

>>645

いや断る。俺下痢。寝る。

・メモリ210KBが使用禁止
・チャネル使用不可（メインメモリ間のDMAももちろん不可）



まあとりあえず脳内珍論はブログでやれ。

線形写像 = 実機動作、高速
解析 = 事前作業、低速

机上の空論には
「Temperingはランダムテーブルルックアップで1回の操作で行うことができますが、
4Byte×2^32 = 16GByteのメモリが必要です」
みたいなオチがつくんだよね

>>648
> 線形写像 = 実機動作、高速
> 解析 = 事前作業、低速

その「線形写像」なんだけど、46KB未満のメモリ空間で確保できるLUTで
一体なにができるのｗｗｗｗ

線形写像の意味わかってる？

線形写像を実装する方法をソフトウェア工学ではLUT（ルックアップテーブル）って言うんだよ。
Cellはローカルメモリが小さいから一般的には不向きと言われる。

ほうほう、じゃそれはアルゴリズムで実装することはできないんだな？ｗ

おいおい団子ちゃんよ、高校の"さんすう"からやり直したらどうなのさ

＞ほうほう、じゃそれはアルゴリズムで実装することはできないんだな？ｗ

君の「アルゴリズム」が何を指すのかわかりませんが
LUTもアルゴリズムの一つです

すまん、「LUT でなく、演算で求めることは、できないんだな？ｗ」だ。

テーブルのオフセットをアドレスを求めて値をロードするのも「演算」です。

むしろNOP系の命令以外は全て演算なんじゃないの？

ま、何でもいーや。線形写像＝ＬＵＴね。tempering も LUT でやってくれｗ

だんご大丈夫か？ ＞ インフルエンザ

ﾌﾟｯ

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

まあ何がアホかって、結局のところ>>637なんだけど

>>656
俺は専門卒なので難しい数学は判らないのだが、
元の計算式自体が「LUTではない方法」で、
結局難しい用語を持ち出してる数学屋の言ってることは

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

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

Prologで何ができるのか知らないけど、元の計算式より計算量の少ない
式が出てくるっていう根拠が数学屋にはあるの？

>>660
みなぎってきたｗｗｗｗｗｗ
とりあえず今週一杯サボるｗｗｗｗｗ

>>662
結局は>>649的な実用性のない発想だから気にすることはない。知識におぼれて本質が見えてない人間が暴れてるだけ。

MTの初期値が固定されていたら何かを打ち破る抜け口がありそうな気がするけど、
init_genrand() の引数と num_rand が未知の場合、「乱数のチェックサム」の計算を
ショートカットするのは無理そうというのがソフト屋の直感。

数学屋と違って何の根拠もないし、自分でもそんなに信じてない直感だけどな。

>「元の計算式と同じ事をするより短い別の計算式を見つければおｋ」
そういうことだ。Tempering より短い写像式を見つければＯＫ。
って、Tempering も十分短いから無理っぽいけどなーｗ

暴れているのはだんごである

だんごは鳥インフルエンザ

中の人二人いて煽り担当とプログラミング担当がいるコテの人はずるいと思います。

>>666
たとえば
A XOR (B AND C)

これをたとえばMUXを使って式変形するとどうなる？
って、このレベルの試みは俺もとっくにやってるわけだが。

>>669
３人じゃね？両方○も居た希ガス

>>671
団子三兄弟ってやつか

そんなに必死にならなくても大丈夫だよ、団子さんより頭の悪い人だっていっぱいいるから

>>673とかな

>>674
まぁ、本当のことだから何もいえないけどね

B = A XOR D

が成立するとき

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

これ、豆知識な

結論から言うと>>676は今回使うところはどこにもありません。




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

↑
これの元ネタ解った奴は俺のドッペルゲンガー

>>676
そういうのを代数学の知識で証明できるようになりたい

知ってると思うけど団子の中の人は広大の松本研究室とメールやりとりしたことがある。
結論を言うとseedとnum_randからpmt(笑)を求めるための一意な論理式なんて存在しないよ。
あっても計算時間・メモリ容量的に実用的なモノではない。

>>678
カルノー図書けば一発じゃないか

>一意な論理式なんて存在しないよ。
いや、存在はするんだってば。実用的なのが見つからないってだけで。

Cell使ってしらみつぶしに探しちゃえば？

その上、端数を処理するのにチートしないと実用的な性能出ないんだろ？
しねばいいのにｗｗｗ

それに比べればこちとらまだ青天井みたいなもんだよ。

どうせMT高速化やるなら、ついでに多変量正規乱数までやってくれよ
デキバイによっては金出すぜ

出来栄え?

あーそれだ
日本語苦手だ許せ

> こちとらまだ青天井みたいなもんだよ。
13cycle 切れた訳でもあるまいにｗ

たとえばさ、

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


たとえば極端な話、

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

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

とりあえず誰か質問してきてよ

>>687
58156364 / 4 * 13 / 40 = 4725204.575(ticks)
だけど何か？

既に12clk/qword台の闘いなんだぜ？

>>688
あー、それは俺も思った。

あと、num_randの期待値も。
下限10,000だけじゃ外側、内側の比重設定に困る。

今日もEven13clockの壁を突破できなかった。なんか極大点に達してるような
気がするので、どこまで戻せば正しい道に戻れるか探してる所です。

コアの部分でEven:12.5、Odd12.1サイクル位
革新がない限りこれ以上どうにもなる気がしない

>>580
レジスタ１２６個使えるんで、カラーリングの必要が無いから楽ですよ。

>>614
stqr + printf でデバッグしてます。バグが出たときは svn diff。

>>693
ループの内側スカスカだったりするだろ？

>>688
その場合って mti もちゃんと更新して、mti が０じゃない
ところからでも再開できるようにしてんの？

全部アセンブリで詰めてるから隙間なんて150サイクルの間にOdd4個あるだけだよ

>>696
当然

evenだけ12切る方法思いついたがOddが恐ろしいことになる

刹那な午後の人が hack the cell 始めてる〜 ＆ここも見てるっぽい。
いやー、さんざん勉強させて貰ったんで、なんか感慨深い感じ。

ああ、herumi氏のことか。

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

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


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

＃妨害ついでにXbyakのAtom新命令対応パッチまた送りつけてやるかﾋﾋﾋ

まてよ
60倍云々って・・・俺のカキコが初出の情報かもしれない・・・ｗｗｗｗ
まああの人は俺の日記読んでるからな

んー、わからん。誰だろ？ > real google の人
&日記更新してたんね。15cycle の latency の話だけど、
6cycle なのは命令実行後 LS に反映されるまでの latency
だから、命令解釈やら register file から各演算器の latch
への転送とかの 15cycle とは別物だよー。マジ長いねw

しょっちゅうherumi氏が日記のネタにしてるじゃないの

ヒント：「yajit」

俺も初めてアセンブラ触った動機がMMXで画像処理したい！で、
へるみさんのサイトに散々お世話になった。
なんか感慨深いなー。

>>704
チーム参戦型のICFPプロコンで、個人で上位を取っちゃうあの方ですね、わかります。

今日もサボリのタミフルが、何故かおとなしいな

呼んだら出てきちまうだろ！ｗ

くそー、13 切れねぇ orz

13が増えてきてるのが凄く脅威なんだが・・・
693、俺、だんごさんが13切ってて、227と709が13か

>>640
>それよりUNIX crypt(3)のハッシュ値からキーをダイレクトに
>求めるアルゴリズムでも解明して下さいよｗｗｗ
暗号乱数とモンテカルロ乱数は別物だと何度もいっているだろバカ

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

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

>>683
>それに比べればこちとらまだ青天井みたいなもんだよ。
青天井の意味知ってる？

どうせ団子理解できないだろうから教えてやるよ。
その前に md5sum = 770e20e29056b7e5d420fc46bdc5ee6a

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

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

欲しいのは 2 進表記の sum なわけだが、最終的に変換可能で
あれば途中経過の表記法は何だって構わない。交番だっていい。
問題なのは、mod 2^32 がガロア体ではないことだ。

ループの内側がガロア体で、外側がガロア体ではなかったら、
そりゃ計数するのは非効率だろう。だったら、2^33 のガロア
拡大体の上で計数してみようという発想にはならんのかい？

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

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

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

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

そして、最後にシンドローム計算すれば 2 進表記に戻せる。

>>631
>ああ、ちなみに最初くらいに1ビット×128並列のビットスライス
>実装思いついたけど全然速くなかったよ。
馬鹿はここで諦める。

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

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

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

ならば、最初に mt[] を別の空間に写像しておいて、その空間で
更新行列の "1" が少なくなるように設計すればいくらでも
(それこそ青天井に)効率は改善される。

しかし、これだけだとビットスライスを用いる根拠としてはまだ
少し弱い。それは、mt[] のサイズがレジスタ数と比較して大きい
(load, store をスケジュールするのが大変)のと、"1" の割合を
減らせたとしても行列自体が大きいので、必然的に計算量は多いまま。

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

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

さて、どうしよう？

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

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

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

課題アナル(仮称)の正体は、直交していないビットを探索するものに
他ならない。

だンゴサんの括約で棺桶スレが成立したな

>>579
なんでこんな大事なことばらしちゃうの？ｗ

一応、みんな判ってると思うが、Hack the Cell の課題が何か確認しておく。

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

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

芽のない方法を芽がないと割り切る能力が欠落した人間の遠吠えはむなしいのう

>>717
机上の空論だよ

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

まったくもって今回の課題の解法として役に立たない。

>>710
あれ？202 も 13 切ってたの？ >>598-599 のやり取り見て、
まだ切ってないと思ってたよｗ
>>720
自分も >>599 が当てはまるとやばいんじゃないの？ｗ

連続投稿引っかかったｗｗ

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

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

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

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

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

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

さーて、そろそろ実装でも始めますかｗｗｗ

>>721
単純にMTの式をMTを32ビット×4並列化したものではないということだよ。
配列状態とサマリの値が等価になる範囲で高速化出来る方法は全て駆使してる。

もうやることは終わってさじ加減次第かな。
部分的にスカスカな部分があったりするのでループ全体を見て命令数が減るようにバランス調整が必要だ。

>>719
自分に自信がないやつほど声がでかいってのは本当だったんだな。

>もうやることは終わってさじ加減次第かな。
青天井じゃなかったのかよ

>>722
机上の空論は結果を出してから言うことだ

>>724←これとかな

>>579
アンタ、糞団子と接するのは初めてかい?
まあ力抜いてアナル(r

だんごも>>579もすごいぜ
少なくとも議論の台に乗れるんだから
俺も工学系だから少なくとも理系ではあるんだが何を言ってるのか全くわからんｗ

とりあえずサイクルの話はあんまりしない方がいいとおもた
サイクルの話見ただけでどこの最適化やっててどこの最適化やってないか想像できるし

負け犬579をアボーンリストに追加しとけばいい
彼は全然役に立たないことしか言ってない。

まあ見えない敵と戦ってる馬鹿だから相手にするな

>>717
どうせ団子理解できないだろ？

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

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

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

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

これが 2 だったら、出題者が問題の意図理解していないよ orz
1 の判断は微妙だが、仮に 1 だとするとできる事は限られてくる、
つまりそんなコンテ誰が出ても結果は一緒。ツマンネ。

ハイ　おさらい。
http://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って

>>721
>>689は超えたよ。
結構苦労してアセンブラ書いたしね。

>>721(=>>693?)もだんごさんも、tempering後の値をまじめに計算して
add を繰り返してる訳じゃないのか・・・
とりあえず、チェックサムだけ合ってればOKなのか訊いてみて、
OKならまただんごさん超えに挑戦してみるよ。

>>728
アナルの力抜いておくよ。

>>730
ｶﾞｸﾌﾞﾙしている姿が見えて楽しいよｗ

693だけどtemperingは毎回やってる
というか処理の7割がtempering
泣きそう

話の腰をもんで悪いんだが
temperingってなんだ？

揉むな!ｗ

勘で出てきた乱数を32bit空間で偏りが無い様に再マッピングしてるんだと勝手に思ってた

マージャン用語です

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

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


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

スタンばる（スタンバイする）、、などと同じ和製語ですね。

さてさて。

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

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

その前にクソして寝る。

>>739
そうだったのか…
勘とはいえすごい的外れな嘘を教えてしまった
ごめんよ>>736

おおざっぱに、MTで乱数生成の為に行うアルゴリズムでビットシフトを行う操作のことだな
tempering

>>729
暗号論の世界にも差分解読法なんてのがあって、ビットの並びの特徴から演算をショートカットする
方法に関しては俺自身もいろいろ試したことがあってね。
んで、今回はそういうショートカットは全くもって役に立たない。

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

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

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

暗号の実装の話になるけど、AltiVecのVPERMやSPUのSHUFBはAESのS-Boxを16並列で処理する
ことができるけど、SSEだと同様のシャッフル命令であるpshufb命令なんかを使うより別の方法のほうが速い。
今回の課題はそう言う観点で何が最適なアルゴリズムかを考えられる人でないと難しいと思う。

> フェイステイル型暗号でいうところの一種のS-boxみたいなもんだ。
ち・が・う

>>739
(y << 15)んとこが16だったらアレしてこうして・・・とか思ったけど
なかなかうまくいかないもんだね

>>744
あらゆるフェイステイル型暗号のS-boxはビット論理演算の組み合わせだけで実装できるの知ってる？

お得意の bitslice か？　それと s-box の意義は全然別物だぞ？

フェイステイル型暗号におけるS-boxの役割は、簡単に言うと前後のビットの並びの相関性を破壊するための仕組み。
MTのTemperingも、Temperingを省いて合計値を計算しようとしても出来ないようにする程度には相関性を破壊できてる。

そりゃ、暗号も擬似乱数も拡散って意味ではなんだって拡散だし、
ほとんどが論理演算の組み合わせで実装できるだろうよ。
その程度の意味で、feistel の s-box と同じって言ったのか？

Tempering＝「調律」
スイーツ（笑）用語でいうとチョコレートコーティングの表面を滑らかにするための行程。

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


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

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

テーブルルックアップを使わない暗号・ハッシュアルゴリズムの実装では
ほとんどMTのTemperingみたいな簡単なシフト＋ビット論理演算をやってる。
だから本質的に同じだって言ったんだよ。

>テーブルルックアップを使わない暗号・ハッシュアルゴリズムの実装では
>ほとんどMTのTemperingみたいな簡単なシフト＋ビット論理演算をやってる。
へー、すごいなｗ。いや、LUT を使わない実装が標準とか思わないほうがいいぞ？
暗号作ってる方は簡単なシフト＋ビット論理演算で求められないように sbox を
導入してるのに、なんか可哀想になってきちゃうよ。

まぁ確かに本質的には両方拡散だから同じだしなｗ

>>751
RSAのRivest Cipher(RC)シリーズとかMD5なんてS-boxを使わずにスワップを繰り返す
暗号・ハッシュアルゴリズムの代表格なわけだが？
RC6はAESの最終候補まで残ったぞ。

なんで軒並み落ちてって、今 feistel ばっかなのか考えようぜｗ

>>743
よわかりませんが、M系列で「加算」する場合もキャリーは１ット隣なのでしょうか？

>>754
最低限言えることは、SPUには任意の位置のビットにキャリーアップしてくれるような特殊な算術加算命令はないということだ。

まあそういうことだ。
ハードウェアに不向きなことをやらせて性能を出そうという方が間違い。

なんだかよくわかりませんが、よくわかりました。
ありがとうございました。

関係ないけどJNBのトークンって暗号形式なんだったっけ？

そろそろ詭弁の○○ヶ条で〆てくれ

>>753
そこはAESばっか、に訂正しろよ。
AESが世界的に選ばれてるのはAESがAESだからだ。
AESに選ばれなかったfeistel暗号の信頼性を保証する根拠にするのは間違いだな。

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

それに比べれば国産暗号のMISTYとかCamelliaなんてまだまだマイナー杉。
松井さんには悪いが。

ん？ DES も Feistel だろ？ MISTY1 も Camellia も NESSIE とってるが。
＆ MD5 と RC4 をこれから新規に採用する規格があったら驚きだが？

ちなみに、SHA-3 コンペでも feistel 使われてるぞｗ

当たり前のこと言ってどうすんだ。鍵長考えてものを言え。
引き合いに出すならRC6あたりだろ。


RijndaelがAESに選ばれたのはその一つとしてDESみたいな複雑なビットシャッフル演算がなくて
専用ハードウェアでなくても実装コストが軽いからだ。
別にRC6の暗号強度が否定されたわけではない。

すまん、ちょっと読み違えてた。が、時間がない。また今度w
あ、俺も RC6 の暗号強度を否定するつもりは毛頭ないよ。

そもそも別にLUTよりビット演算のほうがコストパフォーマンスが優れてるなんて言う気はない。
不毛すぎ

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

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

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


＃あとAESは厳密にはSPNSであってFeistelには分類されない。

日本語でおｋ

当たり前のこと言ってどうすんだ。

個人的にCamelliaのSSE4向け実装とか開発中
おれ松井さん好きだし


＞Fixstarsさん
来年の課題はCamelliaでお願いします。

>>764
俺の見解は、拡散って意味では tempering も sbox も同じってのには同意。
だが、シフト＋ビット論理演算ではできない substitution を実現するために
sbox を導入してんだから、それを安易に同列に扱うのは理解できん。

あ、国産マンセーは俺も一緒。来年 Camellia いいねぇw

ま、とりあえず俺の情報源のひとつ晒しておくわ。

暗号アルゴリズム及び関連技術の評価報告
http://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つだけしかない。
その点でみてソフトウェアでの実装の複雑さと暗号的な強度は別モノと考えてる。

>>710
とりあえず13clock切れた。けど謎のストールに阻まれ停滞中orz

本命：団子
対抗：>>202,>>227
大穴：>>579

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氏も参戦してきたことで、それですら負ける気がしてきた）

まあ、どうやってコンパイラの副作用を抑え込んだのかっていうのはソースにびっしり書いてたりするから
俺が上位に残ってたら参考にしてくれ、的な。

>>769
俺の言いたい事は >>768 で言ったが、「今 feistel ばっか」とかが
気に食わないんかな？ sbox ＝ 堅牢と言ってるんではなくて、堅牢さと
速度を両立するのに sbox が向いてると言いたいだけなんだが。
シフト＋ビット論理演算だけで同等の堅牢さを実現するよりも、
sbox の方が早くし易いし、小さくもし易いって理解なんだけど。
だから NIST にしろ NESSIE にしろ、feistel 系ばっかなんでしょ。
それだけ別物だから俺には tempering と sbox を同列には扱えん。
以上。

>>772
俺はアセンブリじゃないと絶対に出来ないことをやってるから他の点の実装が一緒なら有利かもしれん
正直な話このスレで結構な数のヒント貰ったからこれがないと負けてた

この程度ならあんまり影響っていうレベルで、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が小さいことは、キャッシュメモリが小さいアーキテクチャにやさしいということでもある
で、それでいて十分な強度という評価を得ている。

うーん、論点がどこなんだかイマイチ解らん。
feistel の sbox と spn の sbox は別物なのか？
俺も不可能とは思ってないし否定もしないよ＞RC6
負担が小さいとも思ってない。堅牢性と共に、早く
出来ることも小さくする事も可能なのが重要なだけ。
AES の sbox も 256 だったと思うのだが違うのか？
俺には tempering と sbox を同列に扱うのは理解
できないし、「みたいなもん」なんて説明には到底
同意できんから異は唱えるが、別に団子がそれで
間違ってないって思うのはどーでもいーよ。

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

でもさー、団子も sbox 系とシフト・論理演算系を
綺麗に別けてねーかw　やっぱ別なんじゃね？w

>>770
みんなすげぇなぁ。
おいら even -1 したら、odd +3 = total +1 で意味なかったよ orz

>>778
wwwwwwwwwwwww
すっげーヒントあげたいけど、その壁は自分で超えろ。

>>778
大丈夫、私もその辺で挫折した。つーか、飽きたw

>>693が、58156364 / 4 * 12.5 / 40 = 4543466 か。
この数値が出せてたら俺より速い。
>>775 の意味も判る。

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

だんごさんと >>579 の話にはついていけなかったんだが、
とりあえず >>579 の Prolog が導き出した解法のサイクル数が
出るまではインラインアセンブラで限界まで行った者勝ちっぽいな。

まー普通に考えても、ここに書き込んでないやつで優れた奴もいるだろ〜から
優勝候補をこのスレ内で絞るってのも無理があると思うんだけどな

>>782
もちろんその可能性は否定しない。このスレを読まないと、「命令数どこまで減らせる」という
指標がない状態でチキンレースに参加しないといけないからキツイけど、このスレをROMってるなら
命令数がどこまで減らせるか判るね。

>>781
おい、俺様を優勝・準優勝の可能性からはずすな！

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

とりあえずカードは残してる。

>784
だって亀田兄弟的ポジションじゃんｗ

>>784
まじかよ・・・
>>693の12.5がもう限界だと思ってた。

>>786
全然関係ないけどさ
Oddへの置き換えなしだとEven側は18くらいかかるわけだけど、これを17に減らす方法って気づいた？

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日くらいで考えたネタだけど、最終的に高速化の候補としては外れた方法だから敢えて紹介しておく。
あとブロック単位じゃなくてスカラ単位で取り出す場合はこっちのほうが速いかもしれない。レイテンシ的な意味で。

^ x ^

↑このへんがむかつく

>>787
evenの命令数削減は無意識だから、どうやったら even18 になるか悩んだ。
andc ともう一つ命令を使うヤツか？
もう一つの命令で予約違反してるけど、将来のSPUで動かなくなっても
構わないと判断したよ。

andcじゃなくてselでも良いのか。

>>202 なに言ってんだ？w

いっか、トップランカーには無意味な情報だからバラしちゃえ。
spu_and( matrix_a, spu_cmpeq( spu_and( x , 1 ) , 1 ) )
↓
spu_andc( matrix_a, spu_subx( z, z, x ) )

コンテスト参加してんのお前らだけじゃねーぞ
少しは考えろ

ってか、202 には >>788 の答えは見えてないのか？

>>794
悪い。調子乗りすぎた。
締め切りまで黙ってる。

>>793
そ　　ん　　な　　方　　法　　も　　あ　　っ　　た　　の　　か
第一オペランド破壊する命令はうまく考えて使わないと困るんだよね。

>>788見つけたときは俺SUGEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEって思った

>>797 こんなので思うな!w

8bit×4の水平加算とかあるけど何に使うんだコレ

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

悲しいことに今回の課題でも役に立たない。
如何あがいても垂直加算のほうが性能出る。
これがもしもOddで処理されるならまた使い方も違ったんだけど。

absdb/avgb/sumb あたりは動画のためだぁな。

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アナルに決めたよ。ついでに処理系と実装も変えたけど。

$ 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

ですが、何か？

ちなみに、実装は C99 な。本当の意味でのな。altivec も使っていない。
32bit ビットスライスｗでこの程度。端数の処理はまったく最適化していない。

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

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

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

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

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

>>781=202
俺？優勝する可能性？ないよ。出ないしｗ

>>801
おいORIGANALが本来のターゲットより一桁以上速いぞw
でも、多項式取り違えてたとはいえ、すげえ伸び率だね。

よくできた捏造だな
でもターゲットはＰｏｗｅｒPCじゃなくて「SPU」

よ、よく出来てるのか？ｗ

> 俺？優勝する可能性？ないよ。出ないしｗ
これを書くのはもうちょっとあとの方が面白かったかなｗ

>>805
たしかに>>732より、よくできてるのは間違いないな

ゲハ板で発狂してるアスペル君が勝手に勘違いしただけだろそれ

さすがに俺もそう思う。団子はウザイけど >>732 は無罪。

そうだったのか。団子ごめん

PPUとSPUが同じコードシーケンスで実行できるとかアホなこと言いやがんだもん
ＰＰＵに18issueの命令帯域が必要になるぞって言ったら、十分とかいいやがるし

しまいには、SSEがｘ86のフォーマットとはかけ離れてるとかｗｗｗ
あの命令フォーマットがｘ86でなくてなんなんだよ

大丈夫だよ。あのコピペで団子は間違ってないってみんな分かってるから。

団子が間違いを認めなくてウザい事もかなりあるがな。
あと接頭辞のように付いてくる「知り合いに誰々がいる」って下りもウザい。
知り合いが有名なだけで、別にスネ夫が偉いわけじゃないだろう。

「サマリだけ求めるショートサーキット禁止」
とか胴元が慌てて言い出したら爽快だな。
つか出題者があたまわるいってことになるが。

俺もそろそろトランザム（笑）発動しちゃおうかな
そろそろ勘のいい人は愚直な方法がいくらばかばかしいことに気づいてるかも知れない頃だし

>>814
関数抜ける前にMTの配列に書き戻しさえすれば等価な実装でもかまわないのでは？

ルールを根本変更されると正直悲しい。そしてキツい。
単なるチキンレースなら降りる。

課題見直しで延期とかになったら面白い。

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

コアループ抜けてからMT配列に書き戻せばちゃんと再実行も可能。

>>734の言うとおりになったな

俺もロジックジェネレータ改造したそろそろ走らせようかな
テキトーに当たり付けたパターンを再帰で全部試す馬鹿な方法使ってるから最適に近い方法見つけるのに1ヶ月くらいかかる。
俺の試算だと

ごめん、もうプログラムは書かないから、言わせてくれ。

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

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

俺はHack the Cellに参加したんだ。単なる数学コンテストなら降りる。

様々な分野に対する知見が求められる、それだけのことじゃないか?

>>821
課題を100回読んでよ。　つ http://cell.fixstars.com/challenge/challenge.html
どこに「乱数のチェックサムを計算してください」って書いてある？

「課題は、メルセンヌ・ツイスタの最適化です。」
「メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。」

しかしCellって本当に早い？使ったことないけど
フィクターのサイトにあるパフォーマス例と同じ処理をXeonで組んでみたら
10倍速いのできたんだが・・・

>>693だけど
なんか裏で本気出してる間にお通夜モードになっとる
とりあえず12.0まではきた
まだ0.3位は詰めれるかもしれない
で、大会中止とかルール変更とかなったらおれはどうすればいいんだ

>>820
おちつけ

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

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

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

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

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

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


どこまでが王道でどこからが邪道なのか、無用な線引きを脳内で作ってしまっても「勝ち」はないわけで
とりあえず中の人に明確化してもらいたいところだ。
俺はgcc43って指定してあるのにアセンブラ使用可になった時点で最早ルールなんてないもんだと思ったが。

ごめん文が微妙に抜けてた

×そんなことをSPUで実際やれば56本固定で食っちまう。
○224要素くらいまでを割り当てるにしても、そんなことをSPUで実際やれば56本固定で食っちまう。

>>825
別に、mt[] をいじるなとは言ってないし、一部の計算をメモリ上じゃなくてレジスタ上で
やるのは俺もやってる。

だが、>>579はそもそもMT擬似乱数の生成自体全くやってないように思えた。
mt[]を変形してMT擬似乱数を生成しているだけなら俺の勘違いだ。噛み付いてスマン。

ネタばらししちゃうけど13切った奴はみんな部分的に8並列とか16並列とかやってるだろ？
spu_shuffle使ってパック・アンパックしてやってるだろ？
それがアリなら何でもアリだよ。

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

それが速いかどうかは別にして（っていうかcarryの計算が増える分速くない）

>>828
ごめん、それ気づかなかったわｗｗｗｗ

てか、コンテスト参加者でまだ13cycle切ってない、これから頑張る人も居るんだから、
ネタばらしは止めようぜ。

俺は、 >>598 や >>601 でいってるとおり、まじめに genrand_int32() の戻り値を
計算した上でチェックサムをとってる。

乱数を複数のレジスタに分割するのはどうなんだろうな？
たまたま場所が離れているだけで、ビット単位では元の乱数を生成しているんだし、
別にいい気もするが、、、グレーだな。

じゃあそのグレーな方法を使わせてもらうよ。

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

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

なあに、genrand_int32()の形式で要素を抽出するAPIを別途用意すれば問題ない

とりあえずストール地獄からの脱出に成功。
明日も出勤だけど>>824目指して頑張る。

ところで、
for (int i = 0; i < num_rand; i+=2) {
sum += genrand_int32();
sum -= genrand_int32();
}
とかやってみたらチート対策になったりしないのかな？かな？

俺はチートはしないよ

init_genrand_mine を変更するなとは書いてあるけど、
init_genrand_mine で初期化されたベクタでテストするとは
書いてないわけだが。

トランザム＝通常の3倍の性能
あとはわかるな？

だんごいい加減ネタばれひどいだろ
13は切ってるけど、>>828の方法は使ってない
あんたが天才なのは結構だけど、コンテスト終わってからにしろよ

残念だがその方法には芽は無いようだ。
散々罵倒したけど彼には感謝しないといけない。

なあに、単純な理屈だったよ。

Hack the Cell と見せ掛けて Hack the spu-gcc43、
と思ったら Hack the MT だったでござる。

ツンデレ？

おう

このブレイクスルーは、ある意味でCellの特性を最大限生かしたものになる。
もちろんMTの互換性・再実行性も保障できる。

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

いや、それでも詰めるには必要だけど

実装するのと極めるのは別物だからな

いいや、最後にはSIMDerだからこそできるテクニックがものを言うと思うよ。

なんか色々台無しだね。>>321 の予想通りという事かね。

どのみち最速で無い（愚直にmt[]を舐めるだけ）の方法は近々俺の日記で公開してやろうと思っている。

Fixstarsはなんでmt[]をvec_uint4との共用体にしといてくれなかったのか？
実はそこに答えがあったのだ。

>>845
既に気付いてる人間からしたら、滅茶苦茶迷惑なんですけど。

おいおい
あんまりいらんことするな
12サイクルに到達してない人間の努力は全否定か
ついでに10倍速で参加賞出さなきゃいけないFixstersの身にもなれと

>>847
10倍到達した人が多い場合は上位からってルールがあったはず
どのみち優勝不可能なコードなんだから文句無いだろ？

俺がやらなきゃどうせ上位者（BSDライセンスでソース公開）はアセンブラばっかしのコードになるんだろ？
アセンブラのコードなんて公開されてもソースの再利用性という面では意味が無いんだよ。
高速化のテクニックを、アイディアを再利用性の高い形で世に出す必要がある。
俺は俺の信念で、アセンブラ許可したFixstarsをこき下ろす

アセンブラ無しなら自分が最速で、もっとも優れたテクニックやアイディアを持ってると思ってるあたりが痛いよな……

新しいコードだとTempering相当処理は0.5命令/Word切った。
別のところが増えちゃってるんですけどね。

言ったろ？トランザム発動するって。

すまん、黙っておく。
実は何も思いついてません。ﾋﾋﾋﾋﾋ

土日でエネルギー使い果たして失速するんですね、分かります

ホント今回「も」呆れる。団子痛すぎ。
でも今回は珍しく本人が非を認めたから許す。
もっとやれ。

本当に迷惑するから公開はやめてくれ
何故そんなことをする

じゃあ締切後に公開するよ。
どうせ提出しないコードだ。

>>848に述べられているところの必要性から公開するというなら
まずはフィックスターズに直接文句言ってくれよ
その後でコンテスト終了後に非アセンブラのコードを公開すればいい
それによってあなたの言う「再利用性」の要求は達成されるのでは？

確かに再利用可能なコードとアイディアの公開は必要な要素だと思うし賛同するけど
別にコンテスト中にそれを行って競技を潰さなければ達成できない目的ではないと思う
純粋に自分の信念から公開に踏み切ろうとするのならば、理解して欲しい
また、そんな可能性は無いとは思うが悪意や自己顕示欲からそれを行おうとするのは止めて欲しい
そんなことは分別のない子供のすることだし、恐らく貴方は子供ではないので。

>>855
あ、そうなのか。ありがとう
必死こいて>>856みたいな長文書いたのが恥ずかしい
気分を害してしまったら申し訳ないです

まあ、コンテストの上位を狙うにはどっちにしろ「役に立たない」と思うけどね。
公開予定のコードはもう開発凍結するよ。

無駄だとわかったことはやらない。

無駄でも挑戦するのがロマンだろ?
まぁ、コンテスト潰しはお勧めしない。
# 今回については、「もっとやれ」とは思わなくもないがw

まあ万人にフェアであるべきだよな

>>848
>俺がやらなきゃどうせ上位者（BSDライセンスでソース公開）はアセンブラばっかしのコードになるんだろ？
>アセンブラのコードなんて公開されてもソースの再利用性という面では意味が無いんだよ。

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

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

おまえが凄いのは認めてるやるから、人の”考える”楽しみを奪うなよ。

＞全員のソースコードが取得可能になるとか、最速のコードの他にも十分早くて可読性の良いソースが
＞公開されるとかも可能性もあるだろ。
おめでたいこって。

＞おまえが凄いのは認めてるやるから、人の”考える”楽しみを奪うなよ。
考える能力の低い奴に限ってそう言うよね。
充分能力があるなら、目の前にゴールへの地図があってもその過程を楽しむことができるのに。

>>838
俺は最初から Hack the MT だとおもてたよ。

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

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

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

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

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

片や、物理は帰納の学問。全ては観測に基づく。もっともらしいと評価された
「事実」は、それを反証する観測がなされない限り「事実」であるとする。
そして時には妥協もする。物理屋は、「ありえない仮定」はよく用いる。
「仮想仕事」言葉くらいは聞いたことあるだろ？

数学屋と物理屋、どちらが上だ下だと論じるつもりは毛頭ないが、>>628 で
自ら「算術師」と名乗り、人を「さんすう屋」と呼ぶ「団子」に興味が移った。

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

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

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

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

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

完敗。

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

ごめんな。

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

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

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

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

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

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

>>830
ある程度真面目に計算するにしても、水平加算は最後の1回だろ？

>>837
>残念だがその方法には芽は無いようだ。
>散々罵倒したけど彼には感謝しないといけない。
>なあに、単純な理屈だったよ。

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

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

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

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

なあに、単純な理屈だよ。

俺は疑わしきは罰せよ、０か１かの代数ばっかし扱う畑育ちだから
数学記号とか読んでもモナー板専用の特殊文字の羅列にしか見えないわけで
最も愚かな解法で再実装してみてるが

各処理の演算コストモデルが完全に逆転してしまった。
マジでXORとシフトだけしかない世界だな

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

なんちゅう厨房の会話だw

「同じ乱数列」が何を意味するのかは、Fixstarsに質問投げたから回答待ち。

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

>ある程度真面目に計算するにしても、水平加算は最後の1回だろ？
だから？
同じ乱数列を生成するのが課題で、課題を満たした上でチェックサムを取る順番なんて自由だろ？

何度も言うけど、課題は同じ乱数列の生成で、チェックサムはあくまでも同じ乱数列を
生成しているかを確認する手段に過ぎない。
デクリメンタが時間を計測する手段にしか過ぎないのと同じ。

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

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

乱数生成しないでチェックサムだけ計算しようとしてるヤツは、ネットゲームでバグ技見つけて、
「バグも仕様のうち」とかぬかしてゲームを滅茶苦茶にするタイプか？

>>870
悪いけどな。

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

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

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

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

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

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

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

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

ごめんな。団子に入れ知恵しちまったのは俺だ。

優勝狙ってるならともかく、自分の好きな方法で好きに組めばいいじゃん

別に公的組織が開いてる大会ってわけじゃないから、心配なら純粋な最適化と数学的な方法の２バージョンだすとかもありじゃね？
ダメかもしれんが・・（確認は必要だな）

熱くなりすぎだ
回答待てば万事解決
流石にデクリメンタを書き換えてなんとかとは同列には出来んだろう
きちんと数学的に証明されたアルゴリズムを実装してるだけなんだから

それはそうと11.6まではいった
俺は当分もとのアルゴリズムのままで愚直に乱数列を生成しつつ10↓を目指して頑張るぜ

>>871
逆に聞こう
mt[]のデータレイアウトはmt19937ar.cと完全互換である必要あるか？

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

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

#define mt MT_Array.scl

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

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

みたいな論外な質問だってFAQにあがってるんだし、何ができるかどうかは
聞いたらいいんじゃないの？
自分だけの無用な追加ルールを作ってしまっても損でしかない

>>872
>sum が計算できることと、数列が生成できることは >>865 に書いた通り
>数学的には合同なんだ。
数学的に等価であるから何？これは数学コンテストじゃなくて最適化コンテストだよ？
同じ乱数列が作れるなら、実際に同じ乱数列を作って、その時間を計測して。

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

でも、参加するヤツは、ちゃんと課題どおり乱数生成しようぜ。

回答どうなるかね。回答する側も悩んでるんじゃね？ｗ

プログラムの最適化を競う大会で、気が付いたら非常に高度な数学知識を持った人しか
上位入賞できないっていうのもなんだかなぁ

>「同じ乱数列」が何を意味するのかは、Fixstarsに質問投げたから回答待ち。

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

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

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

もちろん、みんな線形合同法をつついたチートをするわけだ。そしたら突然、
「乱数生成を MT にします」。そんな感じ。

>>874
たしかに>>579の考えた方法は、数学的に正しいらしいし、その方法を求められるのは凄いと思う。

でも、方法が凄くても凄くなくても、「同じ乱数列を生成する」という課題を満たしてない以上、
今回のコンテストの回答としては不適切だろ？
デクリメンタのオーバーフローと同列に扱って何の問題がある？

論理演算を最適化するためのブール代数学も数学の一つだよ。
「^ x ^」のアレだって数学的知識に基づくモノだけど、チートなの？

乱数を変形状態で生成したら駄目だなんて書いてないと思うんだぜ。
その辺の融通がきかないと、閉区間内の浮動小数を正規形でダイレクトに生成するdSFMTは、乱数じゃないみたいな話になっちまう。

>>877
>プログラムの最適化を競う大会で、気が付いたら非常に高度な数学知識を持った人しか
>上位入賞できないっていうのもなんだかなぁ

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

クラスタ計算機持っているやつが優勝する。
俺はかなり妥協した。

よし、Cellのクラスターをつくって勝負しよう！

【内輪話】
Twisted-GFSRのループ内で何かしら集計できるのはTempering後にMSBに相当するビット以外思い当たらなかった。
加算をXOR 1個で置き換えられるのはMSBしかないだろ？キャリーの計算とかめんどいよ。

んでもってUnslicingはTempering＋加算のサイクルに織り込んで一気にやっちまったほうがエレガントかつ速いと言う結論に達した。
SPUにはそれを高速にやるために有用な命令が存在する。

>>880
>論理演算を最適化するためのブール代数学も数学の一つだよ。
>「^ x ^」のアレだって数学的知識に基づくモノだけど、チートなの？

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

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

> その辺の融通がきかないと、閉区間内の浮動小数を正規形でダイレクトに生成するdSFMTは、乱数じゃないみたいな話になっちまう。
いや、今回のコンテストとどういう関係があるのかぜんぜん意味不明なんだが？
dSFMT は同じ乱数列じゃないから、今回の課題の回答としては明らかにアウトだけど、
回答としてアウトだということと乱数であるか否かとは全く関係ない話だ。

残念だけど、数学的に「同じ乱数列」である以上は、どうあがいても
「同じ乱数列」なんだよ。

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

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

ついでに、極論すると MT は GF(2^19937) の「カウンタ」でしかない。

おっと、「unslicing」の意味がわかってる人間はここには殆どいないか

なんか、根本的にみんなと感覚が違う気がしてきたな。。。

プログラマとして、「同じ乱数列」という言葉を聴くと、「同じ (ワード|バイト|ビット) 列」という意味だと
解釈するのが当然だと思っていたんだが、数学屋は「数学的に等価」と解釈するのか？

>>884
>明らかに違うビット列になってたら

ビット列で数値を表現する方法も、数学的に考えられた一つの方法でしか
ないんだよ。

仮に１０００番目の乱数を取り出してといわれたときに、オリジナルと同じ値が取り出せるなら同じ乱数列ってことでいいんじゃね？

Tempering＋加算が爆速になったのはいいとしてGFSRの処理のほうがめんどいことになってる。なんとかサイクルを減らせないものか
ミスアラインロード・ストアがボトルネックになるのは結局同じだった。何かしら方策を考えないといけない。


>>887
BCDでも2進数でも浮動小数方式でも数値的に値を表してれば十分でないの？
データ構造なんて抽象化してナンボだよ。C++屋の考えだけど。

>>888
そんなこと100も承知で、>>887のように解釈してるんだよ。
どっちの解釈を求められていたかは、公式の回答待ちだ。


とりあえず、暗黙の了解が違いすぎるのはよく判った。
>>579 とは絶対に一緒にプログラム書きたくない。
「utf-8で文字列返して」って言ったら、平気でutf-8をbase64エンコードして返してきそうだ。