Port assignment for multiplexer and interconnection optimization

Data path connection elements usually consume a significant amount of both power and area on a VLSI chip. In this paper, we focus on the port assignment problem for multiplexer (MUX) and interconnection optimization in High-Level Synthesis. Given a binding solution of operations and variables, the port assignment problem connects the registers to the operator ports through MUXes, to minimize the interconnections between MUXes and operator ports, as well as the MUX power and area. We formulate the port assignment problem for binary commutative operators as a vertex partition problem on a graph, and propose a local search based heuristic algorithm that iteratively performs the elementary spanning tree transformation on the graph to solve it. We also propose a method to estimate the result of the tree transformation and filter a considerable amount of bad solutions in advance which greatly accelerate the algorithm. The experimental results show that our proposed algorithm is able to achieve 48% execution time reduction and 8.3% power reduction compared with the previous work, and the power reduction can be obtained for 37% test benches.