Chapter 7
Literal Selection in Switching Lattice
Design
Anna Bernasconi, Fabrizio Luccio, Linda Pagli, and Davide Rucci
7.1 Introduction
A switching lattice is a two-dimensional lattice of four-terminal switches linked
to the four neighbors of a lattice cell, so that these are either all connected or
disconnected. A Boolean function can be implemented by a lattice associating each
four-terminal switch to a Boolean literal, so that if the literal takes the value 1 the
corresponding switch is ON and connected to its four 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 (see
Fig. 7.1 for an example).
The idea of using regular two-dimensional arrays of switches to implement
Boolean functions dates back to a seminal paper by Akers [1], but has found a
renewed interest recently, thanks to the development of a variety of nanoscale
technologies. Synthesis algorithms targeting lattices of multi-terminal switches
have been designed [2, 4, 26, 31], and methods based on function decomposition
techniques [15–17] and on function regularities [10–14] have been exploited to
mitigate the cost of implementing switching lattices [18–20, 23, 24]. Moreover,
several studies on fault tolerance for nano-crossbar arrays have been published
recently [5, 22, 32–34].
The synthesis problem on a lattice consists of finding an assignment of literals
to switches in order to implement a target function with a lattice of minimal size.
In [3, 4], Altun and Riedel developed a synthesis method which assigns at least one
literal to each lattice position, with the literal controlling the corresponding switch.
A. Bernasconi () · F. Luccio · L. Pagli · D. Rucci
Dipartimento di Informatica, Università di Pisa, Pisa, Italy
e-mail: anna.bernasconi@unipi.it; fabrizio.luccio@unipi.it; linda.pagli@unipi.it
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_7
159
Literal Selection in Switching Lattice
Design
Anna Bernasconi, Fabrizio Luccio, Linda Pagli, and Davide Rucci
7.1 Introduction
A switching lattice is a two-dimensional lattice of four-terminal switches linked
to the four neighbors of a lattice cell, so that these are either all connected or
disconnected. A Boolean function can be implemented by a lattice associating each
four-terminal switch to a Boolean literal, so that if the literal takes the value 1 the
corresponding switch is ON and connected to its four 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 (see
Fig. 7.1 for an example).
The idea of using regular two-dimensional arrays of switches to implement
Boolean functions dates back to a seminal paper by Akers [1], but has found a
renewed interest recently, thanks to the development of a variety of nanoscale
technologies. Synthesis algorithms targeting lattices of multi-terminal switches
have been designed [2, 4, 26, 31], and methods based on function decomposition
techniques [15–17] and on function regularities [10–14] have been exploited to
mitigate the cost of implementing switching lattices [18–20, 23, 24]. Moreover,
several studies on fault tolerance for nano-crossbar arrays have been published
recently [5, 22, 32–34].
The synthesis problem on a lattice consists of finding an assignment of literals
to switches in order to implement a target function with a lattice of minimal size.
In [3, 4], Altun and Riedel developed a synthesis method which assigns at least one
literal to each lattice position, with the literal controlling the corresponding switch.
A. Bernasconi () · F. Luccio · L. Pagli · D. Rucci
Dipartimento di Informatica, Università di Pisa, Pisa, Italy
e-mail: anna.bernasconi@unipi.it; fabrizio.luccio@unipi.it; linda.pagli@unipi.it
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_7
159