Analogous Computation On Hybrid Genetic Algorithm Biology Essay

Published:

Abstract- Due to rapid advances in VLSI design technology during the last decade, the complexity and size of circuits have been rapidly increasing, placing a demand on industry for faster and more efficient CAD tools. Physical design is a process of converting the physical description into geometric description. Physical design process is subdivided into four problems: 1.Partitioning, 2. Floor planning 3. Placement and 4.Routing. Placement phase determines the positions of the cells. Placement constrains are wire-length, area of the die, power minimization and delay. For the area and wire length optimization a modern placer need to handle the large-scale design with millions of object. This thesis work aims to develop an efficient and low time complexity algorithms for placement. This can be achieved by the use of a problem specific genotype encoding, and hybrid, knowledge based techniques, which support the algorithm during the creation of the initial individuals and the optimization process. In this paper a novel hybrid genetic algorithm, which is used to solve standard cell placement problem is presented. These techniques are applied to the multithread of the VLSI cell placement problem where the objectives are to reduce power dissipation and wire length while improving performance (delay).

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

Index Terms- VLSI design, physical design, placement, standard cell, multithread

INTRODUCTION

IN the paste thirty years, VLSI-CAD (Computer-Aided Design of Very Large-Scale Integrated circuits) has been an enabling force behind the exponential growth of the performance and capacity of integrated circuits[6]. The layout of integrated circuits on chips is one of many interrelated complex tasks in VLSI circuit design. In the combinatorial sense, the layout problem is a constrained optimization problem.

The main objectives of the placement design process are to minimize the total chip area and the total estimated wire length for all the nets.

Optimization of the chip area usage can fit more functionality into a given chip area. Optimization of the total estimated wire length can reduce the capacitive delays associated with longer nets and speed up the operation of the chip. Thus, the placement design process has a pronounced affect on the final chip performance. Since module placement is an NP-hard problem, therefore, it cannot be solved exactly in polynomial time [5, 7]. Trying to get an exact solution by evaluating every possible placement to determine the best one would take time proportional to the factorial of the number of modules. Consequently, it is impos­sible to use this method for circuits with any reasonable number of modules. To search through a large number of candidate placement configurations efficiently, a heuristic algorithm must be used [2].

The traditional approach in placement is to construct a global placement (initial placement) by using con­structive placement heuristic algorithms. A detailed placement follows to improve the initial placement. A modification is usually accepted if a reduction in cost occurs, otherwise it is rejected.

Global placement produces a complete placement from a partial or non-existent placement. Since partitioning-based methods and numerical optimization methods do not di­rectly attempt to minimize wire length, the solution obtained by these methods is sub-optimal in terms of wire length.

Problem Formulation

A mathematical formulation of an approximation to the standard cell placement problem is now presented. Usually, a circuit is represented by a hypergraph G (V, E), where the vertex set V = {v1, v2, v3, …,vn} represent the nodes of the hypergraph (set of cells to be placed), and E = {e1, e2, e3, …,en} represents the set of edges of the hypergraph (set of nets connecting the cells). The two dimensional placement regions are represented as an array of legal placement locations. The hypergraph is transformed into a graph (a hypergraph with all hyperedge sizes equal to 2) via clique model for each net. Each edge ej is an order pair of vertices with a non-negative weight Wij assigned to it. The placement task seeks to assign all cells of the circuit to legal locations such that cells do not overlap. Each cell i is assigned a location on the XY-plane. The cost of an edge connecting two cells i and j , with locations (xi , yj) and (xi, yj) is computed as the product of the squared l2 norm of the difference vector (xi - xj ) ( yi - yj ) and the weight of the connecting edge wij The total cost, denoted Φ(x,y) can then be given as the sum of the cost over all edges; i.e:

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

Wire Length Estimation

It is computationally expensive to determine the exact total wire length for all the nets at the placement stage and therefore, the total wire length is approximated during placement. To make a good estimate of the wire length, we should consider the way in which routing is actually done by routing tools. Almost all automatic routing tools use Manhattan geometry; that is, only horizontal and vertical lines are used to connect any two points. Further, two layers are used; only horizontal lines are allowed in one layer and only vertical lines in the other.

An efficient and commonly used method to estimate the wire length is the semi-perimeter method. The wire length in this method is approximated by half the perimeter of the smallest bounding rectangle enclosing all the pins. For Manhattan wiring, this method gives the exact wire length for all two-terminal and three-terminal nets, provided that the routing does not overshoot the bounding rectangle. For nets with more pins and more zigzag connections, the semi-perimeter wire length will generally be less than the actual wire length. Moreover, this method provides the best estimate for the most efficient wiring scheme, the Steiner tree. The error will be larger for minimal spanning trees and still larger for chain connections. In practical circuits, however, two and three terminal nets are most common. Thus, the semi-perimeter wire length is considered to be a good estimate.

Techniques Used

Genetic Based Placement

Genetic algorithms are powerful optimization techniques that have been successful in solving many hard combinatorial optimization problems [12]. The power of GA's comes from the fact that the technique is robust, and can deal successfully with a wide range of problem areas, including those which are difficult for other methods to solve [3]. It works by simulating the natural process of evolution as a means of progressing toward the optimum. The algorithm starts with an initial set of random solutions, called population. A solution string (called a chromosome) is encoded as a binary or integer string. During each iteration, called a generation, each individual in the current population is evaluated and assigned a fitness value through a scoring function. Based on this fitness, individuals are selected for reproduction and their chance for selection increases with their fitness. A number of genetic operators are then applied to the parents to generate new individuals, called off springs. The commonly used genetic operators are crossover, mutation, and inversion. A new generation is formed by selecting the individuals from the parents and offspring according to their fitness so that the population size can be kept constant. Over many generations, the fitter individuals tend to pre-dominate the population while the less fit individuals tend to die-off and eventually one super-fit individual evolve.

Genetic Algorithm

1. Encode Solution Space

2. set pop size, max_gen, gen=0;

set crossover_rate, mutation_rate;

3. Generate initial population randomly

4. Evaluvate the initial population

5. While (gen <= max_gen)

For (i=1 to pop size/2)

Select parents (mate1, mate2);

if(random(0,1)<= crossover_rate)

child = Do crossover (mate1, mate2);

if(random(0,1)<= mutation_rate)

mutation (child);

evaluate (child);

End For

Replacement ( );

gen = gen +1;

End While

6. Return best solution in current population

Fig. 1. Pesudocode for genetic algorithm

Figure 1 shows a Genetic Algorithm implementation for standard cell placement. The algorithm starts with an initial set of random placement solutions, which are called individuals in a population. These solutions are coded as strings, called chromosomes. A string represents a solution to the placement problem. Next, the initial population will be evaluated, using the placement-specific fitness function. Crossover occurs by exchanging part of the parents' structure into two new individuals called offspring. Each offspring inherits part features of their parents. Following crossover, the offspring is mutated with low probability.

String Encoding

In this genetic-based placement algorithm, a string is represented by a set of alleles (the number alleles equal to the number of cells). Each allele indicates the index, the x-coordinates and row number of the cell.

Scoring Function

Each individual is evaluated to determine its fitness through a scoring function. The scoring function F is the reciprocal of the total HPWL for all the nets.

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

Where HPWL is the sum of the half perimeter of the smallest bounding rectangle for each net. HPWLi is the estimate wire length of net i and n is the number of nets. In the implementation, cell overlaps are removed and row lengths are adjusted before evaluating the chromosome. One reason of doing so is due to the fact that removing the overlaps after every generation not only gives the algorithm a more accurate picture of the wire length but also gives the algorithm repeated chances to optimize the circuit after it has been perturbed by overlap removal. Therefore the row length control and overlap penalty are not considered in the scoring function.

Initial Population Construction

For each configuration in the initial population, the x-coordinate and row numbers of cells are determined randomly. This kind of constructor can diversify the initial solutions but also tend to have a slower rate of convergence. Thus, some placement solutions produced by Cluster Seed method are injected into the initial population to increase the convergence rate.

Selection Function

In the selection function, two methods are considered.

1) Roulette Wheel: It simply choose the individuals in a statistical fashion based on their relative (that is percentage) fitness values. Obviously, the best individuals get more copies and the worst die off.

2) Binary Tournament: In this method, two individuals are taken at random and the individuals with higher fitness value are selected as one parent. The two individuals are immediately replaced into the population for the next selection operation.

Crossover Operator

The Traditional crossover operator used in GA may produce infeasible solutions for the standard cell placement problem, therefore a crossover operator called Order crossover is considered.

Partially matched crossover (PMX) may be viewed as a crossover of permutations, that guarantees that all positions are found exactly once in each offspring, i.e. both offspring receive a full complement of genes, followed by the corresponding filling in of alleles from their parents.

Mutation Operator

Each offspring is mutated with a probability equal to the mutation rate. The muta­tion operator mutates an individual by interchanging randomly selected pair of cells without changing the x-coordinate and row number.

Hybrid Simulated Annealing

In this work we have hybridized the genetic algorithm template with the SA method. The SA method is impregnated within GA, between the crossover and mutation operations, to improve all the solutions obtained after the crossover operation and before subjected to mutation operation.

Simulated Annealing

SA is very simple technique for State Space Search Problem. It can start from any state. And it is always move to a neighbor with the min cost (assume minimization problem). It can stop when all neighbors have a higher cost than the current state.

Multithreading

Multithreading (MT) is a technique that allows one program to do multiple tasks concurrently. The basic concept of multithreaded programming has existed in research and development labs for several decades. Co-routine systems such as Concurrent Pascal and InterLisp's Spaghetti stacks were in use in the mid-70s and dealt with many of the same issues. Ada's tasks are a language based construct that maps directly onto threads (so directly, in fact, that current Ada compilers implement tasks with threads). Burroughs shipped a commercial mainframe OS with co-routinestyle threads as early as 1960. The threading models we describe are strictly software models that can be implemented on any general-purpose hardware. Much research is directed toward creating better hardware that would be uniquely suited for threaded programming.

Fig. 2. Multithreading with genetic algorithm

Experimental Results

In this work the proposed algorithm designed to get a nearer to optimal solution for the VLSI placement problem considered in this work is coded in C++ and experiments were conducted in a Sun Server PC with 3.20 GHz Dual Core Processor. The outcome of results obtained for popular benchmark circuits ISPD02 was compared with that of the standard Genetic Algorithm methodology which is also coded in C++ and run on the same machine.

Tournament selection is used for reproduction. Single point crossover is used in the crossover operation. The parameters are fixed by conducting trials on various population sizes, crossover probabilities, mutation probabilities and the satisfactory convergent speed exploring scope of the proposed search techniques. Population size = 20: Pc = 0.9; Pm = 0.01

Comparison and Results

For all the bench mark circuit taken in this work, the proposed algorithm MHSA is able to outperform the standard Genetic algorithm both in terms of number of iterations required to reach a nearer to optimal solution.

Fig. 3. Performance comparison between Iteration Vs Wire length for ibm01

Conclusion

In this paper, we have presented several global techniques for circuit placement. The performance of the Fast placement algorithm was compared with the Multithreaded Hybrid genetic Algorithm for VLSI placement problem. Due to the ability of the Simulated Annealing method it finds the minimized wire length in fewer generations. We applied these algorithms to ISPD02 benchmark circuits from the results it is clear that MHGA outperforms than Fast Placement method.

TABLE I

Comparison Between Fastplace And Mhga

Circuit

#Nets

#Pins

HPWL (x10e6)

Run Time (Sec)

Fast

Place

MHGA

Fast

Place

MHGA

ibm01

14111

50566

1.86

1.81

3m 59s

3m 50s

ibm02

19584

81199

4.06

4.00

7m 15s

7m 08s

ibm03

27401

93573

5.11

5.09

8m 23s

8m 19s

ibm04

31970

105859

6.39

6.35

10m 46s

10m 35s

ibm05

28446

126308

10.56

10.54

10m 44s

10m 38s

ibm06

34826

128182

5.50

5.45

12m 08s

11m 55s

ibm07

48117

175639

9.63

9.61

18m 32s

18m 15s

ibm08

50513

204890

10.26

10.15

19m 53s

19m 37s

ibm09

60902

222088

10.56

10.50

22m 50s

22m 15s

ibm10

75196

297567

19.70

19.64

29m 04s

28m 58s

ibm11

81454

280786

15.73

15.69

31m 11s

31m 01s

ibm12

77240

317760

25.83

25.74

30m 41s

30m 11s

ibm13

99666

357075

18.73

18.64

39m 27s

39m 24s

ibm14

152772

548616

36.69

36.72

1h 12m

1h 03s

ibm15

186608

715823

43.85

43.79

1h 30m

1h 11s

ibm16

190048

778823

49.63

49.60

1h 31m

1h 12s

ibm17

189581

860036

69.07

69.52

1h 43m

1h 58s

ibm18

201920

819697

47.46

47.41

1h 44m

1h 59s

HPWL = half perimeter wire length, MHGA = multithread hybrid genetic algorithm, m = minute, s = seconds, h = hours.