いつの間にか始まってた！

今回の課題は、連立一次方程式の解、ってことで定石通り
LU 分解の right-looking で攻める人が多数になりそうな予感。

しかし、前はソートだったし、大学生のアルゴリズムの演習みたいな枯れた課題が多いですね。
とはいえ、アーキテクチャが変われば、攻め方も変わるというもの。
前回より戦略に幅が出やすい問題のような気がするし、動向に要注目です。

MITでやってるCellプログラミングの講義。

Selected Projectsを見ると、
Global Illumination や Distributed Realtime Ray Tracer 、Speech Synthesizer 等、骨のありそうな課題が並んでいます。
てか、普通に組むのでも結構大変じゃん、この課題。
ほんとに1ヶ月で、他にも講義とかあって忙しいはずなのに、
Cell向けにマトモに最適化されたものができるの？
(最悪PPUしか使いませんとかなら分かるけど)

そこまでMITは優秀なのか！？
それとも若さゆえの勢いなのか！？
くそっ、嫉妬してしまうぜ、奴らの若さと才能に。

てことで、そろそろ課題が出来上がって、webに公開されるのかも。楽しみ。


レンダリング系だと、巨大なメッシュやテクスチャの扱いが面倒ですし、GIをやろうとすれば、
テンポラリの領域も相当な大きさが必要になるでしょう。

ベクタライズなんて根性があれば誰でもできますが、
256KBの空間とDMAを駆使してプログラミングするのは、
かなりの障壁です(そこも慣れと根性なのかもしれませんが)。
巨大なメモリへのランダムアクセスが苦手というのが、SPUの最大の弱点ですねえ。

かといって、LSの代わりにキャッシュを載せたところで、ロジックやタグが載るので、
128KB程度のI/D混載キャッシュしか載らないとすると、どう考えても性能が出にくいので、
やっぱり今の設計で正解か。
いや、6コアでキャッシュ256KBが一番(楽で)良かったんじゃないかな。うん。
(ピーク性能は落ちますがね)


そこらへんの大変さは、当然IBMも分かっているわけで、
SDK2.0をみると、software managed cache や spu code overlay といった、
プログラマの負担を減らしてくれるライブラリが新たに提供されています。


software managed cacheは、

a = cache_rd(name, addr_a);
b = cache_rd(name, addr_b);
cache_wr(name, addr_c, a + b);

といったように、読みの場合、グローバルアドレスを与えると、
キャッシュに載っているかを判定し、載っていなかったらDMAでローカルに持ってくる、
載っていたらローカルにある値を返す、という処理を行います。

キャッシュはWAY数やTAGの定義をプログラム毎に変えられます。
name を変えることで、複数のキャッシュを持たせ、効率をあげることができます。

ってさあ、重いよね、明らかに。ヒットしてもソフト的な負担が相当に重い。
なにせ、ハードのキャッシュはアドレスと大量のタグとの比較を並列処理で一瞬で終わらせてるから、
それをソフトでやるのはどうしても相対的に厳しい。

それを改善するために、LS上のキャッシュラインをロックして、
ライン単位でしか判定処理を行わないというインタフェイスも用意されている。

それなら速いんだけど、ラインのアラインの問題もあるし、使いにくさは残る。
どのみちポインタを辿る様な処理はかなり煩雑な手続きになってしまう。

また、ライン単位のようにアクセスの粒度が大きいことが始めから分かっていれば、
最初からDMAを使えばいい気もする。
といっても、DMAより扱うのは楽になるので、そういった意味で存在価値はあるが。

キャッシュでも、次にアクセスするブロックが予測できるなら、
予めtouchしてprefetchしておけば、
DMAのダブルバッファとほぼ同等の効果が得られるので、
やっぱLSじゃなくてキャッシュでも良かったのではないかと、若干思うんだよなあ。
そこらへんの設計思想は難しいね。


code overlayに関しては、SIJAMのblogが詳しいです。
要は、関数を mov ax,xxxxh int 21h のような感じに、番号+callで呼ぶようにします。
callされたら、目的の関数がLSに載っているかを調べ、載っていなかったらLSにDMAします。
また、callだけでなく、retする時も、戻り先の関数がLSに居るかを確認しなければなりません。
結構な大技です。
(ほんとは、もっといろんな処理してますが、詳しくはリンク先で)

以上、
d-cache代わりに software managed cache,
i-cache代わりに code overlay
という選択肢もあるよ、という話でした。

よろしくお願いします。(社会人的な癖)

が出ております。

って最近忙しくてプログラム組む時間ないなあ。
よっしゃ、有給取るしかねえ、って無理だわ。
ということで、他の人は頑張っているのだろうかと
国内のCell関連サイト、ブログ等を集めてみた。

企業系
cell.fixstars.com/pukiwiki/index.php The Cell Processor PukiWiki @ FixStars
blog.cell.sijam.com/ CELLプロセッサ @ SIJAM

ブログ系
d.hatena.ne.jp/hagecell/ Cellでがんばってみたログ
rakuto.blogspot.com/ young risk taker
yoffy.dyndns.org/
d.hatena.ne.jp/tueda_wolf/
blog.goo.ne.jp/p3lire

その他
wiki.cellfan.info/index.php/%E3%83%A1%E3%82%A4%E3%83%B3%E3%83%9A%E3%83%BC%E3%82%B8 Wiki CellFan Info
type-x.ddo.jp/pukiwiki/index.php?PS3Linux 突然消失するかもしれないWiki
blog.goo.ne.jp/sdpaninf/ グリッド＆クラスタで最適化

あんまりないですね(きっと探し方が悪い)。
しかし、重要な情報は全部IBMにあるので、
情報的にはそこだけ読んでれば大体OKです。

12/14に色々愚痴ってみましたが、この辺の話は全部
Maximizing the power of the Cell Broadband Engine processor: 25 tips to optimal application performance
に書いてあるし。

Tip 21の
if (a > b) c += 1;
else d = a+b;
の最適化が面白いね。
自力投機実行って奴か。

しかし、恐ろしくシンプルなアーキテクチャ故に
ソフトのデキが速度に直結しているというのは面白くもあり怖いね。

もうチャレンジ可能なようです。

規定課題部門はソーティングです。
マルチコア＋SIMD＋狭メモリ空間という、
可能性と制約に満ち溢れたチップの中で何が最適なソートなのか、
興味深いところです。

odd-even merge sort で巨大なソーティングネットワークを作るのが無難か。
oemsに関しては
d.hatena.ne.jp/yupo5656/20060617/p3
が非常に参考になります。

ただ、8要素までなら shufb * 2 + cmpgt + selb * 2 で、SIMDの恩恵を簡単に受けられるけど、
要素数が膨大になってくると、simd比較命令にかけるためのデータを用意するコストが馬鹿にならない気がする。
あと、ただの並び替えだったらいいけど、データ系列をキーに従って並び替えるのも、単純なSIMD化の妨げになりそう。
って、並列ソートの本とか読んだことないので、
恐らくそのあたりの解決策は既にある…といいな。

毎日更新してやろうかとと思ったけど、さすがに無理。
そんな毎日帰宅してから、ネタを作れるほど元気ないっす。

突然ですが、Cellのいいところは
メインメモリ⇔ローカルストア(LS)　を　DMA
ローカルストア⇔レジスタ　を　奇数パイプ
レジスタ⇔演算器　を　偶数パイプ
と、並列化することにより、メインメモリから演算器までの間において、
DSPばりに滞りなくデータを流せることにあります。(たぶん)

じゃあ弱点は？
というと、よく言われるのがLSが256KBしかない、あたりでしょう。
確かにこれは、プログラミングの制約としては、かなり大きい。
マルチコアと併せて、プログラマへの負担はかなり大きくなってしまう。

けどこの辺は根性というか気合というか、
アイディアでカバーできるとするじゃないですか。無理やり。


で、それを差し引いても厄介だなあ、と思うのが命令セット。

cell.scei.co.jp/index_j.html
を見ると分かりますが、
SPEの命令セットって、レジスタが128本になってる代わりに、
オペコードが削られて、命令の種類がかなり限定的になっている。
演算全般が得意であって欲しいのに、意外と苦手な処理がある。

例えば、32bit同士の乗算。
できません。
やるなら、mpyh,mpyh,mpyuで部分積を3つ作ってから、
a,aで足しこんで完成。
(上位16bit同士の乗算は32bitに収まらないので計算不要)
遅延は10clkくらい。

といっても、32bit同士の掛け算ってそんなにSPEではないだろうから、
これは許せる。


個人的にまずそうだと思ったのが、
vector shortだと8スロットあるのに、
8スロット同時に積和ができないこと。

偶数スロット同士で掛け算してvector intを足すことはできるのですが、
これだと1命令で4スロットしか動かない。
その代わり、32bit精度なんだけど、
画像処理でそんなに精度要らないんだよね。
演算精度は12bitあれば十分。
パネルドライバが最近ようやく10bitになってきたくらいだから、
それ以上あっても出力には現状殆ど関係なくて、無駄なわけだ。

もし、8スロット同時に動かせれば、色々な映像処理の
理論上限スループットが倍近くになるだけに残念です。


altivecだと、vmhaddshsとか、
そういう16bit型で8スロット積和ができる便利な命令があるのにね。
ただ、altivecは32本しかレジスタがないので、十分なunroll-loopができないから、
ストールしやすく結局本来の力は出せない気がするので、
SPEの命令を削ってレジスタを増やす戦略は、
トータルでは間違いではないのかもしれない。
(それに、SPEにしかない命令もあるし、そこは一概に比較できない)


となると気になるのが、
altivecのレジスタを128本に拡張したという XBOX 360 の PX か。
altivec 機能互換かつフラットに128本扱うためには、
32bit固定長は諦めなくちゃならないので、
一度に見えるのは32本な窓とかバンクで対応してるのかな。
それとも64bit長命令？うーん、それは避けたいな。

てか、そういう情報ってどこにあるんじゃー。
よくわからんので寝る。

学部の頃(えーと、5,6年前ですか)、課題で作った超古典的raytracerを
今の環境に手直しして、
cygwin @ Core2Duo E6400 (2.13GHz)
linux(fc5) @ Cell 3.2GHz
で動かしてみた。

ソースは全く同じで、
make時のオプションも -O3 -funroll-loops で同じ。

bmpで保存する際に、Cell側がBigEndianなので、バイトスワップしてるくらい。
SPEは使わず、PPEのみの使用。

結果は、
0m06s @ Core2Duo , 0m10s @ Cell
0m23s @ Core2Duo , 0m25s @ Cell
0m21s @ Core2Duo , 0m19s @ Cell
2m20s @ Core2Duo , 1m56s @ Cell

PPEは意外と速いな。
全部倍くらい差が付くと思ったんですが、
単純なコードなので、純粋にクロックの高さが結果に出てるのかも。

spuでもやるか！と思ったんですけど、無理やり同じソースをspu-gccに食わせたら、
リンク時に relocation truncated to fit : SPU_ADDR16,SPU_REL16 が大量発生して失敗。

このエラーは、コンパイル時は相対ジャンプを想定してたけど、
いざリンクしようとしたら届かなくなっちゃった、ごめん、
という場合に出るものと思っていたのですが、
(その場合は、メモリモデルとかを変えたら大抵通るようになる)
どうやらSPUの場合はこれが出る＝256KBオーバーらしい。
16bitしかアドレス空間ないのか。なるほど。

いろいろライブラリをリンクしてるし、
無茶って事は分かってたので良いけど、
やっぱportingするの面倒だよなあ。
レンダラのコアだけ切り出せば、とりあえず動くようになるとは思うが、
面倒だからまた今度。

これ、アルゴリズムを賢くして若干フェイク寄りにすれば、
多分10倍くらい速くなるし、
ちゃんとベクタライズしてSPE*6使い切れば、
さらに10倍くらい速くなるだろうから、計100倍くらい高速に…
なったりしないかなあ。


使ったソース
kmkz.jp/mtm/lab/raytrace/raytrace-20061212.tar.gz

遅ればせながら、PS3にFC5を入れてみた。

まいにちいっしょのセーブデータが何故かコピーできず、
フォーマットとともに散ってしまったのが誤算でしたが、
とりあえずインストールは至極簡単。
そして、可も不可もない、至極普通のFedoraが入ります。

おさらいをしますと、
- FC5 on PS3 及び PPU/SPU の開発環境は無料で手に入る
- OS は全て hypervisor 上で動く
- hypervisor によってデバイスは仮想化されている、らしい
- RSX も hypervisor で隠蔽されており、直接叩けない
- 現在 RSX は使う方法は未公開


うーん、最初からxglとかが動いてれば、
デスクトップ環境としても、かなりインパクトのあるシステムになったと思うのだけどなあ

といっても、リモートで CELL で遊べれば、今のところは十分だから、
気にすることはない。


とかいいつつ、いつもの癖で apache と samba の設定をして、
無駄にサーバに成り果てたよ、うちのPS3は。

apache/2.2.0 on PlayStation3 !
www.cygx.mydns.jp:8080/~mnishibe/

アクセスできない時は、
僕が龍が如くをやってるか、
レジスタンスをやってるか、
のどちらかです。

つか、サーバ用にもう1台PS3買おうかな。

addon disc の
/doc/ApplicationProgrammingEnvironment.html
を見るとやり方が書いてありますが、
日本語だと、 fixstars さんの wiki に詳しい説明があります(表題)。

といっても、指定の rpm を掻き集めて rpm -ivh *.rpm するだけです。
すると、spu-gcc や libspe が入るので、一通りの事ができるようになります。

最初は、PS3でHello,Worldプログラミングで、動作テストをすると良いでしょう。

というか、こんなページ書かなくても fixstars さんのところで全て済みますな。

しかし、addon disc に入ってる 20061107版 libspe2 の spe_context_run() で
argp と envp が渡されないバグがあったって、凄いな。
豪快すぎるんですが。

ozlabs.org/pipermail/cbe-oss-dev/2006-December/000682.html
↑あたりの新し目のlispe2-2.0.1を入れた方が良いかも。

と思ったら新しい add on disc 出てるじゃん。
ftp.uk.linux.org/pub/linux/Sony-PS3/