GA framework for ATPG

Besides standard GA, there is another best-known GA [1], steady state GA (SS), showed in Figure 6.2. In many optimization problems, it works bet-ter than standard GA. But here it isn’t considered, because it can’t exploit parallel logic simulate. In order to utilize parallel logic simulation, a new generation should be evolved first, then parallel logic simulation can be used to calculate these individual’s fitness value. Whereas, for steady state GA, two new individuals are generated at first, then their fitness values should be calculated immediately. Here I focus on standard GA, which is showed in Figure 6.1.

6.1.3 Selection

Various selection schemes will generate different results. There are many se-lection schemes have been used. Here I will focus on proportional sese-lection (PS) and stochastic universal selection (SUS).

6.1 Genetic algorithm 41

Figure 6.2: Stead state GA Procession

Proportional selection uses a roulette wheel, which is sized according to the fitness of each individual in the population. An individual is selected by spinning the roulette wheel. An example is showed in Figure 6.3. Stochastic universal selection uses a roulette wheel, which has N equidistant marks and N is the number of individuals in the population. The number of copies of each individual selection is equaling to the number of marks inside the corresponding slot. An example is showed in Figure 6.4.

p1 = 0.31 p2 = 0.21 p3 = 0.15 p4 = 0.24 p5 = 0.09

p1 p2

p3 p4

p5

Figure 6.3: Proportional selection

[9] shows stochastic universal selection is a more fair method and with less

p1 = 0.31 p2 = 0.21 p3 = 0.15 p4 = 0.24 p5 = 0.09

p1 p2

p3 p4

p5

Figure 6.4: Stochastic universal selection

noise in the sampling of new individuals than Proportional selection. In this implementation, I compare these two selection methods by experiment re-sults.

6.1.4 GA parameter

Various GA parameters are important in achieving good results.

Firstly, chromosome’s organization is considered. In my case, binary-coded string is used to represent chromosome (population). Each bit in string represents a primary input and each string represents one test vector.

Next, I considerthe size of population. A sufficient population is needed to provide good combinations of characters. However, a reasonable limit on the population size is needed to reduce computation. As [9] presented, the best size of population in ATPG GA is 16 or 32. Increasing size can’t get much improvement but increase run time. [9] also shows that for ATPG, over-lapping population (there are individuals that contain same chromosome in the population) is faster than no overlapping population (each chromosome of individuals are different), almost without any negative influence with fault coverage. Considering ability of parallel simulation, I select size of popula-tion 32 with overlapping. Terminapopula-tion condipopula-tion is another critical condipopula-tion, which can limit the number of repeatation. There are three conditions that will terminate generation.

Theninitial populationis considered. Because without evaluating test vec-tor, no one know which test vector is good or not, so initial population is randomly generated.

6.1 Genetic algorithm 43 1. Convergence condition. The longest hamming distance between highest fit individual and other individual is smaller than N / 10, N is the number of flip-flops.

2. The best fitness value has no improvement in the latest ten iterations.

3. The number of iteration is greater than 600.

Crossover is a very important operation in GAs, which provides a method for creating new solution from two fit parents, which are likely to be helpful in improving the fitness. There are several techniques can be used in crossover.

1. One point crossover

One index (swap point) in the chromosome string is selected. All data beyond that point in the chromosome string is swapped between the two parent organisms. The getting chromosomes are the children. An example is shown in Figure 6.5. There are two methods to implement one point crossover, fixed-index and random-index. Each time, when crossover, for fixed-indes, the swap point is fixed and for random -index, the swap point is randomly.

1

Figure 6.5: One point crossover 2. Two point crossover

Two indices (swap points) are selected in the chromosome. Everything between the two points is swapped between the parent chromosomes, rendering two child chromosomes. An example is showed in Figure 6.6.

There are also two methods to implement two point crossover, i.e. fixed-index and random-fixed-index.

3. Uniform crossover

Uniform crossover is the extreme case of multipoint crossover, for each bit: it takes the value from one of the parents at random. An example is showed in Figure 6.7.

Studies [5] have shown that uniform crossover is superior to one and two-point crossover. The advantage of uniform crossover is that it

per-1

Figure 6.6: Two point crossover

1

forms many different combinations of schemata much more quickly than one or two point crossover. When chromosome length is long the em-phasis of a GA is on performing more combinations of chromosome to obtain new schemata. Therefore, uniform crossover surges forward in this area. Because in the sequential ATPG, the chromosome’s length generally is quite longe, which is shown in Equation 6.1, so uniform crossover is selected for this implementation.

T he length of Chromsome=N ×M (6.1)

• N is the number of primary input.

• M is the number of test vectors in one chromosome.

Mutation rate is a very critical and problem depend parameter, which is used to prevent the loss of key characters at the various string positions. But, mutation also destroys good combinations of characters, so a balance should be found. I tried mutation probabilities from 0.01 to 0.5 respectively to find the best mutation rate of the circuits.

In summary, the GA parameters, selected in this implementation are shown in Table 6.1.

6.1 Genetic algorithm 45 Parameter Name Value or technology

se-lected

Selection Method PS or SUS Determined according

to experiment results Fitness scaling Linear scaling

Crossover Uniform crossover

Mutation Not decided Determined according

to experiment results Table 6.1: GA parameter