Today the logic capacity of Field-Programmable Gate Arrays (FPGAs) has increased dramatically (up to 10-million gates) that prohibitively long compile times may adversely affect instant manufacturability of FPGAs and become intolerable to users seeking very high speed compile. This thesis presents several heuristic techniques and investigates the effectiveness and efficiency of heuristics and meta-heuristics for FPGA placement. In constructive based heuristics, Cluster Seed Search (CSS) is developed to improve averagely random initial solutions by 19%; GRASP and a Partitioning based method are also implemented and achieve 25% and 44% improvement respectively. In iterative based heuristics, an enhanced local search technique is implemented in two forms: Simple Local Search (SLS) and Immediate Neighbourhood Local Search (INLS), which both achieve 50% improvement quickly. A Tabu Search (TS) technique and a Genetic Algorithm approach are also implemented to further enhance solution quality. Results obtained indicate that both Tabu Search and Genetic Algorithms can enhance solution for FPGA placement and produce on average 74% and 20% improvement in reasonable time.
展开▼
