Asian Science Citation Index is committed to provide an authoritative, trusted and significant information by the coverage of the most important and influential journals to meet the needs of the global scientific community.  
ASCI Database
308-Lasani Town,
Sargodha Road,
Faisalabad, Pakistan
Fax: +92-41-8815544
Contact Via Web
Suggest a Journal
Journal of Computer Science
Year: 2009  |  Volume: 5  |  Issue: 4  |  Page No.: 290 - 296

Optimization of Test Scheduling and Test Access for ITC-02 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 ITC-02 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 ITC-02 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 scan-chains 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 ITC-02 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 test-application 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].

PA: 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.

PPA: To determine a Partition of the total TAM width among given number of TAM and to determine the test bus assignment to each core (PA). 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 (PA). Then the problem (PA) will determine the test bus assignment to each core in the SOC.

Genetic Algorithm Based Problem Formulation for PA: The problem (PA) is formulated in such a way that the Genetic Algorithm is used to optimize the solution. In the formulation of PA, number of cores (N) in SOC and number of test buses (B) of TAM of widths w1, w2, w3, …, wB 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 PPA: The problem (PPA) is formulated as a sequence of two problems both of which is solved using Genetic Algorithm. In the formulation of PPA, number of cores (N) of SOC and number of test Buses (B) of TAM of widths w1, w2, w3, …, wB 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:

Ti(Wj) = (1 + max{Lwi, Lwo})* Vni+min{Lwi, Lwo}

Where,
Ti = Test application time of core "i" in SOC
Wj = Width of test bus ‘j’
Lwi = Length of the longest wrapper scan-in chain
Lwo = Length of the longest wrapper scan-out chain
Vni = Number of test vector for core ‘i’

Total test cycles needed to test all the cores in the SOC is:

T = {∑Ti(Wj) * bij}, 1< = i < = N and 1< = j< = B

where, bij a binary variable defined as follows:

bi j = 1 if core ‘i’ is assigned to bus ‘j’
    0 otherwise

The above problem is NP-Hard 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 PA and PPA 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, 1-point crossover, 2-point crossover, uniform crossover, weight based crossover, 1-point mutation, 2-point 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 1-point crossover, 2-point crossover, uniform crossover and weight-based 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 1-point 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 2-point mutation is performing 1-point Mutation two times on the same chromosome one after the other. The values of two bits are changed by the 2-point mutation.

Mutation with neighbor: 1-pont Mutation is performed at two adjacent positions on the same element instead of randomly selected positions as in 2-point 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 ITC-02 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 GA-based 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 GA-based method is relatively less than the ILP-based 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 GA-based 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 GA-based method is relatively less than the ILP-based 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 (PA) and (PPA).

The number of CPU cycles is obtained for the ITC-02 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 ITC-SOC 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 3-partitions than 2-partitions 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 ITC-02 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 ITC-02 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 GA-based methods. The GA based-method 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 GA-based approach are found to be better than the results of the ILP methods available in the literature.

" target="_blank">View Fulltext    |   Related Articles   |   Back
 
 
   
 
 
 
  Related Articles

 
 
 
 
 
 
 
 
Copyright   |   Desclaimer   |    Privacy Policy   |   Browsers   |   Accessibility