Optimization of dual-threshold circuits

Konrad Engel; Thomas Kalinowski; Roger Labahn; Frank Sill; Dirk Timmermann

doi:10.18453/rosdok_id00005895

zum übergeordneten Dokument

Konrad Engel Thomas Kalinowski Roger Labahn Frank Sill Dirk Timmermann

Optimization of dual-threshold circuits

University of Rostock, Institute of Mathematics, 2005

https://doi.org/10.18453/rosdok_id00005895

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 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.

Workingpaper Freier Zugang

Titel:

Optimization of dual-threshold circuits

Schriftenreihe:

Preprints aus dem Institut für Mathematik, 05/5

Beteiligte Personen:

Konrad Engel[VerfasserIn]
	138612366
Thomas Kalinowski[VerfasserIn]
	0000-0002-8444-6848
	128420251
Roger Labahn[VerfasserIn]
	0000-0003-1901-9644
	170999645
Frank Sill[VerfasserIn]
Dirk Timmermann[VerfasserIn]
	0000-0001-9267-9695
	132790505

Zusammenfassung:

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. [Englisch]

Dokumenttyp:

Workingpaper

Einrichtung:

Mathematisch-Naturwissenschaftliche Fakultät

Sprache:

Englisch

Sachgruppe der DNB:

510 Mathematik

Umfang:

1 Online-Ressource (19 Seiten)

Veröffentlichung /
Entstehung:

Rostock: University of Rostock, Institute of Mathematics