The complexity of generalized retiming problems

B.L.E. de Fluiter, E.H.L. Aarts, J.H.M. Korst, W.F.J. Verhaegh, A. Werf van der

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We discuss the complexity of a number of high-level synthesis problems that can be viewed as generalizations of the classical retiming problem introduced by Leiserson and Saxe. The generalizations are concerned with additional degrees of freedom resulting from timefolding and multiplexing. The central problem is the design of multicycle and multifunctional processing units. This problem consists of two subproblems known as operator assignment and retiming. In this paper, we are primarily concerned with the construction of appropriate models and their complexity analysis. We show that both operator assignment and retiming are NP-hard in the presence of multiplexing or timefolding. We present a novel proof of the result obtained by Leiserson and Saxe, which states that retiming without multiplexing or timefolding can be solved in polynomial time
Original languageEnglish
Pages (from-to)1340-1353
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume15
Issue number11
DOIs
Publication statusPublished - 1996
Externally publishedYes

Fingerprint

Multiplexing
Assignment
High-level Synthesis
Complexity Analysis
Operator
Polynomial time
NP-complete problem
Degree of freedom
Unit
Generalization
Model

Cite this

de Fluiter, B.L.E. ; Aarts, E.H.L. ; Korst, J.H.M. ; Verhaegh, W.F.J. ; Werf van der, A. / The complexity of generalized retiming problems. In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1996 ; Vol. 15, No. 11. pp. 1340-1353.
@article{167c8c19eb124c29a6a8ba2c4b78ba42,
title = "The complexity of generalized retiming problems",
abstract = "We discuss the complexity of a number of high-level synthesis problems that can be viewed as generalizations of the classical retiming problem introduced by Leiserson and Saxe. The generalizations are concerned with additional degrees of freedom resulting from timefolding and multiplexing. The central problem is the design of multicycle and multifunctional processing units. This problem consists of two subproblems known as operator assignment and retiming. In this paper, we are primarily concerned with the construction of appropriate models and their complexity analysis. We show that both operator assignment and retiming are NP-hard in the presence of multiplexing or timefolding. We present a novel proof of the result obtained by Leiserson and Saxe, which states that retiming without multiplexing or timefolding can be solved in polynomial time",
author = "{de Fluiter}, B.L.E. and E.H.L. Aarts and J.H.M. Korst and W.F.J. Verhaegh and {Werf van der}, A.",
year = "1996",
doi = "10.1109/43.543767",
language = "English",
volume = "15",
pages = "1340--1353",
journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",
issn = "0278-0070",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "11",

}

The complexity of generalized retiming problems. / de Fluiter, B.L.E.; Aarts, E.H.L.; Korst, J.H.M.; Verhaegh, W.F.J.; Werf van der, A.

In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 15, No. 11, 1996, p. 1340-1353.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - The complexity of generalized retiming problems

AU - de Fluiter, B.L.E.

AU - Aarts, E.H.L.

AU - Korst, J.H.M.

AU - Verhaegh, W.F.J.

AU - Werf van der, A.

PY - 1996

Y1 - 1996

N2 - We discuss the complexity of a number of high-level synthesis problems that can be viewed as generalizations of the classical retiming problem introduced by Leiserson and Saxe. The generalizations are concerned with additional degrees of freedom resulting from timefolding and multiplexing. The central problem is the design of multicycle and multifunctional processing units. This problem consists of two subproblems known as operator assignment and retiming. In this paper, we are primarily concerned with the construction of appropriate models and their complexity analysis. We show that both operator assignment and retiming are NP-hard in the presence of multiplexing or timefolding. We present a novel proof of the result obtained by Leiserson and Saxe, which states that retiming without multiplexing or timefolding can be solved in polynomial time

AB - We discuss the complexity of a number of high-level synthesis problems that can be viewed as generalizations of the classical retiming problem introduced by Leiserson and Saxe. The generalizations are concerned with additional degrees of freedom resulting from timefolding and multiplexing. The central problem is the design of multicycle and multifunctional processing units. This problem consists of two subproblems known as operator assignment and retiming. In this paper, we are primarily concerned with the construction of appropriate models and their complexity analysis. We show that both operator assignment and retiming are NP-hard in the presence of multiplexing or timefolding. We present a novel proof of the result obtained by Leiserson and Saxe, which states that retiming without multiplexing or timefolding can be solved in polynomial time

U2 - 10.1109/43.543767

DO - 10.1109/43.543767

M3 - Article

VL - 15

SP - 1340

EP - 1353

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

SN - 0278-0070

IS - 11

ER -