Binary particle swarm optimization (BPSO) based state assignment for area minimization of sequential circuits

• State assignment for finite state machines is one of the main optimization problems in the synthesis of sequential circuits.
• PSO is a non-deterministic heuristic that optimizes a problem by having a population of candidate solutions called particles.
• An improved binary PSO algorithm is proposed and its effectiveness is demonstrated in solving the state assignment problem.
• One of the objective of state assignment problem is to synthesize sequential circuits targeting area optimization.
• Better results are achieved comparing to BPSO variants, genetic algorithm, simulated evolution and deterministic algorithms.

State assignment (SA) for finite state machines (FSMs) is one of the main optimization problems in the synthesis of sequential circuits. It determines the complexity of its combinational circuit and thus area, delay, testability and power dissipation of its implementation. Particle swarm optimization (PSO) is a non-deterministic heuristic that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. PSO optimizes a problem by having a population of candidate solutions called particles, and moving them around in the search-space according to a simple mathematical formulae. In this paper, we propose an improved binary particle swarm optimization (BPSO) algorithm and demonstrate its effectiveness in solving the state assignment problem in sequential circuit synthesis targeting area optimization. It will be an evident that the proposed BPSO algorithm overcomes the drawbacks of the original BPSO algorithm. Experimental results demonstrate the effectiveness of the proposed BPSO algorithm in comparison to other BPSO variants reported in the literature and in comparison to Genetic Algorithm (GA), Simulated Evolution (SimE) and deterministic algorithms like Jedi and Nova.

Figure optionsDownload as PowerPoint slide