University of York
Circuit Clustering for Cluster-based FPGAs Using Novel Multiobjective Genetic Algorithms
Abstract
dc:description.abstractCircuit 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.
Degree
thesis:*- Name dc:type.qualificationname
- Ph.D
- Level dc:type.qualificationlevel
- doctoral
- Grantor dc:publisher.institution
- University of York
- Year dc:date.issued
- 2015
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Wang, Yuan
- Advisors dc:contributor.advisor
-
- Tyrrell, Andy
- Trefzer, Martin Albrecht
Rights
- Language dc:language.dcterms_iso639_2
- eng
Identifiers
dc:identifier.*- Identifier
- uk.bl.ethos.680610