THE COMPLEXITY OF GENERALIZED RETIMING PROBLEMS

We discuss the complexity of a number of high-level synthesis problems that can be viewed as generalizations of the classical retiming probl em introduced by Leiserson and Saxe, The generalizations are concerned with additional degrees of freedom resulting from timefolding and mul tiplexing, The central problem is the design of multicycle and multifu nctional processing units. This problem consists of two subproblems kn own as operator assignment and retiming, In this paper, we are primari ly concerned with the construction of appropriate models and their com plexity analysis, We show that both operator assignment and retiming a re NP-hard in the presence of multiplexing or timefolding, We present a novel proof of the result obtained by Leiserson and Saxe, which stat es that retiming without multiplexing or timefolding can be solved in polynomial time.