7 Literal Selection in Switching Lattice Design
161
different behavior regarding their computational complexity: the first one can be
solved in time polynomial in the size of the lattice, while the second is intractable.
We design and implement heuristic algorithms for both problems and evaluate
their performances on a set of lattices implementing known circuit benchmarks. We
also analyze the effect of the two different literal selection policies on the physical
layout of lattices.
The paper is organized as follows: Preliminaries on switching lattices are
reviewed in Sect. 7.2 and the general problem of literal selection is discussed in
Sect. 7.3. Section 7.4 introduces and discusses the minimal degree assignment
(MDA) problem that consists in minimizing the maximum number of lattice
cells assigned to the same literal, whereas Sect. 7.5 studies the minimal partition
assignment (MPA) problem consisting in minimizing the number of lattice portions
of adjacent cells whose switches are associated with the same literal. Experiments
on a set of standard benchmark circuits are reported in Sect. 7.6, and Sect. 7.7
concludes the paper.
7.2 Switching Lattices
In this section we briefly review some basic notions and results [1, 4, 26]. A switching lattice is a two-dimensional array of four-terminal switches each contained in
a cell. The four terminals of the switch link to the four neighbors of the cell, so
that these are either all connected with each other (when the switch is ON), or
disconnected (when the switch is OFF).
A Boolean function can be implemented by a lattice with the following rules:
– each four-terminal switch is controlled by a Boolean literal or by the constant 0,
or 1;
– if the literal or the constant takes the value 1 the corresponding switch is
connected to its neighbors; otherwise, it is not connected;
– the function evaluates to 1 if and only if there exists a connected path between
two opposing edges of the lattice, e.g., the top and the bottom edges;
– input assignments that leave the edges unconnected correspond to output 0.
For instance, the 3 × 3 network of switches in Fig. 7.1a corresponds to the lattice in
Fig. 7.1b, which implements the function f = x 1 x 2 x 3 + x 1 x 3 + x 2 x 3 . If we assign
the values 1, 0, 1 to the variables x 1 , x 2 , x 3 , respectively, we obtain paths of gray
square connecting the top and the bottom edges of the lattices (Fig. 7.1c), and f
evaluates to 1. On the contrary, the assignment x 1 = 0, x 2 = 1, x 3 = 0 does not
produce any path from the top to the bottom edge and f evaluates to 0 (Fig. 7.1d).
The synthesis problem on a lattice consists in finding an assignment of literals to
switches in order to implement a given target function with a lattice of minimal size
measured in terms of the number of switches in the lattice.
A switching lattice can similarly be equipped with left edge to right edge
connectivity, so that a single lattice can implement two different functions. This fact
161
different behavior regarding their computational complexity: the first one can be
solved in time polynomial in the size of the lattice, while the second is intractable.
We design and implement heuristic algorithms for both problems and evaluate
their performances on a set of lattices implementing known circuit benchmarks. We
also analyze the effect of the two different literal selection policies on the physical
layout of lattices.
The paper is organized as follows: Preliminaries on switching lattices are
reviewed in Sect. 7.2 and the general problem of literal selection is discussed in
Sect. 7.3. Section 7.4 introduces and discusses the minimal degree assignment
(MDA) problem that consists in minimizing the maximum number of lattice
cells assigned to the same literal, whereas Sect. 7.5 studies the minimal partition
assignment (MPA) problem consisting in minimizing the number of lattice portions
of adjacent cells whose switches are associated with the same literal. Experiments
on a set of standard benchmark circuits are reported in Sect. 7.6, and Sect. 7.7
concludes the paper.
7.2 Switching Lattices
In this section we briefly review some basic notions and results [1, 4, 26]. A switching lattice is a two-dimensional array of four-terminal switches each contained in
a cell. The four terminals of the switch link to the four neighbors of the cell, so
that these are either all connected with each other (when the switch is ON), or
disconnected (when the switch is OFF).
A Boolean function can be implemented by a lattice with the following rules:
– each four-terminal switch is controlled by a Boolean literal or by the constant 0,
or 1;
– if the literal or the constant takes the value 1 the corresponding switch is
connected to its neighbors; otherwise, it is not connected;
– the function evaluates to 1 if and only if there exists a connected path between
two opposing edges of the lattice, e.g., the top and the bottom edges;
– input assignments that leave the edges unconnected correspond to output 0.
For instance, the 3 × 3 network of switches in Fig. 7.1a corresponds to the lattice in
Fig. 7.1b, which implements the function f = x 1 x 2 x 3 + x 1 x 3 + x 2 x 3 . If we assign
the values 1, 0, 1 to the variables x 1 , x 2 , x 3 , respectively, we obtain paths of gray
square connecting the top and the bottom edges of the lattices (Fig. 7.1c), and f
evaluates to 1. On the contrary, the assignment x 1 = 0, x 2 = 1, x 3 = 0 does not
produce any path from the top to the bottom edge and f evaluates to 0 (Fig. 7.1d).
The synthesis problem on a lattice consists in finding an assignment of literals to
switches in order to implement a given target function with a lattice of minimal size
measured in terms of the number of switches in the lattice.
A switching lattice can similarly be equipped with left edge to right edge
connectivity, so that a single lattice can implement two different functions. This fact