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 alloca tion and binding problems in Data Path Synthesis (DPS). We have consid ered the port assignment problem for multiport memories, the Register- lnterconnect Optimization problem (RIO), and the problem of formation of functional units. RIO is a major problem of DPS and we have examine d several versions of it. The simplest case that we have considered is Register Optimization (RO) for straight line code which is solvable i n 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 w ork are results on the hardness of relative approximation of several p roblems of DPS. We have shown that the constant bounded relative appro ximation of PA for triple port memories and SRIO are both NP-hard. (C) 1900 Elsevier Science Ltd. All rights reserved.