A Satisfiability-Based Approximate Algorithm for Logic Synthesis Using Switching Lattices
A Satisfiability-Based Approximate Algorithm for Logic Synthesis Using Switching Lattices
Tarih
2019
Yazarlar
Aksoy, Levent
Altun, Mustafa
Süreli Yayın başlığı
Süreli Yayın ISSN
Cilt Başlığı
Yayınevi
IEEE
Özet
In recent years the realization of a logic function
on two-dimensional arrays of four-terminal switches, called
switching lattices, has attracted considerable interest. Exact
and approximate methods have been proposed for the problem
of synthesizing Boolean functions on switching lattices with
minimum size, called lattice synthesis (LS) problem. However,
the exact method can only handle relatively small instances and
the approximate methods may find solutions that are far from
the optimum. This paper introduces an approximate algorithm,
called JANUS, that formalizes the problem of realizing a logic
function on a given lattice, called lattice mapping (LM) problem,
as a satisfiability problem and explores the search space of the LS
problem in a dichotomic search manner, solving LM problems
for possible lattice candidates. This paper also presents three
methods to improve the initial upper bound and an efficient way
to realize multiple logic functions on a single lattice. Experimental
results show that JANUS can find solutions very close to the
minimum in a reasonable time and obtain better results than
the existing approximate methods. The solutions of JANUS can
also be better than those of the exact method, which cannot be
determined to be optimal due to the given time limit, where the
maximum gain on the number of switches reaches up to 25%.
Açıklama
Anahtar kelimeler
Logic synthesis,
Mantık sentezi,
Anahtarlama kafesleri,
Switching lattices
Alıntı
L. Aksoy and M. Altun, "A Satisfiability-Based Approximate Algorithm for Logic Synthesis Using Switching Lattices," 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), Florence, Italy, 2019, pp. 1637-1642.
doi: 10.23919/DATE.2019.8714809