Next: Files
Up: Evaluating Symbolic Traversal Algorithms
Previous: Fixed variable order results
To make result tables as small as possible we will use the following
codes to identify the traversal methods:
- N for NuSMV using threshold and affinity.
- B for TranSyT BFS.
- C for TranSyT BFS with chaining.
- T for TranSyT Token traverse.
- W for TranSyT Weighed Token traverse.
- D for TranSyT Dynamic Event Clustered traverse.
- I for VIS IWLS.
- H for VIS Hybrid method.
- M for VIS MLP method.
- IH for VIS IWLS with high density.
- HH for VIS Hybrid method with high density.
- MH for VIS MLP method with high density.
|
Name |
Reorderings |
Reordering Time |
Peak BDD |
Time |
|
|
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
|
dartes_1.fsa |
?? |
1 |
1 |
1 |
1 |
- |
- |
- |
- |
- |
- |
- |
?? |
2.8 |
2.8 |
2.8 |
2.8 |
- |
- |
- |
- |
- |
- |
- |
?? |
166751 |
166751 |
166751 |
166751 |
- |
- |
- |
- |
- |
- |
- |
?? |
7.8 |
10.4 |
10.6 |
17.4 |
- |
- |
- |
- |
- |
- |
- |
|
dp_12.fsa |
2 |
1 |
1 |
1 |
1 |
8 |
10 |
9 |
9 |
11 |
11 |
9 |
2.9 |
1.2 |
1.2 |
1.2 |
1.3 |
56.1 |
91.8 |
25.5 |
110.3 |
264.5 |
154.9 |
123.8 |
19563 |
8923 |
8601 |
8830 |
9416 |
237881 |
252725 |
128395 |
434421 |
416413 |
299125 |
346748 |
5.6 |
1.3 |
1.5 |
1.5 |
2.2 |
75.5 |
105.2 |
44.5 |
139.9 |
296.5 |
200.3 |
189.1 |
|
q_1.fsa |
?? |
1 |
1 |
1 |
1 |
12 |
11 |
9 |
11 |
10 |
9 |
11 |
?? |
0.5 |
0.5 |
0.5 |
0.5 |
178.7 |
107.5 |
73.8 |
119.0 |
76.3 |
59.4 |
105.6 |
?? |
94073 |
79241 |
80906 |
82774 |
204587 |
199427 |
217467 |
190112 |
157053 |
187369 |
162915 |
?? |
9.9 |
4.7 |
6.3 |
28.4 |
232.6 |
191.1 |
195.2 |
169.7 |
183.2 |
209.0 |
190.5 |
|
sentest_100.fsa |
1 |
1 |
1 |
1 |
1 |
7 |
7 |
5 |
6 |
7 |
6 |
7 |
1.4 |
1.4 |
1.4 |
1.4 |
1.4 |
37.7 |
28.1 |
9.5 |
17.2 |
26.2 |
16.9 |
24.7 |
106549 |
106549 |
106549 |
106549 |
106549 |
73995 |
58540 |
32668 |
42176 |
62922 |
33402 |
57651 |
2.7 |
1.7 |
3.0 |
3.0 |
2.5 |
44.9 |
32.5 |
23.9 |
20.4 |
31.8 |
29.7 |
27.9 |
|
speed_1.fsa |
2 |
1 |
0 |
0 |
0 |
4 |
6 |
6 |
5 |
6 |
6 |
5 |
0.6 |
0.2 |
0.0 |
0.0 |
0.0 |
0.7 |
1.0 |
1.3 |
0.7 |
1.2 |
1.3 |
0.7 |
9226 |
5033 |
3893 |
4822 |
4898 |
16772 |
23986 |
38227 |
19141 |
31895 |
35097 |
20246 |
1.1 |
0.3 |
0.1 |
0.2 |
0.3 |
1.0 |
1.5 |
2.8 |
1.0 |
1.9 |
2.5 |
1.0 |
|
elevator_ |
|
n |
Reorderings |
Reordering Time |
Peak BDD |
Time |
|
|
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
|
1 |
1 |
1 |
1 |
1 |
1 |
6 |
4 |
4 |
4 |
4 |
4 |
4 |
0.1 |
0.0 |
0.1 |
0.0 |
0.0 |
0.7 |
0.8 |
0.7 |
0.8 |
0.8 |
0.7 |
0.8 |
10252 |
10252 |
10252 |
10252 |
10252 |
21406 |
70574 |
70574 |
70574 |
70574 |
70574 |
70574 |
0.1 |
0.1 |
0.4 |
0.4 |
0.1 |
1.1 |
0.8 |
0.8 |
0.8 |
0.8 |
0.8 |
0.9 |
|
2 |
1 |
1 |
1 |
1 |
1 |
7 |
- |
- |
- |
- |
- |
- |
0.6 |
0.6 |
0.6 |
0.6 |
0.6 |
12.2 |
- |
- |
- |
- |
- |
- |
57507 |
57507 |
57507 |
57507 |
57507 |
72586 |
- |
- |
- |
- |
- |
- |
1.0 |
0.9 |
5.2 |
5.2 |
1.4 |
17.5 |
- |
- |
- |
- |
- |
- |
|
3 |
1 |
1 |
1 |
1 |
1 |
10 |
- |
- |
- |
- |
- |
- |
7.4 |
7.5 |
7.5 |
7.5 |
7.6 |
145.2 |
- |
- |
- |
- |
- |
- |
287475 |
287475 |
287475 |
287475 |
287475 |
259382 |
- |
- |
- |
- |
- |
- |
11.4 |
11.0 |
57.7 |
56.9 |
20.2 |
223.8 |
- |
- |
- |
- |
- |
- |
|
4 |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
hartstone_ |
|
n |
Reorderings |
Reordering Time |
Peak BDD |
Time |
|
|
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
|
25 |
2 |
1 |
1 |
1 |
1 |
7 |
8 |
7 |
7 |
8 |
7 |
8 |
18.0 |
7.1 |
7.1 |
7.1 |
7.4 |
18.1 |
34.7 |
9.9 |
17.3 |
30.0 |
9.8 |
47.5 |
38440 |
25963 |
25554 |
25554 |
25602 |
121878 |
102682 |
59473 |
113587 |
90281 |
62428 |
116733 |
21.4 |
7.3 |
7.5 |
7.5 |
8.0 |
31.9 |
46.1 |
23.5 |
26.1 |
40.0 |
23.4 |
57.8 |
|
50 |
2 |
1 |
1 |
1 |
1 |
11 |
12 |
- |
12 |
- |
- |
- |
182.7 |
60.4 |
60.3 |
60.4 |
60.6 |
1028.7 |
814.5 |
- |
1227.3 |
- |
- |
- |
207455 |
96913 |
96079 |
96079 |
96656 |
944252 |
635437 |
- |
1243712 |
- |
- |
- |
356.6 |
62.2 |
63.0 |
63.2 |
68.1 |
2319.3 |
1449.8 |
- |
2168.0 |
- |
- |
- |
|
75 |
2 |
1 |
1 |
1 |
1 |
- |
- |
- |
- |
- |
- |
- |
754.0 |
215.5 |
216.1 |
214.0 |
215.2 |
- |
- |
- |
- |
- |
- |
- |
597040 |
212863 |
211604 |
211604 |
211802 |
- |
- |
- |
- |
- |
- |
- |
2206.1 |
221.5 |
225.1 |
224.2 |
252.4 |
- |
- |
- |
- |
- |
- |
- |
|
100 |
- |
1 |
1 |
1 |
1 |
- |
- |
- |
- |
- |
- |
- |
- |
553.3 |
553.2 |
555.0 |
554.8 |
- |
- |
- |
- |
- |
- |
- |
- |
373813 |
372129 |
372129 |
373306 |
- |
- |
- |
- |
- |
- |
- |
- |
569.6 |
577.0 |
582.5 |
695.6 |
- |
- |
- |
- |
- |
- |
- |
|
key_ |
|
n |
Reorderings |
Reordering Time |
Peak BDD |
Time |
|
|
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
|
2 |
1 |
1 |
1 |
1 |
1 |
6 |
5 |
5 |
4 |
6 |
5 |
5 |
0.1 |
0.1 |
0.1 |
0.1 |
0.1 |
1.7 |
1.2 |
1.2 |
0.9 |
2.1 |
1.2 |
1.8 |
16859 |
16956 |
17316 |
17263 |
17115 |
29336 |
27639 |
27639 |
27639 |
27639 |
27639 |
27639 |
0.4 |
0.3 |
0.6 |
0.5 |
0.4 |
3.1 |
1.9 |
2.9 |
1.6 |
2.8 |
3.0 |
2.4 |
|
3 |
1 |
1 |
1 |
1 |
1 |
9 |
8 |
6 |
6 |
8 |
6 |
7 |
0.2 |
0.2 |
0.2 |
0.2 |
0.2 |
16.3 |
14.6 |
8.4 |
8.5 |
15.6 |
8.5 |
11.8 |
36538 |
35668 |
34114 |
33848 |
34380 |
69317 |
217264 |
217264 |
217264 |
217264 |
217264 |
217264 |
2.0 |
1.5 |
1.8 |
1.5 |
2.1 |
22.4 |
19.4 |
19.1 |
11.7 |
20.1 |
17.8 |
15.9 |
|
4 |
1 |
1 |
1 |
1 |
1 |
13 |
10 |
8 |
9 |
9 |
8 |
10 |
0.5 |
0.5 |
0.5 |
0.5 |
0.5 |
111.9 |
103.9 |
51.9 |
40.3 |
47.0 |
46.8 |
54.9 |
74989 |
67068 |
57497 |
57205 |
58398 |
176983 |
610331 |
610331 |
610331 |
610331 |
610331 |
610331 |
12.7 |
7.2 |
4.8 |
3.9 |
7.2 |
159.3 |
151.6 |
125.7 |
68.6 |
98.1 |
130.7 |
91.0 |
|
mmgt_ |
|
n |
Reorderings |
Reordering Time |
Peak BDD |
Time |
|
|
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
B |
C |
T |
W |
D |
N |
I |
H |
M |
IHD |
HHD |
MHD |
|
2 |
1 |
1 |
1 |
1 |
1 |
7 |
- |
- |
- |
- |
- |
- |
0.1 |
0.1 |
0.1 |
0.1 |
0.1 |
3.3 |
- |
- |
- |
- |
- |
- |
15687 |
15649 |
14921 |
14921 |
15421 |
34801 |
- |
- |
- |
- |
- |
- |
0.3 |
0.2 |
0.8 |
0.8 |
0.4 |
4.4 |
- |
- |
- |
- |
- |
- |
|
3 |
1 |
1 |
1 |
1 |
1 |
9 |
- |
- |
- |
- |
- |
- |
0.2 |
0.2 |
0.3 |
0.3 |
0.3 |
15.3 |
- |
- |
- |
- |
- |
- |
36272 |
35633 |
31162 |
31162 |
32621 |
75660 |
- |
- |
- |
- |
- |
- |
1.9 |
1.3 |
2.5 |
2.3 |
1.9 |
20.6 |
- |
- |
- |
- |
- |
- |
|
4 |
1 |
1 |
1 |
1 |
1 |
9 |
- |
- |
- |
- |
- |
- |
0.6 |
0.6 |
0.6 |
0.6 |
0.6 |
103.2 |
- |
- |
- |
- |
- |
- |
73542 |
74104 |
56057 |
56057 |
59047 |
188233 |
- |
- |
- |
- |
- |
- |
11.3 |
6.7 |
6.2 |
4.9 |
6.5 |
127.3 |
- |
- |
- |
- |
- |
- |
Next: Files
Up: Evaluating Symbolic Traversal Algorithms
Previous: Fixed variable order results
Enric Pastor
2004-05-28