臺灣博碩士論文加值系統

多核心模擬環境能夠讓程式開發者在開發過程中充分的了解系統狀態，並且進一步的評估系統效能，因此在多核心應用程式的開發過程中，模擬環境佔有舉足輕重的地位。然而，目前嵌入式多核心系統的環境日趨複雜，逐漸朝向多顆處理器、複雜的連線模式以及執行緒間頻繁的交換資料的趨勢發展。在這種複雜的系統環境之下，多核心系統及其應用程式的模擬將變得非常緩慢且耗費系統資源。此外，在複雜的連線模式和資料交換的狀況之下，多核心應用程式偵錯變得相當的不容易; 反覆修改與測試的除錯流程，也會耗費相當多的時間，提高開發成本。因此，我們需要一個有效率的工具來幫助程式開發者快速的找出程式的問題所在，並且能夠加速模擬與測試的流程。

在本論文中，我們提出了兩種SID模擬環境上的系統元件來幫助程式開發者進行除錯的工作。首先，我們提出了一個系統狀態追蹤元件。該元件可以被輕易的整合進多核心模擬系統之中，並且在模擬執行期間，詳細的紀錄該系統上各個元件之執行狀態。利用該追蹤記錄，程式開發者能夠有更充分的資料去判斷程式發生錯誤的原因，並且更進一步利用該追蹤資料將系統狀態回復到錯誤發生的時間點進行偵錯，有效的加速整體的除錯流程。

此外，為了幫助程式開發者在複雜的多核心系統中精確的指出程式錯誤發生的原因，我們提出了一個系統狀態驗證元件。該元件在模擬執行期間，會將多核心系統的實際執行狀態與程式開發者所提供的理想執行狀態進行比對。利用此項功能，模擬環境可以找出錯誤發生的第一時間及成因，保留該時間點的系統狀態，提供最多的偵錯資訊給開發者。特別適用於系統元件間互動非常複雜的多核心應用程式，而這正是傳統偵錯工具的弱點。

為了讓系統狀態的追蹤和驗證更加的實用，我們還提出了「Trace-On-Demand」的追蹤模式，使得追蹤功能在磁碟空間的耗費、系統模擬速度以及狀態回復的速度上都具有相當好的平衡。此外，藉由我們所提供的分析模型，程式開發者可以正確的評估出追蹤與驗證功能所需的磁碟空間。根據實驗的結果指出，在多核心訊號處理器的平台下，分析模型預估所需耗費的磁碟空間與實際狀況的誤差不超過6%。

A mutlicore simulator is useful on multicore programming, which gives programmers an insight into the internal states of multicore systems. Due to the growing number of processors, complicated interconnections, and the frequent data communications of running threads, the simulation process of a multicore application increasingly costs a significant amount of time. In addition, the bug detecting process for multi-core platforms tends to be more difficult and the debugging process might iterate for many times
and thus consumes more simulation time.

In this thesis, we propose two kinds of components to help programmers who needs to debug their applications on such a multicore platform. First, we propose a trace component which can be integrated into processors, memory, and other
components on the simulation platform. This component keeps track of the operations of multicore simulation environment and provides enough information for analyzing the problems or even re-entering a continuation point of a simulation for debugging purposes.

The other component we proposed is an assertion component. With the assertion component, we can check the behavior of an application with the golden models provided by programmers. The assertion component can indicate the point where the application just went wrong according to the provided model. These capabilities help us finding out the problems caused by the interaction between components which are hard to be detected by conventional debugging tools.

In addition, assertion component presents a trace-on-demand methodology such that the simulation performance, the trace data size, and the recovering time can have a good compromise. Besides, an analytical model for possible trace data size is also given to assist programmers in making trace decisions. The experimental results in different views of trace information by incorporating our proposed approach in a multicore DSP simulator reveal that our analytical model for estimating log size is with accuracy with predicting errors less than 6%.

Abstract...........................................i
Contents.........................................iii
List of Figures....................................v
1 Introduction 1
1.1 Motivation . . . . . . . . . . 1
1.2 Thesis Overview . . . . . . . . 3
2 Background 5
2.1 Multicore SID simulation framework . . 5
2.2 Software Model Checking . . . . . . 6
3 System Design and implementation† 7
3.1 Trace Component . . . . . . . . 7
3.1.1 Trace Component API . . . . . 7
3.1.2 State Trace and Recovery Operation . 10
3.2 Assertion Component . . . . . . . 12
3.2.1 Assertion Component API . . . . 12
3.2.2 Assertion Model Definition Language . . 14
3.2.3 State Assertion Operation and Example . .16
3.3 Recover Platform State . . . . . . . 21
3.3.1 Trace-On-Demand . . . . . . . 22
3.3.2 Log Point Scheduling . . . . . 24
3.3.3 Analytic Model of Trace Data . . . 25
4 Experiment Result 28
5 Conclusion 33
5.1 Summary . . . . . . . . . . 33
5.2 Future Work . . . . . . . . . 34

[1] Tankut Akgul, Vincent J. Mooney, and III. Instruction-level reverse executionfor debugging, 2002.
[2] Sudarshan M. Srinivasan, Srikanth Kandula, Srikanth K, Christopher R. Andrews, and Yuanyuan Zhou. Flashback: A lightweight extension for rollback and deterministic replay for software debugging. In In USENIX Annual Technical Conference, General Track, pages 29–44, 2004.
[3] Shyh-Kwei Chen, W. Kent Fuchs, and Jen-Yao Chung. Reversible debugging using program instrumentation. IEEE Transactions on Software Engineering, 27:715–727, 2001.
[4] Sanjay Bhansali, Wen-Ke Chen, Stuart de Jong, Andrew Edwards, Ron Murray, Milenko Drinic, Darek Mihocka, and Joe Chau. Framework for instruction-level tracing and analysis of program executions. In ACM/Usenix International
Conference On Virtual Execution Environments, pages 154–163, 2006.
[5] Hiralal Agrawal, Richard A. Demillo, Eugene H. Spaord, and Eugene H. Spa Ord. An execution backtracking approach to program debugging. IEEE Software, 8:283–299, 1991.
[6] Dave Brolley. [patch] reverse execution in sid, reverse debugging with gdb and sid. http://sourceware.org/ml/sid/2006-q3/msg00047.html, 2006.
[7] Paul Brook and Daniel Jacobowitz. Reversible debugging. Technical report, codesourcery, 2007.
[8] SID Simulator Component Developer's Guide, 2001. Red Hat Inc., http://sources.redhat.com/sid/.
[9] Vojin Zivojnovic, Juan M. Velarde, and Christian Schl¨ager. DSPstone: A DSP-oriented benchmarking methodology. In Proceedings of 5th International Conference on Signal Processing Applications and Technology, 1994.
[10] David Chih-Wei Chang. PAC digital signal processor. In Proceedings of the Fall Microprocessor Forum 2006. In-Stat/MDR, 2006.
[11] Allen E. Emerson. The beginning of model checking: A personal perspective. In 25 Years of Model Checking, volume 5000 of Lecture Notes in Computer Science, pages 27–45. Springer Berlin / Heidelberg, 2008.
[12] Edmund M. Clarke, Orna Grumberg, and Doron Peled. Model Checking. MIT Press, 1999.
[13] James C. Corbett, Matthew B. Dwyer, John Hatcli, Shawn Laubach, Corina S. P˘as˘areanu, Robby, and Hongjun Zheng. Bandera: extracting nite-state models from java source code. In ICSE ’00: Proceedings of the 22nd international conference on Software engineering, pages 439–448, New York, NY, USA, 2000. ACM.
[14] Willem Visser, Klaus Havelund, and Guillaume Brat. Model checking programs. In Automated Software Engineering Journal, pages 3–12, 2000.
[15] Willem Visser, Corina S. Pˇasˇareanu, and Sarfraz Khurshid. Test input generation with java pathnder. In ISSTA ’04: Proceedings of the 2004 ACM SIGSOFTinternational symposium on Software testing and analysis, pages 97–107, New York, NY, USA, 2004. ACM.
[16] Stephan Merz. Model checking and code generation for uml state machines and collaborations. In In G. Schellhorn and W. Reif. 5 th Workshop on Tools for System Design and Verication (FM-TOOLS, pages 59–64, 2002.