臺灣博碩士論文加值系統

平行程式的開發是為了提高大型應用程式的效能。因此平行程式的效能預測就變得非常重要。CCC是一個高階的平行程式語言，它可以支援基於監督結構的平行程式。基於監督結構的平行程式，大多數具有非確定性的執行行為，因此它們的效能預測非常困難。

這篇論文設計和實作一個基於監督結構的平行程式的效能預測工具。它所提出的方法是一個混合式的方法。它使用靜態程式分析來預測循序程式的效能，以及同時使用測量和模擬的方法來預測平行程式的效能。這篇論文也針對這個效能預測工具提出一個初步的評估。

Parallel program aims to improve the performance of large applications. Therefore, it is very important to be able to predict the performance of parallel programs. CCC is a high-level parallel programming language and supports monitor-based parallel programs. It’s very difficult to predict the performance of such parallel programs. Because the non-deterministic behavior of monitor-based parallel programs.

This thesis describes the design and implementation of a performance prediction tool for monitor-based parallel programs. It applies a hybrid method for performance prediction. It uses static program analysis to predict the performance of sequential programs and uses both measurement and simulation to predict the performance of parallel programs. This thesis also presents a primitive evaluation for this performance prediction tool.

第一章、導論 1
1-1 研究動機 1
1-2 研究方法 3
1-3 研究貢獻 5
1-4 論文架構 5
第二章、簡介CCC平行程式語言 6
2-1 控制平行 7
2-1-1 控制平行函式的定義 8
2-1-2 控制平行區段的定義 8
2-2 監督結構 10
2-3 CCC的語法樹 14
2-3-1 語法樹節點 16
第三章、循序程式的效能預測 22
3-1 效能預測架構 23
3-2 暗示指令 25
3-3 函式執行時間的預測 27
3-3-1 運算敘述 28
3-3-2 if條件敘述 29
3-3-3 switch條件敘述 30
3-3-4 for迴圈敘述 30
3-3-5 while迴圈敘述 31
3-3-6 dowhile迴圈敘述 32
3-3-7 函式呼叫敘述 32
3-4 範例 33
第四章、平行程式的效能預測 39
4-1 監督結構模型 40
4-2 監督結構的到達速率和服務速率 44
4-2-1 Poisson Distribution 45
4-3 暗示指令 46
4-3-1 監督結構的暗示指令 46
4-3-2 控制平行呼叫結構的暗示指令 47
4-4 模擬器 48
4-5 範例 53
4-5-1 程式碼 54
4-5-2 監督結構的架構 56
4-5-3 暗示指令 57
第五章、實驗結果 59
5-1 生產者、消費者問題 60
5-2 瓦嚇爾節點遞移演算法 62
5-2-1 程式碼 63
5-2-3 監督結構的架構 65
5-2-3 暗示指令 66
5-2-4 預測結果 67
5-3 高斯消去法 69
5-3-1 程式碼 72
5-3-2 監督結構的架構 74
5-3-3 暗示指令 75
5-3-4 預測結果 76
第六章、結論與未來展望 78
6-1 結論 78
6-2 末來展望 78
參考文獻 80

[1]L. De Rose and D. A. Reed, SvPable: A Multi-Language Performance Analysis System, Proceedings of 1999 International Conference on Parallel Processing, September 1999.

[2]B. P. Miller, M. D. Callaghan, J. M., Cargille, J. K., Hollingsworth, B. R., Irvin, K. L., Karavanic, K., Kunchithapadam, and T. Newhall, The Paradyn Parallel Performance Measurement Tools, IEEE Computer 28, 11, November 1995.

[3]J. C. Yan, S. R. Sarukkai, and P. Mehra, Performance Measurement, Visualization and Modeling of Parallel and Distributed Programs Using the AIMS Toolkit, Software Practice & Experience 25, April 1995.

[4]Sheng-Chau Juang, A Performance Analysis Tool for CCC Parallel Programming Language, National Chung Cheng Univ., Taiwan, R.O.C.,2003

[5]Manish Parashar, Salim Hariri, Compile-Time Performance Prediction of HPF/Fortran 90D, Parallel & Distributed Technology: Systems & Applications, Spring 1996

[6]Guilherme E. Vieira, Jeffrey W. Herrmann, Edward Lin, Predicting the Performance of Rescheduling Strategies for Parallel Machine Systems, Journal of Manufacturing Systems, Vol.19/No.4, 2000

[7]Valerie Taylor, Xingfu Wu, Jonathan Geisler, Rick Stevens, Using Kernel Couplings to Predict Parallel Application Performance, Proceedings of the 11 th IEEE International Symposium on High Performance Distributed Computing HPDC-11 20002 (HPDC'02), 2002

[8]Vikram S. Adve, Mary K. Vernon, Parallel program performance prediction using deterministic task graph analysis, ACM Transactions on Computer Systems (TOCS) Volume 22, Issue 1, Pages: 94 – 136, February 2004

[9]Calin Cascaval, Luiz DeRose, Dvaid A. Padua, Daniel A. Reed, Compile-time Based Performance Prediction, Lecture Notes In Computer Science Vol. 1863, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, 1999

[10]Shi-Yen Ho, A Type Checker for Parallel Programming Language CCC, National Chung Cheng Univ., Taiwan, R.O.C.,2002

[11]RAJ JAIN, The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling, Wiley- Interscience, New York, NY, April 1991