A survey on an optimal solution for VLSI circuit partitioning in physical design using DPSO & DFFA algorithms

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 paper investigates an overview of getting a minimum cut using, a Discrete Particle Swarm Optimization (DPSO) algorithm and a swarm based heuristic approach called as Discrete Fire Fly Algorithm(DFFA).

I. Introduction

In the development of modern fabrication technology, the complexity of VLSI circuits design increases drastically. In order to decrease the complexity of design in VLSI an effective method is used in the circuit partitioning rule. The specific implementation is splitting the complex circuit into several sub-circuits so that each sub-circuit can be designed independently. Due to the substantial advances in very large-scale integration technology, integrated circuits have become more and more complicated. This creates a great challenge for very large-scale-integrated (VLSI) physical design automation. The advancement in VLSI semiconductor technology has led to a phenomenal development in electronic systems, with the reduction in device sizes, a very large number of transistors can fit onto a single chip. VLSI circuit partitioning has various objectives. Two main objectives of VLSI circuit partitioning are the minimization of cutset and minimizing the number of interconnections. Optimizing one design aspect may lead to performance degradation in others. The marketing window has become very narrow such that delivering the product to market in the right time is a company survival issue. Physical design has several stages. First of them is circuit partitioning whose results will be used directly in placement, routine and other stages of physical design. Therefore, circuit partitioning is a very important stage in the VLSI physical design. Circuit partitioning has been proved to be NP-hard [1], and hence, it is very difficult to get the optimal solution. Numerous optimization algorithms have been applied to solve partitioning problem. According to the optimization strategy, these techniques are mainly classified into clustering algorithms [2], [3] and iterative improvement algorithms which include simulated annealing procedure [4], genetic algorithm [5]-[8], Tabu Search heuristic algorithm [9] and so on. However, these algorithms have shortages of low efficiency and local optimum. Moreover, iterative improvement algorithms have the problem of slow convergence. Aiming at the problem concerned above, this paper provides a survey of the problem of circuit partitioning by using Discrete Particle Swarm Optimization (PSO) algorithm and Discrete Fire Fly Algorithm (DFFA). As a population-based evolutionary algorithm, DPSO was introduced by Eberhart and Kennedy in [10]. It is inspired by the flocking behaviour of birds, in which the flight of each individual is influenced by its own experience and its companion. DPSO algorithm has been proved to be a global optimization technique. Because PSO has many advantages, such as fast convergence, simple model and easy to be implemented [11], it has been successfully applied to many fields. DFFA is a popular heuristic algorithm for solving optimization problems. DFFA was proposed by Xin-She Yang(at Cambridge University) which was inspired by the behaviour of fire flies.