A Memetic Algorithm Implementation On a FPGA For VLSI Circuit Partitioning
By Stephen Coe, August 2004
Abstract:
During the last decade, the complexity and size of circuits have
been rapidly increasing, placing a stressing demand on industry
for faster and more efficient CAD tools for VLSI design. One major
problem is the computational requirements for optimizing the place
and route operations of a VLSI Circuit. Thus, this research
investigates the feasibility of using Reconfigurable Computing
platforms to improve the performance of CAD optimization
algorithms for the VLSI circuit partition problem. The proposed
Reconfigurable Computing Genetic Algorithm architecture achieved a
5x speedup over conventional software implementation while
maintaining 85\% solution quality. Furthermore, a Reconfigurable
computing based Memetic Algorithm improved upon this solution
while using a fraction of the execution time required by the
conventional software based approaches.
This research also investigates the tradeoff of developing
Reconfigurable computing solutions using a high-level language
(Handel-C) vs a low-level language (VHDL). Implementing a Local
Search algorithm in VHDL produced speedups of nearly twice that of
the Handel-C implementation while requiring five times more
development time. This speedup is a result of optimizing the VHDL
architecture to target the specific FPGA hardware.
