隨著半導體製程的進步，積體電路的電路密度也逐年提升，且電路的開發也主要都偏往系統晶片去發展，往往一個嵌入式裝置就集結各式各樣的功能，像是各種手持裝置智慧型手機、平板等等，都是匯聚各式各樣的電路在一個裝置上，也因此提升了系統晶片測試的複雜度，也因為測試機台相當昂貴因此我們希望有效率的去測試我們的電路來達到降低成本的效果。
本論文研究半導體系統晶片測試時間縮短的辦法(TTR, test time reduction)，目標最小化整體的測試時間(makespan)，將產品上市之前對產品的各個項目進行測試，預先規劃好輸入輸出匯流排在將測試項目安排至機台來對產品進行評估。
本研究除了將我們的演算法套入單電壓系統晶片與過往的方法比較以外，也有為(DVFS, Dynamic Voltage Frequency Scaling)動態電壓頻率調整的系統晶片架構來進行比較，透過我們設計的基因演算法可以找出較短的測試排程，搭配不同的參數可以達到更好的效果，進而提升系統晶片的測試效率。實驗結果顯示我們的基因演算法不僅在DVFS架構下的SoC，排程出來的結果是優於貪婪演算法的，且在一般SoC d695、p22810和p93791中，d695在我們基因演算法得到的排程是皆優於過去的演算法，p22810及p93791則是大部分的排程結果都優於過去的演算法。

With the progress of semiconductor manufacturing, IP core’s density grew up year by year, and SoC design became more important. With the increase in the number of cores, testing SoC were more complicated. Lots of mobile devices tend to reduce power consumption because high power consumption would cause high temperature for device that consume battery’s lifetime. Many SoC designers employ dynamic voltage scaling and voltage islands that operate at multiple power supply voltage levels which could lower the power consumption but testing this kind of chip will increase cost on testing. SoC test scheduling is an important issue for testing the SoC (system-on-chip) which mainly effect the cost. We propose genetic algorithm to find an efficient scheduling to test SoC, our algorithm not only apply on normal 2D SoC to compare with other methods, we also can solve DVFS(Dynamic Voltage Frequency Scaling) SoC test scheduling. Experimental result on DVFS structure show our method obtaining the best result that effectively reduce test time. And result on itc02 benchmark is also better than other methods. Our makespan is shorter than other methods in most of circumstances so as to decrease SOC test cost.

[1] J. Ahn, and S. Kang , "SoC Test Scheduling Algorithm Using ACO-Based Rectangle Packing" International Conference on Intelligent Computing, 2006 , pp. 655-660
[2] K. Chakrabarty,Test scheduling for core-based systems using mixed integer linear programming, “ IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 19, no. 10, pp. 1163–1174, Oct. 2000.

[3] R. Chou, K. Saluja, and V. Agrawal, "Scheduling tests for VLSI systems under power constraints," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 5, no. 2, pp. 175-185, June 1997.
[4] R. Dorsch, R. Rivera, H. Wunderlich, and M. Fischer."Adapting an SOC to ATE Concurrent Test Capabilities." ITC International Test Conference, 2002 ,pp.1169-1175.
[5] V. Geurkov and L. Kirischian,"A Concurrent Testing Technique for Analog-to-Digital Converters." IEEE 17th International Mixed-Signals, Sensors and Systems Test Workshop, (2011), pp. 133-136.
[6] H. Harmanani and H. Salamy,"Power-Constrained System-on-a-Chip Test Scheduling Using a Genetic Algorithm." The 3rd International IEEE-NEWCAS Conference, June 2005, pp.203-206.
[7] Y. Huang, W. Cheng, C. Tsai, N. Mukherjee, O. Samman, Y. Zaidan, and S. Reddy,"Resource Allocation and Test Scheduling for Concurrent Test of Core-Based SOC Design."IEEE Test Symposium, Proceedings. 10th Asian, Nov. 2001, pp. 265-270.

[8] Y. Huang, S. Reddy, W. Cheng, P. Reuter, N. Mukherjee, C. Tsai, O. Samman, and Y. Zaidan, “Optimal core wrapper width selection and SOC test scheduling based on 3-D bin packing algorithm,” in Proceedings IEEE of International Test Conference (ITC), Baltimore, MD, USA, 2002 , pp. 74–82.

[9] " ITC'02 SOC Test Benchmarks, " http://itc02SoCbenchm.pratt.duke.edu
[10] V. Iyengar, and K.Chakrabarty,"System-on-a-Chip Test Scheduling With Precedence Relationships, Preemption, and Power Constraints." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.21, no.9,pp. 1088-1094, Sep (2002).
[11] V. Iyengar, K. Chakrabarty, and E. Marinissen, “On Using Rectangle Packing for SOC Wrapper/TAM Co-Optimization,” in Proceedings of IEEE VLSI Test Symposium (VTS), Monterey, California, USA, 2002, pp. 253-258.
[12] V. Iyengar ,K. Chakrabarty, and E. Marinissen, “Efficient Wrapper/TAM Co-Optimization for Large SOCs,” in Proceedings of Design and Test in Europe (DATE), Paris, France, (2002), pp. 491-498.

[13] X. Kavousianos, K. Chakrabarty, A. Jain, and R. Parekhji, "Test Schedule Optimization for Multicore SoCs: Handling Dynamic Voltage Scaling and Multiple Voltage Islands," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 31, no. 11, pp. 1754-1766, Nov. 2012.

[14] D. Libao, F. Ning, B. Xiaolong, Q. Liyan, and P. Xiyuan, "Solving the SOC test scheduling problem based on time-divided of IP test," 2015 12th IEEE International Conference on Electronic Measurement & Instruments (ICEMI), Qingdao, 2015, pp. 364-368.

[15] G. Liu, "Parallel elite genetic algorithm for test scheduling of SoC," 2014 9th IEEE Conference on Industrial Electronics and Applications, Hangzhou, 2014, pp. 1985-1988.

[16] M. Lu, M. Wu, H. Chen, and H. Jiang, "Performance Constraints Aware Voltage Islands Generation in SoC Floorplan Design," 2006 IEEE International SOC Conference, Taipei, 2006, pp. 211-214.

[17] W. Mak, and J. Chen ,"Voltage Island Generation under Performance Requirement for SoC Designs", Design Automation Conference in Asia and 6 South Pacific, Jan.2007, pp. 23-26.

[18] K. Man, K. Tang, and S. Kwong, "Genetic algorithms: concepts and applications," in IEEE Transactions on Industrial Electronics, vol. 43, no. 5, pp. 519-534, Oct 1996.

[19] L, Monch, J. Fowler, S. Peres, S. Mason, and O. Rose,"A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations." Journal of Scheduling, vol. 14, no.6, pp.583-599, December 2011.

[20] T. Nakajima, T. Yaguchi, and H. Sugimura,"An ATE Architecture for Implementing Very High Efficiency Concurrent Testing." IEEE International Test Conference, (2012),pp. 1-10.

[21] J. Pouget, E. Larsson, Z. Peng, M. Flottes, and B. Rouzeyre, “An Efficient Approach to SoC Wrapper Design, TAM configuration, and Test Scheduling,”in Proceedings of IEEE European Test Workshop (ETW), Maastricht, The Nederlands, 2003, pp. 117-122.

[22] J. Pouget, E. Larsson, Z. Peng, and M. Flottes, "Multiple-Constraint Driven System-on-Chip Test Time Optimization," journal of electronic: Theory and Applications 21,pp. 599-611, 2005

[23] J. Rivoir,"Parallel Test Reduces Cost of Test More Effectively Than Just a Cheap Tester." Electronics Manufacturing Technology Symposium, IEEE/CPMT/SEMI 29th International, July (2004),pp.263 - 272.

[24] S. Samii, M. Selkala, E. Larsson, K. Chakrabarty, and Z. Peng, "Cycle-Accurate Test Power Modeling and Its Application to SoC Test Architecture Design and Scheduling," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 5, pp. 973-977, May 2008.

[25] Y. Takahashi and A. Maeda,"Multi Domain Test: Novel Test Strategy to reduce the Cost of Test." IEEE 29th VLSI Test Symposium, May (2011),pp.303-308.

[26] Y. Takahashi, A. Maeda, and M. Ogura,"Actual Implementation of Multi Domain Test: Further Reduction of Cost of Test." International Test Conference, pp.1-8, Sept. 2011.

[27] Z. Tao, "TSP Problem Solution Based on Improved Genetic Algorithm," 2008 Fourth International Conference on Natural Computation, Jinan, 2008, pp. 686-690.
[28] C. Tsai, C. Kuo, J. Wu, T. Lee, and R. Hsiao , "A Topology-Based Construction for X-Architecture Clock Routing, " The 18th VLSI Design/CAD Symposium, August (2007),pp. 166-169 .
[29] F. Vartziotis and X. Kavousianos", Time-Division Multiplexing for Testing DVFS-Based SoCs, " IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, VOL. 34, NO. 4, APRIL (2015).
[30] B. Wagenen and E. Seng,"Concurrent Test Planning." IEEE International Test Conference, Nov. (2010),pp.1-10.

[31] Q. Xu, N. Nicolici, and K. Chakrabarty,"Test Wrapper Design and Optimization Under Power Constraints for Embedded Cores With Multiple Clock Domains." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.26, no.8,Aug. 2007,pp1539-1547.
[32] Y. Yu, "A Test Scheduling Algorithm Based on Two-Stage GA", Phys.: Conf. Ser. 48, 2006 July, pp. 658-662.
[33] D. Zhao and S. Upadhyaya,"A Generic Resource Distribution and Test Scheduling Scheme for Embedded Core-Based SoCs." IEEE Transactions on Instrumentation and Measurement, vol.53 no.2, pp. 318-329, April (2004).
[34] D. Zhao and S. Upadhyaya,"Dynamically Partitioned Test Scheduling With Adaptive TAM Configuration for Power-Constrained SoC Testing." IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, vol. 24, no. 6, pp. 956-965, June (2005).
[35] J. Zheng, "An Improved SoC Test Scheduling Method Based on Simulated Annealing Algorithm", Phys.: Conf. Ser. 806, 2017 J, pp. 658-662.