An ILP-Based Optimal Circuit Mapping Method for PLDs

In this paper, we discuss an ILP-based method for simultaneous optimal technology mapping, placement and routing for programmable logic devices, such as FPGAs, as a fundamental research for architecture and algorithm evaluation. In general, heuristic methods are used for technology mapping, placement and routing, and many such methods have been developed. Although they are used to obtain high quality solutions within a practical time period, high quality is not guaranteed. In addition, the separated design processes make the final solutions not optimal. Simultaneous and optimal methods are useful for evaluating and developing heuristic methods, even if optimal methods take a long time. Furthermore, they can be used to evaluate reconfigurable architectures. In experiments, we confirmed that the optimal total wire length and critical path length of small circuits were obtained using our method. Critical path lengths were reduced by 28.6% on average when optimized.