Routing-aware scan chain ordering

ABSTRACT

Scan chain insertion can have a large impact on routability, wirelength and timing of the design. We present a routing-driven methodology for scan chain ordering with minimum wirelength objective. A routing-based approach to scan chain ordering, while potentially more accurate, can result in TSP (Traveling Salesman Problem) instances which are asymmetric and highly non-metric; this may require a careful choice of solvers. We evaluate our new methodology on recent industry place-and-route blocks with 1200 to 5000 scan cells. We show substantial wirelength reductions for the routing-based flow, versus the traditional placement-based flow: in a number of our test cases, over 86% of scan routing overhead is saved. Even though our experiments are so far timing-oblivious, the routing-based flow does also improve evaluated timing, and practical timing-driven extensions appear feasible.

REFERENCES

• 1: S. Barbagallo , M. Lobetti Bodoni , D. Medina , F. Corno , P. Prinetto , M. Sonza Reorda, Scan insertion criteria for low design impact, Proceedings of the 14th IEEE VLSI Test Symposium (VTS '96), p.26, April 28-May 01, 1996
• 2: J. J. Bentley, "Fast Algorithms for Geometric Traveling Problems", ORSA Journal of Computing, 4(4) (1992), pp. 387--410.
• 3: K. D. Boese, A. B. Kahng and R. S. Tsay, "Scan Chain Optimization: Heuristic and optimal Solutions", Internal Report, UCLA CS Dept., October 1994. Downloadable from http://www.gigascale.org/bookshelf/Slots/ScanOpt/
• 4: GSRC Bookshelf, "Scan Chain Optimization", http://www.gigascale.org/bookshelf/Slots/ScanOpt/
• 5: Chau-Shen Chen , Tingting Hwang, Layout Driven Selection and Chaining of Partial Scan Flip-Flops, Journal of Electronic Testing: Theory and Applications, v.13 n.1, p.19-27, Aug. 1, 1998 [doi>10.1023/A:1008381015527]
• 6: "Eighth DIMACS Implementation Challenge", http://www.research.att.com/dsj/chtsp/, 2002.
• 7: M. Feuer and C. C. Koo, "Method for Rechaining Shift Register Latches Which Contain More Than One Physical Book", IBM Technical Disclosure Bulletin 25 (9) (1983), pp. 4818--4820.
• 8: K. Helsgaun, "An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic", European Journal of Operations Research 12 (2000), pp. 106--130. The code is available at http://www.dat.ruc.dk/keld/research/LKH/.
• 9: Mokhtar Hirech , James Beausang , Xinli Gu, A new approach to scan chain reordering using physical design information, Proceedings of the 1998 IEEE International Test Conference, p.348, October 18-22, 1998
• 10: Inki Hong , Andrew B. Kahng , Byung-Ro Moon, Improved Large-Step Markov Chain Variants for the Symmetric TSP, Journal of Heuristics, v.3 n.1, p.63-81, Fall 1997 [doi>10.1023/A:1009624916728]
• 11: David S. Johnson, Local Optimization and the Traveling Salesman Problem, Proceedings of the 17th International Colloquium on Automata, Languages and Programming, p.446-461, July 16-20, 1990
• 12: D. S. Johnson and L. A. McGeoch, "The Traveling Salesman Problem: A Case Study in Local Optimization", In E. H. L. Aarts and J. K. Lenstra, editors, Local Search Algorithms, Wiley and Sons, New York, 1997.
• 13: D. S. Johnson, G. Gutin, L. A. McGeoch, A. Yeo, W. Zhang and A Zverovitch, "Experimental Analysis of Heuristics for the ATSP", To appear in The Traveling Salesman and its Variations, Kluwer Academic Publishers, 2002.
• 14: Andrew B. Kahng , Stefanus Mantik, On mismatches between incremental optimizers and instance perturbations in physical design tools, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 15: P. C. Kanellakis and C. H. Papadimitriou, "Local Search for the Asymmetric Traveling Salesman Problem", Operations Research Letters 11 (1992), pp. 219--224.
• 16: S. Kobayashi, M. Edahiro and M. Kubo, "A VLSI Scan-Chain Optimization Algorithm for Multiple Scan-Paths", IEICE Trans. Fundamentals E82-A(11) (1999), pp. 2499--2504.
• 17: E. L. Lawler, J. K. Lenstra, A. Rinnooy-Kan and D. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, 1985.
• 18: K.-H. Lin, C.-S. Chen and T. T. Hwang, "Layout Driven Chaining of Scan Flip-flops", IEE Proc., Computers and Digital Techniques 143(6) (1996), pp. 421--425.
• 19: Samy Makar, A layout-based approach for ordering scan chain flip-flops, Proceedings of the 1998 IEEE International Test Conference, p.341-347, October 18-22, 1998
• 20: O. Martin, S. W. Otto and E. W. Felten, "Large-step Markov Chains for the Traveling Salesman Problem", Complex Systems 5(3) (1991), pp. 299--326.
• 21: D. L. Miller and J. F. Pekny, "Exact Solution of Large Asymmetric Traveling Salesman Problems", Science 251, 15 February 1991. pp. 754--761.
• 22: G. Reinelt, "Fast Heuristics for Large Geometric Traveling Salesman Problems", ORSA Journal on Computing, 4(2) (1992), pp. 206--217.
• 23: W. Zhang, "On the Expected Complexity of the Traveling Salesman Problem under Subtour Elimination", UCLA CS Dept. Tech. Report CSD-920022, 1992.