Some new results in the complexity of allocation and binding in data path synthesis

In this paper, we present some new results on the complexity of allocation and binding problems in Data Path Synthesis (DPS). We have considered the port assignment problem for multiport 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.