Abstract- Due to rapid progresss in VLSI design engineering during the last decennary, the complexness and size of circuits have been quickly increasing, puting a demand on industry for faster and more efficient CAD tools. Physical design is a procedure of change overing the physical description into geometric description. Physical design procedure is subdivided into four jobs: 1.Partitioning, 2. Floor be aftering 3. Placement and 4.Routing. Placement stage determines the places of the cells. Placement constrains are wire-length, country of the dice, power minimisation and hold. For the country and wire length optimisation a modern placer demand to manage the large-scale design with 1000000s of object. This thesis work aims to develop an efficient and low clip complexness algorithms for arrangement. This can be achieved by the usage of a job specific genotype encryption, and intercrossed, knowledge based techniques, which support the algorithm during the creative activity of the initial persons and the optimisation procedure. In this paper a fresh intercrossed familial algorithm, which is used to work out criterion cell arrangement job is presented. These techniques are applied to the multithread of the VLSI cell arrangement job where the aims are to cut down power dissipation and wire length while bettering public presentation ( hold ) .

Index Terms- VLSI design, physical design, arrangement, criterion cell, multithread

Introduction

IN the paste 30 old ages, VLSI-CAD ( Computer-Aided Design of Very Large-Scale Integrated circuits ) has been an enabling force behind the exponential growing of the public presentation and capacity of incorporate circuits [ 6 ] . The layout of incorporate circuits on french friess is one of many interrelated complex undertakings in VLSI circuit design. In the combinative sense, the layout job is a forced optimisation job.

The chief aims of the arrangement design procedure are to minimise the entire bit country and the sum estimated wire length for all the cyberspaces.

Optimization of the bit country use can suit more functionality into a given bit country. Optimization of the sum estimated wire length can cut down the capacitive holds associated with longer cyberspaces and rush up the operation of the bit. Therefore, the arrangement design procedure has a marked affect on the concluding bit public presentation. Since faculty arrangement is an NP-hard job, hence, it can non be solved precisely in multinomial clip [ 5, 7 ] . Trying to acquire an exact solution by measuring every possible arrangement to find the best 1 would take clip relative to the factorial of the figure of faculties. Consequently, it is impossible to utilize this method for circuits with any sensible figure of faculties. To seek through a big figure of candidate arrangement constellations expeditiously, a heuristic algorithm must be used [ 2 ] .

The traditional attack in arrangement is to build a planetary arrangement ( initial arrangement ) by utilizing constructive arrangement heuristic algorithms. A elaborate arrangement follows to better the initial arrangement. A alteration is normally accepted if a decrease in cost occurs, otherwise it is rejected.

Global arrangement produces a complete arrangement from a partial or non-existent arrangement. Since partitioning-based methods and numerical optimisation methods do non directly try to minimise wire length, the solution obtained by these methods is sub-optimal in footings of wire length.

Problem Formulation

A mathematical preparation of an estimate to the criterion cell arrangement job is now presented. Normally, 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 borders of the hypergraph ( set of cyberspaces linking the cells ) . The two dimensional arrangement parts are represented as an array of legal arrangement locations. The hypergraph is transformed into a graph ( a hypergraph with all hyperedge sizes equal to 2 ) via coterie theoretical account for each net. Each border ej is an order brace of vertices with a non-negative weight Wij assigned to it. The arrangement undertaking seeks to delegate all cells of the circuit to legal locations such that cells do non overlap. Each cell I is assigned a location on the XY-plane. The cost of an border linking two cells one and J, with locations ( eleven, yj ) and ( xi, yj ) is computed as the merchandise of the squared l2 norm of the difference vector ( eleven – xj ) ( yi – yj ) and the weight of the connecting border wij The entire cost, denoted ? ( x, y ) can so be given as the amount of the cost over all borders ; i.e:

Wire Length Estimation

It is computationally expensive to find the exact entire wire length for all the cyberspaces at the arrangement phase and hence, the entire wire length is approximated during arrangement. To do a good estimation of the wire length, we should see the manner in which routing is really done by routing tools. Almost all automatic routing tools use Manhattan geometry ; that is, merely horizontal and perpendicular lines are used to link any two points. Further, two beds are used ; merely horizontal lines are allowed in one bed and merely perpendicular lines in the other.

An efficient and normally used method to gauge the wire length is the semi-perimeter method. The wire length in this method is approximated by half the margin of the smallest bounding rectangle enveloping all the pins. For Manhattan wiring, this method gives the exact wire length for all two-terminal and three-terminal cyberspaces, provided that the routing does non overshoot the bounding rectangle. For cyberspaces with more pins and more zig-zag connexions, the semi-perimeter wire length will by and large be less than the existent wire length. Furthermore, this method provides the best estimation for the most efficient wiring strategy, the Steiner tree. The mistake will be larger for minimum spanning trees and still larger for concatenation connexions. In practical circuits, nevertheless, two and three terminal cyberspaces are most common. Therefore, the semi-perimeter wire length is considered to be a good estimation.

Techniques Used

Genetic Based Placement

Familial algorithms are powerful optimisation techniques that have been successful in work outing many difficult combinative optimisation jobs [ 12 ] . The power of GA ‘s comes from the fact that the technique is robust, and can cover successfully with a broad scope of job countries, including those which are hard for other methods to work out [ 3 ] . It works by imitating the natural procedure of development as a agency of come oning toward the optimum. The algorithm starts with an initial set of random solutions, called population. A solution twine ( called a chromosome ) is encoded as a double star or whole number twine. During each loop, called a coevals, each person in the current population is evaluated and assigned a fittingness value through a scoring map. Based on this fittingness, persons are selected for reproduction and their opportunity for choice additions with their fittingness. A figure of familial operators are so applied to the parents to bring forth new persons, called off springs. The normally used familial operators are crossover, mutant, and inversion. A new coevals is formed by choosing the persons from the parents and offspring harmonizing to their fittingness so that the population size can be kept changeless. Over many coevalss, the fitter persons tend to pre-dominate the population while the less fit persons tend to die-off and finally one super-fit single evolve.

Familial Algorithm

1. Encode Solution Space

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

set crossover_rate, mutation_rate ;

3. Generate initial population randomly

4. Evaluvate the initial population

5. While ( gen & A ; lt ; = max_gen )

For ( i=1 to start size/2 )

Choice parents ( mate1, mate2 ) ;

if ( random ( 0,1 ) & A ; lt ; = crossover_rate )

kid = Do crossover ( mate1, mate2 ) ;

if ( random ( 0,1 ) & A ; lt ; = mutation_rate )

mutant ( kid ) ;

evaluate ( kid ) ;

End For

Replacement ( ) ;

gen = gen +1 ;

End While

6. Return best solution in current population

Fig. 1. Pesudocode for familial algorithm

Figure 1 shows a Familial Algorithm execution for standard cell arrangement. The algorithm starts with an initial set of random placement solutions, which are called persons in a population. These solutions are coded as strings, called chromosomes. A twine represents a solution to the arrangement job. Next, the initial population will be evaluated, utilizing the placement-specific fittingness map. Crossover occurs by interchanging portion of the parents ‘ construction into two new persons called progeny. Each offspring inherits portion characteristics of their parents. Following crossing over, the progeny is mutated with low chance.

Stringing Encoding

In this genetic-based arrangement algorithm, a twine is represented by a set of allelomorphs ( the figure alleles equal to the figure of cells ) . Each allelomorph indicates the index, the x-coordinates and row figure of the cell.

Scoring Function

Each person is evaluated to find its fittingness through a scoring map. The hiting map F is the reciprocal of the entire HPWL for all the cyberspaces.

Where HPWL is the amount of the half margin of the smallest bounding rectangle for each net. HPWLi is the estimation wire length of cyberspace I and N is the figure of cyberspaces. In the execution, cell convergences are removed and row lengths are adjusted before measuring the chromosome. One ground of making so is due to the fact that taking the convergences after every coevals non merely gives the algorithm a more accurate image of the wire length but besides gives the algorithm repeated opportunities to optimise the circuit after it has been perturbed by overlap remotion. Therefore the row length control and overlap punishment are non considered in the marking map.

Initial Population Construction

For each constellation in the initial population, the x-coordinate and row Numberss of cells are determined indiscriminately. This sort of builder can diversify the initial solutions but besides tend to hold 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.

Choice Function

In the choice map, two methods are considered.

1 ) Roulette Wheel: It merely take the persons in a statistical manner based on their relation ( that is per centum ) fittingness values. Obviously, the best persons get more transcripts and the worst dice off.

2 ) Binary Tournament: In this method, two persons are taken at random and the persons with higher fittingness value are selected as one parent. The two persons are instantly replaced into the population for the following choice operation.

Crossover Operator

The Traditional crossing over operator used in GA may bring forth impracticable solutions for the criterion cell arrangement job, hence a crossing over operator called Order crossing over is considered.

Partially matched crossing over ( PMX ) may be viewed as a crossing over of substitutions, that guarantees that all places are found precisely one time in each progeny, i.e. both offspring receive a full complement of cistrons, followed by the matching filling in of allelomorphs from their parents.

Mutant Operator

Each progeny is mutated with a chance equal to the mutant rate. The mutation operator mutates an single by substituting indiscriminately selected brace of cells without altering the x-coordinate and row figure.

Hybrid Simulated Annealing

In this work we have hybridized the familial algorithm templet with the SA method. The SA method is impregnated within GA, between the crossing over and mutant operations, to better all the solutions obtained after the crossing over operation and earlier subjected to mutant operation.

Fake Annealing

SA is really simple technique for State Space Search Problem. It can get down from any province. And it is ever move to a neighbour with the min cost ( assume minimisation job ) . It can halt when all neighbours have a higher cost than the current province.

Multithreading

Multithreading ( MT ) is a technique that allows one plan to make multiple undertakings at the same time. The basic construct of multithreaded scheduling has existed in research and development labs for several decennaries. Co-routine systems such as Concurrent Pascal and InterLisp ‘s Spaghetti tonss were in usage in the mid-70s and dealt with many of the same issues. Ada ‘s undertakings are a linguistic communication based concept that maps straight onto togss ( so straight, in fact, that current Ada compilers implement undertakings with togss ) . Burroughs shipped a commercial mainframe OS with co-routinestyle togss every bit early as 1960. The weaving theoretical accounts we describe are purely package theoretical accounts that can be implemented on any all-purpose hardware. Much research is directed toward making better hardware that would be unambiguously suited for threaded scheduling.

Fig. 2. Multithreading with familial algorithm

Experimental Consequences

In this work the proposed algorithm designed to acquire a nearer to optimum solution for the VLSI arrangement job considered in this work is coded in C++ and experiments were conducted in a Sun Server Personal computer with 3.20 GHz Dual Core Processor. The result of consequences obtained for popular benchmark circuits ISPD02 was compared with that of the standard Genetic Algorithm methodological analysis which is besides coded in C++ and run on the same machine.

Tournament choice is used for reproduction. Single point crossing over is used in the crossing over operation. The parametric quantities are fixed by carry oning tests on assorted population sizes, crossing over chances, mutant chances and the satisfactory convergent velocity researching range of the proposed hunt techniques. Population size = 20: Personal computer = 0.9 ; Pm = 0.01

Comparison and Results

For all the bench grade circuit taken in this work, the proposed algorithm MHSA is able to surpass the standard Genetic algorithm both in footings of figure of loops required to make a nearer to optimum solution.

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

Decision

In this paper, we have presented several planetary techniques for circuit arrangement. The public presentation of the Fast arrangement algorithm was compared with the Multithreaded Hybrid familial Algorithm for VLSI arrangement job. Due to the ability of the Simulated Annealing method it finds the minimized wire length in fewer coevalss. We applied these algorithms to ISPD02 benchmark circuits from the consequences it is clear that MHGA outperforms than Fast Placement method.

Table I

Comparison Between Fastplace And Mhga

Circuit

# Internets

# Pins

HPWL ( x10e6 )

Run Time ( Sec )

Fast

Topographic point

MHGA

Fast

Topographic point

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 margin wire length, MHGA = multithread intercrossed familial algorithm, m = minute, s = seconds, H = hours.