7 Literal Selection in Switching Lattice Design
173
all areas of switches controlled by the same input literal as estimate running the
best-first heuristic described in [21]. Again, we bolded the best results.
By comparing the results, we note that HMPA1 provides better results on the
number of areas and it is slightly more time efficient than HMPA2 in most cases.
We also note that the increase in the number of areas computed with the second
heuristic appears quite limited on average, while it can be relevant on single lattices
as in the case of benchmark sym10(0) in Table 7.2. The lattice degrees are in both
cases much bigger than those computed running heuristic HMDA after the Altun–
Riedel synthesis algorithm, showing how the two minimization goals (degree versus
area) are in contrast with each other, as one could reasonably expect.
Regarding the physical layout, the results of this last experimentation show how
the two heuristics for the minimization of the number of areas guarantee a reduction
of the number of layers, when compared with the layout for lattices synthesized
with arbitrary assignment of literals at switches when multiple choices are possible.
The reduction in the number of layers is of about 19% for the subset of (bigger)
lattices reported in Table 7.2, and of about 14% for the whole set of lattices for
which Rule 1 does not allow to completely solve MPA. Since such improvements
are obtained in a very limited time, running one of these two heuristics before the
physical implementation of lattices appears to be an advisable post-processing step
to be performed after the Altun–Riedel synthesis algorithm.
7.7 Concluding Remarks
We have discussed two different combinatorial problems related to the assignment
of input literals to switches in lattices synthesized with the Altun and Riedel
method [4]. We have proposed and developed efficient heuristic algorithms for
finding satisfactory solutions for both problems, and discussed the implication of
the different solutions on the layout of switching lattices. As future work on this
subject, we plan to study better heuristics and to test them on larger data samples.
More in general, we would like to study the effectiveness of the switching lattice
model to represent and deal with Boolean functions related to biological problems,
as those presented in [7–9].
References
1. Akers, S.B.: A rectangular logic array. IEEE Trans. Comput. 21(8), 848–857 (1972)
2. Alexandrescu, D., Altun, M., Anghel, L., Bernasconi, A., Ciriani, V., Frontini, L., Tahoori,
M.B.: Logic synthesis and testing techniques for switching nano-crossbar arrays. Microprocess. Microsyst. Embed. Hardw. Des. 54, 14–25 (2017)
3. Altun, M., Riedel, M.D.: Lattice-based computation of Boolean functions. In: Proceedings of
the 47th Design Automation Conference, DAC 2010, Anaheim, CA, July 13–18, pp. 609–612
(2010)
173
all areas of switches controlled by the same input literal as estimate running the
best-first heuristic described in [21]. Again, we bolded the best results.
By comparing the results, we note that HMPA1 provides better results on the
number of areas and it is slightly more time efficient than HMPA2 in most cases.
We also note that the increase in the number of areas computed with the second
heuristic appears quite limited on average, while it can be relevant on single lattices
as in the case of benchmark sym10(0) in Table 7.2. The lattice degrees are in both
cases much bigger than those computed running heuristic HMDA after the Altun–
Riedel synthesis algorithm, showing how the two minimization goals (degree versus
area) are in contrast with each other, as one could reasonably expect.
Regarding the physical layout, the results of this last experimentation show how
the two heuristics for the minimization of the number of areas guarantee a reduction
of the number of layers, when compared with the layout for lattices synthesized
with arbitrary assignment of literals at switches when multiple choices are possible.
The reduction in the number of layers is of about 19% for the subset of (bigger)
lattices reported in Table 7.2, and of about 14% for the whole set of lattices for
which Rule 1 does not allow to completely solve MPA. Since such improvements
are obtained in a very limited time, running one of these two heuristics before the
physical implementation of lattices appears to be an advisable post-processing step
to be performed after the Altun–Riedel synthesis algorithm.
7.7 Concluding Remarks
We have discussed two different combinatorial problems related to the assignment
of input literals to switches in lattices synthesized with the Altun and Riedel
method [4]. We have proposed and developed efficient heuristic algorithms for
finding satisfactory solutions for both problems, and discussed the implication of
the different solutions on the layout of switching lattices. As future work on this
subject, we plan to study better heuristics and to test them on larger data samples.
More in general, we would like to study the effectiveness of the switching lattice
model to represent and deal with Boolean functions related to biological problems,
as those presented in [7–9].
References
1. Akers, S.B.: A rectangular logic array. IEEE Trans. Comput. 21(8), 848–857 (1972)
2. Alexandrescu, D., Altun, M., Anghel, L., Bernasconi, A., Ciriani, V., Frontini, L., Tahoori,
M.B.: Logic synthesis and testing techniques for switching nano-crossbar arrays. Microprocess. Microsyst. Embed. Hardw. Des. 54, 14–25 (2017)
3. Altun, M., Riedel, M.D.: Lattice-based computation of Boolean functions. In: Proceedings of
the 47th Design Automation Conference, DAC 2010, Anaheim, CA, July 13–18, pp. 609–612
(2010)