170
A. Bernasconi et al.
A(s) ← a;
R(s) ← h;
else if (Q(s) = 0)
push s → Z;
Q(s) ← 1;
until no more vertices s with (L(s) = L(h)) AND (Q(s) = 0) are encountered;
a ← a + 1;
7.6 Experimental Results
In this section we report the experimental results conducted for evaluating the effectiveness of the proposed heuristics and the effect of the two different literal selection
policies on the physical layout of lattices. The aim of the first experimentation is to
measure the success rate of the heuristic HMDA for the minimization of the lattice
degree with respect to always-optimal algorithms, whereas the aim of the second
experimentation is to determine if and how much the heuristics HMPA1 and HMPA2
for the minimization of the number of areas guarantee a reduction of the number of
layers in the physical layout of the lattices.
In our work we have considered the lattices obtained applying the Altun–Riedel
method to the benchmarks taken from LGSynth93 [35], where each output has been
treated as a separate Boolean function, for a total number of 1918 lattices examined.
The experiments have been run on an Intel Core i7-3520M dual core, 2.90 GHz CPU
with 8 GB of main memory, running macOS 10.13.4. The three heuristic algorithms,
HMDA, HMPA1, HMPA2, have been implemented in C++. For the sake of brevity
we report in Table 7.1 and in Table 7.2 only the results on a very limited subset of
lattices (in fact, 26 out of 1918) as representative of our experiments. These lattices
have been chosen among those of biggest size and with the largest numbers of areas.
In Table 7.1 we report the results of the experimental evaluation of the heuristic
HMDA for the minimization of the lattice degree. The first column reports the
name and the number of the separate output function of the benchmark circuit. The
following two columns report the dimension (N × M) of the lattice and the number
of different literals occurring in it. The next two columns report the lattice degree
computed by the heuristic HMDA, together with the corresponding running time
expressed in milliseconds. Finally, the last two columns report the lattice degree
computed by the second of the two optimal algorithms proposed in [27], with its
running time expressed in milliseconds. Indeed, as expected (see Sect. 7.4) this
algorithm has always performed better than the first one. For each lattice, we bolded
the best degree and the best running time.
By comparing the results, we note that HMDA provides optimal results for the
degree for about 30% of the (bigger) lattices reported in Table 7.1 and that the
increase in the degree w.r.t. the optimal one is very limited on average, only about
0.62%. Considering the whole set of 1918 benchmarks examined, the heuristic
A. Bernasconi et al.
A(s) ← a;
R(s) ← h;
else if (Q(s) = 0)
push s → Z;
Q(s) ← 1;
until no more vertices s with (L(s) = L(h)) AND (Q(s) = 0) are encountered;
a ← a + 1;
7.6 Experimental Results
In this section we report the experimental results conducted for evaluating the effectiveness of the proposed heuristics and the effect of the two different literal selection
policies on the physical layout of lattices. The aim of the first experimentation is to
measure the success rate of the heuristic HMDA for the minimization of the lattice
degree with respect to always-optimal algorithms, whereas the aim of the second
experimentation is to determine if and how much the heuristics HMPA1 and HMPA2
for the minimization of the number of areas guarantee a reduction of the number of
layers in the physical layout of the lattices.
In our work we have considered the lattices obtained applying the Altun–Riedel
method to the benchmarks taken from LGSynth93 [35], where each output has been
treated as a separate Boolean function, for a total number of 1918 lattices examined.
The experiments have been run on an Intel Core i7-3520M dual core, 2.90 GHz CPU
with 8 GB of main memory, running macOS 10.13.4. The three heuristic algorithms,
HMDA, HMPA1, HMPA2, have been implemented in C++. For the sake of brevity
we report in Table 7.1 and in Table 7.2 only the results on a very limited subset of
lattices (in fact, 26 out of 1918) as representative of our experiments. These lattices
have been chosen among those of biggest size and with the largest numbers of areas.
In Table 7.1 we report the results of the experimental evaluation of the heuristic
HMDA for the minimization of the lattice degree. The first column reports the
name and the number of the separate output function of the benchmark circuit. The
following two columns report the dimension (N × M) of the lattice and the number
of different literals occurring in it. The next two columns report the lattice degree
computed by the heuristic HMDA, together with the corresponding running time
expressed in milliseconds. Finally, the last two columns report the lattice degree
computed by the second of the two optimal algorithms proposed in [27], with its
running time expressed in milliseconds. Indeed, as expected (see Sect. 7.4) this
algorithm has always performed better than the first one. For each lattice, we bolded
the best degree and the best running time.
By comparing the results, we note that HMDA provides optimal results for the
degree for about 30% of the (bigger) lattices reported in Table 7.1 and that the
increase in the degree w.r.t. the optimal one is very limited on average, only about
0.62%. Considering the whole set of 1918 benchmarks examined, the heuristic