Next: Automatic variable reordering results
Up: Evaluating Symbolic Traversal Algorithms
Previous: General benchmark data
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 |
Iterations |
Events fired |
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 |
129 |
92 |
1 |
1 |
1371 |
- |
- |
- |
- |
- |
- |
- |
33410 |
23901 |
4714 |
4189 |
1371 |
- |
- |
- |
- |
- |
- |
- |
672554 |
166751 |
166751 |
166751 |
166751 |
- |
- |
- |
- |
- |
- |
- |
605.0 |
4.9 |
7.6 |
7.7 |
14.2 |
- |
- |
- |
- |
- |
- |
- |
|
dp_12.fsa |
33 |
3 |
1 |
1 |
473 |
33 |
33 |
33 |
33 |
98 |
61 |
99 |
1632 |
192 |
841 |
578 |
474 |
170 |
442 |
442 |
340 |
1287 |
806 |
1000 |
49902 |
17589 |
16312 |
17959 |
17184 |
1805661 |
9668765 |
2114911 |
4566074 |
12026346 |
1833414 |
4489826 |
12.8 |
0.6 |
1.2 |
1.2 |
3.8 |
88.0 |
323.8 |
71.6 |
126.5 |
456.5 |
101.9 |
300.2 |
|
q_1.fsa |
78 |
34 |
1 |
1 |
2410 |
78 |
78 |
78 |
78 |
142 |
142 |
155 |
15326 |
6790 |
4679 |
4160 |
2411 |
2607 |
5372 |
5372 |
4503 |
9724 |
9724 |
8892 |
100799 |
94073 |
79241 |
80906 |
82774 |
1728308 |
988454 |
1126940 |
1783352 |
894044 |
567096 |
1694133 |
15.5 |
9.2 |
4.1 |
5.9 |
26.9 |
377.4 |
?? |
92.2 |
250.5 |
438.5 |
73.9 |
484.8 |
|
sentest_100.fsa |
115 |
6 |
2 |
2 |
359 |
115 |
115 |
115 |
115 |
117 |
117 |
117 |
15080 |
910 |
1189 |
1066 |
360 |
1856 |
4176 |
4176 |
2900 |
4248 |
4248 |
2950 |
106549 |
106549 |
106549 |
106549 |
106549 |
211352 |
184315 |
40644 |
186603 |
166470 |
40702 |
157429 |
1.3 |
0.3 |
1.6 |
1.6 |
1.1 |
7.2 |
5.7 |
10.3 |
4.7 |
5.8 |
10.4 |
5.7 |
|
speed_1.fsa |
24 |
7 |
1 |
1 |
265 |
24 |
24 |
24 |
24 |
26 |
26 |
26 |
975 |
312 |
674 |
614 |
266 |
75 |
225 |
225 |
225 |
243 |
243 |
243 |
11320 |
5877 |
3893 |
4822 |
4898 |
331492 |
729603 |
158692 |
504998 |
674979 |
155574 |
459810 |
0.8 |
0.1 |
0.1 |
0.2 |
0.3 |
1.0 |
2.7 |
2.2 |
2.4 |
2.3 |
2.1 |
2.1 |
|
elevator_ |
|
n |
Iterations |
Events fired |
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 |
16 |
6 |
1 |
1 |
133 |
16 |
16 |
16 |
16 |
18 |
18 |
18 |
1683 |
693 |
3590 |
3374 |
134 |
255 |
544 |
544 |
476 |
608 |
608 |
532 |
10252 |
10252 |
10252 |
10252 |
10252 |
310160 |
195792 |
195792 |
195792 |
195792 |
195792 |
195792 |
0.0 |
0.0 |
0.4 |
0.4 |
0.1 |
1.0 |
0.5 |
0.4 |
0.5 |
0.5 |
0.4 |
0.5 |
|
2 |
24 |
8 |
1 |
1 |
356 |
- |
- |
- |
- |
- |
- |
- |
7475 |
2691 |
24648 |
23365 |
357 |
- |
- |
- |
- |
- |
- |
- |
57507 |
57507 |
57507 |
57507 |
57507 |
- |
- |
- |
- |
- |
- |
- |
0.4 |
0.3 |
4.6 |
4.5 |
0.8 |
- |
- |
- |
- |
- |
- |
- |
|
3 |
32 |
10 |
1 |
1 |
1199 |
- |
- |
- |
- |
- |
- |
- |
25839 |
8613 |
141182 |
136080 |
1200 |
- |
- |
- |
- |
- |
- |
- |
287475 |
287475 |
287475 |
287475 |
287475 |
- |
- |
- |
- |
- |
- |
- |
3.9 |
3.5 |
50.1 |
48.5 |
12.3 |
- |
- |
- |
- |
- |
- |
- |
|
4 |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
hartstone_ |
|
n |
Iterations |
Events fired |
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 |
76 |
3 |
1 |
1 |
582 |
- |
- |
- |
- |
- |
- |
- |
5929 |
308 |
647 |
518 |
583 |
- |
- |
- |
- |
- |
- |
- |
38446 |
25955 |
25546 |
25546 |
25603 |
- |
- |
- |
- |
- |
- |
- |
3.2 |
0.2 |
0.3 |
0.4 |
0.6 |
- |
- |
- |
- |
- |
- |
- |
|
50 |
151 |
3 |
1 |
1 |
2101 |
- |
- |
- |
- |
- |
- |
- |
23104 |
608 |
1272 |
1018 |
2102 |
- |
- |
- |
- |
- |
- |
- |
207456 |
96905 |
96071 |
96071 |
96657 |
- |
- |
- |
- |
- |
- |
- |
164.4 |
1.7 |
2.4 |
2.8 |
6.9 |
- |
- |
- |
- |
- |
- |
- |
|
75 |
226 |
3 |
1 |
1 |
4557 |
- |
- |
- |
- |
- |
- |
- |
51529 |
908 |
1897 |
1518 |
4558 |
- |
- |
- |
- |
- |
- |
- |
597041 |
212855 |
211596 |
211596 |
211803 |
- |
- |
- |
- |
- |
- |
- |
1389.9 |
5.6 |
8.9 |
10.1 |
36.2 |
- |
- |
- |
- |
- |
- |
- |
|
100 |
- |
3 |
1 |
1 |
7951 |
- |
- |
- |
- |
- |
- |
- |
- |
1208 |
2522 |
2018 |
7952 |
- |
- |
- |
- |
- |
- |
- |
- |
373805 |
372121 |
372121 |
373307 |
- |
- |
- |
- |
- |
- |
- |
- |
15.3 |
23.1 |
25.8 |
135.8 |
- |
- |
- |
- |
- |
- |
- |
|
key_ |
|
n |
Iterations |
Events fired |
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 |
55 |
40 |
2 |
2 |
273 |
55 |
55 |
55 |
55 |
57 |
57 |
57 |
5152 |
3772 |
2756 |
2352 |
274 |
896 |
1736 |
1736 |
1512 |
1798 |
1798 |
1566 |
16859 |
16956 |
17316 |
17263 |
17115 |
214185 |
179207 |
69452 |
187045 |
180934 |
69668 |
188796 |
0.3 |
0.2 |
0.5 |
0.4 |
0.3 |
2.1 |
1.9 |
1.1 |
0.9 |
2.0 |
1.2 |
1.0 |
|
3 |
67 |
48 |
2 |
2 |
577 |
67 |
67 |
67 |
67 |
69 |
69 |
69 |
9044 |
6517 |
5753 |
4757 |
578 |
1564 |
2788 |
2788 |
2788 |
2870 |
2870 |
2870 |
36538 |
35668 |
34114 |
33848 |
34380 |
2008737 |
786339 |
702311 |
1056011 |
791286 |
702311 |
1101660 |
1.8 |
1.3 |
1.5 |
1.2 |
1.8 |
63.2 |
36.0 |
9.4 |
11.6 |
35.7 |
9.5 |
12.0 |
|
4 |
79 |
56 |
2 |
2 |
1066 |
- |
79 |
79 |
79 |
161 |
154 |
161 |
13920 |
9918 |
10064 |
8127 |
1067 |
- |
4320 |
4320 |
4160 |
8748 |
8370 |
8424 |
74989 |
67068 |
57497 |
57205 |
58398 |
- |
2035824 |
2035824 |
1970192 |
2035824 |
2035824 |
1795025 |
12.1 |
6.6 |
4.2 |
3.3 |
6.6 |
- |
426.8 |
92.1 |
152.6 |
416.6 |
91.0 |
154.6 |
|
mmgt_ |
|
n |
Iterations |
Events fired |
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 |
18 |
14 |
1 |
1 |
257 |
- |
- |
- |
- |
- |
- |
- |
2166 |
1710 |
6359 |
5727 |
257 |
- |
- |
- |
- |
- |
- |
- |
15687 |
15649 |
14921 |
14921 |
15421 |
- |
- |
- |
- |
- |
- |
- |
0.2 |
0.2 |
0.7 |
0.7 |
0.3 |
- |
- |
- |
- |
- |
- |
- |
|
3 |
25 |
18 |
1 |
1 |
447 |
- |
- |
- |
- |
- |
- |
- |
4472 |
3268 |
14210 |
12462 |
447 |
- |
- |
- |
- |
- |
- |
- |
36272 |
35633 |
31162 |
31162 |
32621 |
- |
- |
- |
- |
- |
- |
- |
1.6 |
1.1 |
2.3 |
2.0 |
1.6 |
- |
- |
- |
- |
- |
- |
- |
|
4 |
32 |
22 |
1 |
1 |
905 |
- |
- |
- |
- |
- |
- |
- |
7656 |
5336 |
25639 |
21877 |
905 |
- |
- |
- |
- |
- |
- |
- |
73542 |
74104 |
56057 |
56057 |
59047 |
- |
- |
- |
- |
- |
- |
- |
10.4 |
6.0 |
5.6 |
4.3 |
5.8 |
- |
- |
- |
- |
- |
- |
- |
Next: Automatic variable reordering results
Up: Evaluating Symbolic Traversal Algorithms
Previous: General benchmark data
Enric Pastor
2004-05-28