Input Variable Partitioning Method for Decomposition-Based Logic Synthesis targeted Heterogeneous FPGAs

The functional decomposition has found an application in many fields of modern engineering and science, such as combinational and sequential logic synthesis for VLSI systems, pattern analysis, knowledge discovery, machine learning, decision systems, data bases, data mining etc. It is perceived as one of the best logic synthesis methods for FPGAs. However, its practical usefulness for very complex systems depends on efficiency of method used in decomposition calculation. One of the most important steps in functional decomposition construction is selection of the appropriate input variable partitioning. In case of modern heterogeneous programmable structures efficiency of methods used to solve this problem becomes especially important. Since the input variable partitioning problem is an NP-hard, heuristic methods have to be used to efficiently and effectively search for optimal or near-optimal solutions. The paper presents a method for bound set selection in functional decomposition targeted FPGAs with heterogeneous structure. This heuristic algorithm delivers optimal or near optimal results and is much faster than other methods.