跳到主要內容

臺灣博碩士論文加值系統

(3.87.250.158) 您好!臺灣時間:2022/01/25 19:36
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:洪國書
研究生(外文):kshong
論文名稱:平行程式的除錯機制與封包追蹤
論文名稱(外文):The debug mechanism and message packet tracing of parallel program
指導教授:林偉林偉引用關係
指導教授(外文):Wei Lin
學位類別:碩士
校院名稱:國立中興大學
系所名稱:資訊科學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
中文關鍵詞:平行程式除錯通道拓樸死結相依關係追蹤樹
外文關鍵詞:parallel programDebugchannelTopologyDeadlockDependencyTracing tree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:1263
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
平行程式的撰寫與除錯要比一般循序程式來的困難許多,因此我們設計
出利用Microsoft Windows 作業系統的多緒處理來模擬我們的平行程式,由於平行程式的設計的同時,可能存在許許多多錯誤,包括 run-time error,或 compile time 的 error 這一些錯誤,包括 Channel definition, Racing problem, send() function與 receive() function 之間的同步問題,等等,都是必須要避免並且我們希望能在模擬的階段完成錯誤的偵測!本篇論文,是延續前作 ”以多執行緒為基礎的平行系統模擬工具”,在其定義的 POP97 的平行語言以及其模擬工具之上,增加了除錯的功能,並且對於其架構作了部分的改進,以期能更適切的模擬平行程式的行為。
關鍵字:平行處理系統、平行程式設計、多執行緒、模擬器、死結、除錯

It is more difficult to write and debug parallel program than sequential one,so we design the parallel system to simulate our parallel program by using the multi-
threading processing of Microsoft Windows operation system. But in the tme of designing parallel program, some errors would happen, such as run-time error, or compile-time error. Those errors include Channel redefinition, Racing problem, send() function and receive() function synchronization, etc. All of them should be avoided in our parallel program, and we expect that we can make all error detection in the simulation. This thesis is continued after the one “A multithread-Based Simulation Tool for Parallel system”. The before thesis define the POP97 parallel language and develop some simulation tools of parallel system. we add some debug function and improve the system architecture on the POP97 parallel language on it, expecting to simulate the behavior of parallel program more suitability.
Keyword: parallel system, multi-threading , simulation, deadlock, debug,

誌謝 2
Abstract 4
目錄 5
第一章 緒論 8
1.1動機 8
1.2 目標 8
1.3 目前平行程式除錯機制的發展狀況 8
第二章背景知識與相關研究 10
2.1 背景知識 10
2.2 關鍵字與名詞解釋 10
2.4 作業系統之 context switch 與多緒模擬系統的關係 12
2.5 平行程式的除錯 13
第三章 POP97平行程式語言及平行程式模擬系統 14
3.1 POP97 的新增原件 14
3.2 POP97 的特性 14
3.2.1 POP97 處理程序的定義 14
3.2.2 POP97 Channel 程序的定義 15
3.3 POP97 平行語言的架構 16
第四章 系統架構實作 19
4.1 模擬碼產生及執行之流程 19
4.2平行程式模擬碼的架構 20
4.3 模擬機制 22
4.3 手動排程演算法 23
4.4 Deadlock 的發生原因 25
4.6 結語 25
第五章 平行程式的各種錯誤 27
5.1編譯時期的錯誤與解決 27
5.1.1 編譯時期的錯誤 (compile-time error) 27
5.1.2 Channel 的中重複定義 27
5.1.3 迴路 (Loop Channel) 30
5.1.4 不符合拓樸定義的Channel Access 31
5.2 位移對應問題 (Shifted Mapping problem) 38
5.3 Run-time 中 Deadlock 的偵測與顯示 43
第六章 封包追蹤與節點之間的相依關係 46
6.1 處理程序之間與處理程序內部的相依關係 47
6.2 處理程序內部的相依關係與實作 48
6.2.1 Lex 的工作原理 49
6.2.2 利用 Lex 找出程式碼內的相依關係 50
6.2 Run time 的封包追蹤 60
6.3 Tracing tree 的建構與展示 62
6.3.1 Tracing tree 的建構實之演算法 67
6.3.2 利用遞迴函式展示Tracing tree 69
第七章結論與未來工作 71
7.1 解決資料流回朔的根本之道 71
7.2 作業系統對 context switch 對模擬程式的影響 71
7.3 結論 72
附錄 73
附錄A: scan.l 之原始碼 73
參考文獻 81
圖 2.1 CONTEX SWITCH 對效益量測的影響 12
圖 3.1 POP97 程式語言拓樸定義範例 16
表4.1 模擬碼程式流程圖 19
圖 4.2 中央控管式的多緒程式模擬程式 22
圖 4.3 手動排程演算法之流程圖 24
圖5.1 CHANNEL 重複定義範例 28
圖 5.2 迴路型態的 CHANNEL 定義 30
圖 5.4 TEST.&PA 所產生的 TEST.&DB 範例 34
圖 5.5 SHIFTED-MAPPING 問題的拓樸範例 39
圖 5.6 手動排程演算法與死結處理之流程圖 45
圖 6.1 處理程序之間之相依關係 47
圖 6.1 處理程序內部 SEND()/RECEIVE() 之相依關係 51
圖 6.3 IF條件式的相依關係處理範例 56
圖 6.4 追蹤樹的建構方法一 63
圖 6.5 方法一的建構方式可能產生的問題 64
圖 6.6 追蹤樹的建構方法二 65
圖 6.8 SEND() 以影響自己最近的 RECEIVE() 為父節點 67

[1] DIANNE P. O’LEARY AND G.W. STEWART. “Data-flow Algorithms for Parallel Matrix Computations”, Research Contributions, August 1985 Volume 28 Number 8, pp.840-852.
[2] Introduction to VLSI systems, “Chapter 8: Highly Concurrent Systems”, Carver Mead and Lynn Conway, Addison_Wesley Publishing Company.
[3] ParaSoft Corporation, “Express User’s Guides Version 3.2 —C”, 1992.
[4] Oak Ridge National Laboratory (ORNL), “PVM3 USER‘S GUIDE AND REFERENCE MANUAL”, September 1994.
[5] Thinking Machine Corporation, “The Connection Machine CM-5 Technical”, Thinking Machine Corporation, Massachusetts, 1992.
[6] Occam Inmos Ltd., “Occam Programming the Butterfly Parallel Processor”, 1986.
[7] Ncube Corporation, “Ncube Users’ Handbook”, 1987.
[8] MEIKO Corporation, “MEIKO C Programming Reference Manual”, 1989.
[9] Jim Beveridge, Robert Wiener, “Multithreading Applications in Win32: The Complete Guide to Threads”, Addison Wesley, December 1996.
[10] Peter Newton, James C. Browne, “The CODE 2.0 Graphical Parallel Programming Language”, Technical report, Department of Computer Sciences, University of Texas at Austin, Austin, TX.ACM Press, July 1992.
[11] B. Appelbe, K. Smith and C. McDowell, “Star/Pat: A Parallel-Programming Toolkit”, IEEE Software, page 29, July 1989.
[12] R. M. Keller and W. C. Yen, “A Graphical Approach to Software Development Using Function Graphs”, In Proceeding of Compcon Spring, page 156, 1981.
[13] Vincent Van Dongen, C. bonello, and G. Gao, “Data Parallelism with High Performance C”, In Proceedings of the Supercomputing Symposium ’94, pages 128-135, Toronto, Canada, June 1994.
[14] D. B. Loveman, “High Performance Fortran”, IEEE Parallel and Distributed Technology: Systems and Applications, 1 (1): 25-42, February 1993.
[15] F. Bodin, P. Beckman, D. Gannon, S. Yang, S. Kesavan, A. Malony, and B. Mohr, “Implementing a Parallel C++ Runtime System for Scalable Parallel Systems”, In Proceedings of the 1993 Supercomputing Symposium Conference, pages 558-597, Portland, OR, November 1993.
[16] John B. Evans, “Structures of Discrete Event Simulation: “An Introduction to the Engagement Strategy”, Ellis Horwood Series in Artificial Intelligence, Ellis Horwood Limited, Halsted Press, a division of John Wiley & Sons, 1998.
[17] Kimming So, Frederical Darema, David A. George, V. Alan Norton, and Gregory F. Pfister, “PSIMUL─A System for Parallel Simulation of Parallel System”, In Joanne L. Martin, editor, Performance Evaluation of Supercomputers, volume 4 of Special Topics in Supercomputing, pages 187-211, North-Holland, 1988.
[18] I. Mathieson and R. Francis, “A Dynamic-Trace-Driven Simulator for Evaluating Parallelism”, In Proceedings of the 21th Annual Hawaii International Conference on System Sciences, volume 1 (Architecture), pages 158-166, Kailua-Kona, Hawaii, January 1988.
[19] R. G. Covington, S. Dwarkadas, J. R. Jump, J. B. Sinclair, and S. Madala, “The Effcient Simulation of Parallel Computer Systems”, International Journal in Computer Simulation, 1: 31-58, June 1991.
[20] Helen Davis, Stephen R. Goldschmidt, and John Hennessy, “Multiprocessor Simulation and Tracing Using Tango”, In Proceedings of the 1991 International Conference on Parallel Processing, volume II, pages 99-107, Pleasant Run, IL, August 1991, CRC Press, Inc.
[21] Eric Allen Brewer and Chrysanthos n. Dellarocas, “Proteus: A Hight Performance Parallel-Architecture Simulator”, Performance Evaluation Review, 20 (1) : 247-248, June 1992.
[22] S. Madala, “Concurrent C User’s Manual”, Technical report, Dept. of Electrical and Computer Engineering, Rice University, Houston, TX, January 1987.
[23] R. G. Covington, S. Madala, V. Mehta, J. R. Jump, and J. B. Sinclair, “The Rice Parallel Processing Testbed”, In Proceedings of the 1988 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, volume 16 of Performance Evaluation Review, pages 4-11, Sante Fe, NM, May 1988, ACM Press.
[24] Eric Allen Brewer, “Aspects of a Parallel-Architecture Simulator”, Technical Report MIT/LCS/TR-527, Massachusetts Institute of Technology, January 1992.A slight modification of Brewer’s Master’s thesis.
[25] Eric Reiher, Herbert H. J. Hum, and Ajit Singh, “Simulating Networks of Superscalar Processors”, In Proceedings of the 27th Annual Simulation Symposium, pages 125-133, La Jolla, CA, April 1994.
[26] G. Hurteau, Vincent Van Dongen, and G. Gao, “Overview of EPPP─An Environment for Portable Parallel Programming”, In Proceedings of the Supercomputing Symposium ’94, pages 119-127, Toronto, Canada, June 1994.
[27] Erik Demaine, “Efficient Simulation of Message-Passing in Distributed-Memory Architectures”, Department of Computer Science, University of Waterloo, Ontario, Canada, 1996.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top