Some New Results in the Complexity of Allocation and Binding in Data Path Synthesis CAManda.pdf

Some New Re sults in the Complexity of Allo cation and Binding in Data Path Synthe s i s 1 2 2 C AM andal P P C hak r abar ti SGhose 1 Department of Computer Science Brunel Univers ity Uxbr idge UB PH UK 2 Department of Computer Science Engineer ing Indian Institute of Technology Kharagpur INDIA Ab stract In this paper we pr esent some new results on the complexity of al location and binding pr oblems in Data Path Synthesis DPS We have considered are the p ort assignment pr oblem for multiport memories the registerinter connect optimization pr oblem 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 p olynomial time The next more general case that we have considered is RIO for straightline code SRIO a special case of RIO which we have shown to be NPhard The most signicant contributions of this work are results on the hardness of relative approximation of several pr oblems of DPS We have shown that the constant bounded relative approximation of PA for triple p ort memories and SRIO are both NPhard Key Words Al location NPcomplete pr oblems Data Path Synthesis HighL evel Syn thesis Intro duction Allo cation and binding problems which have to b e addre s s e d for data path