Two-phase multiobjective genetic algorithm for constrained circuit clustering on FPGAs

• Main Authors: Yuan Wang, Walker, James Alfred, Bale, Simon J., Trefzer, Martin A., Tyrrell, Andy M.
• Format: Conference Proceeding
• Language: English
• Subjects: Biological cells; Clustering algorithms; Clustering methods; Field programmable gate arrays; Genetic algorithms; Optimization; Routing
• ISSN: 1089-778X; 1941-0026
• DOI: 10.1109/CEC.2015.7257023

In this paper, we propose a novel technique based on multiobjective genetic algorithms (MOGA) to solve the circuit clustering problem in field-programmable gate array (FPGA) computer aided design (CAD) flow. As the circuit clustering result is subsequently used by the circuit place-and-route process at the post-synthesis stage, the clustering quality significantly affects the routing cost and the utilisation of FPGA. Among clustering metrics, reducing the global interconnects (global nets) between configurable logic blocks (CLBs) can be viewed as the most efficient precondition to improve the clustering quality. Since the circuit has many connection properties, it is difficult to identify the proper component combinations for sub-circuits that optimise interconnect, and it is even more complicated when CLBs pose constraints. In our technique, we break the circuit clustering task into two phases. We firstly apply the MOGA to identify the best component combinations to FPGA CLBs while respecting constraints, and a second MOGA takes clustering results from the first phase and performs further optimisation. Our proposed method is tested using the MCNC-20 benchmark. The results show that the proposed technique produces better results than state-of-art algorithms in reducing global nets. The overall improvement is up to 4.33% and 14.24% in reducing the cluster number and the global net number compared to the FPGA circuit packer, iRAC, which is considered to be the best clustering method to reduce global nets.