Scan-chain design and optimization for three-dimensional integrated circuits

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Scan-chain design and optimization for three-dimensional integrated circuits

Full text

Pdf (602 KB)

Source

ACM Journal on Emerging Technologies in Computing Systems (JETC) archive
Volume 5 , Issue 2 (July 2009) table of contents

Article No. 9

Year of Publication: 2009

ISSN:1550-4832

Authors

Xiaoxia Wu	Pennsylvania State University, University Park, PA
Paul Falkenstern	Pennsylvania State University, University Park, PA
Krishnendu Chakrabarty	Duke University, Durham, NC
Yuan Xie	Pennsylvania State University, University Park, PA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 47, Downloads (12 Months): 142, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1543438.1543442 What is a DOI?

ABSTRACT

Scan chains are widely used to improve the testability of integrated circuit (IC) designs and to facilitate fault diagnosis. For traditional 2D IC design, a number of design techniques have been proposed in the literature for scan-chain routing and scan-cell partitioning. However, these techniques are not effective for three-dimensional (3D) technologies, which have recently emerged as a promising means to continue technology scaling. In this article, we propose two techniques for designing scan chains in 3D ICs, with given constraints on the number of through-silicon-vias (TSVs). The first technique is based on a genetic algorithm (GA), and it addresses the ordering of cells in a single scan chain. The second optimization technique is based on integer linear programming (ILP); it addresses single-scan-chain ordering as well as the partitioning of scan flip-flops into multiple scan chains. We compare these two methods by conducting experiments on a set of ISCAS'89 benchmark circuits. The first conclusion obtained from the results is that 3D scan-chain optimization achieves significant wire-length reduction compared to 2D counterparts. The second conclusion is that the ILP-based technique provides lower bounds on the scan-chain interconnect length for 3D ICs, and it offers considerable reduction in wire-length compared to the GA-based heuristic method.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Emile Aarts , Jan Korst, Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing, John Wiley & Sons, Inc., New York, NY, 1989
	2	Cristinel Ababei , Yan Feng , Brent Goplen , Hushrav Mogal , Tianpei Zhang , Kia Bazargan , Sachin Sapatnekar, Placement and Routing in 3D Integrated Circuits, IEEE Design & Test, v.22 n.6, p.520-531, November 2005 [doi>10.1109/MDT.2005.150]
	3	Arora, R. and Albicki, A. 1987. Computer-aided scan path design for self-testing chips. In Proceedings of Midwest Symposium on Circuits and Systems. 301--304.
	4	Dimitris Bertsimas , John Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997
	5	Bryan Black , Donald W. Nelson , Clair Webb , Nick Samra, 3D Processing Technology and Its Impact on iA32 Microprocessors, Proceedings of the IEEE International Conference on Computer Design, p.316-318, October 11-13, 2004
	6	Brglez, F., Bryan, D., and Kozminski, K. 1989. Combinational profiles of sequential benchmarkcircuits. In Proceedings of the IEEE International Symposium on Circuits and Systems. vol. 3. 1929--1934.
	7	J. Cong , Jie Wei , Yan Zhang, A thermal-driven floorplanning algorithm for 3D ICs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.306-313, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382591]
	8	Shamik Das , Anantha Chandrakasan , Rafael Reif, Design tools for 3-D integrated circuits, Proceedings of the 2003 Asia and South Pacific Design Automation Conference, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119783]
	9	W. Rhett Davis , John Wilson , Stephen Mick , Jian Xu , Hao Hua , Christopher Mineo , Ambarish M. Sule , Michael Steer , Paul D. Franzon, Demystifying 3D ICs: The Pros and Cons of Going Vertical, IEEE Design & Test, v.22 n.6, p.498-510, November 2005 [doi>10.1109/MDT.2005.136]
	10	Dick, R. P. 2002. Multi-objective synthesis of low-power real-time distributed embedded systems. Ph.D. thesis, Princeton University.
	11	Freuer, M. and Koo, C. 1983. Method for rechaining shift register latches which contain more than one physical book. IBM Tech. Disclo. Bull. 25. 4818--4820.
	12	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	13	Debjyoti Ghosh , Swarup Bhunia , Kaushik Roy, Multiple Scan Chain Design Technique for Power Reduction during Test Application in BIST, Proceedings of the 18th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems, p.191, November 03-05, 2003
	14	David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
	15	Puneet Gupta , Andrew B. Kahng , Stefanus Mantik, Routing-aware scan chain ordering, Proceedings of the 2003 Asia and South Pacific Design Automation Conference, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119961]
	16	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
	17	X.-L. Huang , J.-L. Huang, A routability constrained scan chain ordering technique for test power reduction, Proceedings of the 2006 Asia and South Pacific Design Automation Conference, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118453]
	18	W.-L. Hung , G. M. Link , Yuan Xie , N. Vijaykrishnan , M. J. Irwin, Interconnect and Thermal-aware Floorplanning for 3D Microprocessors, Proceedings of the 7th International Symposium on Quality Electronic Design, p.98-104, March 27-29, 2006 [doi>10.1109/ISQED.2006.77]
	19	Il-soo Lee , Yong Min Hur , Tony Ambler, The Efficient Multiple Scan Chain Architecture Reducing Power Dissipation and Test Time, Proceedings of the 13th Asian Test Symposium, p.94-97, November 15-17, 2004 [doi>10.1109/ATS.2004.85]
	20	Illman, R. and Aldrich, G. 2002. On the finish rests with multiple clock. http://www.us.design-reuse.com/articles/2820/on-time-finish-rests-with-multiple-clocks.html.
	21	Vikram Iyengar , Krishnendu Chakrabarty, Test Bus Sizing for System-on-a-Chip, IEEE Transactions on Computers, v.51 n.5, p.449-459, May 2002 [doi>10.1109/TC.2002.1004585]
	22	Joyner, J. W. and Meindl, J. D. 2002. Opportunities for reduced power dissipation using three-dimensional integration. In Proceedings of the Interconnect Technology Conference. 148--150.
	23	Jongman Kim , Chrysostomos Nicopoulos , Dongkook Park , Reetuparna Das , Yuan Xie , Vijaykrishnan Narayanan , Mazin S. Yousif , Chita R. Das, A novel dimensionally-decomposed router for on-chip communication in 3D architectures, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
	24	David E. Lackey , Paul S. Zuchowski , Thomas R. Bednar , Douglas W. Stout , Scott W. Gould , John M. Cohn, Managing power and performance for System-on-Chip designs using Voltage Islands, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.195-202, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774601]
	25	Lee, K. W., Nakamura, T., Ono, T., Yamada, Y., Mizukusa, T., Hashimoto, H., Park K. T., Kurino, H., and Koyanagi, M. 2000. Three-dimensional shared memory fabricated using wafer stacking technology. In Proceedings of the International Electron Devices Meeting. 165--168.
	26	Lewis, D. L. and Lee, H. S. 2007. A scan-island based design enabling pre-bond testability in die-stacked micro-processors. In Proceedings of the International Test Conference.
	27	Lin, K. 1996. Layout-driven chaining of scan flip-flops. In IEE Prcedings-Comput. Digit. Tech. vol. 143.
	28	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
	29	Nakamura, K. 1997. Scan paths wire length minimization and its short path error correction. In NEC Res. Devel. 38, 22--27.
	30	Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
	31	Fabrication Technologies for Three-Dimensional Integrated Circuits, Proceedings of the 3rd International Symposium on Quality Electronic Design, p.33, March 18-21, 2002
	32	Yuh-Fang Tsai , Yuan Xie , N. Vijaykrishnan , Mary Jane Irwin, Three-Dimensional Cache Design Exploration Using 3DCacti, Proceedings of the 2005 International Conference on Computer Design, p.519-524, October 02-05, 2005 [doi>10.1109/ICCD.2005.108]
	33	Balaji Vaidyanathan , Wei-Lun Hung , Feng Wang , Yuan Xie , Vijaykrishnan Narayanan , Mary Jane Irwin, Architecting Microprocessor Components in 3D Design Space, Proceedings of the 20th International Conference on VLSI Design held jointly with 6th International Conference: Embedded Systems, p.103-108, January 06-10, 2007 [doi>10.1109/VLSID.2007.41]
	34	Vucurevich, T. 2007. The long road to 3D integration: Are we there yet? In Keynote Speech at the 3D Architecture Conference.
	35	Wu, X., Falkenstern, P., and Xie, Y. 2007. Scan-chain design for three-dimensional (3D) ICs. In Proceedings of the International Conference on Computer Design.
	36	Yuan Xie , Gabriel H. Loh , Bryan Black , Kerry Bernstein, Design space exploration for 3D architectures, ACM Journal on Emerging Technologies in Computing Systems (JETC), v.2 n.2, p.65-103, April 2006 [doi>10.1145/1148015.1148016]