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

doi:10.1109/43.543767

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 journal › Article › Scientific › peer-review

5 Citations (Scopus)

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 language	English
Pages (from-to)	1340-1353
Number of pages	14
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	15
Issue number	11
DOIs	https://doi.org/10.1109/43.543767
Publication status	Published - 1996
Externally published	Yes

Access to Document

10.1109/43.543767

Cite this

@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",

}

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

SN - 0278-0070

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

IS - 11

ER -

The complexity of generalized retiming problems

Abstract

Access to Document

Fingerprint

Cite this