FPGA module minimization

We examine the problem of minimizing the number of modules in an FPGA with combinational and sequential modules (like the C-modules and S-modules of the ACT2 and ACTS architectures). The constraint is that a combinational module can be combined with one flip-flop in a single sequential module, only if the combinational module drives no other combinational modules. We show that the problem of rearranging the flip-flops by retiming so as to satisfy prescribed individual bounds on the number of combinational and sequential modules is NP-complete. However for the problem of rearranging the flip-flops by retiming so as to minimize the total number of combinational and sequential modules, we present a quadratic-time algorithm. The algorithm uses a minimum-cost flow formulation and offers a significant time improvement over a previous approach that used a general linear program.