Circuit Clustering for Cluster-based FPGAs Using Novel Multiobjective Genetic Algorithms

Circuit clustering is one of the most crucial steps in a post-synthesis FPGA CAD flow. It attempts to efficiently fit synthesised logic functions into FPGA logic clusters. On a FPGA, different clusterings result in different circuit mappings, which affect FPGA utilisation, routability and timing, and therefore impact the circuit performance. This research proposes the use of a Multi Objective Genetic Algorithm (MOGA) as a methodology to solve the cluster-based FPGA circuit clustering problem.

Four alternative approaches based on MOGA methods are proposed in this research: RVPack is inspired by the stochastic feature that exists in Evolutionary Algorithms (EAs). GGAPack, GGAPack2, DBPack and HYPack, T-HYPack (Timing-driven HYPack) are then proposed and developed, which are fully customised MOGA-based circuit clustering methods. GGAPack clusters a circuit using a top-down perspective, and DBPack uses a new bottom-up perspective. HYPack combines GGAPack and HYPack -- a hybrid method. According to experimental results, a few conclusions are drawn: It is possible to improve the performance of the greedy algorithm based circuit clustering methods by incorporating randomness. The performance of MOGA based top-down clustering is poor; however, using MOGA to cluster a circuit from a bottom-up perspective can produce better solutions. T-HYPack clustered circuit has the best timing performance compared with state-of-the-art methods. The experimental results also reflect a wider potential for using GAs to solve FPGA circuit mapping problems.