臺灣博碩士論文加值系統

近年來，由於汽車電子有在線測試的需求，許多研究人員對軟體自我測試 (Software-Based Self-Test) 產生了濃厚的興趣。我們將問題定義為識別現代處理器中的行為。在論文中，給定指令集結構 (Instruction Set Architecture)和其對應的處理器設計，我們提出了一個自動化的流程來識別處理器中的行為。我們的方法利用無監督 (Unsupervised) 的分群方法，將相似的行為用群來表示。此外，我們提出一個以數據流向圖 (Data Flow Graph)為基礎的對模擬結果的預處理過程。他不僅對人更有可讀性，而且還有可擴充性。
通過我們的自動化流程，人們可以省下時間去理解所有在現代模擬器裡的模塊。藉由合理的轉換，我們的方法可以被引用在基於模板設計的軟體自我測試方法。

In recent years, many researchers show the interest in software-based self-test (SBST) due to the necessity of on-line testing on automotive electronics. We address our problem to identify the behaviors in the modern processors. In the thesis, we proposed an automation flow to recognize the behaviors in modern processors only given the instruction set architecture (ISA) and its corresponding design. This methodology utilizes an unsupervised clustering approach to obtain similar behaviors in group representation. Additionally, a data-flow-graph (DFG) based preprocessing on the simulation results is proposed. It is not only more readable for humans but also flexible if the extension of ISA is provided.
With the proposed automatic flow, people can save the time realizing the whole modules inside the modern processor. By a suitable conversion, our method can be used for template-based approach of SBST.

口試委員會審定書 #
致謝 i
中文摘要 ii
Abstract iii
Contents iv
List of Figures vii
Chapter 1 Introduction 1
1.1 Machine learning in Integrated Circuit testing . . . . . . . . . . . . . 1
1.2 Software-based self-test (SBST) . . . . . . . . . . . . . . . . . . . . 2
1.3 Motivation and previous work . . . . . . . . . . . . . . . . . . . . . 3
1.4 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Chapter 2 Preliminaries 5
2.1 Software-based test program generation on MIPS Processor . . . . . 5
2.2 MIPS Instruction set architecture . . . . . . . . . . . . . . . . . . . . 7
2.3 MIPS architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Data flow graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5 Graph clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5.1 Unsupervised clustering . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5.2 Graph kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Chapter 3 Proposed Methodology 12
3.1 Random Program Generation and Simulation . . . . . . . . . . . . . 13
3.1.1 Base template for pipelined processor . . . . . . . . . . . . . . . . 13
3.1.2 Template with data dependency . . . . . . . . . . . . . . . . . . . . 14
3.2 DFG Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.1 Relations between Registers . . . . . . . . . . . . . . . . . . . . . 16
3.2.2 DFG construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.3 Heuristics during DFG Construction . . . . . . . . . . . . . . . . . 20
3.2.4 Example DFG of single instruction . . . . . . . . . . . . . . . . . . 23
3.3 Graph Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Chapter 4 Experimental Results 27
4.1 Environment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Configuration of random program . . . . . . . . . . . . . . . . . . . 28
4.3 Fake and missing relation in DFG . . . . . . . . . . . . . . . . . . . 28
4.4 Clustering Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.5 Local Explanation of DFG . . . . . . . . . . . . . . . . . . . . . . . 31
4.6 Concealed instructions . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.7 Influence of instruction type . . . . . . . . . . . . . . . . . . . . . . 34
Chapter 5 Conclusion and future work 35
5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
References 36

[1] P. Krishnamurthy, A. Basak Chowdhury, B. Tan, F. Khorrami, and R. Karri, “Explaining and interpreting machine learning cad decisions: An ic testing case study,” in Proceedings of the 2020 ACM/IEEE Workshop on Machine Learning for CAD, MLCAD ’20, (New York, NY, USA), p. 129–134, Association for Computing Machinery, 2020.
[2] D. S. Boning, I. A. M. Elfadel, and X. Li, A Preliminary Taxonomy for Machine Learning in VLSI CAD, pp. 1–16. Cham: Springer International Publishing, 2019.
[3] S. Roy, S. K. Millican, and V. D. Agrawal, “Machine intelligence for efficient test pattern generation,” in 2020 IEEE International Test Conference (ITC), pp. 1–5, 2020.
[4] O. Ibarra and S. Sahni, “Polynomially complete fault detection problems,” IEEE Transactions on Computers, vol. C-24, no. 3, pp. 242–249, 1975.
[5] Fujiwara and Toida, “The complexity of fault detection problems for combinational logic circuits,” IEEE Transactions on Computers, vol. C-31, no. 6, pp. 555–560, 1982.
[6] G. Seroussi and N. Bshouty, “Vector sets for exhaustive testing of logic circuits,” IEEE Transactions on Information Theory, vol. 34, no. 3, pp. 513–522, 1988.36
[7] H.-G. Stratigopoulos, “Machine learning applications in ic testing,” in 2018 IEEE 23rd European Test Symposium (ETS), pp. 1–10, 2018.
[8] S. Roy, S. K. Millican, and V. D. Agrawal, “Special session –machine learning in test: A survey of analog, digital, memory, and rf integrated circuits,” in 2021 IEEE 39th VLSI Test Symposium (VTS), pp. 1–14, 2021.
[9] N. Kranitis, A. Paschalis, D. Gizopoulos, and G. Xenoulis, “Software-based selftesting of embedded processors,” IEEE Transactions on Computers, vol. 54, no. 4, pp. 461–475, 2005.
[10] T. H. Lin, “Software-based self-test for aging defect detection,” M.S. thesis, National Taiwan University, Taipei, Taiwan, 2018.
[11] Y. H. Chang, “Simulation-based test patterns to program converter for softwarebased self-test,” National Taiwan University, Taipei, Taiwan, 2019.
[12] K.-H. Chen, B.-Y. Yang, J.-R. Liang, H.-L. Chen, and J.-L. Huang, “Automatic test program generation for transition delay faults in pipelined processors,” in 2021 IEEE International Test Conference in Asia (ITC-Asia), pp. 1–6, 2021.
[13] D. A. Patterson and J. L. Hennessy, Computer Organization and Design, Fifth Edition: The Hardware/Software Interface. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 5th ed., 2013.
[14] G. Ayers, “A 32-bit mips processor which aims for conformance to the mips32 release 1 isa..” https://github.com/grantae/mips32r1_xum, 2014.