Sun Sep 10 08:19:53 JST 2006

あれ? cmp_memory1 では、アドレスを識別しているので、(comment とは
反対に...)  アドレスが異なるメモリパターンはshare されてないね。
こまったものだ。

copy_memory の呼び出す、memory_lookup を書き換えないとだめだな。

state.c/h は、必要ないみたいだな。

state 間のpointer を用意した方があとで実行させてみる時には
便利だろう。(実行って言うのかな? これは、なんだろう? trace 
generation? )

Sun Sep 10 05:09:02 JST 2006

1.6MHz 17inch PowerBook Memory 1GB

+leo+kono time ./tableau 8 > ers; tail ers
./tableau 8 > ers  237.58s user 12.92s system 79% cpu 5:16.63 total
found 3915727
no more banch 3915727
All done count 3915727
        memory_header 11747304
        memcmp_count 830530587
        memory_body 1792
        restore_count 82230288
        restore_size 1096403840
        range_count 24
        range_size 320
+leo+kono time ./tableau 7 > ers; tail ers
./tableau 7 > ers  35.42s user 1.99s system 90% cpu 41.401 total
found 845529
no more banch 845529
All done count 845529
        memory_header 2536695
        memcmp_count 114942650
        memory_body 1568
        restore_count 15219540
        restore_size 202927200
        range_count 21
        range_size 280
+leo+kono time ./tableau 6 > ers; tail ers
./tableau 6 > ers  5.04s user 0.32s system 97% cpu 5.514 total
found 159299
no more banch 159299
All done count 159299
        memory_header 477990
        memcmp_count 15198190
        memory_body 1344
        restore_count 2389500
        restore_size 31860000
        range_count 18
        range_size 240
+leo+kono time ./tableau 5 > ers; tail ers
./tableau 5 > ers  1.04s user 0.08s system 96% cpu 1.154 total
no more banch 38984
no more banch 38984
All done count 38984
        memory_header 117030
        memcmp_count 2432088
        memory_body 1120
        restore_count 467820
        restore_size 6237600
        range_count 15
        range_size 200

Lite ( tableau on SICStus Prolog ) では、

208.57 sec.
1365 states
60 subterms
21075 state transions
renaming,singleton,length limit 5

なので、結構、いい値かな。つうか、知っていはいたが、Lite 遅すぎ。
状態数が多いのは何故だろう? たぶん、code segment のtask のpointer
が細かすぎるのだろう...

Sun Sep 10 02:45:16 JST 2006

Iterator を使えば、tableau 自体もそんなに難しくないか。

Sat Sep  9 23:25:42 JST 2006

あ、そうか。
    memory の部分木が同じなら、それもshareした方が良い
でも、そのためには、pattern だけでなく、adr/left/right も
含んだ形で share を行わないとダメ。

まぁ、とりあえず、全部copyってことで...

copy_memory を、もっとintelligentにすればいいんだろうな...

Sat Sep  9 22:15:10 JST 2006

range を登録して、そのrangeに対して、state を決める。
それを look up するわけだけど、
    state, memory range for real address
    state, memory range in database (as copy)
と二つあることになる。

実際に、code segement を実行して、すべてのmemory rangeを
lookup するのは、実はばかげてる。code segment で memory に
書き込んだときに、どこを書き込んだのか dirty list みたいな
形で持っておくべきでしょうね。

単にデータを圧縮するだけでなく、そのあたりを工夫しないと
速度的に厳しい。

code segment の実行も、同じパターンの実行だったら、二度は
行わないみたいな工夫が必要だと思う。それは、一種の理論に
なるんだろうけど...

まぁ、とりあえずは、それはやらないけどさ。

memory range は、実際には増減することになる。malloc / free
した時にどうするかは、これからの課題だろう。

Sat Sep  9 19:16:10 JST 2006

memory_add は、いいんだけど、state DB のlookup で使う状態は、
どうやって作るんだろう?

間が開いているので、何やろうとしていたんだか、良くわからん。

memory_add は、状態に対して行うべきものなんじゃないの?

たぶん、memory_add に相当するものは、
    state に対する address range の登録
    memory pattern の検索と登録
の二種類があるんだと思われる。そのあたりを曖昧に作ってしまった
らしい。


Sun Aug  6 15:23:05 JST 2006

tree をbaranceさせないとだめなのは、そうなんだけど、
tree search routine も code segement で記述した方が
やっぱり良い。

main loop を書くのが面倒だが、あと、も少しなはずだが、
今日中に終る自信はないね。

Binary Tree そのものが状態データベースになるわけなので、
そこに安直なものを使うのはまずい。

Sat Aug  5 22:04:00 JST 2006

はぁ、だいぶ出来た。

    MemoryPtr
    add_memory(void *ptr,int length, MemoryPtr *parent)

で、登録していくわけね。

test routine を書いていかないと。

Sat Aug  5 19:35:56 JST 2006

typedef struct memory {
        void *adr;
        int  length;
        void *body;
        int  crc;
        struct memory *left,*right;
} Memory, *MemoryPtr;

body と address をわけて、中身が同じなら、同じものを
さすようにする。ということは、crc でhashしないとだめ。
crc じゃなくて hash か。

content hash で 2分木をつくって、さらに、adr/length pair
で2分木を作ればいいんじゃないか? そうすれば hash はいりません。
バランスはさせないとまずいけど。

Sat Aug  5 17:45:26 JST 2006

state と state_db にわけるのか。

typedef struct memory {
        void *ptr;
        int  length;
        struct memory *next;
} Memory, *MemoryPtr;

なんだが、binary tree にするべきかどうか。まぁ、するべきな
んだけど、そうすると、形がuniqueでなくなるのがまずい。正規
形にならないの? まぁ、正規形でなくても、maximum share され
ていれば、文句はないんだけど。 

大半のルーチンで、変更されるメモリはごく一部なはず。それを
効率的に捕まえるためには、compiler or program 変換で捕まえる
必要があるはず。(OSのサポートとか?)

同じ形のメリットは同一性の判定の問題だけ。連続した領域とか
の同一性はどうする? MD5? MD5 はだめだな。

address が違うだけで、中身が同じ場合は共有するべきだろ?
だとすれば、中身はハッシュするべきだろう。

queue とかの場合の対称性は、abstrct()で正規形に変換してから
db に登録すれば良いわけなんだが、そこまでは間に合わないらしい。
正規形の大半は、制御に影響しない(あるいはランダムに影響する)
データをzero clearすることになるはず。

まぁ、何か変だね。もう少し考えると、すっきりしたもの(ordered BDD
を含む)なにかが見つかるだろう。

   |------|    |------|

という領域ではなくて、

   |------xxxxxx------|

という don't care を含むメモリ領域の正規化という問題だってこと?

BDD は、
   |tfxxxxxfxtxxfffttt|
という文字列の正規化とみなせるわけだから... なんか、どっかで
見た問題だな。

Sat Jul 29 18:44:33 JST 2006

No compile errors.

まぁ、走らせるのは簡単なんだが、状態の登録をどうする?

malloc() した状態の登録をどうする?

*同じ* pointer というのを識別する必要がある。 id で識別する?

まぁ、最初は malloc しないでも良い。
    add_state(void *p,int length);
ぐらい。

同じ id (つまり、address )は、同じアドレスである必要があるが...
同じ大きさとは限らない。一番大きなものに合わせる?

malloc を許すと、そもそも、止まるアルゴリズムにならないが...

malloc() しても、中身の多様性を無視できる場合。
    add_state(void *p,int length, (*abstrct)(void *,int ));

メモリreferece は、id で抽象化する必要がある。ということは、
メモリ演算は、抽象化される必要がある。(移動をともなう場合)

まぁ、とりあえず固定でやるしかないか。

つまり、最初のtablue 展開ルーチンに来るまでに、
add_state は有限固定回起きるという話なわけね。
しかも順序が固定というわけか。

/* epoch */