Compatibility path based binding algorithm for interconnect reduction in high level synthesis
Taemin Kim, Xun Liu · Digest of technical papers/Digest of technical papers - IEEE/ACM International Conference on Computer-Aided Design · 2007
This paper describes a register and functional unit (FU) binding al- gorithm in high level synthesis. Our algorithm targets the reduction of multiplexer inputs. Since multiplexers connect multiple inputs to FUs or registers, the multiplexer count is a good indicator of the in- terconnect complexity. Reducing the number of multiplexer inputs results in reducing interconnect cost. Specifically, our algorithm constructs a weighted and ordered compatibility graph, and binds operations that form a long path in the graph together. As a result, operations with many flow dependencies and common inputs are bound to same FU, leading to a small number of FU inputs. In addition, the operation variables generated by a single FU are as- signed to the same register so that connections between FUs and registers are reduced. We have implemented our algorithm within a MATLAB to Verilog conversion tool, and applied it to a suite of benchmark programs. Our experimental results have shown that the proposed scheme achieves 11.8%, 43.6% and 58.8% multiplexer input count reduction on average over weighted bipartite matching algorithm, k-cofamily algorithm and left edge algorithm, res- pectively. To assess the impact on interconnect reduction, we have generated layouts of the circuits from our Verilog description. It is shown that our approach delivers a 10.1% reduction in total wire- length of global interconnects with minor area overhead of register and FUs in comparison to the best previously proposed scheme.