A non classical approach to the logic synthesis of Boolean functions based on switching lattices is considered, for which deriving a feasible layout has not been previously studied. All switches controlled by the same literal must be connected together and to an input lead of the chip, and the layout of such connections must be realized in superimposed layers. Inter-layer connections are realized with vias, with the overall goal of minimizing the number of layers needed. The problem shows new interesting combinatorial and algorithmic aspects. Since the specific lattice cell where each switch is placed can be decided with a certain amount of freedom, and one literal among several may be assigned for controlling a switch, we first study a lattice rearrangement (Problem 1) and a literal assignment (Problem 2), to place in adjacent cells as many switches controlled by the same literal as possible. Then we study how to build a feasible layout of connections onto different layers using a minimum number of such layers (Problem 3). We prove that Problem 2 is NP-hard, and Problems 1 and 3 appear also intractable. Therefore we propose heuristic algorithms for the three phases that show an encouraging performance on a set of standard benchmarks.

The Connection Layout in a Lattice of Four-Terminal Switches

Bernasconi A.;Boffa A.;Luccio F.;Pagli L.
2019-01-01

Abstract

A non classical approach to the logic synthesis of Boolean functions based on switching lattices is considered, for which deriving a feasible layout has not been previously studied. All switches controlled by the same literal must be connected together and to an input lead of the chip, and the layout of such connections must be realized in superimposed layers. Inter-layer connections are realized with vias, with the overall goal of minimizing the number of layers needed. The problem shows new interesting combinatorial and algorithmic aspects. Since the specific lattice cell where each switch is placed can be decided with a certain amount of freedom, and one literal among several may be assigned for controlling a switch, we first study a lattice rearrangement (Problem 1) and a literal assignment (Problem 2), to place in adjacent cells as many switches controlled by the same literal as possible. Then we study how to build a feasible layout of connections onto different layers using a minimum number of such layers (Problem 3). We prove that Problem 2 is NP-hard, and Problems 1 and 3 appear also intractable. Therefore we propose heuristic algorithms for the three phases that show an encouraging performance on a set of standard benchmarks.
2019
Bernasconi, A.; Boffa, A.; Luccio, F.; Pagli, L.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/998628
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact