7 Literal Selection in Switching Lattice Design
171
Table 7.1 Heuristic vs optimal lattice degree for a subset of standard benchmark circuits taken
from [16]
HMDA
[27]
Benchmark
N×M
lit
Degree
Time
Degree
Time
b3(14)
125 × 96
32
1840
4.1
1840
469.1
bcc(29)
93×71
26
263
1.3
262
11.6
ex1010(1)
89×48
10
218
1.6
214
4.1
ex1010(3)
94×49
10
236
0.9
231
5.2
ex1010(4)
92×47
10
223
1.0
218
21.3
ex1010(6)
91×44
10
205
0.8
201
3.8
ex1010(8)
90×49
10
224
0.7
222
3.5
in4(13)
125×96
32
1840
2.1
1840
315.7
mainpla(5)
100×54
27
338
0.7
338
118.1
mainpla(9)
105×55
27
343
1.6
339
87.6
mainpla(10)
113×65
27
385
1.4
385
183.8
mainpla(16)
105×64
27
431
1.3
427
52.2
mainpla(26)
99×66
27
607
1.0
607
57.3
mainpla(27)
93×66
27
484
2.5
479
130.5
mainpla(28)
104×72
27
515
1.3
508
197.5
mainpla(35)
127×73
27
638
1.0
621
455.8
mainpla(36)
110×64
27
570
1.2
570
103.8
max1024(4)
83×82
10
366
2.5
365
6.0
max1024(5)
117×122
10
733
16.5
718
13.2
sym10(0)
130×210
10
2537
6.9
2536
65.4
test3(13)
93×46
10
217
2.5
214
3.4
test3(29)
94×47
10
225
0.7
221
3.4
tial(2)
90×90
14
487
1.5
486
12.5
tial(3)
66×188
14
588
2.2
588
10.4
tial(5)
181×181
14
1967
6.2
1967
47.4
xparc(24)
143×80
41
530
2.9
509
80.0
Total
17, 010
65.4
16, 906
2462.5
The selection of literals has been performed with the heuristic HMDA and with the second optimal
algorithm proposed in [27]. Running times are expressed in milliseconds
found the optimal degree for about 89% of the lattices (1707 out of 1918). Again,
the average increase in the degree computed heuristically is very limited (0.64%).
The running times of the heuristic are smaller in all but one case for the
benchmarks in Table 7.1, and the gain in computational time is of about 97% on
average. For whole set of 1918 benchmarks examined, the heuristic was faster for
all but 28 benchmarks, with an average gain of about 95%.
We have then conducted an experimental evaluation of the heuristics HMPA1 and
HMPA2 for the minimization of the number of areas. First of all, we have applied
Rule 1 to reduce the sets of literals assigned to each lattice cell and we have verified
that Rule 1 allows to completely solve the MPA problem in 55% of the lattices (1051
171
Table 7.1 Heuristic vs optimal lattice degree for a subset of standard benchmark circuits taken
from [16]
HMDA
[27]
Benchmark
N×M
lit
Degree
Time
Degree
Time
b3(14)
125 × 96
32
1840
4.1
1840
469.1
bcc(29)
93×71
26
263
1.3
262
11.6
ex1010(1)
89×48
10
218
1.6
214
4.1
ex1010(3)
94×49
10
236
0.9
231
5.2
ex1010(4)
92×47
10
223
1.0
218
21.3
ex1010(6)
91×44
10
205
0.8
201
3.8
ex1010(8)
90×49
10
224
0.7
222
3.5
in4(13)
125×96
32
1840
2.1
1840
315.7
mainpla(5)
100×54
27
338
0.7
338
118.1
mainpla(9)
105×55
27
343
1.6
339
87.6
mainpla(10)
113×65
27
385
1.4
385
183.8
mainpla(16)
105×64
27
431
1.3
427
52.2
mainpla(26)
99×66
27
607
1.0
607
57.3
mainpla(27)
93×66
27
484
2.5
479
130.5
mainpla(28)
104×72
27
515
1.3
508
197.5
mainpla(35)
127×73
27
638
1.0
621
455.8
mainpla(36)
110×64
27
570
1.2
570
103.8
max1024(4)
83×82
10
366
2.5
365
6.0
max1024(5)
117×122
10
733
16.5
718
13.2
sym10(0)
130×210
10
2537
6.9
2536
65.4
test3(13)
93×46
10
217
2.5
214
3.4
test3(29)
94×47
10
225
0.7
221
3.4
tial(2)
90×90
14
487
1.5
486
12.5
tial(3)
66×188
14
588
2.2
588
10.4
tial(5)
181×181
14
1967
6.2
1967
47.4
xparc(24)
143×80
41
530
2.9
509
80.0
Total
17, 010
65.4
16, 906
2462.5
The selection of literals has been performed with the heuristic HMDA and with the second optimal
algorithm proposed in [27]. Running times are expressed in milliseconds
found the optimal degree for about 89% of the lattices (1707 out of 1918). Again,
the average increase in the degree computed heuristically is very limited (0.64%).
The running times of the heuristic are smaller in all but one case for the
benchmarks in Table 7.1, and the gain in computational time is of about 97% on
average. For whole set of 1918 benchmarks examined, the heuristic was faster for
all but 28 benchmarks, with an average gain of about 95%.
We have then conducted an experimental evaluation of the heuristics HMPA1 and
HMPA2 for the minimization of the number of areas. First of all, we have applied
Rule 1 to reduce the sets of literals assigned to each lattice cell and we have verified
that Rule 1 allows to completely solve the MPA problem in 55% of the lattices (1051