臺灣博碩士論文加值系統

資料流計算模式被認為是最自然達到高度平性處理的方法，而程序式語言的設計方式卻較為人們所接受，但是資料流計算模式不同於傳統計算機系統運作模式。因此，本論文旨在研發一個程序式語言轉譯成資料流計算模式的轉譯器，用以提供程序式語言程式在資料流計算機平台上執行。
轉譯器的研發是以派翠網為系統描模工具，利用派翠網架構資料流系統。研究的方法以程序式語言中的序列(sequence)算式、選擇(selection)敘述、與迴圈(looping)敘述為實例。首先，利用自由軟體基金會(Free Software Foundation)所提供的Flex和Bison兩個分析產生程式發展轉譯器的語彙、語法、與語意分析三個步驟，這些工具可以協助快速地完成分析階段。其次，合成階段中分為四個步驟進行派翠網路建模，步驟依序是基本算式派翠網建模、控制敘述派翠網建模、變數視界階層相關派翠網模型調整連結、以及變數相依性的搜尋與連結。最後，進行派翠網模型的模擬驗證與效能評估的工作，用以證明資料流計算模式的優異性。

The dataflow computing system has been recognized to as the innovative computing platform that is able to achieve highly parallel process in the most natural style. However, the most of programmer are trained to use the procedural programming language to realize the software systems. Specifically, the dataflow computing system is accepted to perform the intensive computing tasks more outstanding than the traditional computing systems. Thus, the aim of this thesis is to develop a translator which compiles a procedural language program to the corresponding dataflow computing model. The translator will make the procedural language programs that can be executed on a dataflow computing platform, easily and conveniently.
Petri net is an internal representation of the translated dataflow computing model in our research. In order to systematically construct the dataflow computing model on Petri nets, there are some primitive Petri net templates being constructed to correspond the primary statements of procedural languages that include sequence, selection, and looping statements. In general, the compiler will be composed by analysis and synthesis phases. First, we implement lexical analysis, syntax analysis and semantic analysis of the translator by Flex and Bison as two tools for rapidly generating analysis programs. Secondly, there are four steps in the synthesis phase, that are different to the traditional synthesis phase, to convert the parse tree into the corresponding Petri net model. The function of revised synthesis phase includes the modeling Petri net from basic expressions and control statements, adjusting the links of some sub-Petri net models referring to the variable scope levels, and reconstructing the Petri net links on the dependent variables according to the statement sequence. Finally, we perform the simulation and verification on the generated Petri net models to exemplify the correctness and efficiency of the translated dataflow computing model.

中文摘要………………………………………………………………… i
英文摘要…………………………………………………………………ii
致謝………………………………………………………………………iv
目錄……………………………………………………………………… v
圖目錄………………………………………………………………… vii
表目錄……………………………………………………………………ix

第一章 緒論………………………………………………………………1
1-1研究動機………………………………………………………………1
1-2文獻回顧………………………………………………………………3
1-3章節提要………………………………………………………………3
第二章 派翠網模式的資料流系統………………………………………5
2-1 派翠網基本原理………………………………………………5
2-2資料流系統之派翠網樣版…………………………………… 6
2-3派翠網之資料結構…………………………………………… 9
2-4派翠網基本執行規則…………………………………………11
第三章 轉譯器的研發方法…………………………………………… 13
3-1 基本算式派翠網建模……………………………………… 17
3-2 控制敘述派翠網建模……………………………………… 18
3-3 變數視界階層相關派翠網模型調整連結………………… 19
3-4 數相依性的搜尋與連結…………………………………… 23
3-4-1 一般算式的變數相依性連結…………………………23
3-4-2 控制敘述的變數相依性連結…………………………26
3-4-2-1 控制敘述中資料通道的分析………………26
3-4-2-2 變數相依性的搜尋…………………………28
3-4-2-3 資料與控制連結的建構……………………30
第四章 資料流架構的實例分析與效能評估………………………… 34
4-1 實例驗證與分析……………………………………………………34
4-1-1 while迴圈敘述之派翠網模型的實例驗證…………………… 35
4-1-2 if-then-else選擇敘述之派翠網模型的實例驗證……………36
4-2 系統的效能評估與比較……………………………………………38
第五章 結論…………………………………………………………… 41
參考文獻…………………………………………………………………42
作者簡介…………………………………………………………………44

[1] W. Y. Hsu, C. P. Hwang, K. T. Lee, H. Y. Yu, “The Study of Translator for Compiling a C-like Procedural Language to Data Flow Model,” Cross Strait Tri-regional Radio Science and Wireless Technology Conference (CSTRWC2005), pp. 533-537, Beijing, August 2005.
[2] T. Yuba, T. Shimada, Y. Yamaguchi, K. Hiraki, and S. Sakai, “Dataflow computer development in Japan,” Proceedings of the 4th international conference on Supercomputing, vol. 18, no. 3, pp. 140–147, 1990.
[3] D. A. Patterson and J. L. Hennessy, Computer Organization and Design, San Francisco, California: Morgan Kaufmann Publishers, Inc., 1998.
[4] W. Wolf, “A Decade of Hardware/Software Codesign,” IEEE Computer, vol. 36, no. 4, pp. 38–43, April 2003.
[5] J. M. P. Cardoso and M. P. Vestias, “Architectures and Compiler to Support Reconfigurable Computing,” ACM Crossroads Student Magazine, 1999.
[6] P. Eles, K. Kuchcinski, Z. Peng, and M. Minea, “Compiling VHDL into a High-level Synthesis Design Representation,” Design Automation Conference, EURO-VHDL '92, September 1992, pp.604–609.
[7] J. L. Peterson, Petri Net Theory and the Modeling of Systems, Prentice-hall, Inc., Englewood Cliffs, 1981.
[8] J. L. Peterson, “Petri Nets,” ACM Computing Surveys, vol. 9 no. 3, pp. 223–252, September 1977.
[9] W. Yao and X. He, “Mapping Petri Nets to Parallel Programs in C&C++,” Proceedings of 20th International Conference on Computer Software and Applications, pp.70–75, August 1996.
[10] Free Software Foundation, Inc., Flex Tutorial, http://www.gnu.org/ software/flex/, 2005.
[11] Free Software Foundation, Inc., Bison Tutorial, http://www.gnu.org/ software/bison/, 2005.
[12] T. Niemann, “A Compact Guide to Lex & Yacc,” http://epaperpress.com, 2005.
[13] ARM, Inc., ARM10 Thumb Family Product Overview, http://www.arm.com/pdfs/ DVI0014A_ARM10T_PO.pdf, 2000.