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

Yuan Wang, James Alfred Walker, Simon J. Bale, Martin A. Trefzer, Andy M. Tyrrell

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publication2015 IEEE Congress on Evolutionary Computation (CEC)
Number of pages1190
Publication statusPublished - 14 Sept 2015


Dive into the research topics of 'Two-phase multiobjective genetic algorithm for constrained circuit clustering on FPGAs'. Together they form a unique fingerprint.

Cite this