An efficient algorithm for simultaneous wire permutation, inversion, and spacing

In very deep sub-micron (VDSM), interconnects are the major source of power dissipation on buses. In this paper, we address this problem by simultaneously optimizing wire permutation, inversion and spacing (space between consecutive wires) with a fast algorithm. Unlike previous studies, our approach is applicable not only to address buses (which behave more regularly), but can also be applied to instruction buses of a microprocessor. Further, for the spacing problem, we use an algorithm which determines the optimal solution instead of applying time consuming heuristic algorithms. Experimental result shows that we can save energy up to 70% for the best case and 56% on average while increasing the total wire space by only about 50% (compared to a bus with minimal spacing between adjacent wires for a particular technology). Further, it turned out that our algorithm produces nearly the same results as an appropriate genetic algorithm while requiring significant less runtime.