optimal solution for VLSI circuit partitioning in physical design using DPSO

              Circuits partitioning assumes a vital part in designing very large scale integration (VLSI) chips. Circuit partitioning is a critical step in the front end design. The interest in finding an optimal solution for partitioning in VLSI circuits has been a hot issue now days. In VLSI circuit partitioning, the issue of getting a minimum cut, less interconnects, low power, minimum delay and less area is included. The use of Evolutionary algorithms is increased to solve the above mentioned NP complete problems. This blog  investigates an overview of getting a minimum cut using, a Discrete Particle Swarm Optimization (DPSO) algorithm .

  

    The DPSO algorithm proposed a new discrete position updating method of particles  and the operators of evolutionary algorithm for reference: the velocity is changed by mutation operator and influence of individual optimal solution and global optimal solution on particles by crossover operator.

Encoding-  

     The DPSO algorithm uses the method of integer encoding for circuit partitioning. Considering the circuit which contains n modules and m nets, initially, number every module with 1, 2,…, n; a particle represents a feasible solution in circuit partitioning, the position of particles at a certain time is a full permutation of n modules.

Evalution function-

    DPSO algorithm takes minimizing the interconnections among the sub-circuits as a unique objective; it uses the objective of partitioning as the evaluation function directly. In evaluation function k is the number of subsets (k=2 in this paper), lab denotes the number of the interconnections between subset A and subset B.

Conclusion-

DPSO was easy to implement and can be extended for circuit multi-partitioning problem. Experimental results shows that DPSO algorithm has better performance of global searching and can obtain better partitioning results compared with the conventional genetic algorithm. The future work can focus on the partitioning problem with multi-objective by using the DPSO algorithm.