Optimal joint module-selection and retiming with carry-save representation

Abstract—This paper is the first to combine the joint module-selection and retiming problem with the use of carry-save representation in the optimization of a synchronous circuit. To solve this problem efficiently, we first create a mixed-represen-tation data-flow graph (MFG) by inserting signal representation conversion vertices into the data-flow graph, thus allowing carry-save representation to be freely selected for use. We then identify key properties of an optimal implementation of the MFG that consider the different signal representations as well as the sharing of registers and adders. These properties enable us to formulate the problem as a mixed-integer linear programming problem with cost functions that accurately reflect the true implementation costs of the circuit. Our algorithm, by allowing carry-save representation, can produce a wider range of solutions. In our experiments, our fastest implementation is 27 % faster and our smallest implementation is 27 % smaller, in comparison with solutions obtained using the previously known joint module-selec-tion and retiming technique. Index Terms—Carry-save, mixed-integer linear programming (MILP), module selection, retiming, synchronous data-flow graph (DFG). I