Mercurial > hg > CbC > old > DPP

comparison Changes @ 0:d4bc23cb728b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS (CVS_DB/member/atsuki/cbc/DPP)
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Wed, 16 Dec 2015 15:16:11 +0900
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:d4bc23cb728b
1 Sun Sep 10 08:19:53 JST 2006
2
3 あれ? cmp_memory1 では、アドレスを識別しているので、(comment とは
4 反対に...) アドレスが異なるメモリパターンはshare されてないね。
5 こまったものだ。
6
7 copy_memory の呼び出す、memory_lookup を書き換えないとだめだな。
8
9 state.c/h は、必要ないみたいだな。
10
11 state 間のpointer を用意した方があとで実行させてみる時には
12 便利だろう。(実行って言うのかな? これは、なんだろう? trace
13 generation? )
14
15 Sun Sep 10 05:09:02 JST 2006
16
17 1.6MHz 17inch PowerBook Memory 1GB
18
19 +leo+kono time ./tableau 8 > ers; tail ers
20 ./tableau 8 > ers 237.58s user 12.92s system 79% cpu 5:16.63 total
21 found 3915727
22 no more banch 3915727
23 All done count 3915727
24 memory_header 11747304
25 memcmp_count 830530587
26 memory_body 1792
27 restore_count 82230288
28 restore_size 1096403840
29 range_count 24
30 range_size 320
31 +leo+kono time ./tableau 7 > ers; tail ers
32 ./tableau 7 > ers 35.42s user 1.99s system 90% cpu 41.401 total
33 found 845529
34 no more banch 845529
35 All done count 845529
36 memory_header 2536695
37 memcmp_count 114942650
38 memory_body 1568
39 restore_count 15219540
40 restore_size 202927200
41 range_count 21
42 range_size 280
43 +leo+kono time ./tableau 6 > ers; tail ers
44 ./tableau 6 > ers 5.04s user 0.32s system 97% cpu 5.514 total
45 found 159299
46 no more banch 159299
47 All done count 159299
48 memory_header 477990
49 memcmp_count 15198190
50 memory_body 1344
51 restore_count 2389500
52 restore_size 31860000
53 range_count 18
54 range_size 240
55 +leo+kono time ./tableau 5 > ers; tail ers
56 ./tableau 5 > ers 1.04s user 0.08s system 96% cpu 1.154 total
57 no more banch 38984
58 no more banch 38984
59 All done count 38984
60 memory_header 117030
61 memcmp_count 2432088
62 memory_body 1120
63 restore_count 467820
64 restore_size 6237600
65 range_count 15
66 range_size 200
67
68 Lite ( tableau on SICStus Prolog ) では、
69
70 208.57 sec.
71 1365 states
72 60 subterms
73 21075 state transions
74 renaming,singleton,length limit 5
75
76 なので、結構、いい値かな。つうか、知っていはいたが、Lite 遅すぎ。
77 状態数が多いのは何故だろう? たぶん、code segment のtask のpointer
78 が細かすぎるのだろう...
79
80 Sun Sep 10 02:45:16 JST 2006
81
82 Iterator を使えば、tableau 自体もそんなに難しくないか。
83
84 Sat Sep 9 23:25:42 JST 2006
85
86 あ、そうか。
87 memory の部分木が同じなら、それもshareした方が良い
88 でも、そのためには、pattern だけでなく、adr/left/right も
89 含んだ形で share を行わないとダメ。
90
91 まぁ、とりあえず、全部copyってことで...
92
93 copy_memory を、もっとintelligentにすればいいんだろうな...
94
95 Sat Sep 9 22:15:10 JST 2006
96
97 range を登録して、そのrangeに対して、state を決める。
98 それを look up するわけだけど、
99 state, memory range for real address
100 state, memory range in database (as copy)
101 と二つあることになる。
102
103 実際に、code segement を実行して、すべてのmemory rangeを
104 lookup するのは、実はばかげてる。code segment で memory に
105 書き込んだときに、どこを書き込んだのか dirty list みたいな
106 形で持っておくべきでしょうね。
107
108 単にデータを圧縮するだけでなく、そのあたりを工夫しないと
109 速度的に厳しい。
110
111 code segment の実行も、同じパターンの実行だったら、二度は
112 行わないみたいな工夫が必要だと思う。それは、一種の理論に
113 なるんだろうけど...
114
115 まぁ、とりあえずは、それはやらないけどさ。
116
117 memory range は、実際には増減することになる。malloc / free
118 した時にどうするかは、これからの課題だろう。
119
120 Sat Sep 9 19:16:10 JST 2006
121
122 memory_add は、いいんだけど、state DB のlookup で使う状態は、
123 どうやって作るんだろう?
124
125 間が開いているので、何やろうとしていたんだか、良くわからん。
126
127 memory_add は、状態に対して行うべきものなんじゃないの?
128
129 たぶん、memory_add に相当するものは、
130 state に対する address range の登録
131 memory pattern の検索と登録
132 の二種類があるんだと思われる。そのあたりを曖昧に作ってしまった
133 らしい。
134
135
136 Sun Aug 6 15:23:05 JST 2006
137
138 tree をbaranceさせないとだめなのは、そうなんだけど、
139 tree search routine も code segement で記述した方が
140 やっぱり良い。
141
142 main loop を書くのが面倒だが、あと、も少しなはずだが、
143 今日中に終る自信はないね。
144
145 Binary Tree そのものが状態データベースになるわけなので、
146 そこに安直なものを使うのはまずい。
147
148 Sat Aug 5 22:04:00 JST 2006
149
150 はぁ、だいぶ出来た。
151
152 MemoryPtr
153 add_memory(void *ptr,int length, MemoryPtr *parent)
154
155 で、登録していくわけね。
156
157 test routine を書いていかないと。
158
159 Sat Aug 5 19:35:56 JST 2006
160
161 typedef struct memory {
162 void *adr;
163 int length;
164 void *body;
165 int crc;
166 struct memory *left,*right;
167 } Memory, *MemoryPtr;
168
169 body と address をわけて、中身が同じなら、同じものを
170 さすようにする。ということは、crc でhashしないとだめ。
171 crc じゃなくて hash か。
172
173 content hash で 2分木をつくって、さらに、adr/length pair
174 で2分木を作ればいいんじゃないか? そうすれば hash はいりません。
175 バランスはさせないとまずいけど。
176
177 Sat Aug 5 17:45:26 JST 2006
178
179 state と state_db にわけるのか。
180
181 typedef struct memory {
182 void *ptr;
183 int length;
184 struct memory *next;
185 } Memory, *MemoryPtr;
186
187 なんだが、binary tree にするべきかどうか。まぁ、するべきな
188 んだけど、そうすると、形がuniqueでなくなるのがまずい。正規
189 形にならないの? まぁ、正規形でなくても、maximum share され
190 ていれば、文句はないんだけど。
191
192 大半のルーチンで、変更されるメモリはごく一部なはず。それを
193 効率的に捕まえるためには、compiler or program 変換で捕まえる
194 必要があるはず。(OSのサポートとか?)
195
196 同じ形のメリットは同一性の判定の問題だけ。連続した領域とか
197 の同一性はどうする? MD5? MD5 はだめだな。
198
199 address が違うだけで、中身が同じ場合は共有するべきだろ?
200 だとすれば、中身はハッシュするべきだろう。
201
202 queue とかの場合の対称性は、abstrct()で正規形に変換してから
203 db に登録すれば良いわけなんだが、そこまでは間に合わないらしい。
204 正規形の大半は、制御に影響しない(あるいはランダムに影響する)
205 データをzero clearすることになるはず。
206
207 まぁ、何か変だね。もう少し考えると、すっきりしたもの(ordered BDD
208 を含む)なにかが見つかるだろう。
209
210 |------| |------|
211
212 という領域ではなくて、
213
214 |------xxxxxx------|
215
216 という don't care を含むメモリ領域の正規化という問題だってこと?
217
218 BDD は、
219 |tfxxxxxfxtxxfffttt|
220 という文字列の正規化とみなせるわけだから... なんか、どっかで
221 見た問題だな。
222
223 Sat Jul 29 18:44:33 JST 2006
224
225 No compile errors.
226
227 まぁ、走らせるのは簡単なんだが、状態の登録をどうする?
228
229 malloc() した状態の登録をどうする?
230
231 *同じ* pointer というのを識別する必要がある。 id で識別する?
232
233 まぁ、最初は malloc しないでも良い。
234 add_state(void *p,int length);
235 ぐらい。
236
237 同じ id (つまり、address )は、同じアドレスである必要があるが...
238 同じ大きさとは限らない。一番大きなものに合わせる?
239
240 malloc を許すと、そもそも、止まるアルゴリズムにならないが...
241
242 malloc() しても、中身の多様性を無視できる場合。
243 add_state(void *p,int length, (*abstrct)(void *,int ));
244
245 メモリreferece は、id で抽象化する必要がある。ということは、
246 メモリ演算は、抽象化される必要がある。(移動をともなう場合)
247
248 まぁ、とりあえず固定でやるしかないか。
249
250 つまり、最初のtablue 展開ルーチンに来るまでに、
251 add_state は有限固定回起きるという話なわけね。
252 しかも順序が固定というわけか。
253
254 /* epoch */