Constructive/Iterative Based Techniques For FPGA Placement
By Xiaojun Bao, August 2004
Abstract:
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 research 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.
