White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

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

Wang, Yuan (2015) Circuit Clustering for Cluster-based FPGAs Using Novel Multiobjective Genetic Algorithms. PhD thesis, University of York.

Available under License Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 UK: England & Wales.

Download (10Mb) | Preview


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.

Item Type: Thesis (PhD)
Academic Units: The University of York > Electronics (York)
Identification Number/EthosID: uk.bl.ethos.680610
Depositing User: Mr Yuan Wang
Date Deposited: 29 Feb 2016 11:45
Last Modified: 24 Jul 2018 15:21
URI: http://etheses.whiterose.ac.uk/id/eprint/11830

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)