Two Combinatorial Problems on the Layout of Switching Lattices
| Autor: | Fabrizio Luccio, Antonio Boffa, Linda Pagli, Anna Bernasconi |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Computer science
0211 other engineering and technologies 02 engineering and technology Logic Syn- thesis Switching Lattices Topology 020202 computer hardware & architecture Circuit Layout Logic synthesis Lattice (order) 0202 electrical engineering electronic engineering information engineering Circuit Layout Switching Lattices Logic Syn- thesis NP-Complete Problems NP-Complete Problems Boolean function 021106 design practice & management |
| Zdroj: | VLSI-SoC |
| DOI: | 10.1109/vlsi-soc.2018.8644855 |
| Popis: | 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. The problem presents new interesting combinatorial and algorithmic aspects. Our basic assumptions are that the positions of the switches in the lattice are fixed in the synthesis stage, and the layout for connecting the subsets of switches with the same input literal must be realized in superimposed planes through vias that take the same switch area. The overall goal is to minimize the number of layers needed. Since multiple choices of input literals are possible for each switch, we first study how to assign a single literal to each switch, to minimize the number of lattice portions of adjacent cells associated to the same literal (Problem 1). Then we study how to derive a feasible layout by building connections onto different layers, to minimize the number of layers (Problem 2). Problem 1 is NP-hard. Problem 2 seems to be also intractable, and exhibits limit instances that require an exceedingly number of layers or are even unsolvable. Heuristic algorithms are then developed for both problems and their encouraging performances are proved on a set of known benchmarks. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|