172
A. Bernasconi et al.
Table 7.2 Number of areas and layers for a subset of standard benchmark circuits taken from [35]
HMPA1
HMPA2
Layers
Benchmark Areas
Time Deg.
Areas
Time Deg.
HPMA1 HPMA2 Random
b3(14)
3226 39.3
4653
3387
90.9
3726 16
16
17
bcc(29)
2915 23.2
524
2969
26.7
458 16
17
19
ex1010(1)
2062 20.2
398
2103
14.1
400 19
17
21
ex1010(3)
2022 16.5
347
2122
16.4
371 18
17
23
ex1010(4)
2104 17.4
330
2137
15.1
304 16
18
24
ex1010(6)
2084 18.4
369
2094
16.7
338 17
16
21
ex1010(8)
2114 17.8
549
2136
14.6
561 16
15
34
in4(13)
3021 38.3
4779
3197
96.8
3780 15
15
18
mainpla(5)
2022 20.0
731
2117
25.6
662 19
16
19
mainpla(9)
2186 20.0
910
2294
25.3
805 18
17
17
mainpla(10)
2528 23.5
1044
2667
38.0
835 17
18
16
mainpla(16)
2078 27.5
1155
2217
34.0
862 14
15
18
mainpla(26)
2002 23.0
1332
2056
35.3
1437 16
15
18
mainpla(27)
2053 21.1
1365
2145
29.8
1230 17
16
17
mainpla(28)
2372 21.9
1441
2548
38.8
1296 16
17
21
mainpla(35)
3204 36.1
1460
3298
49.2
1499 17
16
18
mainpla(36)
2527 27.0
1376
2577
31.9
1404 17
18
19
max1024(4)
3200 27.0
720
3293
22.4
647 22
22
23
max1024(5)
6254 74.8
1177
6709
62.6
1145 19
19
31
sym10(0)
3606 71.5
4247
5114
31.7
5466 11
11
11
test3(13)
2183 17.5
370
2209
19.6
380 18
18
29
test3(29)
2234 24.0
419
2235
14.1
419 20
18
26
tial(2)
3410 28.9
1458
3456
35.7
1516 15
16
20
tial(3)
3269 38.2
1868
3582 113.0
1626 19
17
22
tial(5)
11, 873 11.9
6161 12, 474
22.6
6356 21
21
21
xparc(24)
3427 45.9
943
3565
82.4
942 17
17
18
Total
79, 976 751.0 40, 126 84, 701 1003.2 38, 465 446
438
541
The selection of literals has been performed with the two heuristics HMPA1 and HMPA2, or at
random. Running times are expressed in milliseconds
out of 1918) reducing all subsets with more than one literal, when present, to just
one literal. For the remaining lattices, we have run the two heuristics HMPA1 and
HMPA2. The results reported in Table 7.2 are relative to the lattices with the largest
numbers of areas, already examined before.
The first column reports the name and the number of the separate output function
of the benchmark circuit. The following six columns report the number of areas
computed by heuristics HMPA1 and HMPA2, together with the corresponding
running time expressed in millisecond, and the degree of the resulting lattice. For
each lattice, we bolded the best area, the best running time, and the best degree.
Finally, the last three columns report the number of layers needed for connecting
A. Bernasconi et al.
Table 7.2 Number of areas and layers for a subset of standard benchmark circuits taken from [35]
HMPA1
HMPA2
Layers
Benchmark Areas
Time Deg.
Areas
Time Deg.
HPMA1 HPMA2 Random
b3(14)
3226 39.3
4653
3387
90.9
3726 16
16
17
bcc(29)
2915 23.2
524
2969
26.7
458 16
17
19
ex1010(1)
2062 20.2
398
2103
14.1
400 19
17
21
ex1010(3)
2022 16.5
347
2122
16.4
371 18
17
23
ex1010(4)
2104 17.4
330
2137
15.1
304 16
18
24
ex1010(6)
2084 18.4
369
2094
16.7
338 17
16
21
ex1010(8)
2114 17.8
549
2136
14.6
561 16
15
34
in4(13)
3021 38.3
4779
3197
96.8
3780 15
15
18
mainpla(5)
2022 20.0
731
2117
25.6
662 19
16
19
mainpla(9)
2186 20.0
910
2294
25.3
805 18
17
17
mainpla(10)
2528 23.5
1044
2667
38.0
835 17
18
16
mainpla(16)
2078 27.5
1155
2217
34.0
862 14
15
18
mainpla(26)
2002 23.0
1332
2056
35.3
1437 16
15
18
mainpla(27)
2053 21.1
1365
2145
29.8
1230 17
16
17
mainpla(28)
2372 21.9
1441
2548
38.8
1296 16
17
21
mainpla(35)
3204 36.1
1460
3298
49.2
1499 17
16
18
mainpla(36)
2527 27.0
1376
2577
31.9
1404 17
18
19
max1024(4)
3200 27.0
720
3293
22.4
647 22
22
23
max1024(5)
6254 74.8
1177
6709
62.6
1145 19
19
31
sym10(0)
3606 71.5
4247
5114
31.7
5466 11
11
11
test3(13)
2183 17.5
370
2209
19.6
380 18
18
29
test3(29)
2234 24.0
419
2235
14.1
419 20
18
26
tial(2)
3410 28.9
1458
3456
35.7
1516 15
16
20
tial(3)
3269 38.2
1868
3582 113.0
1626 19
17
22
tial(5)
11, 873 11.9
6161 12, 474
22.6
6356 21
21
21
xparc(24)
3427 45.9
943
3565
82.4
942 17
17
18
Total
79, 976 751.0 40, 126 84, 701 1003.2 38, 465 446
438
541
The selection of literals has been performed with the two heuristics HMPA1 and HMPA2, or at
random. Running times are expressed in milliseconds
out of 1918) reducing all subsets with more than one literal, when present, to just
one literal. For the remaining lattices, we have run the two heuristics HMPA1 and
HMPA2. The results reported in Table 7.2 are relative to the lattices with the largest
numbers of areas, already examined before.
The first column reports the name and the number of the separate output function
of the benchmark circuit. The following six columns report the number of areas
computed by heuristics HMPA1 and HMPA2, together with the corresponding
running time expressed in millisecond, and the degree of the resulting lattice. For
each lattice, we bolded the best area, the best running time, and the best degree.
Finally, the last three columns report the number of layers needed for connecting