請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/35463完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 黃俊郎 | |
| dc.contributor.author | Chih-Chiang Huang | en |
| dc.contributor.author | 黃志強 | zh_TW |
| dc.date.accessioned | 2021-06-13T06:53:57Z | - |
| dc.date.available | 2005-08-01 | |
| dc.date.copyright | 2005-08-01 | |
| dc.date.issued | 2005 | |
| dc.date.submitted | 2005-07-27 | |
| dc.identifier.citation | [1] Yu Huang, Sudhakar M. Reddy, Wu-Tung Cheng, Paul Reuter, Nilanjan Mukherjee, Chien-Chung Tsai, Omer Samma, and Yahya Zaidan, “Optimal core wrapper width selection and SoC test scheduling based on 3-D bin packing algorithm”, Proceedings of IEEE International Test Conference (ITC)
[2] Sandeep Karenna and Vikram Iyengar, “On the use of k-tuple for SoC test schedule representation”, Proceedings of IEEE International Test Conference (ITC) [3] Vikram Iyengar and Kirshnendu Chakrabarty, “System-on-a-Chip test scheduling with precedence relationships, preemption, and power constraints”, IEEE transactions on CAD of integrated circuits and systems, vol. 21, no. 9, SEP. 2002 [4] Sadiq M. Sait and Habib Youssef, “VLSI physical design automation”, World Scientific Publishing Co. Pte. Ltd., ISBN 981-02-3883-5, 1999 [5] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “VLSI module placement based on rectangle-packing by the sequence pair”, IEEE Transaction on Computer Aided Design of Integrated Circuits and Systems, vol. 15:12, pp. 1518-1524, 1996 [6] Xiaoping Tang, Ruiqi Tian, and D. F. Wong, “Fast evaluation of sequence-pair in block placement by longest common subsequence computation”, Design Automation and Test in Europe (DATA’00), March 27-30, 2000 Paris, France, p106 [7] W. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller, “Equation of state caculations by fast computing machines”, J. Chem. Phys., 21, 1087-1092, 1953 [8] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing”, Science, vol. 220, pp. 671-680, 1983 [9] 2003 IC/CAD Contest. [10] R. M. Chou, K. K. Saluja, and V. D. Agrawal, “Scheduling tests for VLSI systems under power constraints,” IEEE Trans. VLSI Syst., vol. 5, pp. 175-185, June 1997 [11] V. Muresan et al., “A comparison of classical scheduling approaches in power-constrained block-test scheduling,” in Proc. Int. Test Conf., 2002, pp. 882-891 [12] T. Gonzalez and S. Sahni, “Open shop scheduling to minimize finish time,” J. Assoc. Computing Machinery, vol. 23, no. 4, pp. 665-679, Oct. 1976 [13] Erik Larsson and Hideo Fujiwara, “Optimal system-on-chip test scheduling,” Test Symposium, 2003, ATS 2003, 12th Asian, 16-19 Nov. 2003, pp. 306-311 [14] Julien Pouget, Erik Larsson, and Zebo Peng, “SoC test time minimization under multiple constraints,” Test Symposium, 2003, ATS 2003, 12th Asian, 16-19 Nov. 2003, pp. 312-317 [15] Vikram Iyengar, Krishnendu Chakrabarty, and Erik Jan Marinissen, “Recent advances in test planning for modular testing of core-based SoCs,” Test Symposium, 2002, ATS’02, Proceedings of the 11th Asian, 18-20 Nov. 2002, pp. 320-325 [16] Erik Jan Marinissen, Sandeep Kumar Goel, and Maurice Lousberg, “Wrapper design for embedded core test,” Test Conference, 2000, Proceedings, International, 3-5 Oct. 2000, pp. 911-920 [17] Dan Zhao and Shambhu Upadhyaya, “Power constrained test scheduling with dynamically varied TAM,” VLSI Test Symposium, 2003, Proceedings, 21st, 27 April-1 May 2003, pp. 273-278 [18] Vikram Iyengar and Krishnendu Chakrabarty, “Precedence-based, preemptive, and power-constrained test scheduling for system-on-a-chip,” VLSI Test Symposium, 19th IEEE Proceedings on, VTS 2001, 19 April-3 May 2001, pp. 368-374 [19] Paulo R. S. Mendonca and Luiz P. Calba, “New simulated annealing algorithm,” Circuits and Systems, 1997, ISCAS’97, Proceedings of 1997 IEEE International Symposium on, Volume: 3, 9-12 June 1997, pp. 1668-1671 vol.3 [20] Wei Zou, Sudhakar M. Reddy, Irith Pomeranz, and Yu Huang, “SoC test scheduling using simulated annealing,” VLSI Test Symposium, 2003, Proceedings 21st, 27 April-1 May 2003, pp. 325-330 [21] Valentin Muresan, Xiajun Wang, and Mircea Vladutiu, “Distribution-graph based approach and extended tree growing technique in power-constrained block-test scheduling,” ATS 2000, Proceedings of the 9th Asian, 4-6 Dec. 2000, pp. 465-470 [22] Erik Larsson and Hideo Fujiwara, “Power constrained preemptive TAM scheduling,” European Test Workshop, 2002, Proceedings, the 7th IEEE, 26-29 May 202, pp. 119-126 [23] Krishnendu 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, Oct, 2000, pp. 1163-1174 [24] C. P. Ravikumar, Ashutosh Verma, and Gaurav Chandra, “A polynomial-time algorithm for power constrained testing of core based systems,” Test Symposium, 1999, (ATS’99) Proceedings, 8th Asian, 16-18 Nov. 1999, pp. 107-112 [25] Alex Orailoglu and Ian G. Harris, “Test path generation and test scheduling for self-testable designs,” VLSI in Computers and Processors, 1993, ICCD’93, Proceedings, 1993 IEEE International Conference on, 3-6 Oct. 1993, pp. 528-531 [26] Chang-Yun Shen, Yoh-Han Pao, and Percy Yip, “Scheduling multiple job problems with guided evolutionary simulated annealing approach,” Evolutionary Computation, 1994, IEEE World Congress on Computational Intelligence, Proceedings of the 1st IEEE Conference on, 27-29 June 1994, pp. 702-706 vol. 2 [27] Erik Larsson and Hideo Fujiwara, “Optimal system-on-chip test scheduling,” Test Symposium, 2003, ATS 2003, 12th Asian, 16-19 Nov. 2003, pp. 306-311 [28] Yervant Zorian, Erik Jan Marinissen, and Sujit Dey, “Testing Embedded-Core Based System Chips,” Proceedings of IEEE International Test Conference (ITC), pages 130-143, Washington, DC, October 1998. [29] K. Chakrabarty, “Design of system-on-a-chip test access architectures under place-and-route and power constraints,” Proc. Design Automation Conf., pp. 432-437, 2000. [30] Erik Jan Marinissen, Robert Arendsen, Gerard Bos, Hans Dingemaanse, Maurice Lousberg, and Clemens Wouters, “A Structures And Scalable Mechanism for Test Access to Embedded Reusable Cores,“ Proceedings of IEEE International Test Conference (ITC), pp. 284-293, Washington, DC, October 1998. IEEE Computer Society Press. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/35463 | - |
| dc.description.abstract | 伴隨著系統晶片設計的複雜與多元化，系統晶片的測試排程也變成了一個需要被認真考慮的課題。ㄧ個好的測試排程可以大幅的縮短總測試時間。一般在探討測試排程的時候，通常要考慮到功率的損耗、匯流排的指定、與個別測試的測試時間。因此，測試排程的問題可以當成三維的封裝問題來思考。
在這篇論文中，我們採用序列組表示法合併模擬退火法的方法來架構基本的框架藉以實踐系統晶片的測試排程。遵循著`最短優先`的概念原則，我們提出我們的初始排程方法而不採用隨機產生一個合法解的方式，因為對於我們的限制來說，若隨機產生的話會耗費太多時間在產生合法解上面。除此之外，序列組表示法所產生的「樹結構」在此時也被我們拿來當作檢驗各種限制條件的方法。由實驗的結果可知，藉由我們的方法可以在合理的時間內得到比較好的解。 | zh_TW |
| dc.description.abstract | With the growing complexity of SOC designs, the SOC test scheduling problem becomes a great issue. A good test scheduling can greatly decrease the total test time. When we investigate the scheduling problem, the power consumption, TAM bus assignment, and individual test time must all be considered. Hence, the test scheduling can be thought as the 3-D bin packing problem.
In this thesis, we adopt the Sequence-Pair representation combining with the Simulated-Annealing process to construct the basic frame. Using the shortest-first concept, we proposed our initial scheduling method to generate a legal result instead of generating it randomly which is experimentally proven to be time wasting. Besides, the tree graph comprehended in Sequence-Pair is used to check the constraints when doing perturbations. The experimental results show that we can obtain a better solution within an acceptable run time by our proposed algorithm. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T06:53:57Z (GMT). No. of bitstreams: 1 ntu-94-R91943070-1.pdf: 342784 bytes, checksum: 2195ea0d3d74b6cadec0abcff5939800 (MD5) Previous issue date: 2005 | en |
| dc.description.tableofcontents | LIST OF FIGURES V
CHAPTER 1 INTRODUCTION 1 CHAPTER 2 PROBLEM FORMULATION 5 2.1 RESOURCE CONFLICT CONSTRAINTS 6 2.2 PRECEDENCE CONSTRAINTS 6 2.3 POWER DISSIPATION CONSTRAINTS 7 2.4 PREEMPTION 8 CHAPTER 3 TECHNICAL OVERVIEW 9 3.1 SEQUENCE-PAIR 9 3.1.1 From a Packing to a Sequence-Pair 9 3.1.2 Information of the Sequence-Pair 11 3.1.3 The Constraint Graphs 12 3.1.4 From a Sequence-Pair to a Packing 14 3.2 SIMULATED ANNEALING 15 CHAPTER 4 PROPOSED ALGORITHM 17 4.1 INITIAL SCHEDULE 17 4.1.1 Why Not Generate Randomly. 18 4.1.2 Initial Scheduling 22 4.1.2.1 External Test 22 4.1.2.2 BIST Test 22 4.2 INITIAL SEQUENCE-PAIR 23 4.3 SIMULATED ANNEALING 25 4.3.1 Perturbations 26 4.3.1.1 Perturbation 1: Two Tests Exchange 26 4.3.1.2 Perturbation 2: Two Cores Exchange 27 4.3.1.3 Perturbation 3: Randomly Exchange 27 4.3.2 H-Graph and V-Graph 29 4.3.3 Locate the Tests Without Considering Power Constraint 30 4.3.4 Locate Tests With Power Constraint 31 4.3.5 Preemption 33 CHAPTER 5 EXPERIMENTAL RESULTS & CONCLUSIONS 35 REFERENCES 37 APPENDIX A -- A SIMPLE EXAMPLE (INPUT FILE) 41 | |
| dc.language.iso | en | |
| dc.subject | 序列組表示法 | zh_TW |
| dc.subject | 測試 | zh_TW |
| dc.subject | 排程 | zh_TW |
| dc.subject | sequence-pair | en |
| dc.subject | scheduling | en |
| dc.subject | test | en |
| dc.title | 以序列組表示法實踐系統晶片測試排程 | zh_TW |
| dc.title | SOC Test Scheduling Using Sequence-Pair Representation | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 93-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 呂學坤,陳竹一,李建模 | |
| dc.subject.keyword | 測試,排程,序列組表示法, | zh_TW |
| dc.subject.keyword | test,scheduling,sequence-pair, | en |
| dc.relation.page | 42 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2005-07-28 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
| 顯示於系所單位： | 電子工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-94-1.pdf 未授權公開取用 | 334.75 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。