On the complexity of connectivity binding
Barry M. Pangrle · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1991
The complexity of the assignment of operations to hardware components to specify the design at a register-transfer level, which is referred to as connectivity binding, is discussed. Connectivity binding is an important issue in high-level behavior synthesis systems that start with abstract behavioral descriptions and synthesize register-transfer level architectures for implementation. The corresponding decision problem is shown to be NP-complete and the complexity of the optimization problem is discussed. This research is intended to provide insight into the nature of this problem. It is shown that problems as simple as performing optimal function unit binding for a hardware structure containing only one commutative operator are hard.>