Test Scheduling of Core Based System-on-Chip Using Modified Ant Colony Optimization

Currently, Integrated Circuits (ICs) are embedded in a variety of products and systems. IC’s comprises of a huge number of transistors and hardware modules. Millions of transistors and hardware modules can be manufactured on a single chip called a System on Chip (SoC). An SoC chip consists of peripheral devices, processors and controllers. The complexity of ICs is a major challenge in SoC design. Intellectual Property (IP) cores used for SoC designs are embedded in system chip and it is impossible to access it directly. Testing cost highly depends on the testing time which increases when the system becomes more complex. After manufacturing to test individual cores on system-level Test Access Mechanism (TAM) is necessary. The major parts in test access architecture of SoC are TAM and Test wrapper. These components have an impact on the vector memory required on Automatic Test Equipment (ATE). The wrapper is a thin shell surrounding the core acting as an interface between the core and TAM [1-3].

The wrapper is linked to core inputs, outputs and scan chains outside the core. The TAM wires are used to apply test vectors to the wrapper. ATE stores the test vectors which are to be applied to SoCs and are applied through TAM wires. The cores are scheduled for testing in order to obtain minimum test time. Due to the increase in SoC size, Test Application Time (TAT), test data volume and test resource usage also increase.

To reduce TAT, SoC test resources should be designed and used effectively. The main aim is to reduce the test time of SoCs by efficient scheduling techniques. In this research paper, a Modified Ant Colony Optimization (ACO) technique is used to optimize the testing time for various ITC’02 SoC benchmark circuits. The results show that the Modified ACO technique provides better results compared to other techniques.

The ITC'02 SoC Test Benchmark circuits are a set of benchmark circuits presented at the IEEE International Test Conference (ITC'02). Table 1 gives the details of the ITC’02 benchmark circuits. Tables 2 and 3 give the details of the d695 and p22810 ITC’02 benchmark circuits respectively.

The task of the optimization algorithm is to minimize the test time taken as the objective function represented in the following equation (1).

$T\left(W_{i}\right)=(1+\max (S i, S o) \cdot t p i+\min (S i, S o)$      (1)

where, S_i  and So are the length of the input and output scan chain and tpi is the test pattern for the SoC benchmark circuit optimization of core i.

Table 1. Benchmark circuit details

3.1 Ant colony optimization (ACO) algorithm

Ant Colony Optimization (ACO) [12, 13] is a population-based approach to solving computational problems. This is based on the social behavior of ants in finding the best route to the nesting food source through indirect communication between the ants using the chemical substance pheromone.

Ants leave pheromones as they move so that other ants can detect and follow this pheromone which is shown in Figure 1. 

1.png

Figure 1. Ant colony optimization

In ACO, artificial ants use heuristic information and a combination of artificial pheromones to develop new solutions. ACO has been shown to have been very successful in solving many problems.

3.2 Modified ant colony optimization (MACO)

In the Modified Ant Colony Optimization (MACO) [14-16], the core scheduling of the selection is based on 'maxtw' and partly relies on the probability. First, the core is selected based on the probability, and then tested using the constraints. If the conditions are satisfied, the core will be chosen. Otherwise, the next highest probability core will be tested. This step will be repeated until all conditions have been satisfied. Let us assume that an ant begins with a core i and has to reach out to other cores. The first core i is chosen at random and then the next core j is selected with probability ‘prob’. This process will be repeated until all cores have been scheduled. This algorithm uses an ant density model. According to the ant density model, the quantity of the pheromone trail left by the ants remains constant throughout the path.

$\operatorname{prob}_{i j}=\frac{\tau_{i j} \eta_{i j}^{\beta}}{\sum_{i=n}^{n} \tau_{i j} \eta_{i j}^{\beta}}$              (2)

where, prob_ij=Probability of core j being scheduled as the next core

$\tau_{i j}$ = Trail value for pheromones from route i to j >= 0

$\eta_{i j}$ = Heuristic value, which depends on the core test time >= 0

$\eta i j$ = 1/tt where tt is the test time of the core.

2.png

Figure 2. Flowchart for modified ant colony optimization

In ACO cores are selected randomly whereas in MACO cores are selected based on the probability and the cores satisfying the constraints are chosen.

$\beta$ is a parameter for heuristic value enhancement. Its value for hierarchical cores is higher than for flat cores so that the hierarchical cores can be tested first. When an ant travels from core i to j, the pheromone route needs to be updated. This process is referred to as trail intensification. The following Eq. (3) can be used for the formulation of trail intensification.

      $\tau_{(i t o j)}=\left\{\begin{array}{l}{Q, \text { if ant goes from } i \text { to } j} \\ {0, \text { otherwise }}\end{array}\right.$               (3)

Q is a parameter that is constant. It is the amount of trail left when an ant moves from core i to j. The trail intensification is done at the time of core selection. After scheduling, using an ant, the test time is calculated. The scheduling process is repeated for no. of ants and the best test time of all is selected. The results using ITC’02 benchmark circuits are shown in the next chapter. This algorithm schedules the cores with a fork and merge technique and provides the optimal solution.

Input: Let there be n number of cores with maximum tam width available which is ‘maxtw’. Each core has a core number, tam width ‘tw’. The test time ‘tt’ of each core is calculated using the wrapper algorithm and the int u which is used to verify whether the core is scheduled or not.

Output: best_time is the minimum test time attained after a number of iterations. The test time is calculated for each iteration and the best_test time represents the minimum test time of all the test times.

Table 4. Input parameters for core initialization

Figure 2 shows the MACO algorithm flow chart. Initially, the input parameters are read followed by parameter initialization and for all the ants updating of the parameter is done. The probability for a core i is updated and check the test condition. If the condition is true, the values are updated else if it is false, initialize the array of all cores. Then update pheromone trial and assign i value to j. Test time is calculated and updated with the best test time.