In this paper we present some new results on the complexity of allocation and binding problems in Data Path Synthesis (DPS). We have considered are the port assignment problem for multi-port memories, the register-interconnect optimization problem (RIO) and the problem of formation of functional units. RIO is a major problem of DPS and we have examined several versions of it. The simplest case that we have considered is register optimization (RO) for straight line code which is solvable in polynomial time. The next more general case that we have considered is RIO for straight-line code (SRIO), a special case of RIO, which we have shown to be NP-hard. The most significant contributions of this work are results on the hardness of relative approximation of several problems of DPS. We have shown that the constant bounded relative approximation of PA for triple port memories and SRIO are both NP-hard.

Keywords: Allocation, NP-complete problems, Data Path Synthesis High-Level Synthesis