181
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020
MEMETIC ALGORITHM BASED ON HILL CLIMBING
ALGORITHM FOR IC PARTITIONING
K. Jeya Prakash
Assistant Professor, ECE Department,
Kalasalingam Academy of Research and Education
(Deemed to be University).
Krishnankoil, (India).
E-mail: k.jeyaprakash@klu.ac.in ORCID: https://orcid.org/0000-0001-7493-1914
P. Sivakumar
Professor, ECE Department,
Kalasalingam Academy of Research and Education
(Deemed to be University).
Krishnankoil, (India).
E-mail: siva@klu.ac.in ORCID: https://orcid.org/0000-0003-1328-8093
Recepción:
05/12/2019
Aceptación:
17/12/2019
Publicación:
23/03/2020
Citación sugerida:
Jeya Prakash, K., y Sivakumar, P. (2020). Mememtic algorithm based on hill climbing algorithm for IC
partitioning. 3C Tecnología. Glosas de innovación aplicadas a la pyme. Edición Especial, Marzo 2020, 181-193.
http://doi.org/10.17993/3ctecno.2020.specialissue4.181-193
Suggested citation:
Jeya Prakash, K., & Sivakumar, P. (2020). Mememtic algorithm based on hill climbing algorithm for
IC partitioning. 3C Tecnología. Glosas de innovación aplicadas a la pyme. Edición Especial, Marzo 2020, 181-
193. http://doi.org/10.17993/3ctecno.2020.specialissue4.181-193
182 http://doi.org/10.17993/3ctecno.2020.specialissue4.181-193
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020
ABSTRACT
To reduce the premature convergence of the optimization problem, the genetic algorithm
with local search called “memetic algorithm” is introduced. The proposed memetic
algorithm can partition a complex circuit design into a few sub-circuits. The aim of this
paper is to reduce the interconnects between the partitioned blocks. The experimental
results show that the method is eective for solving the given input and to nd the minimum
cut size. Applying memetic algorithm like Hill Climbing algorithm for 3D IC partitioning
is the novelty in this work.
KEYWORDS
Memetic algorithm, Genetic algorithm, Circuit partition, Cut size.
183 http://doi.org/10.17993/3ctecno.2020.specialissue4.181-193
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020
1. INTRODUCTION
Very-large-scale integration (VLSI) is a process which integrates many transistors into a
single chip called “Integrated Circuit”. An electronic circuit requires many sub circuits like
CPU, ROM, RAM and other glue logic. VLSI made it possible to include all of them into
one chip. Designers depend on Computer Aided Design (CAD) tools to provide a higher
level of idea to reduce the complexity of circuits.
The phrase related with the mission of automatically designing a circuit by means of CAD
tools is known as Electronic Design Automation (EDA). In VLSI design, physical design
is one of the steps in the standard design cycle which trails the circuit design as shown in
Figure 1. At this step, circuit representation of the devices and interconnects of the design
are changed into geometric representations of shapes which, at the point when produced in
the relating layers of materials, will guarantee the essential functioning of the components.
This geometric representation is called IC layout.
Circuit partitioning is a vital step which ensures the interactions between circuit blocks is
minimal. The minimal inter-partition communication may lead to have a few numbers of
wires between them. This in turn leads to small interconnect delay and low power.
Figure 1. Design ow of VLSI.
184 http://doi.org/10.17993/3ctecno.2020.specialissue4.181-193
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020
Hence, the main goal is partitioning a circuit into multiple blocks with an attempt to lessen
the cut-size.
2. PROBLEM FORMULATION
In circuit partitioning problem, the logic representation of the circuit, modules and
interconnection between modules are represented as geometric representation, vertices (V)
and edges (E) of a graph (G) respectively. The vertices and edges of G may be weighted to
reveal module area or signicance of an interconnection. The circuit partitioning has the
following goals to make the IC compact:
Minimum Cut: Given G = (V, E), partition V into disjoint subsets X and Y such that e (X,
Y), the number of edges in
, is minimized.
Minimum-Width Bisection: Given G = (V, E), partition V into disjoint subsets X and
Y, with |X| = |Y|, such that e (X, Y) is minimalized. Since this leads to equal number of
modules in each partition, it is needed. The more general partitioning problem is when k
disjoint subsets are formed.
Given two n*n matrix X=(x
ij
) and Y=(y
ij
), where usually x
ij
, y
ij
>0, and the objective is:
where Sn is set of all probable permutation of (1, 2……. n). Sometimes there is an accessory
n*n matrix Z = (z
ij
), then the equation becomes,
x
ij
represents the ow from the module i to the module j,
y
ij
represents the distance from the location i to the location j,
z
ij
represents the cost of the placing module i to the location j.
185 http://doi.org/10.17993/3ctecno.2020.specialissue4.181-193
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020
3. MEMETIC ALGORITHM
In evolutionary computation, the Memetic algorithms (MA) play a vital role in growing
areas of research. The word MA is now broadly used as a synergy of any global search
procedure with local enhancement procedures for problem search.
Global Search
(Generic Algorithm)
Local Search
(Hill Climbing Algorithm)
Figure 2. Memetic Algorithm.
The memetic algorithm, which is shown in Figure 2 is utilized to reduce the interconnections,
i.e. min-cut problem of circuit partitioning based on a balanced limitation.
3.1. GENETIC ALGORITHM
A global exploration procedure to solve optimization problem, which evolves toward better
solution, known as Genetic algorithm, is shown in Figure 3.
ENCODING
FITNESS EVALUATION SIMULATION
STOP
YES
RESULTS
NO
SELECTION
CROSSOVER
MUTATION
Figure 3. Genetic Algorithm- Flow Chart.
Encoding: The parameter like wire-length are represented as xed length binary strings.
Initialization: Refers to generation of population of ‘n’ chromosomes randomly. Here,
the population is the tentative solution for the problem. The population is here initialized
by Roulette wheel Selection or Tournament methods.
186 http://doi.org/10.17993/3ctecno.2020.specialissue4.181-193
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020
Fitness Evaluation: Evaluate the tness f(x) of each chromosome x in the populace
Selection: In this process, the better t two strings are selected as two parent chromosomes
to create the ospring.
Crossover: Two parent qualities are mixed to get new children so that solution
characteristics get changed. A probability is associated with this.
Mutation: With a mutation probability mutate new ospring to introduce new properties.
Termination: The process continues and replaces the existing solution until the termination
condition is satised.
Encode solution space
Set population_size,
maximum_genertions, generation=0
Set crossover_rate, mutation_rate;
initialize populace
while maximum_generation ≥ genera-
tion evaluate tness
for (i =1 to populace size)
select (mp1, mp2)
if (rnd (0,1) ≤ cross_rate)
child = cross (mp1, mp2)
if (rnd (0,1) ≤ mutation_rate)
child = mutation ();
repari child if necessary
end for
Add ospring to new generation
Generation = generation + 1
End while
return best chromosomes
Figure 4. Pseudo code for Genetic Algorithm.
The algorithm takes specic paces, Initialization, Evaluation, Selection, Crossover, and
Mutation. Every time, each person’s tness in the populace is evaluated. The tness is
typically the assessment of the target work in the issue being tackled. The best individual
is preferred arbitrarily from the present populace and every individual’s chromosomes and
qualities are altered to make the ttest. The new populace is then used in the algorithm.
The algorithm will end after predened number of populaces are produced or achieved the
optimal tness function.
187 http://doi.org/10.17993/3ctecno.2020.specialissue4.181-193
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020
3.2. HILL CLIMBING ALGORITHM
As stated in Lin and Zhu (2014), the GA is not t for nding solutions which have closed
to optimal solutions. Hence, usually GA is combined with local search algorithms like
Hill climbing algorithm called Memetic Algorithms are used. In this paper we proposed
a Memetic algorithm based on Genetic Algorithm and Hill climbing algorithm for circuit
partitioning. Hill climbing algorithm is one of the algorithms to nd the best state in
optimization problems with less conditions than other techniques.
The genetic algorithm is not appropriate for ne-tuning the solution which are close
to optimal. So, for ne tuning separate algorithm (local hill climbing algorithm) is used
with genetic algorithm called Memetic. They have demonstrated that they are requests
of greatness speedier than customary hereditary Algorithms for some issue areas. In a
memetic algorithm, the population is initialized randomly or using a heuristic. Then, every
individual makes nearby search to enhance its wellness. To frame another populace for the
following group, higher quality solutions are chosen. The selection stage is similar stage.
With two individuals selected, their chromosomes are joined to produce new individuals.
While (termination condition is not satised) do
New solution ⟵ neighbors (best solution);
If new solution is better than actual solution, then
Best solution ⟵ actual solution
End if
End while
Figure 5. Pseudo Code for Hill climbing search algorithm.
The later are boosted utilizing a neighbourhood seek method. The role is to trace the
local best more prociently than the genetic algorithm. The hill climbing search algorithm
proposed as a local search procedure shown in Figure 5. It is just a loop that ceaselessly goes
toward expanding quality.
4. RESULTS
The parameter settings of iteration are varied, and the cut size is calculated. The best cost
for various iterations up to 20 iterations as example, is taken in partitioning ami33 is shown
in gures below:
188 http://doi.org/10.17993/3ctecno.2020.specialissue4.181-193
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020
Figure 6. Iterations Vs. Best cost (for MaxIt=5).
Figure 7. Iterations Vs. Best cost (for MaxIt=10).
Figure 8. Iterations Vs. Best cost (for MaxIt=15).
189 http://doi.org/10.17993/3ctecno.2020.specialissue4.181-193
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020
Figure 9. Iterations Vs. Best cost (for MaxIt=20).
The tabulation for memetic algorithm of min cut, max cut and average cut is shown in the
Table 1.
Table 1. Min cut, max cut and average cut of partitioning.
Iterations Min cut Max cut Average cut Memetic Mean (*106)
5 32.06 576.02 29.03 5.26
10 32.38 544.03 27.2 5.26
15 33.5 544.08 28.29 5.44
20 32.40 320.00 19.20 5.44
The results clearly show that the proposed work results in one of the best ways to partition
a 3D IC.
5. CONCLUSION
The combination of genetic algorithm with local hill climbing algorithm forms a memetic
algorithm which is proposed to circuit partitioning yields a major development in result
quality. The experimental result shows that the algorithm provides good and consistent
result. This result shows the exibility of the memetic methodology in solving the problem
of VLSI circuit netlist partitioning.
190 http://doi.org/10.17993/3ctecno.2020.specialissue4.181-193
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020
ACKNOWLEDGEMENT
Authors want to express their gratitude to ECE Department at Kalasalingam Academy of
Research and Education for allowing them to utilize the computing facilities in DST-FIST
sponsored VLSI Research Laboratory.
191 http://doi.org/10.17993/3ctecno.2020.specialissue4.181-193
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020
REFERENCES
Ababei, C., Selvakkumaran, N., Bazargan, K., & Karypis, G. (2002). Multi-objective
circuit partitioning for cutsize and path-based delay minimization. Proceedings of the
2002 IEEE/ACM International Conference on Computer-Aided Design - ICCAD 02, 181–185.
https://doi.org/10.1145/774572.774599
Alpert, C. J. (1998). The ISPD98 circuit benchmark suite. Proceedings of the 1998 International
Symposium on Physical Design - ISPD 98. https://doi.org/10.1145/274535.274546
Areibi, S., & Yang, Z. (2004). Eective Memetic Algorithms for VLSI Design = Genetic
Algorithms Local Search Multi-Level Clustering. Evolutionary Computation, 12(3), 327–
353. https://doi.org/10.1162/1063656041774947
Du, H. Q., & Qi, J. B. (2010). Application of a Hybrid Algorithm Based on Genetic
Algorithm and Hill-Climbing Algorithm to Tool Path Optimization in CNC
Machining. Advanced Materials Research, 102-104, 681–685. https://doi.org/10.4028/
www.scientic.net/amr.102-104.681
Gill, S. S., Chandel, R., & Chandel, A. (2010). Genetic Algorithm Based Approach to
Circuit Partitioning. International Journal of Computer and Electrical Engineering, 196–202.
https://doi.org/10.7763/ijcee.2010.v2.136
Lin, G., & Zhu, W. (2014). An Ecient Memetic Algorithm for theMax-Bisection Problem.
IEEE Transactions on Computers, 63(6), 1365–1376. https://doi.org/10.1109/tc.2013.7
Marichelvam, M. K., Prabaharan, T., & Yang, X. S. (2014). A Discrete Firey
Algorithm for the Multi-Objective Hybrid Flowshop Scheduling Problems. IEEE
Transactions on Evolutionary Computation, 18(2), 301–305. https://doi.org/10.1109/
tevc.2013.2240304
Nagarajan, K. (2018). A Predictive Hill Climbing Algorithm for Real Valued multi-
Variable Optimization Problem like PID Tuning. International Journal of Machine
Learning and Computing, 8(1), 14–19. https://doi.org/10.18178/ijmlc.2018.8.1.656
192 http://doi.org/10.17993/3ctecno.2020.specialissue4.181-193
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020
Roy, S., & Sarma, S. S. (2012). Improvement of the quality of VLSI circuit partitioning
problem using Genetic algorithm. Journal of Global Research in Computer Science, 3(12),
18–22.
Sharma, P. K., & Kaur, M. (2014). A Discrete FireFly Algorithm for VLSI Circuit
Partitioning. 2014 International Conference on Electronics and Communication Systems
(ICECS). https://doi.org/10.1109/ecs.2014.6892764
Subbaraj, P., Sivasundari, K., & Kumar, P. (2007). An eective memetic algorithm
for VLSI partitioning problem. IET-UK International Conference on Information and
Communication Technology in Electrical Sciences (ICTES 2007), 667–670. https://doi.
org/10.1049/ic:20070696
