※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

buyobuyonのぺぇじ


コンパイラ…、
ひどく汚いソースなので、不特定多数の人に見られるのは避けたい…、
とはいえアップしないわけにもいかない…。
というわけで、メンバーのみ閲覧可能のページを作成して、そちらにアップしました。

コンパイラのダウンロードはこちらから
その他のプログラムのダウンロードはこちらから


残り作業


チェック/デバッグ

  • parse error時の過不足ないメモリ解放

最適化

  • restore(imm in 変数)→mov(imm)
  • 定数レジスタの設置
  • 遅延スロットとSTOREDの直後のスロットを埋める
  • その他


進行状況


4/30(Mo)


rs232c経由でレイトレ完動しました!
細かいところを修正し、BAUDを下げてみたら動きました。
クロック周波数を25MHzにしていることもあり、cosなどの計算で時間がかかり、
入力バッファがあふれてしまっていたようです。
バッファのサイズを今の4倍くらいにできれば、BAUDはデフォルトの値で大丈夫なのでしょうが、
さすがにそこまで余裕はなさそうでしたので…。
さすがにフローコントロール機能をつける気力は無かったので、BAUDを下げる方法をとりました。
  • とりあえず、お疲れ様でした。
    rs232c通信用に作成したファイルを
    com_diff.ZIPにまとめてあげておきました。 -- buyobuyon (2007-05-01 19:10:13)
  • おつかれさまです! -- harry (2007-05-02 12:42:35)
  • お疲れ様です!&ありがとうございました! -- yastak (2007-05-02 23:05:14)
  • 結局、その後、確実に動作するようになって、
    菅原先生にも見ていただき、機材もその日のうちに返却しました。

    あと、拡張基盤(と箱)は回収されなかったので、いま預かっているのですが、
    どなたか心優しい方、もらってください。 -- buyobuyon (2007-05-04 19:43:45)
名前:
コメント:


4/28(Sa)


ええと、いくらか修正した後、実機でrs232c経由のechoが動きました。
その後、rs323cは下のビットから順に流す(リトルエンディアンって言って良いのかな?)ことに気づき、修正。
echoだと、2回ひっくり返って元に戻ってしまうので、この問題が見える形で現れないのですね…。
まだCPUへの組み込みに成功していませんので、レイトレ実行まではもう少しかかりそうです。


4/17(Tu)


rs232cコントローラ修正中。
とりあえず、バッファへの同時アクセス問題が解消されていなかったので、修正。
それから、echoにバグ発見。STATEが0のときでBUSYが1のときに、
START信号を0にしていないので、ずっと書き込み要求が出ることになるはず。

  • ちなみに、先日、テストベンチを書いてみて、
    フリーのシミュレータで実行してみたら、
    簡単なテストは通りました。 -- buyobuyon (2007-04-17 14:19:43)
  • >バッファへの同時アクセス問題

    あ、忘れてました…。申し訳ないですm(_ _)m
    -- yastak (2007-04-17 19:00:09)
  • すぐ直せたので、大丈夫ですよ。
    滅多に起こらない問題なので放置してしまっても良かったのですが…。 -- buyobuyon (2007-04-18 12:20:48)
  • もう一つバグを修正したらシミュレータでechoが動くようになりました。

    readの方の問題だったようです。
    バッファから値が出てくるのを待つためのステートが抜けていたようです。

    むしろ、自分で書いたテストベンチはなぜ正しく動いているように見えたのだろう…。 -- buyobuyon (2007-04-18 16:07:27)
  • ・rs323cは下のビットから順に流す。
    ・echoで、write命令を発行した後、もう1クロック待つ -- buyobuyon (2007-04-27 22:40:23)


3/19(Mo)


  • tsuyさ~ん、math.sを眺めてみたのですが、何か間違っていますかね?
    確か、atan内でのlatan_loop呼び出しがインライン展開された部分に
    変なdivが入るという話だったと思うのですが。
    手元にあったmath.mlを新たにコンパイルしたものなので、
    見ているmath.sそのものが違うかもしれないのですが、特に変な部分は見つからず…。

(長いので、中略)

  • すみません、返信が遅くなってしまいました。

    インライン展開されているということに気付いていませんでした。
    math.mlも多分同じ定義のようですし、つじつまもあってますし、問題ないようですね。
    早とちりというか、理解不足でお手数をおかけしました。すみません。 -- tsuy (2007-04-03 00:27:58)
  • いえいえ、インライン展開を実装したはずの私も、
    最初に見たときには混乱しましたので。
    中途半端な回数だけインライン展開したのが悪かったのかもしれませんね。 -- buyobuyon (2007-04-03 16:12:03)


3/18(Su)


ちょびちょびとコンパイラのデバッグ中。

一ヶ所、呼び出す関数を間違えていたもので、
関数適用の構造がある場合にメモリリークを生じていたようです。

↑の問題を解決した現時点で、メモリリークは生じなさそうな感じ…。
malloc/freeの際に、間に関数を挟み、
確保したが解放していない領域の先頭アドレスを2分木に保存するようにしてみたところ、
fibやmin-rtのコンパイル終了時にはこの2分木は空でした。

もちろん他のプログラムではメモリリークを生じるかもしれませんが…。

この2分木に保存する処理を追加したときに極端に遅くなったところを見ると、
かなりの回数mallocしていたと言うことですね…。

  • あぁ…、考えてみるとこの場合は、平衡木にしないなら
    むしろリストにしておいた方が良かったかもしれませんね…。 -- buyobuyon (2007-03-18 17:51:22)
  • 忘れていましたが、parse errorの時にはメモリリークが生じてしまいますね…。 -- buyobuyon (2007-03-18 18:14:00)


3/17(Sa)


皆さん、どうもお疲れ様でした。
とりあえず完動して良かったですね。

ええと、一時的にコンパイラをページから削除してあります。
実演の日までには形を変えて戻しておくつもりですが、
もしそれまでに必要なら言ってください。


3/14(We) Part.3


ええと、(inv (inv x))をxに、(1.0 *. x)をxに変換する最適化を実装しました。
fdiv, fsqrtの変換方法から言って、結構効果があるはずだと思ったのですが、
プログラム全体におけるfdiv, fsqrtの割合が少ないのか、あまり良い効果は得られませんでした。
実際に適用してみて、命令数が0.2%減ったくらい…。
あ、でも浮動小数点数演算ライブラリの方に適用するとある程度は効果があるかもしれません。

そういえば、math.s、fdivの符号部分に問題のある古いバージョンを使用してコンパイルしたので、
結構問題があるかもしれません。
というか、なぜそれでもレイトレがあれだけ動いているのでしょう…。

  • inline展開の程度を中途半端にしたら、
    saveの挿入部にバグが現れました。 -- buyobuyon (2007-03-15 04:13:43)
  • 修正しました。一つフラグを見落としていたみたいです。 -- buyobuyon (2007-03-15 04:25:40)
  • 違う…、何か別の要因のようです。
    inline=256, opt=1とした時にエラーが出る…、
    まぁ最悪そのパラメータを使わなければ良いわけですけど…。 -- buyobuyon (2007-03-15 04:33:29)
  • 今度こそ直りました。
    restore+mov→restoreという変換で、
    ちょっとしたミスをしました。 -- buyobuyon (2007-03-15 05:12:36)
  • >tsuyさん
    そういえば、定数畳み込みで、(inv 定数)が
    定数に変換されるので、今のコンパイラなら
    /. 2.0 → *. 0.5 が自動で行われますね…。
    すみません、気づくのが遅くて。 -- buyobuyon (2007-03-15 05:17:17)
  • とりあえず、
    ループを9に、int_of_floatを切り捨てに、
    新たなコンパイラでコンパイル、
    という3つの変更を加えたところ、

    (104, 101) : (0, 41, 52) <--> (0, 39, 52)

    この1点だけ、色が2(以上)違う点がある、という状況になりました。 -- buyobuyon (2007-03-15 07:19:38)


3/14(We) Part.2


ええと、朝の時点では、

総命令数:4,761,859,127
NOP数:713,139,256

でしたが、今では、

総命令数:2,293,078,714
NOP数:302,635,866

となりました…。
最適化って重要ですね…。
一応、今日実装したのは、β簡約・インライン展開・定数畳み込み・11bit即値演算の使用です。
不要定義除去は仮想マシンコード生成後(11bit即値演算への変換の直後)に行っているので、
これでMinCamlに実装されている最適化はほとんど網羅されたはずです。
(if not x then A else B → if x then B else A は未実装)
SPとHPを見た感じでは、メモリはまだまだ余っていますが、既にこれ以上インライン展開しても
効果がなくなるところまでは展開したので、後は…、ifの展開ですかね…。
ちょっとすぐには実装できないような気がしますが…。

とりあえず、あとは、余裕があれば、余っているレジスタを存分に利用して、
定数のmovを減らしたいですね。何かアセンブリコードを見たら、15%くらいが
movだったもので…。ちなみにNOPも15%くらいを占めています。
NOPは簡単に取り外せるものだけ何とかしますね。


3/14(We) Part.1


シミュレータで、総命令数などを調べたところ、

総命令数:4,761,859,127
NOP数:713,139,256

だそうです…。
最適化なしとはいえ、どうなのでしょう…。
ちなみに、スタックポインタは最小でfffa3、ヒープポインタは最大で1eb86ということで、
インライン展開などの余地は十分に残されています。
あと、レジスタは128個中、使用しているのが確か20個未満だったと思うので、
まぁ思う存分使えます。

  • FEQ演算(コンパイラ内部で変換している)に問題があることに気づき、修正。
    FSUBで2数の差ととり、cmpeqiで0と比較することにした。
    FSUBは答えが0なら0x00000000Uを返すはずなのでこれでOKのはず…。 -- buyobuyon (2007-03-14 18:48:28)
  • cmpeqiでなくて、cmpeqでr0と比較でもOKですね。
    後者にします。 -- buyobuyon (2007-03-14 18:49:43)
  • math.sを見ていて思ったのですが、ひょっとして関数ur_tan_loop
    のループ回数が19回のままだったりします?
    一番最初にあげたOCamlライブラリファイルのループ回数が19回で、
    その後精度テストで精度が保証される最小の回数が9回であることが分かりました。
    ということで、テストファイルとともに訂正したファイルを上げたつもりでしたが、
    分かりにくかったようですみません。
    OCamlでのループ回数を定めた変数large_nはur_tan_loopでしか使ってないので、
    math.sの24行目、
    mov r13, 19;

    mov r13, 9;
    にすれば修正できるかと思います。
    勘違いorテストは100万パターンでしか行っていないので実はループ回数が足りない
    とかだったらすみません -- tsuy (2007-03-14 19:56:36)
  • math.sについてですが、もとのOCaml文法で書いたライブラリで
    定数で割る箇所が多いのですが、例えばx/.2.0とするよりもx*.0.5と
    する方がいいですよね。ひょっとするとコンパイラの最適化でなんとか
    なるのかもしれませんが、とりあえず書き換えてみます。 -- tsuy (2007-03-14 20:58:45)
  • 元のライブラリの関数ur_tanの2行目、int_of_floatがあるのですが、
    これはmath.sの46行目のftoiのみに対応しているんですよね?
    OCamlのint_of_floatは切捨て、ftoiは四捨五入なので、値が
    変わってくる気がするのですが、どうなんでしょう。勘違いだったらすみません。 -- tsuy (2007-03-14 21:12:03)
  • すみません、上のほうの書き込み、19回なのはループ回数でなく
    ループ用の変数ですね。 -- tsuy (2007-03-14 22:40:14)
  • ええと、ur_tan_loopの19の件は、
    結局修正は必要ないということでしょうか?
    ライブラリの方はあまり把握していないもので…。

    /. 2.0 → *. 0.5の件については…、お願いします。
    ルール上コンパイラの最適化で書き換えるのはOKなのですが、
    ちょっと今からだと対応しきれなさそうなので…。

    それから、int_of_float→ftoiとしています。
    コンテストルールのint_of_floatの仕様も
    四捨五入になっていますので…。
    とすると、ftoiする前に0.5足したりしておいた
    方が良いのですかね? -- buyobuyon (2007-03-14 23:25:16)
  • ur_tan_loopの方は、単に言葉を間違えただけで、修正は必要です。
    たびたびすみません。
    ループ変数と定数の書き換えはすでに行い、tsuyの方に上げました。

    OCamlのint_of_floatを用いたライブラリでテストを通ったので、
    やはりコンテストのライブラリは修正した方がいいかと思います。
    四捨五入を切り捨てにするのだから0.5引くのですかね。
    一応、上げたプログラムにその場合のコードをコメントでつけておきました。 -- tsuy (2007-03-15 00:23:31)
  • そうですか…。
    今日コンパイラがいろいろと変化しましたので、
    明日落ち着いたところで修正しますね。 -- buyobuyon (2007-03-15 00:53:34)
  • tsuyさん、ありがとうございます。
    本格的な変更はあとにすることにして、
    とりあえず試しに0.5引く処理を入れてみたのですが、
    少し誤差が減ったようです。
    r, g, bのいずれかが2以上違う点は

    (109, 98) : (0, 41, 75) <--> (0, 38, 71)
    (104, 101) : (0, 41, 52) <--> (0, 39, 52)

    の2つになりました。
    とりあえず、パラパラ漫画にしても
    違いがわからない程度にはなっています。 -- buyobuyon (2007-03-15 01:10:42)
  • とりあえず、現時点での最新版の各プログラムをあげておきました。

    コンパイラとmath.hは今後変更する可能性がありますが、
    それ以外は基本的にこのままになると思います。 -- buyobuyon (2007-03-15 02:44:46)



3/13(Tu) ~Part.2~


レイトレを実行したら白い画像が…(画像削除済み)。何か間違えたらしいです。原因を探ってみますね。

  • ↑の原因は判明しました。
    finvsqrtを少し修正したら直りました。
    直っても、やはり白い点3つはあいかわらずですね…。 -- buyobuyon (2007-03-13 16:49:07)
  • pika.sldで実行したところ、繰り上がりバグ修正前とは違って、
    一応、正しい画像にノイズが入ったようなものが生成されました。
    修正前は、そもそも形が違っていたので…。

    でも、今回修正したバグは頻繁には起こらないだろうと思っていたのですが、
    修正してみたらこれだけ画像が変化したところを見ると、
    残っている白い点やpika.sldのノイズも、気づいていない何らかのバグが
    影響しているのかもしれません。
    引き続き検証を続けます。 -- buyobuyon (2007-03-13 17:04:29)
  • とりあえず、問題はFADD/FSUBのようです。
    FADD/FSUB以外のシミュレート関数を全てCライブラリ関数に置き換えても
    ノイズが出ますが、逆にFADD/FSUBのみCライブラリ関数で置き換えると
    (肉眼で観察できるような)ノイズは入りません。

    FADD/FSUBの中でも、符号が同じ値同士の加算が特に問題を引き起こしやすいようです。
    が、符号が違う値の間での加算もわずかにノイズを発生させているようです…。 -- buyobuyon (2007-03-13 17:52:48)
  • 大変申し訳ありません。
    白い点問題はFPUシミュレート関数のバグでした。
    論理シフトの法を考慮せず、シフト量が32を超えた時には、
    0になるものだと思いこんでいたもので、
    指数部の差(32以上になることがある)だけシフトをするFADD/FSUB関数で
    問題が生じていたようです。

    とりあえず、pika.sldで出力された画像には
    肉眼で確認した範囲では問題はありませんでした。

    contest2.sldで出力された画像は、
    境界の位置が1bitずれて、異なる色が表示されるドットが
    1つありましたがその他には肉眼で確認できるOCaml画像との相違点は
    ありませんでした。 -- buyobuyon (2007-03-13 21:11:48)
  • contest2.sldで、OCaml画像との差を調べてみました。
    r, g, bいずれかの値が2以上違ったのは3点で、
    (5, 32) : (31, 114, 120) <--> (82, 26, 38)
    (7, 42) : (255, 255, 232) <--> (255, 8, 231)
    (104, 101) : (0, 41, 52) <--> (0, 39, 52)
    という状況でした。
    最初の2つは色が違うのに違和感がないので、
    たぶん境界が1ビットずれたことによる違いで、
    最後の1つは誤差の蓄積で値が2ずれてしまったようです。

    どうなのでしょう…、もう少し何とかすべきなのでしょうかね? -- buyobuyon (2007-03-13 22:01:15)

↑がうちの班のFPUの仕様に従った場合の生成画像、↓がOCamlでの生成画像


3/13(Tu) ~Part.1~


今日はまずDIV10をどうするかを決めたあと、シミュレート関数の変更を行って、
ひたすらシミュレータ上でのテストをし、白い点問題の解決策を探ります。

家で作業していますので、何かあったらここに書き込んでおいてください。

  • pika.sldで実行すると、白い点とかいうレベルでなく、
    全くうまくいかない…。
    まだシミュレート関数が、FPUの繰り上がりバグ修正に
    対応していないので、もしかしたらそのせいかもしれませんが
    (そのせいであってほしいですが…)。

    とりあえず、いまさら焦っても仕方がないですし、
    一つずつ問題を解決していきましょう。 -- buyobuyon (2007-03-13 07:34:51)
  • よし。print_intをインライン展開します。
    これでdiv10不要。
    コードは長くなるので御覚悟を。 -- buyobuyon (2007-03-13 07:52:57)
  • div10が無くなりました。
    代わりにprint_intが100行近くなりました。 -- buyobuyon (2007-03-13 08:50:35)
  • FMULとITOFのシミュレート関数の修正終わり。 -- buyobuyon (2007-03-13 12:33:44)
  • 全シミュレート関数の修正終わり。
    これから再びテストに入ります。 -- buyobuyon (2007-03-13 13:55:22)


3/12(Mo) ~Part.2~


とりあえず、レイトレ実行に必要なプログラム達を挙げておきました。
結構量が多かったので、整理したりMakefileを作ったりするのに結構時間がかかりました。
一応、シミュレータに関してはまたすぐに次のバージョンをアップすると思います。
FPU部分とDIVに関する部分を変更する可能性があるもので。

  • とりあえず、白い点は符号が等しい
    2浮動小数点数の足し算が原因のようです。
    いろいろためしているのですが、うまくいかず…。 -- buyobuyon (2007-03-12 16:31:10)
  • tsuyのページに変更したファイルをまとめた
    fpu-sim-03-12.zipを上げておきました。 -- tsuy (2007-03-12 21:42:08)
  • ありがとうございます。
    print_int中のDIV10問題が解決したら
    シミュレート関数の変更に取りかかります。 -- buyobuyon (2007-03-13 07:06:19)


3/12(Mo) ~Part.1~


とりあえず、FPUの変更箇所をFPUシミュレート関数に反映させて実行。
ノイズは相変わらずなので、もう一度FADD/FSUBを見直してみます。
あと、FLESSの仕様変更に伴いFISNEGを変更(-0.0が無くなったので)。

  • ええと、コンパイラ・シミュレータ等、
    調整のためにいろいろと少しずつ書き換えて、
    レイトレを実行してみたら、出力されたファイルが
    正しい形式のppmファイルでなくなってしまいました…。

    一番原因として可能性が高いのが、シミュレータのDIVを、
    割る数が2のときと答えが0以上9以下のときにのみ正しい答えを返し、
    そのほかの場合には0を返すようにしたことなのですが。
    もしかしてどこかで想定外の使い方でDIVを使っているのかもしれません。
    ちょっと検証してみます。
    (たとえノイズがあっても)正常に動いたら、各プログラムをアップしますね。 -- buyobuyon (2007-03-12 09:40:44)
  • うん、やっぱりDIV結果の問題のようです。
    滅多にDIVは使っていないのですが…。 -- buyobuyon (2007-03-12 09:44:39)
  • なんと、結果が10以上になる"○÷10"演算がありました…。
    ええと…、乗算器が圧迫しているようですし、runtime.sを書き換えた方がはやいかな…。 -- buyobuyon (2007-03-12 09:48:17)
  • もう一声制約がかかれば実装できると思いますが…。
    /10だとエラーがでてしまうので…。 -- yastak (2007-03-12 10:57:51)
  • そうですね…、ちょっと考えてみます。
    とりあえず、10^nから10^(n-1)を生成する部分で
    /10を使っているのですが、
    そもそもprint_intの実装がいい加減なのでそちらを見直した方が良いかと思ってみたり。 -- buyobuyon (2007-03-12 11:05:26)


3/11(Su)


いえ、別に大した進展があったわけではないのですが、
今日になってからWiki自体にはいろいろと書き込んでいるのに、
自分のページを更新していなかったので、何となく書きこみを。

一応、FADD/FSUB/FMUL/FTOI/ITOF/FLESSの(現在の)実装を再現した関数の作成が終了しました。
ATOFとprint_floatはとりあえず諦めて、ライブラリ関数のatofとprintfを使用することにします
(これらは実機で使う関数ではなくて演算ではなくてコンパイラなどが使うものだからOK)。

あとはちょっと厄介なFINVSQRTで終わりです。

  • 一応、FPUシミュレート関数は全部作成し終えました。
    fdivやfsqrtなどのFPU演算の組み合わせで表現される演算を
    いくらか試してみたら、早速レイトレやってみますね。
    実行に何分かかるかな…。 -- buyobuyon (2007-03-11 12:09:32)


レイトレ試してみました。
何十分という単位で時間がかかると思っていたのですが、それほど遅くはなかったです。
ええと、一応ある程度正しい画像が出力されましたが、今度は肉眼でわかるノイズが3つほど入りました。
右上の球のてっぺんのあたりに白い点があるのが一番わかりやすいかと思います。
あと、その近くに少しぼやけてはいますがノイズっぽいのがあり、あと車(?)の黄緑色の部分にも
色違いの点が入っています。
とりあえず、sqrt(0)が正しく求められないなど、既に原因はわかっているものの、
デバッグには至っていないことがいくつかありますので、それらを調整してから
また実行してみますね。

  • とりあえず、sqrt(0)が問題では無かったようです。
    う~ん…、では各関数を一つずつCのライブラリ関数で
    置き換えてみてどの関数に問題があるか探ってみますね。 -- buyobuyon (2007-03-11 13:02:37)
  • FADDとFSUBとFMULの3つをライブラリ関数に置き換えたところ、
    上記のノイズはなくなりました。
    まぁ、よく使われる関数ですからね…。
    もう少し様子を見てみますね。 -- buyobuyon (2007-03-11 13:36:45)
  • FADDとFSUBの2つを置き換えただけでもノイズが無くなりました。
    原因は誤差か、バグか…。
    さすがにつかれたので、そろそろ休みますね。 -- buyobuyon (2007-03-11 13:46:37)
  • シミュレート関数作成お疲れ様です。
    昨晩ご指摘いただいた部分の書き換えと、
    丸め方式の変更を行いました。
    必要かどうかはわかりませんが、ソース中の
    変更部分をメモしたchange.txtをtsuyのページ
    に上げておきます。 -- tsuy (2007-03-11 23:43:46)
  • ありがとうございます、早速シミュレート関数の方も
    書き換えておきます。 -- buyobuyon (2007-03-12 07:12:17)


3/10(Sa)


ええと、シミュレータ用に、うちの班のFPUと全く同じ出力を返す浮動小数点数演算関数を
作成しています。
コンパイラの最適化もやりたいのですが、
とりあえずはコンテストでレイトレを完動させることを優先しないといけませんし。
まぁ、これはこれで定数畳み込みで使えるので、最適化に関係ない訳でもないですし。
FPUの演算fadd/fsub/fmul/finvsqrt/fless/ftoi/itofに加えて、
せっかくなのでatof/fneg/print_floatあたり(これまでlexerではこれらのCライブラリ関数を
使用していたので、この機会に自作関数に置き換える)を実装したいと思っています。
間に合うのかどうかは不明…。

  • まだ、fadd/fsubしか終わっていません。
    とりあえず、この時点でシミュレータでレイトレ実行してみたところ、
    結構時間がかかりました&OCaml画像と色が違う点がかなり増えました。
    r, g, bが1以上違う点を一応挙げておくと、

    (110, 19) : (187, 106, 255) <--> (155, 74, 228)
    (111, 21) : (3, 170, 172) <--> (1, 169, 171)
    (61, 25) : (27, 0, 0) <--> (21, 0, 0)
    (55, 30) : (32, 0, 0) <--> (21, 0, 0)
    (7, 32) : (119, 83, 84) <--> (100, 64, 65)
    (49, 35) : (39, 0, 0) <--> (21, 0, 0)
    (73, 43) : (255, 255, 69) <--> (242, 255, 32)
    (59, 59) : (135, 202, 0) <--> (93, 138, 76)
    (115, 64) : (203, 255, 0) <--> (129, 209, 0)
    (84, 80) : (0, 144, 149) <--> (0, 132, 136)
    (91, 83) : (252, 165, 168) <--> (250, 163, 166)
    (104, 100) : (0, 52, 87) <--> (0, 51, 76)
    (104, 101) : (0, 0, 0) <--> (0, 39, 52)
    (30, 121) : (255, 0, 255) <--> (185, 0, 177)
    (32, 122) : (189, 0, 181) <--> (185, 0, 177)
    (33, 122) : (209, 250, 201) <--> (185, 226, 177)
    (34, 122) : (255, 255, 255) <--> (185, 226, 177)
    (37, 124) : (255, 30, 255) <--> (255, 15, 255)
    (42, 125) : (255, 16, 255) <--> (255, 14, 255)
    (50, 127) : (255, 19, 255) <--> (255, 12, 255)

    誤差で色がずれたと思われる点(rgb値の誤差小)がぼちぼち、
    誤差で境界がずれたと思われる点(rgb値の誤差大)がたくさん、
    といった感じでしょうか。

    一応、変な白い点が現れた、というようなことはなく、
    肉眼で見た限りは正しい画像になっています。

    OCaml画像と自作画像とでパラパラ漫画すると、
    違いがわかるのは1点だけで、車(?)と背景の境界が
    1ドットずれるかずれないかの違いのようです。

    今後、他の演算も自作関数に置き換えたときに
    どの程度誤差が増えるか気になりますね…。
    やっぱり、FPUシミュレート関数を実装して、損はなさそうですね。

    あと問題は、全部置き換えたときに、シミュレータの速度がどれだけ下がるか…。
    先ほど実装したFADDは、プライオリティエンコーダ部分だけで20命令くらい使うので、
    かなり遅いです…。 -- buyobuyon (2007-03-10 23:49:55)


3/8(Th)


とりあえず昨日生成した画像は、それ自体を見ても画像に矛盾はないのですが、
正しい画像と比較すると画面中央右下部分の形が少し異なっていたので、
おそらくSLDファイル読み込み部分のバグだろうと思って眺めていたところ、
SLDファイルのlexerにバグ(負の浮動小数点数を正の値として読み込んでしまう)がありました。
修正後、新たに生成した画像が↓(削除済み)。

ちなみに、O'Camlで生成した画像が↓。

まぁ、基本的にはOKですよね。あ、ちなみにどちらもcontest2.sldです。
一応差分をとってみたところ、ほとんどの点はrgb値の差が1以下(r, g, bそれぞれ1以下)で
済みましたが、3点だけ大きく違う点がありました。
(96, 33) : (21, 0, 0) <--> (1, 39, 64)
(7, 42) : (255, 255, 232) <--> (255, 8, 231)
(104, 101) : (0, 0, 0) <--> (0, 39, 52)
どれもノイズというよりは、浮動小数点数演算の誤差によって、
境界が1ドットずれたために生じた違いのようなのですが(∵お隣以降の連続する点の色と一致する)、
こういうのはOKなのですかね?


3/8(Th)


とりあえず肉眼で正常に見えるレイトレ画像を生成してもらうことを目標として、
いろいろ試行錯誤を重ねています。
SLDファイルをバイナリ形式に変換するプログラムが一番怪しいように思えたのですが、
今まで見たところではその部分には特に問題はなさそうですね。

  • シミュレータのFPU部分(FPUの厳密な再現でなく、Cライブラリで代用したもの)のうち、
    ftoiを実際のものと同じ正負対称の四捨五入型のものに変えたところ、
    黒い部分は黒いままですが、一部消えていた模様が正しく表示されるようになりました。
    ちなみに、invsqrtを精度が多少よいものに変えても目立った変化はありませんでした。
    たぶん黒い部分に関しては、判定系の関数のバグが影響しているのだと思うのですが…。
    引き続き調査を続けます。 -- buyobuyon (2007-03-08 22:23:11)
  • とりあえず、一つ気づいたことが。

    現在のfdivは引数が負の値の場合に問題が生じます。
    (x /. y)→(x *. (1.0 /. y))
    というのが現在の方針ですが、
    (1.0 /. y)の求め方を(invsqrt (y *. y))としていたため、
    (1.0 /. y)でなく(1.0 /. |y|)を求めてしまっていたようです。

    (sqrt x)を求める際にも上の方針で(1.0 /. x)を求めていますが、
    こちらの場合は、x < 0の場合を考えなくて良いので問題は生じません。

    問題はどのように求めるように直せばよいかということですが、
    効率の良い求め方がなかなか思い浮かばず…。 -- buyobuyon (2007-03-08 23:06:51)

  • ええと、invの求め方を修正したところ、
    いきなり黒い部分が無くなって上のように(削除済み)なりました。
    これであっているのかな?

    なお、先ほど述べたように、上の画像を生成したときには、
    シミュレータのFPU部分はtsuy氏のFPUの挙動を厳密に再現したものでなく、
    Cライブラリを適用したものを用いたので、
    実際にはもっとノイズが入るかもしれません
    (逆にもっときれいになるかもしれません)。 -- buyobuyon (2007-03-09 00:04:11)
  • 真ん中ちょっと右下部分、本来は裏側が見えるようですね。
    何が悪いのだろう…。 -- buyobuyon (2007-03-09 00:15:32)
  • 昨日はどうもすみませんでしたm(_ _)m

    ぉお、それっぽい!
    こちらもはやく実機動作確認をします~。
    (これから学校に行きます) -- yastak (2007-03-09 09:35:33)


3/7(We)


とりあえず、tsuyさんの作成してくれたライブラリを自作コンパイラでコンパイルできる形に直し、
コンパイルして、シミュレータ上でのcos, sin, atan, floorの軽いテストを行ってみました。
ちゃんと動きましたのでご安心を。
ただ、現段階ではコンパイラが最適化処理をほとんどしてくれない上、
コンパイルしたものに対して特に手を加えていないので、効率はあまり良くないと思います。
あと1週間でどれだけ最適化処理を実装できるのやら…。

途中で、create_array関数を作成するのを忘れていることに気づき、
一応、実装し終えました。

その後、print_intに関して勘違いをしていたことに気づき
(fwrite(&r, sizeof(int), 1, fp);ではなく、fprintf(fp, "%d", r);なのですね…)、
実装し直しているところです。
とりあえず、divとmulを役立てることができそうです。

  • print_intでなく、print_uintにしたい…。
    -(-2^31) = -2^31なのがちょっと嫌です…。
    そもそもmin-rt実行時には負の値の出力はないはずなのに…。 -- buyobuyon (2007-03-07 19:30:38)
  • print_intは、ヘッダ書き込み時3回呼び出されるだけなので、
    とりあえず、てきと~な実装にします。 -- buyobuyon (2007-03-07 20:46:30)
  • print_int、できました。
    が、37行、div使いまくりのひどいコードです。 -- buyobuyon (2007-03-07 21:46:54)
  • ついに、コンパイラのバグ発見です。

    let rec compose f g =
    let rec composed x = g (f x) in
    composed in
    let rec dbl x = x + x in
    let rec inc x = x + 1 in
    let rec dec x = x - 1 in
    let h = compose inc (compose dbl dec) in
    print_int (h 123)

    これを実行すると、123が出力されます。
    これから検証してみますね。 -- buyobuyon (2007-03-07 22:31:36)
  • 末尾呼び出し最適化とレジスタ割り付けのバグのようです。

    リンクレジスタLRを汎用レジスタとして使用していて、
    呼び出す関数のアドレスをLRに入れることがあるのですが、
    それが末尾呼び出しだと、さらにそのあとで戻りアドレスをLRに書き込むので、
    関数呼び出しが正しく行われないようですね。

    とりあえずレジスタも余っていることですし、
    LRは原則として戻りアドレスを入れる以外の用途では使わないことにしますね。 -- buyobuyon (2007-03-07 22:53:07)
  • 関数呼び出し時に関数のアドレスをLRに入れておく場合に
    問題が生じるので、その場合のみLRの使用を禁止することにしました。

    一応、この問題は解決しました。 -- buyobuyon (2007-03-07 23:32:55)
  • クロージャ変換にバグが。
    関数の自由変数を見つける際に、
    自分自身を内部で定義されたものとしてしまっていたために、
    レジスタ割り付けの際にinternal errorが起きていました。

    それにしても、min-rtの実行には全く関係のないバグばかり見つかりますね…。 -- buyobuyon (2007-03-08 01:18:33)
  • あれからいろいろ試してはいるものの、新しいバグは発見されず…。
    ちなみに、fib 40は102334155だそうです。 -- buyobuyon (2007-03-08 03:04:50)
  • SLDファイルをバイナリ化するプログラムを作成中。
    完成したつもりだったのですが、ちょっとした勘違いがあって、
    一からやり直しています。 -- buyobuyon (2007-03-08 03:48:24)

  • とりあえずこういう状況(画像削除済み)…、やばいっすね。 -- buyobuyon (2007-03-08 06:12:51)


3/6(Tu)


どうも、ただいま戻りました。
おかげさまで無事用事を済ましてくることができました。
ありがとうございます。

2日間何も作業をできなかったもので
(その代わり、昼夜逆転していた生活のリズムが正常に戻りました!)、
明日からまた頑張っていきますので、よろしくお願いします。

  • fibが引数30あたりで求まらなくなる件、原因がわかりました。
    シミュレータのバグでもコンパイラのバグでも無かったようです。
    バイナリコード(harryさんのアセンブラで作成したものではなく、私の手動変換で作成したもの)が
    間違っていたようです。
    スタックポインタSPの初期値が2^20なのに、
    実行時にSPの値が2桁になったいたのを見た時点で気づくべきでした…。

    一応、fib 32も正しく求まったので、
    他のプログラムも試してみて、うまくいったらmin-rtやってみますね。
    tsuyさんのおかげで、floorもできたことですし。 -- buyobuyon (2007-03-07 01:30:39)


3/3(Sa)


おひな祭り、おめでとうございます。



コンパイラの方は、今はひたすら組み込み関数を実装しています。

  • ええと、組み込むつもりの関数は組み込み終えました(入出力ライブラリはまだ)。

    xor/float_of_int/int_of_float/flessは
    そのまま対応する命令を呼び出すだけで、その他は

    fiszero → rd := (rs AND 0x7f800000) = 0
    fispos → rd := rs >. 0x00000000(+0.0)
    fisneg → rd := rs <. 0x80000000(-0.0)
    fabs → rd := rs AND 0x7fffffff
    fhalf → rd := rs *. 0x3f000000(+0.5)
    fneg → rd := r0 -. rs
    fsqr → rd := rs *. rs

    という感じで実装しました。
    fisnegに関しては、fless r1 +0.0ではなく
    fless r1 -0.0として実装したのですが、どうですかね?
    問題があれば前者に変えますが…
    (むしろその方が0レジスタを利用できる点で都合が良い)。 -- buyobuyon (2007-03-04 04:38:12)
  • fiszeroなどのテストをしている最中にバグ発見。
    バグとは言っても悪さはしないのですが、
    仮想マシンコードでの不要定義除去の際に、
    連鎖した不要定義があると一番後ろしか除去してくれません。
    理由は明らかなので、一休みしてからなおします。 -- buyobuyon (2007-03-04 06:39:44)
  • 上記のバグをとりました。

    ついでに、無駄なmov(addi r2, r2, 0;みたいなもの)も
    削除するようにしました。
    おかげでfibが一行だけ短くなりましたが、再帰部ではなくて
    再帰しない方の分岐の中のmovなので、あまり意味はないですね…。 -- buyobuyon (2007-03-04 08:53:03)
  • 外部変数やら入出力関数やらを使ったfibをシミュレータでテストをしてみました。
    やっぱりfibの30あたりになると原因不明のエラーが出ますね。
    スタックもヒープもあふれていないのですが…。
    マシンコードにも特に問題はなさそうなのですが…。

    まあ、見ておきます。
    今日はもう45:30なのでもう寝ます…。 -- buyobuyon (2007-03-04 21:38:52)
名前:
コメント:


3/1(Th)


3月に入ってしまった…。

とりあえず、適当ながらもコンパイラ係用選択課題を出して、
今のところダメ出しも来ていないので、再びコンパイラ制作に入ります。

まず、.word文を使用して、外部変数定義(globals.ml)の解析・コード生成機作りますね。

  • とりあえず、globals.mlで定義された(外部)変数の型が、
    コンパイラが推論した外部変数の型と一致するかどうか
    チェックするのは省略しますね。 -- buyobuyon (2007-03-01 15:41:09)
  • とりあえず、外部変数関連の構文解析&コード生成器が完成しました。
    harryさん、.wordの実装、よろしくお願いします。 -- buyobuyon (2007-03-02 04:58:07)
  • お疲れさまです〜.wordを追加しました☆ -- harry (2007-03-02 09:00:14)
  • ありがとうございます。

    一応、リンカ(ただファイルを結合するだけ)と
    プリプロセッサ("(*MINCAML*)"で始まる行と"open"で始まる行を削除して、
    プログラムの"in 0"を"in ()"に変えるだけ)が完成したので、
    あとは、read_int関数などの挙動をアセンブリ言語で記述したものが完成すれば、
    min-rtは動くはず…、正しく動くかどうかはわかりませんが…。 -- buyobuyon (2007-03-02 11:54:44)



続きは、buyobuyon中およびbuyobuyon古に。