Incremental Multiple-Scan Chain Ordering for ECO Flip-Flop Insertion

Incremental Multiple-Scan Chain Ordering for ECO Flip-Flop Insertion Andrew B. Kahng, Ilgweon Kang and Siddhartha Nath VLSI CAD LABORATORY, UC San Diego 32ndIEEE/ACM International Conference on Computer-Aided Design November 20th, 2013 UC San Diego / VLSI CAD Laboratory

Outline Motivation Related Work Problem Formulations IMSCO Flow Experimental Results Conclusions and Future Works -2-

Motivation Engineering Change Orders (ECOs) are IC design changes close to tapeout The testability of ECO logic is very challenging to the design schedule To avoid loss of test coverage, ECO flip-flops (FFs) must be added for ECO logic -3-

Challenges for ECO FF Insertion ECO FFs should be distributed among existing scan chains to minimize test time Only a subset of existing scan chains will be compatible with ECO FF depending on clock domain Existing routing should be minimally perturbed to minimize impact on timing and existing routing congestion ECO FF insertion flow should be automated Manual ECO FF insertion near tapeout can cost days or weeks of design time -4-

Why Is The Problem Difficult? How to tradeoff wirelength, test time, and impact to existing timing and routing? Compromise between wirelength and #edges perturbed Large incremental wirelength (timing impact) Many edges perturbed (routing disturbance) Chain 1 Chain 1 Chain 1 ECO FF Insertion Requires Good Heuristics -5-

Our Work New Incremental Multiple-Scan Chain Ordering (IMSCO) formulation Minimize test time (or scan chain depth) Minimize incremental wirelength and congestion Affects setup timing slacks and routability of ECO changes Minimize disturbance of the existing routing and timing By minimizing number of edges that are modified Develop heuristics for ordering scan chains based on Traveling Salesman Problem (TSP) Develop Incremental Scan Chain solver (ISC-solver) tool that implements IMSCO heuristics to minimize test time, wirelength and routing disturbance shows promising results -6-

Outline Motivation Related Work Problem Formulations IMSCO Flow Experimental Results Conclusions and Future Works -7-

Relationship to TSP TSP: Given a set of cities, find a minimum-cost tour that visits every city exactly once In IMSCO City :: Scan FF Cost :: Wirelength Our problem Multiple salesmen Multiple starting points mTSP Scan chain ordering can be formulated as TSP -8-

Prior Works Two broad classifications Clustering and assignment of scan FFs Ordering of assigned scan FFs Clustering and assignment Elm et al. [2008] present partitioning heuristics to cluster scan FFs into scan chains Seok et al. [2006] use placement information to divide a scan chain into multiple chains Ordering Feuer and Koo [1983] first use TSP for scan chain optimization Gupta et al. [2003] propose routing-driven and timing-driven methodology to order scan chains -9-

Outline Motivation Related Work Problem Formulations IMSCO Flow Experimental Results Conclusions and Future Works -10-

Minimize Test Time Scan depth of chain 2 > scan depth of chain 1 Scan depth of chain 2 = scan depth of chain 1 Not good solution Good solution Chain 1 Chain 1 Chain 2 Chain 2 -11-

Minimize Incremental Wirelength We can minimize timing impact to existing scan chains We can reduce routing congestion Smaller incremental wirelength Potentially less impact to existing routing Larger incremental wirelength Not good solution Good solution Chain 1 Chain 2 Chain 1 Chain 2 -12-

Minimize #Cut Edges We can minimize the disturbance to existing routing (Major changes to existing routing may break previously-achieved timing closure) Two cut edges disturb existing routing Not good solution One cut edge reduces routing disturbance Good solution Chain 1 Chain 1 -13-

Outline Motivation Related Work Problem Formulations IMSCO Flow Experimental Results Conclusions and Future Works -14-

Overall Flow Input: Original Scan Chains, ECO FFs, Constraints (1) Construction of Initial Clustering (Affinity) (2) Improvement of Initial Clustering (modified FM) (GainWL) (3) Selection of Multiple Cut Edges (k-way clustering, GainWL_byCE) Output: Clustering and Ordering of ECO FFs with Multiple Cut Edges -15-

Initial Clustering Affinity: Weighted sum of scan depth (SD), wirelength (WL) and #cut edges (CE) affinities between ECO FF and original scan chain Assign ??to scan chain ?? Calculate Affinity of ECO FF ?? to all compatible scan chains Find ??and ??pair with largest affinity Ordered list of ECO FFs per scan chain with min WL Invoke TSP-solver (Concorde) Repeat red blocks for all remaining ?? Distances for WL affinity are calculated differently for congestion- and non-congestion-aware modes Non-congestion mode: Manhattan distance between FFs Congestion mode: ???? ?? ??+ ???? ?? ?? -16-

Improvement of Initial Clusters Invoke FM (iterative hill-climbing) algorithm for each ECO FF from scan chain ?1to scan chain ?2 Search for ECO FF ??that maximizes ?????? Move ??from ?1to ?2 Remove three edges (two from ?1and one from ?2) Add three edges (one from ?1and two from ?2) Fix ??to ?2 Invoke TSP-Solver (Concorde) to order FFs to minimize WL ?????? ??,C = ?? removed edges ??(added edges) ?????? = ? + ?? + ? (?) (? + ?) = ? > ? 2 2 5 6 Chain 1 Chain 2 Chain 1 7 Chain 2 F 8 11 5 -17-

Selection of Multiple Cut Edges We can reduce the incremental wirelength even more We select multiple cut edges by using greedy k-way clustering For ECO scan FFs in a given scan chain Disconnect two longest edges of ECO FFs in a cluster for each chain Reconnect sub-clusters to nearest original scan FFs Calculate ?????? and find ????????? Retain new connections if ?????????> 0 Invoke TSP-solver (Concorde) to order FFs to minimize WL -18-

Outline Motivation Related Work Problem Formulations IMSCO Flow Experimental Results Conclusions and Future Works -19-

Experimental Setup Develop ISC-solver to implement three-phase heuristics Written C++ with several user configurations Compiled with g++ 4.8.0 Concorde as TSP-solver Validated on 12-core HT Intel Xeon E5-2640 2.5GHz, 128GB RAM server Testcases Industrial (from industry partners) Artificial with our configurable scan instance generator User options include layout size, #scan chains, #scan FFs per scan chain, #ECO FFs, congestion map, . -20-

ISC-Solver User Parameters psd : Max % increase in scan depth allowed in chain after ECO FFs insertion mel : Max edge length between scan FFs To avoid use of high-leakage LVT cells lel : Min edge length between scan FFs To avoid the need for excessive hold buffer insertion mce : Max #cut edges in each individual scan chain MCE : Max #cut edges in the entire design -21-

Option: psd psd maximum scan depth 620 610 Maximum Scan Depth 600 590 mel 500 lel 0 mce MCE 580 570 0 2 4 6 8 10 psd -22-

Option: mel mel wirelength 1995000 1994000 WireLength ( m) 1993000 1992000 psd 0 lel 0 mce MCE 1991000 1990000 10000 1000 100 10 mel -23-

Option: lel lel wirelength 2050000 2040000 WireLength ( m) 2030000 2020000 psd 0 mel 500 mce MCE 2010000 2000000 1990000 1 10 lel 100 -24-

ISC-Solver Example Solutions mce is max #cut edges per scan chain Final chain WL is 4116?? when mce = 1 Final chain WL is 3818?? when mce = 10 ISC-solver reports smaller WL when mce increases -25-

ISC-Solver: Congestion-Awareness Congested regions Non-congestion-aware Congestion-aware Cut edges ISC-solver generates more cut edges to avoid high congestion area -26-

Comparison to Industrial Results Industrial testcase 320 scan chains 634 ECO FFs 7 compatible scan chain groups 5.3% reduction in SD (no additional test time) from manual 45.71% reduction of incremental WL compared to manual 40 Scan Depth (test time) ISC-solver Results Manually-Solved Result 30 20 RECOMMENDED SOLUTION !! 10 WireLength 0 -27- 6000 10000 14000

Outline Motivation Related Work Problem Formulations IMSCO Flow Experimental Results Conclusions and Future Works -28-

Conclusions and Future Works IMSCO provides automated flow to improve testability of ECO logic in SOC implementation flow ISC-solver implements clustering, incremental clustering and ordering heuristics Compared to manual solutions, ISC-solver achieves 5.3% of test time reduction 45.71% reduction in incremental wirelength Future works Code optimizations to speedup ISC-solver Connections to operations research literature, e.g., via dynamic MDVRP with variable number of movable depots -29-

Thank You!

Affinity Calculation Scalability Time complexity ? ??2; ? = #scan FFs; ? = #ECO FFs 6000 5000 CPU Time (s) 4000 3000 ? = 49300 #scan chains = 100 Memory Usage 36MB 2000 1000 0 0 500 1000 1500 2000 2500 n 4000 ? = 300 #scan chains = 20 to 500 Memory Usage 150MB CPU Time (s) 3000 2000 1000 0 0 50 100 150 200 250 -31- m (K)

Option: mce mce wirelength mce # of cut edges 120 1998000 1997000 90 WireLength ( m) # of Cut Edges 1996000 60 psd 0 mel 5000 lel 0 MCE 1995000 30 1994000 1993000 0 0 5 10 15 20 25 0 5 10 15 20 25 mce mce -32-