
Journal of Computer Science
Year: 2009  Volume: 5  Issue: 4  Page No.: 290  296


Optimization of Test Scheduling and Test Access for ITC02 SOC Benchmark Circuits

P. Sakthivel,
R. Delhi Babu
and
P. Narayanasamy

Abstract: Problem statement: This study presented the optimized test scheduling and test access for ITC02 SOC benchmark circuits using genetic algorithm. In the scheduling procedure of SOC, scheduling problem was formulated as a sequence of two problems and solved. Approach: Test access mechanism width was partitioned into two and three partitions and the applications of test vectors and test vector assignments for different partitions were scheduled using different operators of genetic algorithm. Results: The test application time was calculated in terms of CPU time cycles for two and three partitions of twelve ITC02 SOC benchmark circuits and the results were compared with the integer linear programming approach. Conclusion: The results showed that the genetic algorithm based approach gives better results. 

• 
Design of an infrastructure for the transportation of test
data in the system 
• 
Design of a test schedule to minimize test time 
The testable units in an SOC design are the cores, the UDL and the interconnections^{[8]}. The cores are usually delivered with predefined test methods and test sets, while the test sets for UDL and interconnections are to be generated prior to test scheduling and TAM Design. The workflow when developing an SOC test solution can mainly be divided into two consecutive parts^{[10,11]} namely (i) An early design space exploration and (ii) An extensive optimization of the final solution. During the process, conflicts and limitations must be carefully considered. For instance, tests may be in conflict with each other due to the sharing of test resources and power consumption. Otherwise the system may be damaged during test. Further, test resources such as external testers support a limited number of scanchains and limited memory.
Research has been going on in developing techniques for test scheduling, TAM design and testability analysis^{[5,6]}. In this study, a new technique is proposed using Genetic Algorithm for optimizing the test vector for Globally Asynchronous Locally Synchronous (GALS) SOC with the objective to minimize the test application time. The aim of the proposed approach is to reduce the gap between the design space exploration and the extensive optimization that is to produce a high quality solution in respect of test time and TAM at a relatively low computational cost. Earlier research^{[14]} has studied wrapper design or TAM optimization as independent problems. They have not addressed the issue of sizing the TAM to minimize SOC testing time. Alternative approaches that combine TAM design with test scheduling do not address the problem of wrapper design and its relationship to TAM optimization^{[18,19]}.
The GA based approach to solve the problems of test scheduling optimization for wrapper design and TAM is presented here. This approach provides improved results, comparable to the existing ILP approach.
The study related to our approach and various issues related to SOC testing and test scheduling techniques, Test vector optimization and test scheduling framework based on genetic algorithm, the experimental results for the 12 SOC benchmark circuits of ITC02 are presented.
MATERIALS AND METHODS
Soc test scheduling: The basic problem in test scheduling^{[4]} is to assign a start time for all tests. In order to minimize the test application time, tests are scheduled as concurrent as possible. However, various types of constraints must be considered. A test to be scheduled consists of a set of test vectors produced or stored at a test source. The test response from the test is evaluated at a test sink. When applying a test, a test conflict may occur, which must be considered during the scheduling process. For instance, often a testable unit is tested by several test sets. If several tests are used for a testable unit, only one test can be applied to the testable unit at a time.
The tests are scheduled in sessions where tests at cores placed physically close to each other are grouped in the same test session. In a fully BISTed system^{[2]}, each core has its dedicated test source and test sink and there might not be any conflicts among tests. However, in general, conflicts among tests may occur during testing.
The testapplication time can be minimized by scheduling the execution of the test sets as concurrently as possible. The basic idea in test scheduling is to determine when each test set should be executed. The main objective is to minimize the test application time.
Proposed test access mechanism: The test access mechanism takes care of chip test pattern transport^{[13,14]}. It can be used to transport test stimuli from the test pattern source to the core under test and to transport test responses from the core under test to the test pattern sink. The TAM is, by definition, implemented on the chip.
The wrapper and TAM are structured into the following two problems in the order of increasing complexity^{[1]}.
P_{A}: To determine the test bus assignment to each cores. The
TAM is partitioned into different test buses and the problem here is to identify
the bus assignment to each core in the SOC.
P_{PA}: To determine a Partition of the total TAM width among given number of TAM and to determine the test bus assignment to each core (P_{A}). The size of the TAM is given and the TAM should be divided into many partitions according to the requirement. The number of partition required should be obtained first and it will be given as an input to the problem (P_{A}). Then the problem (P_{A}) will determine the test bus assignment to each core in the SOC.
Genetic Algorithm Based Problem Formulation for P_{A}: The problem
(P_{A}) is formulated in such a way that the Genetic Algorithm is used
to optimize the solution. In the formulation of P_{A}, number of cores
(N) in SOC and number of test buses (B) of TAM of widths w_{1}, w_{2},
w_{3}, …, w_{B} are considered.
The main objective is to determine the assignment of cores to test buses of TAM such that the assignment is used for test application for SOC and the total testing time is minimized.
Distributing the cores of SOC equally among test buses of TAM and taking the permutations of cores of SOC assigned to test buses of TAM can obtain initial populations for Genetic Algorithm. Then the
GA (Selection, Crossover and Mutation) is applied on the initial population to generate new chromosomes (children). The solution to the above problem obtained as a set of chromosome (child) consists of integers in the range 1 to B. Each
value in the chromosome set represents the core assignment to the test bus. The ‘i’th element of the chromosome set represents the bus number of TAM to which core ‘i’ of SOC is assigned.
Genetic algorithm based problem formulation for P_{PA}: The
problem (P_{PA}) is formulated as a sequence of two problems both of
which is solved using Genetic Algorithm. In the formulation of P_{PA},
number of cores (N) of SOC and number of test Buses (B) of TAM of widths w_{1},
w_{2}, w_{3}, …, w_{B} are considered. The objectives
are (i) To determine the distribution of the total TAM width among the given
number of TAM and (ii) To determine the assignment of cores of SOC to the test
buses of TAM. A chromosome in our approach consists of two parts. (i) The assignment
of cores of SOC to test buses of TAM which is a set of integer numbers with
‘i’th element representing the test bus number for which the core ‘i’ of SOC
is assigned. (2) The chromosome is the bus width distribution of each test bus
of TAM, which is also set of integer numbers where the total of all the integers
is equal to the size of TAM. The ‘j’th entry of the set represents width of
the test bus ‘j’, such that sum of these widths is equal to TAM width.
Function for total time: Total time is the time required to test all
the cores in the system, which is given below. If the core ‘i’ of SOC is assigned
to test bus ‘j’ of the TAM, then the testing time for core ‘i’ of SOC is given
by:
T_{i}(W_{j}) = (1 + max{L_{wi},
L_{wo}})* V_{ni}+min{L_{wi}, L_{wo}} 
Where, 
T_{i} 
= 
Test application time of core "i" in SOC 
W_{j} 
= 
Width of test bus ‘j’ 
L_{wi} 
= 
Length of the longest wrapper scanin chain 
L_{wo } 
= 
Length of the longest wrapper scanout chain 
V_{ni} 
= 
Number of test vector for core ‘i’ 
Total test cycles needed to test all the cores in the SOC is:
T = {∑T_{i}(W_{j}) * b_{ij}},
1< = i < = N and 1< = j< = B 
where, b_{ij} a binary variable defined as follows:
b_{i j} 
= 
1 if core ‘i’ is assigned to bus ‘j’ 


0 otherwise 
The above problem is NPHard problem^{[1]}. Therefore, efficient heuristics and other techniques are needed for large problem instances. In this study, genetic algorithm based approach to effectively solve these problems namely P_{A} and P_{PA} are presented.
Test vector optimization based on genetic algorithm: Genetic Algorithms can effectively be used to solve the search and optimization problems. The genetic algorithm that is used for generating test sequences for SOC is described. First, the basic idea of the method is given. Then the representation of test conditions, the objective function and some insights into the parameter settings of the genetic algorithm are presented. GAs consist of population of solutions called chromosomes. Here the chromosomes are an encoding of the solution to a given problem. The algorithm proceeds in steps called generations. During each generation, a new population of individuals is created from the old population by applying genetic operators. Given old generation, new generation is built, according to the genetic operations such as selection, 1point crossover, 2point crossover, uniform crossover, weight based crossover, 1point mutation, 2point mutation and mutation with neighbor.
Selection: This operator selects the individuals from the old generation. The fitness of an individual determines its chances to reproduce. The individual with a better performance possesses higher chances of getting selected. For each parent, two elements are chosen randomly. Only these elements are evaluated by the objective function. The element with higher ranking is selected. Thus, for the selection of two parents only four elements are evaluated instead of the whole population. Various selection schemes such as roulette wheel selection, stochastic universal selection and binary tournament selection with and without replacement are used depend upon the requirement. The objective of the GA is to converge to an optimal individual and selection pressure is the driving force which determines the rate of converges. A high selection pressure will cause the population to converge quickly, possibly at the expense of a suboptimal result. The GA selects individual with probability proportional to their fitness.
Crossover: Once two chromosomes are selected, the crossover operator is used to generate two offspring. The details about 1point crossover, 2point crossover, uniform crossover and weightbased crossover operators are illustrated in the Chapter 3. Crossover combines the schemata or building blocks from two different solutions in various combinations. Smaller good building blocks are converted into progressively larger good building blocks over time until a completely good solution is found.
Point mutation: The 1point Mutation produces incremental random changes in the offspring generated through crossover. Mutation may be done by flipping a bit. One new element C from a parent P is constructed by copying the whole element and changing a bit at a randomly chosen position.
Point mutation: The 2point mutation is performing 1point Mutation two times on the same chromosome one after the other. The values of two bits are changed by the 2point mutation.
Mutation with neighbor: 1pont Mutation is performed at two adjacent positions on the same element instead of randomly selected positions as in 2point mutation. The values of two adjacent bits are changed by the mutation with neighbor operation. In the Genetic Algorithm mutation serves the crucial role of replacing the gene values lost from the population during the selection process so that they can be tried in a new context or of providing the gene values that were not present in the initial population.
Pseudo code for the proposed genetic algorithm based method: The pseudo
code of the proposed GA based algorithm is shown in the Fig. 1.

Fig. 1: 
The GA based test vector optimization algorithm 
RESULTS
The experiments were conducted for the ITC02 SOC benchmark circuits. The results
were obtained for each of the benchmark circuits by partitioning TAM width into
two and three partition. W is the width of Test Access Mechanism. w1, w2 and
w3 are the size of the partition 1, partition 2 and partition 3. The vector
assignment in the Table 1 is the information about the bus
assignment ("1" in the "ith" position indicates the "bus
1" or "partition 1" of size "w1" is assigned to the
"ith" core for the transportation of test vector) for test vector
transportation of each core in the SOC. ILP cycles are the result of the existing
algorithm, which utilized the integer linear programming techniques to solve
the SOC test scheduling problem. GA cycles are the result of the proposed experiment,
which utilizes Genetic algorithm to solve the problem, In the Table
1, the results of ILP and GA for SOC u226 is presented for the partition
size of 16, 24, 32, 40, 48, 56 and 64 bits. The TAM is partitioned into 2 parts.
The optimized scheduling of test vectors are obtained for the proposed GAbased
method and the required amount of test time that is the number of CPU cycles
are obtained and tabulated. These values are also plotted for each partition
against the number of CPU cycles in the Fig. 2. From the results
and comparison graph, it is observed that the amount of CPU cycle required for
the GAbased method is relatively less than the ILPbased method. Further, if
the size of the TAM gets increased, the amount of time required for test application
also gets reduced.
Table 1: 
Results of ILP versus proposed GA approach for SOC u226 with
two partitions 


Fig. 2: 
Comparison of ILP with GA for SOC with two partitions 
Table 2: 
Results of ILP versus proposed GA Approach for SOC u226 with
three partitions 


Fig. 3: 
Comparison of ILP with GA for SOC with three partitions 
In the Table 2, the results of ILP and GA for SOC u226 is presented for the partition size of 16, 24, 32, 40, 48, 56 and 64 bits. The TAM is partitioned into 3 parts. The optimized scheduling of test vectors are obtained for the proposed GAbased method and the required amount of test time that is the number of CPU cycles are obtained and tabulated.
These values are also plotted for each partition against the number of CPU cycles in the Fig. 3. From the results and comparison graph, it is observed that the amount of CPU cycle required for the GAbased method is relatively less than the ILPbased method. Further, if the size of the TAM gets increased, the amount of time required for test application gets reduced. Another important result obtained from the Table 1 and 2 is, if the number of partition gets increased, the amount of test application time gets reduced.
In both the cases of GA based approach for SOC u226 with two partitions and GA based approach for SOC u226 with three partitions; the amount of test application time gets reduced.
DISCUSSION
Genetic Algorithms work by evolving a population of individuals over a number
of generations. A fitness value is assigned to each individual in the population,
where the fitness computation depends on the application.
Table 3: 
Average CPU Cycles for benchmark circuit with 2 partitions 

In the GA based test scheduling and TAM optimization, the initial population is randomly generated over a number of generations. The fitness function "improvement in the total test application time" is checked for each generation. The fitness function is not satisfied, the individuals are selected from the population for reproduction, crossed to generate new individuals and the new individuals are mutated to the population repeatedly until the fitness function is satisfied. During each generation of the Genetic Algorithm, the new individual may completely replace the old individuals in the population or new individual may be combined with the old individuals in the population. Since selection is biased toward more highly fit individuals, the average fitness of the population next. The fitness of the best individual is also chosen as a solution after several generations. The genetic algorithm uses two basic processes "inheritance" or the "passing features from one generation to the next" and "competition" or "survival of the fittest" which results in weeding out the bad features from individuals in the population. Due to these reasons, the GA based method produces improved results for the problems (P_{A}) and (P_{PA}).
The number of CPU cycles is obtained for the ITC02 SOC Benchmark circuits
given in^{[15]} with the TAM width as 16, 24, 32, 40, 48, 56 and 56
bits and by dividing the TAM into 2 and 3 partitions. The average values of
CPU cycles are obtained for GA based method and tabulated in the Table
3 and 4 for 12 ITCSOC benchmark circuits for the TAM
partition of 2 and 3 respectively along with the CPU cycles of ILP method. The
comparison graph for the GA based method and ILP based method are shown in the
Fig. 4 and 5 respectively. For all the circuits,
the GA based method outperforms the ILP based method. The number of CPU cycle
is relatively reduced for 3partitions than 2partitions of TAM. This is due
to the faster and parallel transportation of test vector when the partition
of TAM gets increased.
Table 4: 
Average CPU cycles for benchmark circuit with 3 partitions 


Fig. 4: 
Average CPU cycles for benchmark circuit with 2 partitions 

Fig. 5: 
Average CPU cycles for benchmark circuit with 3 partitions 
When the numbers of partitions of TAM are increased, the possibility for parallel transportation of test vectors also increased and it naturally reduces the total test application time.
CONCLUSION
The investigation of the results show that the GA based approach produces the required partition of TAM width and vector assignment for the cores in SOC, such that the testing time is less than the ILP based approach. The experimental results are given for twelve ITC02 SOC Benchmark circuits with two partitions and three partitions. The result gives good approximation compared to ILP within a few generations with acceptable processor times.
Further, the comparison of results of 12 ITC02 SOC benchmarks circuits in Table 4 shows that the test application time for circuit increases with the complexity of the circuit in both the ILP and GAbased methods. The GA basedmethod takes less amount of test application time. This establishes the suitability of this problem to be solved by genetic algorithm. This technique can be applied to all the SOC benchmarks with more number of TAM widths and partitions. The results of proposed GAbased approach are found to be better than the results of the ILP methods available in the literature.
" target="_blank">View Fulltext

Related
Articles 
Back