Discrete Multi Objective Particle Swarm Optimization Algorithm for FPGA Placement (RESEARCH NOTE)

Abstract

Placement process is one of the vital stages in physical design. In this stage, modules and elements of circuit are placed in distinct locations according to optimization basis. So that, each placement process tries to influence on one or more optimization factor. In the other hand, it can be told unequivocally that FPGA is one of the most important and applicable devices in our electronic world. So, it is vital to spend time to better learning its structure. VLSI science looks for new techniques for minimizing expense of FPGA in order to gain better performance. Diverse algorithms are used for running FPGA placement procedures. It is known that particle swarm optimization (PSO) is one of the practical evolutionary algorithms for this kind of applications. So this algorithm is used for solving placement problem. In this work, a novel method for optimized FPGA placement has been used. According to this process, the goal is to optimize two objectives defined as wire length and overlap removal functions. Consequently, we are forced to use multi-objective particle swarm optimization (MOPSO) in the algorithm. Structure of MOPSO is in a way that introduces set of answers, we have tried to find a unique answer with minimum overlap. This is worth noting that discrete nature of FPGA blocks forced us to use a discrete version of PSO. In fact, we need a combination of multi-objective PSO and discrete PSO for achieving our goals in optimization process. Tested results on some of FPGA benchmark (MCNC benchmark) are shown in “experimental results” section, compared with popular method “VPR”. These results show that proper selection of FPGA’s size and reasonable number of blocks can get us good response.