| Title: |
Optimization of Dual-Threshold Circuits |
| Authors: |
Konrad Engel; Thomas Kalinowski; Roger Labahn; Frank Sill; Dirk Timmermann |
| Contributors: |
The Pennsylvania State University CiteSeerX Archives |
| Source: |
http://ftp.math.uni-rostock.de/pub/preprint/2005/pre05_05.pdf. |
| Publication Year: |
2005 |
| Collection: |
CiteSeerX |
| Subject Terms: |
directed acyclic graphs; Sperner family; cutset; low-power design; leakage power; threshold voltage; timing constraints |
| Description: |
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 d0(v) ≤ d1(v) and two leakage values c0(v) ≥ c1(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. |
| Document Type: |
text |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.2005 |
| Availability: |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.2005; http://ftp.math.uni-rostock.de/pub/preprint/2005/pre05_05.pdf |
| Rights: |
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| Accession Number: |
edsbas.64364C8C |
| Database: |
BASE |