Konrad Engel, Thomas Kalinowski, Roger Labahn, Frank Sill, Dirk Timmermann
Optimization of Dual-Threshold Circuits
Preprint series: Preprints aus dem Fachbereich Mathematik, Universität Rostock
90C35 Programming involving graphs or networks
06A07 Combinatorics of partially ordered sets
Abstract: In this paper, we consider an optimization problem on directed acyclic graphs which is motivated by a standard task in low power VLSI design. With each vertex $v$ of a directed acyclic graph, we associate two delay values $d_0(v)\leq d_1(v)$ and two leakage values $c_0(v)\geq c_1(v)$. The objective is to choose one of the indices $0$ or $1$ for each vertex, such that in first instance the corresponding total delay along any directed path is minimal, and in second instance the total leakage is minimized. We prove that a very restricted special case of this problem already is NP-hard, and we present four different heuristic approaches to the problem. Further, we test our algorithms on ISCAS85 benchmark circuits.
Keywords: directed acyclic graphs, Sperner family, cutset, low-power design, leakage power, threshold voltage, timing constraints, VLSI CAD