sessions being preemptive or nonpreemptive. To start with, a few definitions
are presented that are used in the algorithm:
1. A set C = {i, 1 ≤ i ≤ N c } of cores in the NoC.
2. A set T = {T ji , 1 ≤ j ≤ N ti , 1 ≤ i ≤ N c } of test sessions for the cores in C.
Each core i can have N ti test sessions, each of which can be BISTed,
external, preemptive, or nonpreemptive.
3. For each test session k, a six-tuple I = {(wc, cl, p, pwr, preemp, payload) k ,
1 ≤ k ≤ |T|} is defined, where wc is the number of wrapper scan
chains, cl is the maximum length of scan chains, p is the number
of test patterns, pwr is the power consumption during test, preemp
indicates whether the test is preemptive or not, and payload is the
size of the test packet.
4. A set Prec = {(p 1 ,…, p n ) k , 1 ≤ n, k ≤ |T|} of precedence constraints for
each test session k. For any test to be scheduled, all test sessions in its
precedence list must have been finished.
5. A graph G = (V,E) corresponding to the topology of the NoC. Each
vertex corresponds to a router to which a number of cores may
be connected. An edge corresponds to a communication channel
between the two routers for the vertices.
6. A list of I/O ports corresponding to some vertices in G, indicating
that these cores can be used as I/O ports during testing.
The scheduling process first creates an ordered list of test sessions and a list of
I/O pairs. For each core, a list of possible access paths is created, sorted by the
number of routers on each path. While allocating a path to a core for test, the
availability of shorter paths is checked earlier than longer ones. Once a test
packet p is picked up for scheduling, one of the following situations can occur.
256
Network-on-Chip
1. p belongs to a nonpreemptive test: The first available I/O pair that can
be used by this packet is chosen. If no such I/O pair is available, the
next ready packet is picked up for scheduling. The delivery time of
packet p is set to the time when the first I/O pair in the list becomes
available. If an I/O pair is available, the entire test session to which
p belongs to gets scheduled (since the test is nonpreemptive). Power
consumption of the packet is calculated. It is checked that no power
violation occurs in the duration for which the test session runs. The
network channels identified by the I/O pair are marked unavailable during the transmission time of the packet. The corresponding
response packet is then automatically scheduled.
2. p belongs to a preemptive test: The shortest available path for this packet
is selected and the duration for its transmission is calculated. If no
path is available for p, the next ready packet is picked up for possible
are presented that are used in the algorithm:
1. A set C = {i, 1 ≤ i ≤ N c } of cores in the NoC.
2. A set T = {T ji , 1 ≤ j ≤ N ti , 1 ≤ i ≤ N c } of test sessions for the cores in C.
Each core i can have N ti test sessions, each of which can be BISTed,
external, preemptive, or nonpreemptive.
3. For each test session k, a six-tuple I = {(wc, cl, p, pwr, preemp, payload) k ,
1 ≤ k ≤ |T|} is defined, where wc is the number of wrapper scan
chains, cl is the maximum length of scan chains, p is the number
of test patterns, pwr is the power consumption during test, preemp
indicates whether the test is preemptive or not, and payload is the
size of the test packet.
4. A set Prec = {(p 1 ,…, p n ) k , 1 ≤ n, k ≤ |T|} of precedence constraints for
each test session k. For any test to be scheduled, all test sessions in its
precedence list must have been finished.
5. A graph G = (V,E) corresponding to the topology of the NoC. Each
vertex corresponds to a router to which a number of cores may
be connected. An edge corresponds to a communication channel
between the two routers for the vertices.
6. A list of I/O ports corresponding to some vertices in G, indicating
that these cores can be used as I/O ports during testing.
The scheduling process first creates an ordered list of test sessions and a list of
I/O pairs. For each core, a list of possible access paths is created, sorted by the
number of routers on each path. While allocating a path to a core for test, the
availability of shorter paths is checked earlier than longer ones. Once a test
packet p is picked up for scheduling, one of the following situations can occur.
256
Network-on-Chip
1. p belongs to a nonpreemptive test: The first available I/O pair that can
be used by this packet is chosen. If no such I/O pair is available, the
next ready packet is picked up for scheduling. The delivery time of
packet p is set to the time when the first I/O pair in the list becomes
available. If an I/O pair is available, the entire test session to which
p belongs to gets scheduled (since the test is nonpreemptive). Power
consumption of the packet is calculated. It is checked that no power
violation occurs in the duration for which the test session runs. The
network channels identified by the I/O pair are marked unavailable during the transmission time of the packet. The corresponding
response packet is then automatically scheduled.
2. p belongs to a preemptive test: The shortest available path for this packet
is selected and the duration for its transmission is calculated. If no
path is available for p, the next ready packet is picked up for possible