とりあえず、現段階のコンパイラは以下に集中する : 構造体アクセスの生成 bit-IRの生成 packing (SIMDレジスタを活用するように纏めてロード/ストアする) 制御コードの生成 Graph-IRの生成 プレディケーションによるselectをIFに戻す Basic Blockの関数化 i…

というわけで評価の準備に入る。数回に分けて。 spuのbinutils ./configure --prefix=/opt.cell --target=spu-elf 特に何も。binutilsは何が無くとも先にビルドする必要がある。 newlib spuではnewlibを使う。プラットフォームの抽象化は主にnewlibのlibglos…

論文書いてて気付いたけど、GCC 4.4にはそれ以前のバージョンのGCC 4.xに有った、『char型のbit-fieldはpackできない』というバグが修正されている。 http://gcc.gnu.org/onlinedocs/gcc-4.4.0/gcc/Variable-Attributes.html http://gcc.gnu.org/gcc-4.4/cha…

skySchemeのプログラムは、スコープ間のやりとりをパケットの送受信で行うと仮定している*1。つまりデータのアップデートも返信のパケットによって行われ、インポートするのは呼び出し側の責任になる。(これはもちろん隠蔽されるし、非効率なので最適化フェ…

IPsecは、鍵の交換と暗号化そのものが明確に分離されているアーキテクチャで、IKEは既存の実装を流用しつつ、暗号化(とIP)だけ自前で実装するという方向性が行けそうな気もする。 IPsec的には暗号化キーと、各エンドポイントのアドレスをSA(Security Associa…

http://wiki.osdev.info/?%A5%D3%A5%C3%A5%C8%CA%C2%CE%F3%B2%BD 今後も拡充予定。。 テーブル参照の置換 DESやAESのような暗号化をbit slicingで実装した！というものは、要するにS-Boxの参照処理を論理ゲートに置き換えていく。 S-Boxとはランダムな対応表…

http://wiki.osdev.info/?MachineDescription 既存のコンパイラではマシン記述をプロセサ機能を記述するために用いていた。マシン記述は命令と動作の対応を示したもので、コストの導出は別のプログラムによってなされることが多い(gccやLLVMの場合)。 ところ…

skyは3種類のIR(中間表現)を駆使して、プロトコル処理で良く出てくるタイプの処理を最適化したい。 IRにはbit-IR(1bit単位の幅で構造体を表現する)、graph-IR(bit-IRで提供されるオブジェクトに対して演算や比較を提供する)、word-IR(CPUのword幅に合わせた…

http://shinh.skr.jp/h/?HackTheCellPostMortem - 学生部門2位の木下君は一緒にPROSYM下働きをした人だな*1。 最適化手法を分類整理して使えそうなのをパタンとして入れ込む事にする。 ストレージ仮想化 skySchemeの応用として、高スループットなストレージ…

GCC4.3以降にはstruct-reorgが取り込まれているため、特殊な条件下で内部データ構造を最適化することができる。 構造体の最適化を行うためには、以下の条件をクリアしなければならない。 プログラム全体を一度にコンパイルする(-fwhole-program --combineを…

http://journal.mycom.co.jp/articles/2009/03/30/asiabsdcon4/index.html 元々はpuffsとのからみで( http://www.netbsd.org/docs/rump/index.html )デザインされている。 我々の関心は常にオーバヘッドで、もしオーバヘッドが受け入れ可能なら、カーネルコ…

昨日の奴はbitsliceとも呼ばれているらしい。AJAXみたいに誰かbuzzwordを作ってくれるといいんだけど。 http://dsas.blog.klab.org/archives/51389536.html bitsliceといってもAm2900でなく。少なくとも2000年代のテクニックではないよなVRAM操作的な意味で…

http://parabix.costar.sfu.ca/ SIMDでXMLパースやREマッチを行うもの。要するに1byteの処理を8本のbitstreamの処理に変換し、可能な限り並列にandとかorとかnotを取る。andやorはSIMD演算器の長いレジスタの中で完全に並列に求めることが出来る(cf http://d…

http://www.ie.u-ryukyu.ac.jp/~kono/papers/kono/2002/okinawa_workshop.pdf skySchemeに近いことをやっている論文を見つけた。 やりたいことも近い。つまり、継続を基本概念に持つ実行システムはコンテキストスイッチなどもそのまま表現できるので、"自然"…

skySchemeの重要な視点は、OSのI/O抽象化戦略が全てにフィットすることは"絶対に無い"というもので、これ自体は非常に当たり前の事だが以下について示唆をもたらす。 シングルレベルストアは問題を解決しない C言語が用意している唯一の抽象化はメモリ抽象化…

学会投稿よりも前に中間発表が有るので一般人にもわかる解説を先に考える必要が有る。元々僕はそういう解説を準備するのが非常に苦手で、過去に何度も研究リソースの獲得に失敗してきた過去がある*1。 説明するべきパート hardest firstの教えに従って、skyS…

なかなかTCPでは有意な結果を出せずにいる。けど、PROのCFPも出たことだしそろそろ仕様をフリーズしてベンチマーク用の実装を始めないと不味い*1。 inflate, deflate, JPEG, MPEG, ... 非常にベタなネタだが、skySchemeを使ってinflateやdeflateを実装するの…

今の実装は一旦Schemeコードをコンパイル(scheme→scheme変換)する必要があって非常に使うのが面倒。せっかくのインタプリタなのだから、言語の中で完結したテスト用の実装が有るのが望ましい。 最初にいきなり躓いたのはquoteの逆、要するにシンボルを評価し…

テキスト構文も一応設計してみたけど、バイナリ構文と同じところが多いので統合することに。 当初、Preccsよりも絞り込んだプリミティブがウリだったのに、なんだかだんだんと同じような内容になってきてしまった。 バイナリ構文はTTでもしゃべったdefine-pa…

printfは%dとか%sのようなフォーマット文字列を受け取って、言語内のデータを人間に可読な形で入力する。その逆のscanfもある。 skyschemeでやるようなプロトコル記述言語はpackとかunpackのフォーマット文字列をS式に置き換えるけど、同様にprintfのような…

skySchemeの開発ベースをmoshに移すことにしたのでLLVMを呼べるようにする。LLVMはC++で書かれているのでちゃんとしたbindingを書くのが望ましいが、面倒なのでFFIを使う。原理上、FFIからはCインターフェースしか使うことは出来ない。 現状ではかなり再現性…

人間にプロトコル記述をしてもらう以外に、既存のソースコードからプロトコル記述を抽出する方法を考えることもできる。 ASN.1 http://wiki.osdev.info/?ASN.1 ASN.1は、SSLで使われる秘密鍵といった各種PKIで利用されるフォーマットやSMNPなどのネットワー…

skySchemeはGCではなく明示的なメモリ管理を前提に設計している。もし、GCが利用されるようなケースがあるならば、それはホストSchemeで実行されることになる。 明示的なメモリ管理とは、オブジェクトの寿命が明示的に決定されていることを指す。skySchemeに…

skySchemeにも簡単なシェルが欲しくて、例えば、 [VUSB] > [USB Mass storage] > [SCSI] > [EXT2].myfs myfs > (dir "/").mydir mydir > (myfilter) > [HTTP server]のような感じでHTTP経由でファイルが公開できると良い。(skySchemeはR6RSと異なり、空白を…

一級継続が無く、(現在の仕様では)クロージャも無いので、基本的にはMinCamlのステップを踏んで個々をデザインしていくことが出来る。 最終出力の確認 最終出力は"あいまいでない"プリミティブ関数の呼び出しの連続で構成されるBB(Basic Block)と、BB同士を…

研究室内で計画(skySchemeを使った研究について)を発表した。 http://storage.osdev.info/pub/idmjt/diaryimage/0901/neta090110l1.pdf ここでのScheme subsetがskySchemeに相当する。 本来はPPL( http://millsmess.cs.uec.ac.jp/ppl2009/ )合わせで実装とか…

インタプリタはいろいろと紆余曲折有ったが、とりあえずschemeはそれなりに習得したということにしてコンパイラの製作に進む。 Schemeコンパイラといえばアレを読む。 http://www.iro.umontreal.ca/~boucherd/mslug/meetings/20041020/minutes-en.html 書か…

DrSchemeと紛らわしいので、dryScheme→skySchemeと改名した。??ySchemeにしたくて*1、flySchemeとかcrySchemeとかいろいろ考えたけどこれで。 以前Monaで話だけ出ていて立ち消えになった、「S式によるIPC」を想定したシステムに方針を転換して、 普通の処理…