跳到主要內容

臺灣博碩士論文加值系統

(3.87.33.97) 您好!臺灣時間:2022/01/27 17:14
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:韓開旭
研究生(外文):Kevin Kai-Shu Han
論文名稱:藉由掃描鏈重序達到低耗能嵌入測試之設計
論文名稱(外文):Low Power DFT by Scan Chain Reordering
指導教授:單智君
指導教授(外文):Jyh-Jiun Shann
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:72
中文關鍵詞:低耗能掃描鏈嵌入式測試重序旅行商人
外文關鍵詞:low powerscan chainDFTreorderingtraveling salesman
相關次數:
  • 被引用被引用:0
  • 點閱點閱:178
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
循序電路(Sequential Circuit)的測試往往藉由插入掃描鏈(Scan Chain)的方式將測試資料(Test Pattern)傳送給待測的電路(Circuit Under Test, CUT); 藉由掃描鏈串聯的傳輸方式,可大幅減少傳輸測試資料時所需的資料埠(Data Ports)。可是當待測電路越來越複雜,為達到要求的偵錯率(Fault Coverage),所需的掃描鏈長度便相對的增加。此時,測試資料的傳遞不僅耗時,而且其耗能很可能超過晶片設計時所容許的最大規格,進而造成測試的誤失,甚至有可能因為瞬間的大電流造成待測電路的毀損!因此一個經過省能考慮並顧及最大繞線距離的掃描鏈是相當重要而且實用的設計需求。
在本篇論文中,我們嘗試將掃描鏈定序(Scan Chain Ordering)轉化成一個「旅行商人」(Traveling Salesman Problem)的問題模式,其中包括了全連通圖(Fully Connected Graph)的建立與權重(Weight)的計算,然後提出一個「最小權重優先」(Lowest Weight First)演算法以找出新的定序方式。模擬結果顯示,重新定序後的掃描鏈其資料傳輸時的總耗能最多可節省33.8%,最大功率消耗則最多可節省29.8%。另外,將本篇論文的方法應用在掃描鏈繞線長度上的縮減時,重新定序的掃描鏈其繞線總長度最多將可縮減至原來的5%以下。
此外,本論文提出的方法在執行時間方面非常有效率,相較於其他掃描鏈重序的方法,我們的方法所需的計算時間僅為他法的千分之一至萬分之一不等。此將更有助應用於超大型積體電路測試時的實際情況與需求。

Scan-Chain insertion is widely used in design for testability (DFT) technique to test sequential circuit. The test pattern could propagate to the Circuit Under Test (CUT) through the scan chain serially to reduce needed data ports. However, the power of scan testing is usually three to four times larger than the power under normally functional operation of the same circuit. The large power of testing may fail the testing result and even damage the circuit under test (CUT). So that an efficient method to reduce power consumption and total routing length concurrently is important for nowadays IC design.
In this thesis, we propose a method to lower down the power consumption by scan chain reordering. The method also could take the total routing length of the scan chain into consideration concurrently. By modeling the whole system as a traveling salesman problem (TSP) and solving it using a Lowest Weight First (LWF) heuristic algorithm, the saved energy of the reordered scan chain could up to 33.8% and the saved maximum power consumption could up to 29.8%. Moreover, the total routing length could also be minimized to be shorter than 5% of the original one.
The time efficiency of our proposed method is better than the previous approaches for about three to four magnitude of order. That makes our proposed method more feasible and suitable than other approaches to deal with nowadays’ more and more complicated IC designs.

Contents
摘要……………………………………………………………..i
Abstraction……………………………………………………...ii
Contents………………………………………………………..iv
List of Figures………………………………………………….vi
List of Tables………………………………………………….vii
Chapter. 1 Introduction…………………………………………1
1.1 Motivation………………………………………………1
1.2 Background……………………………………………..4
1.3 Our Purpose & Proposed Method………………………9
1.4 Organization of the Thesis…………………………….13
Chapter. 2 Previous Work Survey……………………………..14
2.1 Pattern/Scan Chain Reordering…………….…………14
2.2 Test Scheduling………………………………………..16
2.3 Clock Gating and Primary Input Freezing……….……18
2.4 Pattern Compression and Compaction………...………19
2.5 Layout-Based Ordering Designs………..……………..21
Chapter. 3 Proposed Method…………………………………..23
3.1 Overview………………………………………………25
3.2 TSP Modeling…………………………………………27
3.2.1 Fully-Connected-Graph……..…………………..27
3.2.2 Weights Calculation……………………………..30
(1) Power Consumption Weights……………..…..30
(2) Routing Length Weights………..……………..32
(3) Combine the Both Parts into One……………33
3.3 TSP Solving……..……………………………………35
3.4 Modified Modeling for Further Constraints…………38
Chapter. 4 Experiment & Performance Evaluation…………...40
4.1 Simulation Environment………………………………40
4.2 Experiment Result…………………………………….41
4.3 Compare with Previous Work…………………………46
4.4 Weight Ratio…………………………………………..48
Chapter. 5 Conclusions……………………………………..…51
Reference List…………………..……………………...……..52

Reference List
1. Y, Zorian, "A distributed BIST control scheme for complex VLSI devices," VLSI Test Symposium, Page(s): 4 —9, 1993
2. Stroele, A.P.; H.-J, Wunderlich, "Test register insertion with minimum hardware cost," Computer-Aided Design, 1995. ICCAD-95. Digest of Technical Papers, 1995 IEEE/ACM International Conference, Page(s): 95 —101, 1995
3. Pranav Ashar; Sharad Malik, "Implicit computation of minimum-cost feedback-vertex sets for partial scan and other applications," Proceedings of the 31st annual conference on Design automation conference, Page(s): 77 — 80, 1994
4. Srimat T. Chakradhar, "An exact algorithm for selecting partial scan flip-flops," Annual ACM IEEE Design Automation Conference, Proceedings of the 31st annual conference on Design automation conference, Page(s): 81 - 86, 1994
5. Chau-Shen Chen; Kuang-Hui Lin; TingTing Hwang, "Layout driven selecting and chaining of partial scan flip-flops," Annual ACM IEEE Design Automation Conference, Proceedings of the 33rd annual conference on Design automation conference, Page(s): 262 — 267, 1996
6. Hirech, M.; Beausang, J.; Xinli Gu, "A new approach to scan chain reordering using physical design information," Test Conference, 1998. Proceedings., International, Page(s): 348 -355, 1998
7. A. Chandra; K. Chakrabarty, "Efficient test data compression and decompression for system-on-a-chip using internal scan chains and Golomb coding," Design, Automation, and Test in Europe, Proceedings of the DATE 2001 on Design, automation and test in Europe, Page(s): 145 — 149, 2001
8. http://www.cadence.com/products/dracula.html
9. Chakravarty, S.; V.P. Dabholkar, "Two techniques for minimizing power dissipation in scan circuits during test application," Test Symposium, Proceedings of the Third Asian, Page(s): 324 —329, 1994
10. Dabholkar, V.; Chakravarty, S.; Pomeranz, I.; S. Reddy, "Techniques for minimizing power dissipation in scan and combinational circuits during test application," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, Volume: 17 Issue: 12, Page(s): 1325 -1333, Dec. 1998
11. Nicola Nicolici; Bashir M. Al-Hashimi, "Scan latch partitioning into multiple scan chains for power minimization in full scan sequential circuits," Design, Automation, and Test in Europe, Proceedings of the conference on Design, automation and test in Europe, Page(s): 715 - 722, 2000
12. Nicolici, N.; B.M. Al-Hashimi, "Minimising power dissipation in partial scan sequential circuits," Computers and Digital Techniques, IEE Proceedings- , Volume: 148 Issue: 4-5 , Page(s): 163 —166, July-Sept. 2001
13. Yervant Zorian; Erik Jan Marinissen , "System chip test: how will it impact your design? " Proceedings of the 37th conference on Design automation, Page(s): 136 - 141, 2000
14. Chou, R.M.; Saluja, K.K.; V.D. Agrawal, "Power constraint scheduling of tests," VLSI Design, Proceedings of the Seventh International Conference on, Page(s): 271 —274, 1994
15. Chou, R.M.; Saluja, K.K.; V.D. Agrawal, "Scheduling tests for VLSI systems under power constraints," Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, Volume: 5 Issue: 2 , Page(s): 175 —185, June 1997
16. Kuen-Jong Lee; Tsung-Chu Haung; Jih-Jeen Chen, "Peak-power reduction for multiple-scan circuits during test application," Test Symposium (ATS 2000). Proceedings of the Ninth Asian, Page(s): 453 —458, 2000
17. Muresan, V.; Xiaojun Wang; Vladutiu, M."A comparison of classical scheduling approaches in power-constrained block-test scheduling," Test Conference, Proceedings, International, Page(s): 882 —891, 2000
18. Larsson, E.; Z. Peng, "An integrated system-on-chip test framework," Design, Automation and Test in Europe, Conference and Exhibition 2001, Proceedings, Page(s): 138 -144, 2001
19. K. Chakrabarty, "Test scheduling for core-based systems," Computer-Aided Design, Digest of Technical Papers. 1999 IEEE/ACM International Conference on, Page(s): 391 —394, 1999
20. K. Chakrabarty, "Test scheduling for core-based systems using mixed-integer linear programming," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, Volume: 19 Issue: 10, Page(s): 1163 —1174, Oct. 2000
21. Sankaralingam, R.; Pouya, B.; N.A. Touba, "Reducing power dissipation during test using scan chain disable," VLSI Test Symposium, 19th IEEE Proceedings on, VTS 2001, Page(s): 319 —324, 2001
22. Nicolici, N.; Al-Hashimi, B.M.; A.C. Williams, "Minimisation of power dissipation during test application in full-scan sequential circuits using primary input freezing," Computers and Digital Techniques, IEE Proceedings-, Volume: 147 Issue: 5, Page(s): 313 —322, Sept. 2000
23. Neil H.E. Weste; Kamran Eshraghian, “Principles of CMOS VLSI Design, a systems perspective,” Addison-Wesley Publishing company, second edition, October, 1994
24. Girard, P.; Guiller, L.; Landrault, C.; S. Pravossoudovitch, "A test vector ordering technique for switching activity reduction during test operation," VLSI, Proceedings, Ninth Great Lakes Symposium on, Page(s): 24 —27, 1999
25. Sankaralingam, R.; Oruganti, R.R.; N.A. Touba, "Static compaction techniques to control scan vector power dissipation," VLSI Test Symposium, Proceedings, 18th IEEE, Page(s): 35 —40, 2000
26. Anshuman Chandra; Krishnendu Chakrabarty, "Combining low-power scan testing and test data compression for system-on-a-chip," Annual ACM IEEE Design Automation Conference, Proceedings of the 38th Conference on Design Automation Conference, Page(s): 166 — 169, 2001
27. Ismet Bayraktaroglu; Alex Orailoglu, "Test volume and application time reduction through scan chain concealment," Proceedings of the 38th Conference on Design Automation Conference, Page(s): 151 — 155, 2001
28. S. Makar, "A layout-based approach for ordering scan chain flip-flops," Test Conference, Proceedings, International, Page(s): 341 —347, 1998
29. Brglez, F.; Bryan, D.; K. Kozminski, "Combinational profiles of sequential benchmark circuits", Circuits and Systems, IEEE International Symposium on, vol.3, Page(s): 1929 —1934, 1989
30. http://www.syntest.com/
31. L. Posa, “Hamiltonian circuits in random graph,” Discrete Mmathematics, Pages: 359 —364, 1976
32. Dana Angluin; Leslie G. Valiant, “Fast probabilistic algorithms for hamiltonian circuits and matchings,” Annual ACM Symposium on Theory of Computing, Proceedings of the ninth annual ACM symposium on Theory of computing, Pages: 30 - 41, 1977
33. B Bollobas; T I Fenner; A M Frieze, “An algorithm for finding Hamilton cycles in random graphs,” Annual ACM Symposium on Theory of Computing, Proceedings of the seventeenth annual ACM symposium on Theory of computing, Pages: 430 — 439, 1985
34. William Kocay; P.C. Li, “An algorithm for finding a long path in a graph,” Utilitas Mathematica, pages: 169 —185, 1994
35. Andrei Z. Broder; Alan M. Frieze; Eli Shamir, “Finding hidden Hamiltonian cycles,” Annual ACM Symposium on Theory of Computing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, Pages: 182 — 189, 1991
36. Francesco A. Brunacci, “DB2 and DB2A: Two useful tools for constructing Hamiltonian circuits,” European Journal of Operational Research, Pages: 231 —236, 1988
37. William Kocay, “An extension of the multi-path algorithm for finding Hamiltonian circuits,” Discrete Mmathematics, pages: 171 —188, 1996

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top