See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/224310146

Integrated test scheduling, wrapper design, and TAM assignment for

hierarchical SOC

Conference Paper in Midwest Symposium on Circuits and Systems · September 2007

DOI: 10.1109/MWSCAS.2007.4488807 · Source: IEEE Xplore

CITATIONS READS
3 61

2 authors:

Haidar M. Harmanani Rana Farah

Lebanese American University Polytechnique Montréal
97 PUBLICATIONS 1,024 CITATIONS 22 PUBLICATIONS 150 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Rana Farah on 23 September 2014.

The user has requested enhancement of the downloaded file.

 Integrated Test Scheduling, Wrapper Design, and
TAM Assignment for Hierarchical SOC
Haidar M. Harmanani and Rana Farah
Department of Computer Science and Mathematics
Lebanese American University
Byblos, 1401 2010, Lebanon

Abstract— System-On-Chip (SOCs) test minimization has re- however, this assumption is only valid if the embedded cores
ceived a lot of attention in the past few years. However, most are mergeable. Iyengar et al. [6] first formulated the integrated
recent work assumed flat hierarchy. This assumption is unrealistic wrapper/TAM optimization problem using ILP and developed
especially in the case of non-mergeable legacy cores that have been
placed and routed. This paper presents an efficient approach later several heuristic techniques using rectangle packaging
for test scheduling hierarchical core-based systems based on [7]. Goel et al. [4] proposed an efficient heuristic for fixed-
simulated annealing. The method minimizes the overall test width architecture while Huang et al. [5] modeled the problem
application time while performing wrapper design and TAM as a restricted 3-D bin packing problem and proposed a
assignment. We present experimental results for various SOC heuristic to solve it. Su et al. [12] formulated the problem
examples that demonstrate the effectiveness of our method.
using graph-based approach and solved it using tabu search.
I. I NTRODUCTION Zou et al. [16] used sequence pairs to represent bins placement
and optimized the test schedule using simulated annealing;
The design and manufacturing methods of integrated circuits however, the approach is not constraint-driven. Pouget et
have known advances allowing the creation of a complete sys- al. [9] proposed a constraint-driven wrapper design and test
tem on a single die. In order to keep pace with such advances, scheduling. However, the method did not support hierarchical
hardware engineers have adopted reuse methodologies where SOCs. Recently, Chakrabarty et al. [3] proposed a combina-
predesigned and preverified intellectual property blocks are tion of integer linear programming, enumeration and efficient
embedded on a single chip (SOC) [10]. A core maybe soft, heuristics in order to solve the problem for hierarchical cores.
firm, or hard. Typically, soft and firm cores are mergeable with Xu et al. [14] proposed a method for design space exploration
their surrounding logic while hard cores are usually placed and of multi-level test access mechanism that facilitates test data
routed and are consequently non-mergeable. A core maybe reuse for hard mega-cores in hierarchical SOCs.
designed in a hierarchical fashion and thus embeds other cores.
Hierarchical cores have multiple levels of test hierarchy where II. P ROBLEM D ESCRIPTION
a level corresponds to the depth in the test hierarchy tree. The The test time of a SOC is based on the individual cores test
top level is the SOC itself and consists of several mega-cores time as well as on the determination of test start times. The
that have their own non-mergeable embedded cores. Cores at cores test times are based on TAM assignments as well as on
level n are called parent cores with respect to child cores the wrapper design. The number of wrapper scan chains should
at level n + 1 [11]. A major challenge in the SOC design be equal to the TAM width provided to the core. Typically,
paradigm involves integrating IP blocks and developing a test test adaptation is performed by serially connecting internal
methodology for post-manufacturing tests in addition to test core scan-chains, the wrapper input cells and the wrapper
time reduction by maximizing the simultaneous test of all output cells in order to form wrapper chains [2]. The length
cores. The problem, known as test scheduling, determines the of the wrapper chains directly affects the core’s test time
order in which cores are tested and is equivalent to the N P- since short wrapper chains lead to a short loading/unloading
complete m-processor open shop scheduling problem [1]. time. The number of wrapper chains, on the other hand,
Simulated Annealing is a global stochastic method that affects the number of TAM bits as each wrapper chain’s
is used to generate approximate solutions to combinatorial input and output must be connected to a TAM wire. Thus,
problems. The algorithm begins with an initial feasible con- there is a clear trade-off between test time and the TAM
figuration and generates a neighboring solution by perturbing capacity. However, increasing the number of TAM bits may
the current one. The neighboring solution is accepted if its not necessarily guarantee decreasing test time as the test time
cost is less than that of the current solution; otherwise, it is may hit a Pareto optimal point [7]. Furthermore, embedding
accepted or rejected with a probability which is a function of cores adds an additional test conflict problem arising from
the temperature, T . The temperature is decreased during the the fact that it may not be possible to test the parent and
optimization process following a cooling schedule. the child cores concurrently due, for example, to a conflict
Several researchers addressed the test scheduling problem in the use of the input wrapper cells. Therefore, an effective
but mostly assumed flat cores with a single level TAM [15]; test scheduling approach must minimize the test time while
 Assign TAM(Core i)

TAM
Core index
{
max(pi ,po )
1 2 ... n
Core’s test
start time
T AM = number of scan-chains + longest scan chain
if (TAM > maxTAM)
S1
S2 ... Sn TAM = maxTAM
if the core is not level 0 and has less than two peers, then TAM = TAMparent
Test Time
if the core is at level n and has more than one peer then
er TAM = 0.5 * TAMparent
w
Po

If a core is dominant, TAM = TAM + number of peer cores.

if a core is test dominant then TAM = TAM + number of peer cores
Fig. 1. Configuration representation }

Fig. 2. Hierarchical TAM assignment algorithm

addressing test resources allocation and conflicts arising from
the use of shared test access mechanism.
This paper presents an efficient method for integrated test the minimum number of balanced wrapper chains and are
minimization, TAM assignment and wrapper design for hier- adapted to the number of assigned TAM bits using the BFD
archical SOCs using simulated annealing. Formally, given a algorithm. The test time for core i is determined based on
SOC with NC cores, a total TAM width W, a set of design ti = (1 + max(si , so )) × p + min(si , so ) where, si and so
and test constraints, and a set of parameters for each mega- denote respectively the scan-in and scan-out time for the core
core, the problem we address in this paper is to minimize the and pi denotes the number of test patterns applied on the
overall test time such that, (i) the test schedule for the entire core i [8]. The algorithm ensures that all cores test times
SOC is efficient, (ii) the TAM wires are optimally partitioned are less than the lower bound by allocating additional TAM
and assigned to cores (iii) the wrapper configuration for each bits. The initial test schedule is next chosen to be a serial
core is determined, (iv) W is not exceeded, and (v) hierarchical schedule. However, when considering precedence constraints,
cores receive at least their prespecified TAM widths. the initial solution is chosen based on the topological sorting
The remainder of the paper is organized as follows. Section of all tests represented in the precedence constraint graph. The
3 formulates the hierarchical SOC test scheduling problem and result of our topological sorting is a valid serial solution when
describes the annealing configuration, the initial solution, the precedence constraints are incorporated.
neighborhood functions, and the test scheduling algorithm. We
conclude with experimental results in section 4. C. Neighborhood Functions
The algorithm iterates exploring test scheduling possibili-
III. I NTEGRATED T EST S CHEDULING A LGORITHM
ties, TAM assignment, and wrapper configuration using three
The proposed test scheduling method starts with a set of neighborhood solutions. The neighborhood functions are ap-
cores and generates, through a sequence of transformations, a plied while ensuring precedence and concurrency constraints.
set of compact and efficient test schedules. We explore design
1) Test Schedule Exploration where the algorithm randomly
trade-offs by integrating test scheduling, wrapper design and
selects a random core i from the current configuration
TAM assignment into a single problem that we solve using
and changes its starting time Si to the end time Fj of a
a multi-objective simulated annealing algorithm that supports
randomly chosen core j (i 6= j), 0 ≤ i, j ≤ Nc . If core
both flat and hierarchical SOC test scheduling.
j is selected such that j = Nc + 1, then the start time
A. Configuration Representation of core i is set to be a 0.
The test minimization problem is mapped to an initial 2) Test Schedule Swap where the algorithm randomly se-
configuration based on a vector where every cell corresponds lects two cores and swaps their test start time.
to a 3-D core as shown in Figure 1. The first dimension 3) TAM Exploration where the algorithm P finds all testing
corresponds to a specific test start time, Si , the second paths in the schedule such that Cj > LBT where
dimension corresponds to TAM width and the third dimen- Cj is the test time for core j and LBT is the lower
sion corresponds to the maximum power that the core may bound. The algorithm allocates additional TAM bits to
consume. The core test finish time, Fi , is equal to the test all cores until they reach the next Pareto-optimal point
start time plus the core test time, Ti , that is, Fi = Ti + Si . and selects the core that has the highest rate of test time
Note that the test start time, Si , is not constant and it changes improvement with respect to TAM bits.
to the end times of other cores as the algorithm explores the The neighborhood functions are followed by two determin-
neighborhood of the solution. istic transformations that compact the schedule by removing
idle slots.
B. Initial Configuration
The initial configuration is chosen by assigning each core D. Hierarchical Test Scheduling
one bit TAM and computing the theoretical test time lower The hierarchical core model is a recursive model where
bound, LBT , in order to guide the test minimization pro- a wrapped parent core has an external TAM that connects
cess. The wrapper input cells, the core scan-chains, and the externally to the parent core and an internal TAM that consists
wrapper output cells are serially connected in order to form of the TAM architecture of the children cores. We start with
 Annealing TestScheduling() assigned more than the TAM bits of its parent. Once the TAM
{
M axT ime = Total allowed time for the annealing process assignment is performed, the wrapper design is determined
Assign one TAM bit to each core. Compute the Core test time, Ci . using the BFD algorithm.
Design the Core Wrapper using the BFD algorithm.
do { Once the TAM has been assigned, the algorithm iterates
M = M0 over each mega-core using our simulated annealing in order
do {
if (iteration % 10 == 0) to determine the test schedule as well as the wrapper design
NewS = TestScheduleSwap(CurrentS); for the mega-core itself (Figure 4). On the other hand, test data
else if (iteration % 11 == 0)
NewS = TAMExplore(CurrentS); serialization maybe necessary since a mega-core width maybe
else NewS = TestScheduleExplore(CurrentS); assigned less than the TAM width it requires. Thus, a mega-
NewCost=Cost(NewS)
∆Cost = N ewCost − CurrentCost core i with top-level TAM width wi maybe provided with wi∗
if (∆Cost < 0)
{
TAM bits such that wi∗ ≤ wi . The test time for mega-core i
wi
CurrentS=NewS then reduces to Ti∗ = d w ∗ e ∗ Ti where Ti is the total testing
i
CurrentCost=Cost(CurrentS);
If (N ewCost < BestCost) then
time for the embedded cores on the internal TAM partition
BestS=NewS for mega-core i. Finally, the testing time for mega-core i must
BestCost = Cost(BestS)
}
include ∗the test time for the top-level test time and this reduces
W W∗
else if (Random < e− T
∆Cost
then // T = temperature
to: Ti i = Ti∗ + TiM ega where Ti i is the testing time for
CurrentS=NewS mega-core i with an external TAM of width wi∗ and TiM ega
CurrentCost = Cost(CurrentS);
M =M −1 is the testing time at the system level TAM architecture. Once
} while (M ≥ 1) // M is time until next parameter update all cores at level i have been processed, the algorithm recurses
T ime = T ime + M0 ;
T = α ∗T ; // α = Cooling rate back to level i − 1 and considers the remaining mega-cores.
M0 = β ∗ M0 ; // β = Iteration multiplier The process repeats until all cores have been scheduled.
} while (Time < MaxTime);
CompactSchedule(BestS); The last step of the algorithm is to explore further improve-
Return(BestS); ments by iterating over the schedule for n iterations (n = 100).
}
During each iteration, the algorithm selects a random core
from any level of the SOC hierarchy and applies one of two
Fig. 3. Annealing SOC test scheduling algorithm
transformations based on a random probability. The first frees
m TAM-bits by moving the core’s test time to the previous
Hierarchical Test Schedule() Pareto-optimal point. The second reduces the core’s test time
{
for all levels starting from level n − 1 to level 0 by adding p TAM-bits and moving to the next Pareto-optimal
find all mega cores point. If the move results with an improvement, then the SOC
for each mega core
assign TAM bits for the children cores is test scheduled using the annealing algorithm. If the affected
calculate the test time for each child core core is a child core then all its parents are updated accordingly.
use simulated annealing to find the schedule for the children cores
calculate overall test time
if (level == 0) IV. R ESULTS
calculate the overall time of the SOC.
for (i = 0; i < n; i + +) We ran the test scheduling algorithm for flat as well as for
Select a random core i from any level
Randomly increase/decrease TAM bits in order to move to the hierarchical SOCs. The ITC’02 benchmark suite has only four
next/previous Pareto-optimal point. benchmarks with a hierarchical structure which are shown in
¿ If the transformation is accepted then
simulated annealing(); Table I and are compared to [3], [13], [14]. The TAM widths
Update Ti and all parents cores that contain this core. supplied to the mega-cores were fixed at 8 bits for SOCs
}
p22810 and a586710, and at 16 bits for SOCs p34392 and
p93791. As it is shown, our system clearly outperforms other
Fig. 4. Hierarchical test scheduling algorithm
systems in almost all attempted cases in a very short time.
For flat SOCs, the algorithm assumes that all cores are at
the same level with the ITC benchmark results for flat SOCs
the mega-cores that are at level n where each mega-core is shown in Table II. The CPU time did not exceed 1.31 minutes.
considered as a separate SOC. The embedded child cores The simulated annealing cooling schedule was experimentally
are initially assigned TAMs based on the algorithm shown determined as follows: the temperature reduction multiplier,
in Figure 2 where we define a dominant core as a core such α = 0.99 and Tinit = 4000. The stopping criterion was
that when allocated the same TAM width as all its peers it T ≤ 0.001 while the number of iterations, M , was set to
returns a larger test time than its peers. For cores that are 5 and the the iteration multiplier, β, to 1.05.
at level n and that have more than one peer, the algorithm
allocates half the TAM bits of the parents to the child cores.
However, the number of allocated TAM bits may change in R EFERENCES
the iterative part of the annealing process. During the TAM
[1] K. Chakrabarty. Test Scheduling for Core-Based Systems Using Mixed-
assignment process, the algorithm ensures that no mega-core is Integer Linear Programming. IEEE Trans. on CAD, 19(10):1163–1174,
assigned more than the specified TAM bits and that no core is 2000.
 SOC W [14] [13] [3] Ours SOC W [4] [5] [12] [16] [9] Ours
d695 16 44307 42716 41905 41604 41847 42382
a586710 16 5.27 ×107 – 4.44 ×107 42117546 24 28576 28639 28231 28064 29106 29103
24 3.06 ×107 – 3.06×107 22973206 32 21518 21389 21467 21161 20512 21456
40 17617 17366 17308 16993 18691 17480
32 2.19 ×107 – 2.28 ×107 21058772 48 14608 15142 14643 14182 17257 14779
40 1.91 ×107 – 2.50 ×107 17229905 56 12462 13208 12493 12085 – 12708
48 1.53 ×107 – 2.14×107 13401037 g1023
64
16
11033
34459
11279
31444
11036
32602
10723
31139
13348
-
11069
31777
56 – 2.14 ×107 13031723 24 22821 21409 22005 21024 - 20261
64 1.41 ×107 2.14 ×107 13031723 32 16855 16489 17422 15890 - 16332
40 14794 14794 14794 14794 - 14794
p93791 16 1865140 – – 1953223 48 14794 14794 14794 14794 - 14794
24 1486628 – 1650880 1377332 56 14794 14794 14794 14794 - 14794
32 1486628 1937130 1021320 991915 64 14794 14794 14794 14794 - 14794
p22810 16 458068 446684 465162 438619 473418 464809
40 801271 – 916852 845391 24 299718 300723 317761 289287 352834 310456
48 801271 1272314 681816 670660 32 222471 223462 236796 218855 236186 233101
56 – – 632125 629510 40 190995 184951 193696 175946 195733 197566
48 160221 167858 174491 147944 159994 166169
64 553775 947554 521064 545583 56 145417 145087 155730 126947 – 145417
p22810 16 496804 – 505858 496146 64 133405 128512 145417 109591 128332 123543
p34392 16 1010821 1016640 995739 944768 - 940626
24 353619 – 412682 334202 24 680411 681745 690425 628602 - 637263
32 280634 466044 396473 280634 32 551778 553713 544579 544579 - 544579
40 280634 – 366260 280634 40 544579 544579 544579 544579 - 544579
48 544579 544579 544579 544579 - 544579
48 280634 338374 366260 280634 56 544579 544579 544579 544579 - 544579
56 – – – 280634 64 544579 544579 544579 544579 - 544579
64 280634 285231 366260 280634 p93791 16 1791638 1791860 1767248 1757452 1827819 1777840
24 1185434 1200157 1178776 1169945 1220469 1204168
p34392 16 1467705 – – 1188916 32 912233 900798 906153 878493 945425 943087
24 1467705 – 1347023 778273 40 718005 719880 737624 718005 787588 760868
32 776537 – 788873 713071 48 601450 607955 608285 594575 639217 638993
56 528925 521168 539800 509041 – 557890
40 776537 – 728426 606261 64 455738 549233 485031 447974 457862 489591
48 60261 – 618597 606261 u226 16 18663 13416 18663 13333 – 13333
56 – 618597 606261 24 13331 10750 14745 8084 – 8084
32 10665 6746 10665 6746 – 6746
64 60261 – 618597 606261 40 8084 5332 8084 5332 – 5332
48 7999 5332 7999 5332 – 5332
56 7999 4080 7999 4080 – 4080
TABLE I 64 7999 4080 7999 4080 – 4080
f2126 16 372125 357109 357089 357088 – 357088
H IERARCHICAL ITC’02 SOC RESULTS COMPARISONS 24 335334 335334 335334 335334 – 335334
32 335334 335334 335334 335334 – 335334
40 335334 335334 335334 335334 – 335334
48 335334 335334 335334 335334 – 335334
56 335334 335334 335334 335334 – 335334
64 335334 335334 335334 335334 – 335334
t512505 16 10530995 10531003 11210100 10530995 – 10530995
24 10453470 10453470 10525823 10453470 – 10453470
[2] K. Chakrabarty, V. Iyengar, and A. Chandra. Test resource Partitioning 32 5268868 5268872 6370809 5268868 – 5268868
for System-On-a-Chip. Kluwer Academic Publishers, 2002. 40 5228420 5228420 5240493 5228420 – 5228420
48 5228420 5228420 5239111 5228420 – 5228420
[3] K. Chakrabarty, V. Iyengar, and M. Krasniewski. Test Planning for 56 5228420 5228420 5228474 5228420 – 5228420
Modular Testing of Hierarchical SOCs. IEEE Trans. CAD, 24(3):435– 64 5228420 5228420 5228489 5228420 – 5228420
a586710 16 41523868 42198943 42067708 32626782 – 32417445
448, 2005. 24 28716501 27785885 27907180 23413604 – 22973206
[4] S.K. Goel and E.J. Marinissen. SOC Test Scheduling Design for 32 22475033 21735586 22704821 18838663 – 17195389
40 19048835 19041307 19041307 14260216 – 14249791
Efficient Utilization of Bandwidth. ACM TODAES, 8(4):399–429, 2003. 48 15315476 15071730 15212440 12811087 – 12811087
[5] Y. Huang, S.M. Reddy, W.-T. Cheng, P. Reuter, N. Mukherjee, C. Tsai, 56 13415476 14945057 13401034 12573448 – 1148660
64 12700205 12754584 11567464 10659014 – 9572169
O. Samman, and Y. Zaidan. Optimal Core Wrapper Width Selection d281 16 8444 7948 8156 7946 – 7347
and SOC Test Scheduling on 3-D Bin Packing Algorithm. In Proc. 24 6408 5486 5830 5485 – 4992
32 5084 4070 4640 4070 – 3926
ITC, pages 74–82, 2002. 40 3964 3926 3926 3926 – 3926
[6] V. Iyengar, K. Chakrabarty, and E. Marinissen. Test Wrapper and Test 48 3926 3926 3926 3926 – 3926
56 3926 3926 3926 3926 – 3926
Access Mechanism Co-Optimization for System-On-a-Chip. JETTA, 64 3926 3926 3926 3926 – 3926
18:213–230, 2002.
[7] V. Iyengar, K. Chakrabarty, and E. J. Marinissen. On Using Rectangle TABLE II
Packing for SOC Wrapper/TAM Co-Optimization. In Proc. VTS, pages
253–258, 2002. F LAT ITC’02 SOC RESULTS COMPARISONS
[8] E.J. Marinissen, S.K. Goel, and M. Lousberg. Wrapper Design for
Embedded Core Test. In Proc. ITC, pages 911–920, 2000.

24 16
[9] J. Pouget, E. Larsson, and Z. Peng. Multiple-Constraint Driven System-
13
on-Chip Time Optimization. JETTA, pages 599–611, 2005.
20
[10] R. Saleh, S. Wilton, S. Mirabbasi, A. Hu, M. Greenstreet, G. lemieux,
8
P. Pande, C Grecu, and A. Ivanov. System-on-Chip: Reuse and
Integration. Proceedings of the IEEE, 94(6):1050–1069, 2006.
5
16
[11] A. Sehgal, S.K. Goel, E.J. Marinissen, and K. Chakrabarty. IEEE P1500-
Compliant Test Wrapper Design for Hierarchical Cores. In Proc. ITC,
pages 1203–1212, 2004.
102565
103938
105009
106545

110906
59584

86357

[12] C. Su and C. Wu. A Graph-Based Approach to Power-Constrained Test

(b)
8 Scheduling. JETTA, 20:45–60, 2004.
16
15
14
[13] T.-P. Wang, C-Y. Tsai, M.-D. Shieh, and K.-J. Lee. Efficient Test
13
Scheduling for Hierarchical Core Based Designs. In Proc. VLSI-TSA-
8
DAT, pages 200–203, 2005.
[14] Q. Xu and N. Nicolici. Time/Area Tardeoffs in Testing Hierarchical
13322
13623
15853

23535

24833
27191
27857

SOCs with Hard Mega-Cores. In Proc. ITC, pages 1196–1202, 2004.

404970

575246
761887
778273

(a)
[15] Q. Xu and N. Nicolici. Resource-Constrained System-On-a-Chip Test:
(c)
A Survey. IEE Proceedings, 152(1):67–81, 2005.
[16] W. Zou, S. R. Reddy, I. Pomeranz, and Y. Huang. SOC Test Scheduling
Fig. 5. a) Hierarchical test schedule for p34392; b) Mega-core 2 test schedule; Using Simulated Annealing. In Proc. VTS, pages 325–330, 2003.
c) Mega-core 1 test schedule

View publication stats