Test scheduling of System-on-Chip using Dragonfly and Ant Lion optimization algorithms

Abstract

Test scheduling of System-on-Chip (SoC) is a major problem solved by various optimization techniques to minimize the cost and testing time. In this paper, we propose the application of Dragonfly and Ant Lion Optimization algorithms to minimize the test cost and test time of SoC. The swarm behavior of dragonfly and hunting behavior of Ant Lion optimization methods are used to optimize the scheduling time in the benchmark circuits. The proposed algorithms are tested on p22810 and d695 ITC’02 SoC benchmark circuits. The results of the proposed algorithms are compared with other algorithms like Ant Colony Optimization, Modified Ant Colony Optimization, Artificial Bee Colony, Modified Artificial Bee Colony, Firefly, Modified Firefly, and BAT algorithms to highlight the benefits of test time minimization. It is observed that the test time obtained for Dragonfly and Ant Lion optimization algorithms is 0.013188 Sec for D695, 0.013515 Sec for P22810, and 0.013432 Sec for D695, 0.013711 Sec for P22810 respectively with TAM Width of 64, which is less as compared to the other well-known optimization algorithms.

Keywords

System-on-chip test scheduling Dragonfly algorithm Ant Lion optimization

1 Introduction

Integrated Circuits play a major role in the development happened in technologies like smartphones, tablets, camera etc. The first developed IC consists of one capacitor, one transistor, and three resistors. Improvements in fabrication technology have caused the ICs to be built with billions of transistors called System-on-Chip (SoC). The SoC contains more than one million gates, memories, cores, analog and digital blocks placed on a single chip. Designing and manufacturing a large-scale IC has major issues like power consumption and thermal issues. Since testing involves large switching activities, more attention should be paid to test mode than normal mode [1, 2]. To overcome the problem in SoC testing, an effective method is modular testing of embedded cores. These cores are complex predefined blocks that allow for design reuse leading to shortening the product development cycle. However, the main challenge lies in the manufacturing test and the debugging of the SoC designs [1].

Hence to access the cores and test resources, there is a need for test architecture design. Modular testing in which Test Access Mechanism (TAM) and embedded cores are present in an SoC sends and receives data from Automatic Test Equipment (ATE) [3]. In modular testing, the embedded cores are isolated, and test access is gained to the individual SoCs for test data delivery. In this process, the divide and conquer approach is followed, promoting pre-computed test sets of embedded cores. These cores become the primary motivation for modular testing [4].

The testing cost is minimized by proper test planning, including test scheduling and test architecture design. Testing time is considered as the objective function shown in the equation below (1). $T (W_{i}) = [1 + \max (S_{i}, S_{o})] . t_{pi} + \min (S_{i}, S_{o})$ (1)

Where S_o and S_i are the output and input length of the scan chain and t_pi is the test pattern.

At ITC’02 SoC Test Benchmark Circuits [5] was presented. Table 1 shows the particulars of the SoC benchmark circuits.

Table 1

Benchmark circuit details

SOC		P22810	D695
Contributor		Philips Semiconductors	Duke University
Number of SFFs		24723	6384
Number of I/O’s		4283	1845
Number of Levels		3	2
Number of Tests		30	10
Number of Scan Chain Length		196	137
Number of Modules		29	11
Number of Pattern Count	Average	830	88
	Maximum	12324	234
	Minimum	1	12
Length of Scan Chain	Average	126	46
	Maximum	400	55
	Minimum	1	32

Test scheduling is an important concern in SoC test automation. Efficient test schedules minimize the overall cost and time to market the chip.

The advantage of the proposed approaches is that we implicitly minimize the test time, which implicitly reduce the test cost. In this paper, we propose evolutionary approaches for test scheduling to reduce cost and time. The contributions of this paper are as follows:

Dragonfly and Ant Lion Optimization algorithms used for the test scheduling yields considerably better test times than the other heuristic methods.

The performance of heuristic algorithms for various TAM widths are computed to test its efficiency on two benchmark circuits.

The rest of this article is organized as follows. In Section 2 literature review is described. The proposed works are described in Section 3. In Section 4 the experimental results are presented. Conclusions and future work are in Section 5.

2 Literature review

For test time reduction in core-based systems, wrapper and TAM optimization have been done effectively. Access requirement-based wrapper design of cores was developed. Using TAM and wrapper design optimization techniques, algorithms are developed for the NP-hard problem in test scheduling. Two architectures, namely, distribution architecture and multiplexing architecture, were developed to compute the testing time [6]. Particle Swarm Optimization (PSO) [5] algorithm is based on bird behavior when searching for food. In this algorithm, particle refers to an individual bird, and the dimension represents the number of the parameter. The natural evolution process inspires a Genetic Algorithm (GA) [7]. It offers different operations like selection, mutation, crossover, and many other natural evolution processes.

Liu [8] introduced a parallel elite genetic algorithm to reduce test time. In this offspring are generated using parent A and parent B, and then crossover and mutation are done. This algorithm is tested in 2D SoC benchmark circuits, and it has proved to be one of the effective scheduling algorithms. The real-time behavior of ant in search of food by using pheromone leads to Ant Colony Optimization (ACO) [9, 10]. This pheromone helps to find new routes for their food, and other ants follow the same route. In the modified ACO [12, 13], when the number of cores is reduced, the number of ants also decreases, which reduces the system’s test time.

Artificial Bee Colony (ABC) algorithm [14] is enthused from the nectar searching process carried out by artificial bees. Here, bees belonging to the same colony are divided into three sets; the first set of bees’ search food source, another set of bees (onlooker bees) selects best food source, and the third set of bees (scout bees) search for food in search space randomly. Modified ABC algorithm [15, 16] enhances the population’s average fitness by mutating weak possible solutions to the most appropriate solution. Firefly Algorithm (FA) [17] works on assumptions that the gender of all fireflies is the same, attractiveness depends upon brightness of light, and fitness function relies on brightness. The Modified FA [18] reduces the randomness so that the convergence can be obtained speedily, and the fireflies move towards global optima. Bat Algorithm (BA) [19] mimics the echolocation process that bats use to detect prey from a distance in the dark. The echolocation process perceives objects by reflected sound. Hence bats can identify prey through reflected frequency. The exploration and exploitation processes are maintained through frequency and zooming parameters.

Due to the increase in test power consumption and volume of test data sets, the serious challenges are faced in testing a system-on-chip. Hence, three coding test compression techniques [20] is used. The testing time is reduced with an increase in the compression ratio. For circular scan circuits, new test set compression scheme is developed [21]. This method efficiently minimizes the test data volume and testing time. For digital circuits, Two-Stage Low Power Test Data Compression was proposed [22]. The two-stage test data compression applied with filled test cubes. The test sets are encoded and the test data compression is enhanced using alternative statistical run-length coding. Then the compressed ASRL sets are encoded using Run Length based Huffman Coding. Due to an increase in demand for test data compression, the newest and easiest method is implemented to minimize the test data volume. Based on bit reversion, test data compression approach was developed [23] in which the compression becomes easier. This approach can be used in various coding schemes. The technique enhances test compression for multiple expansion results was suggested [24]. This method is mainly used to detect faults at higher expansion ratios. The faults at a higher expansion ratio can also be detected, and hence the concatenation of the scan chain is done.

Test time minimization is done by both test compression and test sharing in one framework. The optimization time is increased using this approach since the complexity is increased [25]. Research present a SoC testing approach that integrates test data compression, test scheduling and TAM design. It shows that the dynamic scheduling approach is more flexible since the performance of the static method depends on the configuration of the predetermined test cubes. In this work test algorithm is static in nature [26 –28]. The algorithm used will adaptively find the earliest start time of each test and will generate a test schedule to reduce the test time, this test schedule is a thermal aware test [29]. SoC is designed addressed in such a way where it tries to minimize the test access mechanism (TAM) design and test schedules via reconfigurable core wrappers Further, it also tries to minimize via extended core design and extract the properties by the hierarchical way [30]. The further study approached the genetic algorithm to minimize TAM but the process followed is a hierarchical core [31]. In these all study the way of reduce TAM is traditional and modified, but it’s still need improvement as stated by researcher in their study for future work.

3 Proposed methodologies

The cores are represented as rectangle bins with their height represents TAM width and length represents test time as shown in Fig. 2. The unfilled bin area is the idle time.

Fig. 1

Modular testing.

Fig. 2

SoC Test Scheduling.

Figure 3 shows the block diagram of the proposed architecture. The first step in the proposed architecture is the assignment of input parameter values followed by population initialization. Using these input parameters training and testing of data is done. Optimization is done using dragonfly and ant lion algorithm. Then the test time is estimated using optimal test scheduling.

Fig. 3

Proposed Architecture.

3.1 Dragonfly algorithm

Dragonfly Algorithm (DA) [32, 33] is a swarm optimization technique based on the dragonfly’s behavior. DA is used to address a wide variety of optimization concerns, such as image processing, robotics, medical, computer science, engineering, and many others. In comparison to other well-considered optimization algorithms. DA is influenced by the natural behaviour of artificial dragonflies and has proved its effectiveness and robustness. The exploitation and exploration parameters are well modeled for global optimization in this method. The life cycle of Dragonflies includes two phases of adult and nymph. Nymphs also hunt on other tiny insects and small fishes in water ponds. The dragonflies are unique and swarm for migration and hunting. The latter is known as dynamic (migratory) swarm, and the former is known as static (feeding) swarm. In a static swarm, dragonflies form small groups for predating other insects such as mosquitoes and butterflies. Three stages in the dragonfly behavior are

Separation (S): To avoid a collision from the neighbors, the swarms are separated from others. Separation (S) is represented by equation (2) $S_{i} = - \sum_{j = 1}^{N} X - X_{j}$ (2)

Whereas X is the current individual position X_j is the jth individual neighboring position and

N represents the number of neighborhoods.

Alignment (A): Each individual’s velocity is matched by the other. The alignment is denoted by Equation (3) $A_{i} = \frac{\sum_{j = 1}^{N} V_{j}}{N} - X$ (3)

Whereas V_j is the neighboring individual j velocity.

Cohesion (C): Swarm attraction to the core of the swarm population described by the Equation (4) $C_{i} = \frac{\sum_{j = 1}^{N} X_{j}}{N} - X$ (4)

The mathematical representation of attraction towards the food Fⁱ is given by $F^{i} = X^{+} - X$ (5)

The distance from the enemy Eⁱ is calculated by $E^{i} = X^{-} + X$ (6)

Where X⁺, X^- are the food source and enemy position.

With separation (s), alignment (a), cohesion (c), food (f), and enemy factors (e), different exploitative and explorative behaviors can be reached during optimization shown in Fig. 4. A small change in the position of the dragonfly is calculated as follows $X_{t + 1} = ({sS}_{i} + {aA}_{i} + {cC}_{i} + {fF}_{i} + {eE}_{i}) + {wX}_{t}$ (7)

Fig. 4

Various stages of DA.

Where w, t represents inertia weight and iteration counter.

The updated position vector is $X_{t + 1} = X_{t} + X_{t + 1}$ (8)

The randomness and stochastic dragonflies’ behavior of the can be enhanced by carried out levy flight in the search space. The dragonflies position update is given by $X_{t + 1} = X_{t} + Levy (d) * X_{t}$ (9)

Where t is the current iteration, and d is the search space dimension. The Levy flight is given by $Levy (d) = 0.01 (\frac{r_{1} * σ}{{| r_{2} |}^{\frac{1}{β}}})$ (10)

Where r₁ and r₂ represent the random numbers [0; 1] and β is a constant and σ is given by $σ = {(\frac{Γ (1 + β) sin \frac{π β}{2}}{Γ (\frac{1 + β}{2}) * β * 2^{(\frac{β - 1}{2})}})}^{\frac{1}{β}}$ (11)

Pseudocode of DA for test schedule is shown below:

Initialize the core parameters of p22810 and d695

Initialize the population of dragonflies X_i = [X₁; X₂; X₃ ... Xn] depends on the benchmark

circuits p22810 and d695

Initialize X_i (i = 1; 2 ... n) step vectors

While (end condition not fulfilled)

Calculate the objective values of dragonfly’s

Update the food source.

Update s, c, a, f and e.

By using Equations (2) to (6) Calculate S, C, A, F, E

Update neighborhood radius

if at least one adjacent dragonfly is present in the current dragonfly

Update the velocity vector and position vector using Equation (7) & (8)

else Update the position vector Equation (9)

end if

Check and update new positions based on new variable boundary

end while

3.2 Ant Lion Optimization (ALO) algorithm

Ant Lion Optimization (ALO) algorithm [34 –36] is derived from natural behavior patterns and was introduced by Mirjalili. ALO has been shown to have good efficiency in solving optimization problems with the advantages of few parameters and high speed. The algorithm makes use of the hunting behavior of antlions. The antlions use sandpits to trap its prey, and the property of these pits depends on various parameters like availability of moonlight. The algorithm considers all these and highlights on five main steps which include (i) Capturing walking patterns of ants (prey), (ii) Antlion builds cone-shaped pits to catch ants, (iii) Trapping of ants/prey in cone-shaped pits, (iv) The preys get caught by antlion and gets eaten and (v) Finally antlion rebuilds traps based on various conditions. Antlions species come under the Myrmeleontidae family (family well known for hunting behavior of their larvae) and Neuroptera order (includes all net-winged insect). The pattern of cone-shape pits is another peculiar behavior of antlions and needs to be noted for the algorithm’s development. The cone trap’s size varies on dual scenarios - 1) Antlion hunger level and 2) Moonlight or Shape of the moon. The pit size is directly proportional to the moonlight. When there is more moon, the antlion prey has more visibility, and there are fewer chances of being caught. All of these are depicted in Fig. 5.

Fig. 5

Ant lions hunting behaviour - Pits for Catching prey and Influence of Moon.

For the development of the antlion optimization algorithm following steps are considered

Ants / Antlion prey move around in the sand space (area under consideration) using various random walks.

These random walks are taken and considered to be applied to all the areas on the sand.

Antlions create traps, and these walks of ants get impacted by the traps (sandpits) created by antlions.

Antlions build pits as per their energy level, which is considered as its fitness function.

Larger sand pits antlions have more chance/possibility of catching ants as their prey.

An antlion can trap every ant/prey in each of the iterations, and it is treated that the fittest gets caught.

he random walks are decreased effectively to emulate the sliding effect of ants towards antlions.

If an ant is a fitter than the antlion, it gets caught by the antlion. In this, the antlion pulls the ant under the sandpits.

After catching the ant, antlion makes into a new position (or improves existing sandpit) and makes necessary modifications on the existing sandpit to improve to catch another ant.

Ant Lion Algorithm Mathematical Model:

The mathematical model of random walks of ants are represented as $\begin{matrix} X (t) = [0, cumsum (2 r (t_{1}) - 1), cumsum (2 r \\ (t_{2}) - 1) . . . cumsum (2 r (t_{n}) - 1)] \end{matrix}$ (11)

Where

n, t indicates the total number of iterations and the random walk to the specific step of an ant.

cumsum, r(t) indicates the cumulative sum of random walks and the main function defined.

The position of ants concerning antlions is stored first. The following matrix indicates the same. $M_{Ant} = [\begin{matrix} A_{1, 1} & A_{1, 2} & \dots & A_{1, d} \\ A_{2, 1} & A_{2, 2} & \dots & A_{2, d} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ A_{n, 1} & A_{n, 2} & \dots & A_{n, d} \end{matrix}]$ (12)

Fitness of ants is considered as the probability of the same being caught by antlion. This fitness needs to be represented in a matrix as well. $M_{ObjAnt} = [\begin{matrix} \int A_{1, 1} & \int A_{1, 2} & \dots & \int A_{1, d} \\ \int A_{2, 1} & \int A_{2, 2} & \dots & \int A_{2, d} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ \int A_{n, 1} & \int A_{n, 2} & \dots & \int A_{n, d} \end{matrix}]$ (13)

In addition to ants’ behavior, it assumed that the antlions are also hidden in the area (cone-shaped pits). Their position becomes another critical criterion, and the same is depicted as follows. $M_{Antlion} = [\begin{matrix} {AL}_{1, 1} & {AL}_{1, 2} & \dots & {AL}_{1, d} \\ {AL}_{2, 1} & {AL}_{2, 2} & \dots & {AL}_{2, d} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ {AL}_{n, 1} & {AL}_{n, 2} & \dots & {AL}_{n, d} \end{matrix}]$ (14)

A fitness function for antlions is also to be considered for better treatment of use-case. M_ObjAntlion is treated as the matrix indicating the fitness function of each antlion $M_{ObjAntlion} = [\begin{matrix} \int {AL}_{1, 1} & \int {AL}_{1, 2} & \dots & \int {AL}_{1, d} \\ \int {AL}_{2, 1} & \int {AL}_{2, 2} & \dots & \int {AL}_{2, d} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ \int {AL}_{n, 1} & \int {AL}_{n, 2} & \dots & \int {AL}_{n, d} \end{matrix}]$ (15)

Another need is to maintain the random walk within the area chosen. A mix-max normalization technique is applied as indicated below. $X_{i}^{t} = \frac{(X_{i}^{t} - a) (d_{i} - C_{i}^{t})}{d_{i}^{t} - a_{i}} + C_{i}$ (16)

Where a_i is treated as the lowest of walks of variable i, d_i indicates the highest of the walk with variable i. $C_{i}^{t}$ indicates the lowest of an ith variable at tth iteration. $d_{i}^{t}$ indicates the highest of ith variable at tth iteration. This equation needs to be applied for each iteration. $C_{i}^{t} = {Antlion}_{j}^{t} + C^{t}$ (17) $d_{i}^{t} = {Antlion}_{j}^{t} + d^{t}$ (18)

This behavior’s mathematical model can be done by gradually reducing the diameter of the ant’s walk’s search area. The following equations are added to compensation. $c^{t} = \frac{c^{t}}{I}$ (19) $d^{t} = \frac{d^{t}}{I}$ (20) ${Antlion}_{j}^{t} = {Ant}_{i}^{t} if ({Ant}_{i}^{t}) > \int {Antlion}_{j}^{t}$ (21)

The present iteration, ${Antlion}_{j}^{t}$ represents the jth antlion position of selected at tth iteration. Every ant walk in random was encircled with the selected antlion. ${Ant}_{i}^{t} = \frac{R_{A}^{t} + R_{E}^{t}}{2}$ (22)

Where $R_{A}^{t}$ indicates ant walk around the antlion represented by the roulette wheel at the location of tth iteration, $R_{E}^{t}$ indicates the random walk around the elite at the location of tth iteration, ${Ant}_{i}^{t}$ indicates the position of ith ant at the position of tth iteration. While searching for food, the ant’s natural behaviour is to move at random. This random movement, termed as ‘random walk’ is considered. Thus, the random walk is considered and assumed, every ant’s random walk is around the elite antlion chosen by the roulette wheel. The roulette wheel is the process of selecting the fittest antlion with a probability proportional to fitness. Figure 6 explains the flowchart of ALO. The process starts with the initialization of d695and p22810 soc parameters followed by fitness calculation. The minimum fitness value is selected as elite. Check iteration condition and select the ant lion using roulette wheel. Evaluate the fitness value and update the ant lion and elite ant lion position if it is better than the previous one. The elite ant provides the optimal value and terminate the process

Fig. 6

Flowchart of ALO.

4 Results and discussions

The results are obtained using C# software using Visual Studio IDE. To demonstrate the effectiveness of the proposed solution for testing SoCs, we present experimental results for two ITC’02 benchmark SoCs: d695 and p22810. The benchmark circuit d695 contains 10 cores and p22810 contains 30 cores. The number of inputs, number of outputs, number of pins, the number of wrapper inputs, number of wrapper outputs, the number of scan chains, and the length of the scan chain are the details shown in the format of the d695 benchmark circuit. This benchmark circuit is given as input to the program and the optimization algorithms are implemented to find the minimum test application time. The testing time for individual cores when tested using the number of pins in an SoC is calculated. Provided a SoC with K TAM wires, a set of N cores, and a set of wrapper designs for each core, we expect to define the assignment of TAM wires to each core test and determine the test start time for each test so that the overall test time is minimized. Since at any point during the test, any TAM wire can only be assigned to one core for the test, the rectangles transformed from the test scheduling problem cannot overlap.

Table 2 shows the initialization of input parameters of DA and ALO for various TAM widths. Choice of these parameter values is a trade of between SoC testing time and TAM width available to test the cores. The values of the parameters are chosen such that improved SoC testing time is obtained. Overall test times have been calculated using proposed algorithms. Test scheduling algorithms are used to calculate the optimum test time for core based SOC system. While doing this, different parameters are also taken in to consideration. Figures 7 and 8 show the initialization of core for d695 and p22810 SoC benchmark circuits for TAM width W = 16 using the DA. Figures 9 and 10 show the initialization of core for d695 and p22810 SoC benchmark circuits for TAM width W = 16 using the ALO. Figures 5, 6, 7 and 8 show that for initialization of core, various parameters are taken as input, and they are initialized with a particular value. The figures show that the parameters are initialized, and the optimal test time can be calculated for the TAM width of 16 for both benchmark circuits.

Table 2
Input parameters of DA, ALO for core initialization

Proposed Algorithms DA ALO

Benchmarks D695 P22810 D695 P22810

No. of cores 10 30 10 30

Population Count 20 60 20 60

No. of iterations 100

TAM width 64, 56, 48, 40, 32, 24, 16

r₁ / r₂ / rand 0,1

s, a 0.1 Random walk size = 20

C 0.7

f, e 1

Inertia Factor 0.9–0.2

Proposed Algorithms	DA	ALO
Benchmarks	D695	P22810	D695	P22810
No. of cores	10	30	10	30
Population Count	20	60	20	60
No. of iterations	100
TAM width	64, 56, 48, 40, 32, 24, 16
r₁ / r₂ / rand	0,1
s, a	0.1	Random walk size = 20
C	0.7
f, e	1
Inertia Factor	0.9–0.2

Fig. 7

Initialization of DA for D695 SoC.

Fig. 8

Initialization of DA for P22810 SoC.

Fig. 9

Initialization of ALO for D695 SoC.

Fig. 10

Initialization of ALO for P22810 SoC.

Tables 3, 4 shows the test time comparison for d695 and p22810 SoC using different algorithms with various TAM widths such as 16, 24, 32, 40, 48, 56, 64. Among these algorithms, the DA algorithm reduces the test time of SoC for all the TAM widths considered to reduce the test cost. From Table 3 it is noted that proposed DA minimizes the test time to 89%, 63%, 49%, 36%, 59%, 54% and 9% than ACO, Modified ACO, ABC, Modified ABC, Firefly, Modified Firefly and BAT algorithms for d695 SoC benchmark circuit. Similarly, the proposed ALO minimizes the time for testing to 88%, 61%, 48%, 34%, 58%, 52%, and 7% than ACO, Modified ACO, ABC, Modified ABC, Firefly, Modified Firefly and BAT algorithms for d695 SoC benchmark circuit. From Table 4 it is noted that proposed DA minimizes the time for testing to 98%, 97%, 51%, 66%, 70%, 66% and 9% than ACO, Modified ACO, ABC, Modified ABC, Firefly, Modified Firefly and BAT algorithms for p22810 SoC benchmark circuit. Similarly, the proposed ALO minimizes the time for testing to 97%, 96%, 49%, 64%, 68%, 65%, and 7% than ACO, Modified ACO, ABC, Modified ABC, Firefly, Modified Firefly and BAT algorithms for p22810 SoC benchmark circuit. The proposed DA, ALO algorithms show the minimization of test time compared to ACO, Modified ACO, ABC, Modified ABC, Firefly, Modified Firefly, and BAT algorithms. Similarly, Figs. 11, 12 show the box plot of TAM width and test time of ALO for D695 and P22810 benchmarks. From the figures, it is observed that test time is reduced when the TAM width increases.

Table 3

Test Time Comparison for D695 SoC

TAM	ACO	Modified	ABC	Modified	Firefly	Modified	BAT	DA	ALO
Width (W)	[13]	ACO [15]	[13]	ABC [15]	[13]	Firefly [15]	[13]
W=16	0.124665	0.03778	0.027183	0.021583	0.033769	0.029798	0.015109	0.013795	0.014023
W=24	0.116116	0.037656	0.027072	0.021472	0.03337	0.028549	0.014902	0.013679	0.013981
W=32	0.116222	0.0361	0.027006	0.021416	0.033273	0.028706	0.014818	0.013661	0.013877
W=40	0.116406	0.038202	0.026977	0.021377	0.033179	0.029081	0.014799	0.013542	0.013761
W=48	0.116412	0.036792	0.026922	0.021327	0.033134	0.028727	0.014613	0.013428	0.013657
W=56	0.115731	0.03665	0.026808	0.021208	0.033049	0.02885	0.014493	0.013291	0.013541
W=64	0.115899	0.035986	0.026773	0.021173	0.033009	0.02849	0.014402	0.013188	0.013432

Table 4

Test Time Comparison for P22810 SoC

TAM	ACO	Modified	ABC	Modified	Firefly	Modified	BAT	DA	ALO
Width (W)	[13]	ACO [15]	[13]	ABC [15]	[13]	Firefly [15]	[13]
W=16	1.010569	0.958393	0.028118	0.02154	0.045942	0.042049	0.01542	0.014092	0.014334
W=24	0.992587	0.934244	0.028007	0.021567	0.045682	0.041512	0.015396	0.013991	0.014241
W=32	0.976376	0.900799	0.027767	0.021427	0.045074	0.041876	0.015322	0.013886	0.014144
W=40	0.973105	0.869147	0.026935	0.021265	0.044973	0.040888	0.015248	0.013803	0.014035
W=48	0.958831	0.840924	0.025931	0.02111	0.044532	0.040941	0.015194	0.013748	0.01393
W=56	0.950874	0.821869	0.025099	0.02101	0.044011	0.041019	0.015121	0.013635	0.013829
W=64	0.948847	0.819487	0.023997	0.020897	0.043711	0.041298	0.01501	0.013515	0.013711

Fig. 11

Box plot of DA.

Fig. 12

Box plot of ALO.

The results clearly show that proposed DA, ALO algorithms show the minimization of test time compared to ACO, Modified ACO, ABC, Modified ABC, Firefly, Modified Firefly, and BAT algorithms.

5 Conclusions and future work

This paper presented a solution for the test scheduling and TAM optimization problem using meta-heuristic algorithm. In this paper, Dragonfly and Ant Lion optimization algorithms have been successfully implemented to optimize the testing time in the two benchmark circuits. The testing time of the two proposed and other well-known algorithms are estimated for various TAM widths. The effectiveness of the proposed algorithms is tested by comparing it with various algorithms in testing time. Under varying TAM widths like 16, 24, 32, 40, 48, 56, and 64, it has been found that the testing time of the Dragonfly algorithm is lesser than other algorithms. It was observed that the testing time is reduced to 89%, 63%, 49%, 36%, 59%, 54% and 9% for d695 and 98%, 97%, 51%, 66%, 70%, 66% and 9% for p22810 when dragonfly algorithm is used when compared to ACO, Modified ACO, ABC, Modified ABC, Firefly, Modified Firefly, and BAT algorithms. Results of the ITC’02 benchmarks show that the Dragonfly algorithm was able to find optimal results in most cases as compared to other algorithms. The Dragonfly algorithm is best suited for test scheduling problems in SoCs, where the optimization is a very crucial task. Therefore, it may be concluded that the Dragonfly algorithm may be used to do scheduling in SoCs. In the future, algorithms like Emperor Penguins Colony, Random Forest Algorithm, Invasive Weed Optimization, and Tree-Seed Algorithms could be tested to minimize the test time.

Footnotes

Acknowledgments

The test bench is done in CEG, Anna University, and results collected from the same. We thank Prof. Dr. P. Sakthivel for his continuous support and guidance.

References

Ingelsson

, Goel

S.K.

, Larsson

and Marinissen

E.J.

, Abort-on-fail test scheduling for Modular SOCs without and with Preemption, IEEE Transactions on Computers 64 (2015), 3335–3347.

Chen

, Huang

and Knoll

, Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM combination, ACM Transactions on Embedded Computing Systems (TECS) 13 (2014), 1–21.

Kish

, Lal

, Evans

and Corzine

S.W.

, System-on-chip photonic integrated circuits, IEEE Journal of Selected Topics in Quantum Electronics 24 (2017), 1–20.

Iyengar

, Chakrabarty

and Marinissen

E.J.

, Efficient test access mechanism optimization for system-on-chip, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 22 (2003), 635–643.

Marinissen

E.J.

, Iyengar

, Chakrabarty

, A set of benchmarks for modular testing of SOCs, IEEE Proceedings International Test Conference, 2002, pp. 519–528.

Larsson

and Fujiwara

, System-on-chip test scheduling with reconfigurable core wrappers, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 14 (2006), 305–309.

Mahi

, Baykan

O.K.

and Kodaz

, A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem, Applied Soft Computing 30 (2015), 484–490.

Janakiraman

and Kumar

P.N.

, Multi-objective module partitioning design for dynamic and partial reconfigurable system-on-chip using genetic algorithm, Journal of Systems Architecture 60 (2014), 119–139.

Tsai

C.C.

, Huang

H.C.

and Chan

C.K.

, Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation, IEEE Transactions on Industrial Electronics 58 (2011), 4813–4821.

10.

Dorigo

, Birattari

and Stutzle

, Ant colony optimization, IEEE Computational Intelligence Magazine 1 (2006), 28–39.

11.

Ahn

J.H.

, Kang

, SoC test scheduling algorithm using ACO-based rectangle packing, Computational Intelligence 2006, pp. 655–660.

12.

Yang

and Zhuang

, An improved ant colony optimization algorithm for solving a complex combinatorial optimization problem, Applied Soft Computing 10 (2010), 653–660.

13.

Chandrasekaran

, Periyasamy

and Rajamanickam

K.P.

, Minimization of test time in system on chip using artificial intelligence-based test scheduling techniques, Neural Computing and Applications 32 (2020), 5303–5312.

14.

Karaboga

and Akay

, A comparative study of artificial bee colony algorithm, Applied Mathematics and Computation 214 (2009), 108–132.

15.

Akay

and Karaboga

, A modified artificial bee colony algorithm for real-parameter optimization, Information Sciences 192 (2012), 120–142.

16.

Chandrasekaran

, Periyasamy

and Rajamanickam

K.P.

, Test scheduling for system on chip using modified firefly and modified ABC algorithms, SN Applied Sciences 1 (2019), 1079.

17.

Yang

X.S.

, Multiobjective firefly algorithm for continuous optimization, Engineering with Computers 29 (2013), 175–184.

18.

Wang

G.G.

, Guo

, Duan

and Wang

, A new improved firefly algorithm for global numerical optimization, Journal of Computational and Theoretical Nanoscience 11 (2014), 477–485.

19.

Yang

X.S.

, Gandomi

A.H.

, Bat algorithm: a novel approach for global engineering optimization, Engineering Computations, 2012.

20.

Chakrapani

, Saravanan

and Muthaiah

, Three-Coding Test Compression Technique for SoC Based Design, ARPN Journal of Engineering and Applied Sciences 12 (2017), 6183–6191.

21.

Zhang

, Mei

and Yan

, A new test set compression scheme for circular scan, EURASIP Journal on Embedded Systems 2018 (2018), 1–5.

22.

Thilagavathi

and Sivanantham

, Two-Stage low power test data compression for digital VLSI circuits, Elsevier-Computers & Electrical Engineering 71 (2018), 309–320.

23.

Cai

, Zhou

, Liu

, Yu

and Wang

, A novel test data compression approach based on bit reversion, IEICE Electronics Express 14 (2017), 1–11.

24.

Lee

, Touba

N.A.

and Yang

, Enhancing Test Compression with Dependency Analysis for Multiple Expansion Ratios, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 36 (2017), 1571–1579.

25.

Larsson

, Larsson

, Eles

, Zebo

, Optimized integration of test compression and sharing for SOC testing, Design, Automation & Test in Europe Conference & Exhibition, 2007, 1–6.

26.

Wang

, Chakrabarty

and Wang

, Integrated LFSR reseeding, test-access optimization, and test scheduling for core-based system-on-chip, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 28 (2009), 1251–1264.

27.

Shahabi

, Pourahangarian

, Edalatpanah

S.A.

and Beheshti

, A multilevel image thresholding approach based on crow search algorithm and Otsu method, International Journal of Computational Intelligence and Applications 19 (2020), 33–41.

28.

Najafi

H.S.

and Edalatpanah

S.A.

, A note on A new method for solving fully fuzzy linear programming problems, Applied Mathematical Modelling 37 (2013), 7865–7867.

29.

Yao

, Saluja

K.K.

and Ramanathan

, Power and thermal constrained test scheduling under deep submicron technologies, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 30 (2011), 317–322.

30.

Goel

, Marinissen

E.J.

, Sehgal

and Krishnendu

, Testing of SoCs with hierarchical cores: common fallacies, test access optimization, and test scheduling, IEEE Transactions on Computers 58 (2008), 409–423.

31.

Giri

, Tipparthi

D.K.R.

, Chakrabarty

, Genetic algorithm based approach for hierarchical SOC test scheduling, IEEE International Conference on Computing: Theory and Applications (ICCTA’07), 2007, 141–145.

32.

Mirjalili

, Dragonfly algorithm: a new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems, Neural Computing and Applications 27 (2016), 1053–1073.

33.

Mafarja

, Aljarah

, Heidari

A.A.

, Faris

, Fournier-Viger

, Li

and Mirjalili

, Binary dragonfly optimization for feature selection using time-varying transfer functions, Knowledge-Based Systems 161 (2018), 185–204.

34.

Mirjalili

, The ant lion optimizer, Advances in Engineering Software 83 (2015), 80–98.

35.

Mirjalili

, Jangir

and Saremi

, Multi-objective ant lion optimizer: a multi-objective optimization algorithm for solving engineering problems, Applied Intelligence 46 (2017), 79–95.

36.

Ali

E.S.

, Elazim

S.A.

and Abdelaziz

A.Y.

, Ant lion optimization algorithm for renewable distributed generations, Energy 116 (2016), 445–458.