Multiobjective genetic algorithm for routability-driven circuit clustering on FPGAs

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

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

2 Citations (Scopus)


This paper presents a novel routability-driven circuit clustering (packing) technique, DBPack, to improve function packing on FPGAs. We address a number of challenges when optimising packing of generic FPGA architectures, which are input bandwidth constraints (the number of unique cluster input signals is greater than the number of unique signals available from routing channel), density of packing to satisfy area constraints and minimisation of exposed nets outside the cluster in order to facilitate routability. In order to achieve optimal trade-off solutions when mapping for groups of Basic Logic Elements (BLEs) into clusters with regard to multiple objectives, we have developed a population based circuit clustering algorithm based on non-dominated sorting multi-objective genetic algorithm (NSGA-II). Our proposed method is tested using a number of the “Golden 20” MCNC benchmark circuits that are regularly used in FPGA-related literature. The results show that the techniques proposed in the paper considerably improve both packing density of clusters and their routability when compared to the state-of-art routability-driven packing algorithms, including VPack, T-VPack and RPack.
Original languageEnglish
Title of host publication2014 IEEE International Conference on Evolvable Systems
Number of pages116
Publication statusPublished - 15 Jan 2015


Dive into the research topics of 'Multiobjective genetic algorithm for routability-driven circuit clustering on FPGAs'. Together they form a unique fingerprint.

Cite this