Technology mapping for field-programmable gate arrays using integer programming
Amit Chowdhary, John P. Hayes · 1995
We show that the FPGA technology mapping prob-lem can be eciently implemented as a mixed inte-ger linear programming (MILP) problem which gener-ates truly optimal mappings. The MILP approach can handle a wide variety of FPGA logic block architec-tures. We present a compact MILP formulation for logic blocks based on lookup tables (LUTs) or multi-plexers. We also show that the MILP formulation can be easily modied to optimize area, delay, or a combi-nation of both. We demonstrate that moderately large benchmark circuits can be mapped in a reasonable time using the MILP approach directly. For larger circuits, we propose a technique of partitioning a circuit prior to mapping, which drastically reduces the computation time with little or no loss in optimality. 1