A fast algorithm for minimizing FPGA combinational and sequential modules

ABSTRACT

We present a quadratic-time algorithm for minimizing the number of modules in an FPGA with combinational and sequential modules (like the C-modules and S-modules of the ACT2 and ACT3 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. Our algorithm uses a minimum-cost flow formulation to solve the problem with a significant time improvement over a previous approach that used a general linear program.

REFERENCES

• 1: ACTEL CORPORATION, 1992. The FPGA Design Guide 2, Dec.
• 2: Yao-Ping Chen , D. F. Wong, On Retiming for FPGA Logic Module Minimization, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.394-397, October 10-12, 1994
• 3: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 4: LEISERSON, C. E., AND SAXE, J.B. 1991. Retiming synchronous circuitry. Algorithmica, 6, 5-35.
• 5: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 6: VAIDYA, P. M. 1989. Speeding-up linear programming using fast matrix multiplication, IEEE Symposium on Foundations of Computer Science (Research Triangle Park, NC, Oct. 30-Nov.1), 332-337.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization; Automatic synthesis

General Terms:
Algorithms, Design

Keywords:
field programmable gate arrays, retiming