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 nonmetric; 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 also improves 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: Bentley, J. J. 1992. Fast algorithms for geometric traveling problems. ORSA J. Comput. 4, 4, 387--410.
• 3: Boese, K. D., Kahng, A. B., and Tsay, R. S. 1994. Scan chain optimization: Heuristic and optimal solutions. Internal rep. UCLA Computer Science Dept. (Oct.). Available at http://www.gigascale.org/bookshelf/Slots/ScanOpt/.
• 4: Feuer, M. and Koo, C. C. 1983. Method for rechaining shift register latches which contain more than one physical book. IBM Tech. Disclos. Bull. 25, 9, 4818--4820.
• 5: Puneet Gupta , Andrew B. Kahng , Stefanus Mantik, A Proposal for Routing-Based Timing-Driven Scan Chain Ordering, Proceedings of the 4th International Symposium on Quality Electronic Design, p.339, March 24-26, 2003
• 6: Helsgaun, K. 2000. An effective implementation of the Lin-Kernighan traveling salesman heuristic. European J. Operat. Res. 12, 106--130. The code is available at http://www.dat. ruc.dk/keld/research/LKH/.
• 7: 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
• 8: 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]
• 9: 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
• 10: Johnson, D. S. and McGeoch, L. A. 1997. The traveling salesman problem: A case study in local optimization. In E. H. L. Aarts and J. K. Lenstra Eds. Local Search Algorithms, John Wiley and Sons, New York, NY.
• 11: Johnson, D. S., Gutin, G., McGeoch, L. A., Yeo, A., Zhang, W., and Zverovitch, A. 2002. Experimental analysis of heuristics for the ATSP. The Traveling Salesman and its Variations. Kluwer Academic Publishers. To appear.
• 12: 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
• 13: Kanellakis, P. C. and Papadimitriou, C. H. 1992. Local search for the asymmetric traveling salesman problem. Operat. Res. Letters 11, 219--224.
• 14: Kobayashi, S., Edahiro, M., and Kubo, M. 1999. A VLSI scan-chain optimization algorithm for multiple scan-paths. IEICE Transaction Fundamentals E82-A(11), 2499--2504.
• 15: Lawler, E. L., Lenstra, J. K., Rinnooy-Kan, A., and Shmoys, D. 1985. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley and Sons, New York, NY.
• 16: Lin, K.-H., Chen, C.-S., and Hwang, T. T. 1996. Layout driven chaining of scan flip-flops. In IEE Comput. Digit. Techn. 143, 6, 421--425.
• 17: 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
• 18: Martin, O., Otto, S. W., and Felten, E. W. 1991. Large-step Markov chains for the traveling salesman problem. Complex Syst. 5, 3, 299--326.
• 19: Miller, D. L. and Pekny, J. F. 1991. Exact solution of large asymmetric traveling salesman problems. Science 251, 15 (Feb.), 754--761.
• 20: Reinelt, G. 1992. Fast heuristics for large geometric traveling salesman problems. ORSA J. Comput. 4, 2, 206--217.
• 21: Zhang, W. 1992. On the expected complexity of the traveling salesman problem under subtour elimination. UCLA Computer Science Dept. Tech. Rep. CSD-920022.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

General Terms:
Algorithms, Design, Performance, Verification

Keywords:
Layout, scan chain, testing