Preemptive Test Scheduling for Network-on-Chip Using Particle Swarm Optimization - VLSI Design and Test - page 79

5.1 Particle Structure and Fitness Calculation
The individual particles of the formulated PSO consists of three parts (shown in
Fig. 2) - the core part ,the I/O pair part and the preemption part . For an NoC
with n cores, each part has got n entries in it. The core part is a permutation of
numbers 1 through n , identifying the order in which the scheduler will attempt
to schedule the testing of cores. If the NoC has k number of I/O pairs, the i th
entry in I/O pair part identifies the I/O pair through which core i will be tested.
Each preemption part entry is a number between 0 and 1 . For non-preemptive
cores, the entry is always 1 . For a preemptive core, if the corresponding entry
is x and the core has a total of m test patterns, x

m number of patterns will
be tested as a single block. Thus, testing of entire core is distributed over a
number of blocks, each block being scheduled independent of others. However,
since the same I/O pair is attached to the core in each test session, the same
routing resources will be utilized for them. The overall test time resulting from
the scheduling of all cores is the fitness of the particle.

∗

5.2 Evolution Process
The initial population of particles is generated randomly, their fitness values
are computed and the gbest particle is identified. Local best for each particle is
taken to be the same as the particle itself. To evolve particles of generation i
to generate i + 1, evolution using both continuous and discrete PSO policy are
utilized. The core part and the I/O pair part evolve via discrete PSO, while the
preemption part evolves via continuous PSO. The evolution process continues till
either a maximum number of generations has been evolved, or, the best solution
does not improve over a pre-decided number of generations.

Tabl e 1. Test scheduling result for 10% preemptive cores

SoC Number of I/O ports

(2,2) (3,3) (4,4)
PSO Heu. [2] PSO Heu. [2] PSO Heu. [2]

d695(10) 19618 20815 13238 14633 10104 12368

g1023(14) 29117 29608 18880 20543 14794 18248

p22810(28) 290125 313582 187800 223021 141630 175275

p34392(19) 263172 321815 176322 260332 162626 188035

p93791(32) 318199 346219 204424 235398 150200 193033

t512505(31) 500222 613211 330579 402660 249130 412922

Avg.% improvement 9.9 16.1 22

6 Result for ITC'02 Benchmarks

The experimental results have been shown in this section for some ITC'02 bench-
marks [5]. Mesh based topology has been used for this experiment. We have run