ISSN ONLINE(2320-9801) PRINT (2320-9798)

Performance of Hybrid Genetic Algorithm on Digital Circuit Area Minimization

Rajine Swetha R1, DR Sumithra devi KA2
  1. Assistant Professor, Department of Electronics and Instrumentation, RVCE, Bangalore, India
  2. Director & Professor, RVCE, Bangalore, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering


At present, evolution based Genetic algorithm is used for optimization of the digital circuits. In physical design backend of Chip designing, these algorithms play a major role in optimizing the various design constraints. The current age design automation tools provide the designer with a predefined optimized circuits without further choice in terms of backend algorithms. This paper explores a possible combination of move based algorithm of Fidducia Matthyses effectively used with minimum distance based genetic algorithm. This approach ensures the designer of maximum possible optimization of the circuit possible. The aim of this paper is to apply FM-Mincut hybrid algorithm on bench mark circuits and discuss the effect of it on the area of the design. This approach provides a scope to unify the stages of partitioning and placement and optimize the physical design process and floor area of the application.


FM based hybrid algorithm, area reduction, digital VLSI circuit partitioning algorithm


Partitioning is the first design step towards the production and fabrication of a circuit design. The CAD plays a vital role in modeling the algorithms with minimal effort and efficient logic design optimization [1].The application logic is mapped as a graph and the connectivity of all the elements of the design are translated to non directed graph. Then the soft and hard blocks are decided. The choice of the design style as full custom or semi-custom ASICs depends on the intended functionality of the chip, time to market and the total number of chips to be manufactured.
The Design styles can be seen as to cater to the differing needs of the application development purpose. The full custom provides compact layouts for high performance designs and FPGA is completely prefabricated and requires no user specific fabrication steps [2]. This necessitates the need for unification of these consecutive and distinctly irreversible stages of the physical design. VLSI physical design involves the division of a circuit into smaller parts for ease of design and layout [2,3]. The main objectives of circuit partitioning include minimization of number of interconnections between the partitions, minimization of delay due to interconnections between partitions, and ratio-cut minimization [4, 12]. The circuit under consideration is considered as a graph.
A sample graph is shown in the Fig [1].The graph is the representation of the test circuit of ACM /SIGDA [15] and has 7 gates. Its a small size test circuit. The graph has all the circuit components expressed as nodes and the connections as edges of the graph. The circuit under consideration has 5 inputs and 2 outputs. The inputs and the outputs are connected to the gates. Partition is also referred to as a cut [13, 14]. The cost of partitioning is called the cut size [6,7] which is the number of hyper edges crossing the cut. The FM algorithm has no basic requirement that the two Partitions be of same size. So when there is swapping done between the partition 1 and 2.The gain of each swap is calculated in terms of number of nets crossing the partitions.


In the past decade there are many works emphasizing the need of miniaturization. The partitioning stage forms the base of the physical design process. In the earliest work on graph theory, nodes have been modeled and partitioned using algorithms to minimize the distance and form a cluster .These algorithms are move based and the earliest algorithm focused on mutual swapping of nodes between the partitions [2,8]. This approach did not work for the partitions with odd number of nodes and the partitions of different sizes were accommodated in the further work done by Fidduccia and Mathysses [3, 9].The consolidated survey on the importance of area parameter minimization of VLSI applications [4,5] suggests that, there is ample scope of algorithmic choices for reducing the design area than the default optimized design made available by the CAD tool.


A. Design Considerations:
• Initial circuit chosen is to be converted to directed graph.
• Difference in the number of inward connections to outward connections is calculated as gain.
• Keeping track of previous area.
• Considered all possible partitioning and making gain nearing 1.
B. Description of the Proposed Algorithm:
Aim of the proposed algorithm is to reduce the area of the VLSI circuit through hybrid genetic algorithm approach during CAD design of the circuit. The proposed algorithm is consists of four main steps.
Step 1: Calculating the area of the VLSI circuit before applying the algorithms
Step 2: Convert the circuit to nodes and applying the algorithms.
Step 3: Calculate the area for the optimized circuit for the partitioning value.
Step 4: Change the partitioning value and obtain the area reductions for the optimized circuit.


Step 1: Convert the circuit to nodes and map the adjacency matrix.
Step 2: Implement the VLSI circuit and calculate the area parameter.
Step 3: Feed it as input to the FM +mincut +GA algorithm in C language.
Step 4: Check the below condition for convergence.
If ( mindis1 = mindis)
the area is optimal so no swapping of the nodes between the partitions
swap the nodes and calculate distance
Step 5: Implement the new optimized VLSI circuit and calculate the area parameter.
Step 6: Go to step 3 with different partitioning value for same circuit.
Step 8: End.


In this paper, to circuit C17 netlist, the move based algorithm of Fidducia Matthyses [FM] is applied in C Language, then the mincut algorithm merged GA [10,11] is applied to the partitioning result. This step uses the partition stage output to perform the optimization. The effect of the hybridization on the physical parameter of area of the circuit is calculated from the synthesis report of the EDA tools. The methodology consists of obtaining the netlist from the graph, then applying the algorithms and optimizing the partitioning result. Using Cadence EDA tool area report is generated before and after application of this algorithm, to assess the efficiency of the algorithm.
The effect of FM and mincut algorithms on C17 and C1908 test circuits is shown in Fig [2].The effect on the area of the application is seen as about 30% on an average. For various partitions the area optimization also varies. The criteria for the genetic algorithm to converge, is defined by the mincut algorithm. It is also observed that the size of the circuit does not affect the performance of the algorithm, but the number of partitions vary the optimization outputs.


The implementation of hybrid genetic algorithm based FM-Mincut algorithm on a series of digital circuits and benchmarks, suggest that there is a lot of advantages in unifying the partitioning and placement stages. The area optimization can be more accurate before further physical design stages. The optimization of the area can be obtained by employing greedy Heuristic algorithms to the same level of physical design in continuation with hybrid algorithm discussed in the paper. This approach may provide further area optimization to the circuit. The applications of such approach, has greater impact on designs of biomedical circuits and wearable sensors where the size of the application is a major design constraint.

Figures at a glance

Figure 1 Figure 2
Figure 1 Figure 2