臺灣博碩士論文加值系統

CLIPS 程式語言常用於開發專家系統應用，該語言的特性與C或JAVA這類演算法式程式語言不同，開發人員不需詳細定義執行的步驟，而是定義解決問題的方式透過推理找出答案，但推理的過程中會受資料量及應用複雜度的影響，資料量或複雜度的增加會使執行時間大幅度的增加。由於多核心電腦、叢集系統、格網系統與雲端運算的普及，如何擴充CLIPS為平行語言，並藉用這些技術的平行計算能力，大幅縮短程式所需的執行時間，成為一個非常重要的研究議題。
在先前研究中我們提出兩種不同的平行化方法，能透過平行的方式加速專家系統應用的執行，但上述所提程式設計模型在處理複雜的應用時，未能同時提供良好的平行度、程式彈性及簡易的操作等層面，前述問題係由於應用在平行化時僅能選擇其中一種方法加速執行，若有無法平行的部份則是保持原先循序的方式執行所造成；為了完善先前設計，我們提出流程式平行程式開發模型，以專案規劃的方式提供專家系統應用開發人員有效率且易於上手的平行開發方式，該開發模型根據不同執行特性分成數個區段，每個區段都能使用不同的平行化方法加速，且能透過工作流程的設定區段執行的先後，以符合應用本身的執行順序；其中，目前設計中提供四種區段執行方式，考慮到區段有可能無法被平行執行，因此區段執行方式除了先前研究中的兩種平行化方式和新提出的平行化方式外，我們還設計循序執行的選項；另外，在研究的過程中我們發現有些彼此獨立的區段，本身雖然無法平行執行，但可同時執行這些區段，為了將該平行執行方式加入開發模型中，我們利用原先工作流程的設計，提供額外的執行方式供開發人員選擇。
因為以平行加速執行時係將應用分成數個區段後依各自設定的方式執行，故能提高應用的平行度及執行效能；除此之外，區段執行方式的設定及先後順序都可以根據開發人員的需求進行調整，在設計時能更有彈性，也能藉由選擇合適的設計，進一步提高平行後的效能增益。從實驗數據來看，在知識系統的應用中平行後所帶來的效能增益最多能達到25倍左右，而人力資源網站的應用則是能達到260倍左右的效能增益；除了透過實驗呈現新設計的效能增益外，我們更進一步探討平行化專家系統應用時影響實驗結果的因素，並整理出幾點平行化時的建議供專家系統應用開發人員參考。

CLIPS language is designed especially for developing expert systems. Programmers have no need to write algorithms for solving problems. Instead, they only need to list facts and rules. The feature makes the execution time much longer. In this thesis, we study how to utilize the compute power of emerging multicore computers, cluster systems, grid systems and cloud systems to parallelize CLIPS applications.
Previously, we proposed different techniques to enable programmers to use the originally sequential CLIPS language to write parallel applications with newly defined parallel syntax and directives. These techniques can garner superlinear speedups because of the feature of the CLIPS inference engine. However, each application can be parallelized by only one of our proposed techniques.
To further improve the performance, we propose a workflow-based parallel programming model in this thesis for enabling more complicate application developments. Programmers can partition an application into sections and specify the execution order of the sections by a workflow. A section can be parallelized either automatically by our system if there are no data dependences between tasks in the section or manually by inserting parallel functions otherwise. Different sections can be executed in parallel or sequentially. The outcomes of parallel sections can be merged by one of our proposed logical operations. The proposed workflow-based model can exploit different kinds of parallelism for a single application and achieve much better performance.

中文摘要 IV
英文摘要 V
致謝 VI
圖目錄 VIII
表目錄 X
第一章 緒論 1
第二章 相關文獻 4
第一節 專家系統 4
第二節 CLIPS和Fuzzy CLIPS 5
第三節 負載平衡問題及自我排程機制 6
第四節 Data-parallel programming mode 7
第五節 Send-receive programming mode 11
第三章 工作流程式平行程式開發模型 14
第一節 設計理念 14
第二節 平行程式模型設計 23
第三節 軟體系統架構 29
第四章 研究成果與探討 35
第一節 應用說明及執行特性 35
第二節 實驗結果 37
第五章 總結與未來展望 45
第六章 參考文獻 47

圖 1. 先前研究中平行化CLIPS應用範例圖 2
圖 2. 流程式平行程式開發模型工作流程示意圖 3
圖 3. 簡單循序CLIPS程式範例 5
圖 4. 不同排程機制工作量分佈曲線圖 7
圖 5. SPMD程式設計模型範例 8
圖 6. 採data-parallel方法平行化程式設計模型範例 9
圖 7. 採data-parallel平行化Fuzzy CLIPS程式執行流程圖 10
圖 8. 採send-receive平行化Fuzzy CLIPS程式流程圖 11
圖 9. 將給不同節點之事實放入對應緩衝區示意圖 12
圖 10. 節點間以副程式處理訊息傳遞示意圖 12
圖 11. 範例一：混和式平行化示意圖 17
圖 12. 範例一：區段S1,S2中節點互動示意圖 17
圖 13. 範例二：以data-parallel平行化資料流示意圖 18
圖 14. 範例二：以data-parallel平行化工作流示意圖 19
圖 15. 範例二：以job-parallel 平行化資料流示意圖 20
圖 16. 範例二：以job-parallel 平行化工作流示意圖 20
圖 17. 依序執行之執行方式示意圖 21
圖 18. 非中斷平行之執行方式示意圖 22
圖 19. 中斷平行之執行方式示意圖 23
圖 20. 專案式程式規劃，平行前後檔案內容對應表 24
圖 21. 平行化專家系統應用程式流程及檔案內容對應示意圖 31
圖 22. Source-to-source interpreter架構圖 31
圖 23. 重要性歸屬函數 36
圖 24. 符合程度歸屬函數 36
圖 25. 人力資源網工作經驗及科系要求欄位設定畫面 36
圖 26. 模糊聚合運算後結果(依符合程度排序) 37
圖 27. 以不同自我排程機制進行平行化效能增益(不同資料量) 39
圖 28. 以不同排程機制進行data-parallel平行化執行時間(不同processor數) 39
圖 29. 不同平行化方法使用8個processors效能增益圖(不同資料量) 40
圖 30. 不同排程機制使用32個processors效能增益圖(不同資料量) 41
圖 31. 不同排程機制平行化效能增益(不同processor數) 41
圖 32. 以不同機型為主節點採CSS(50)排程機制所需執行時間 43
圖 33. 以GSS排程機制執行多次執行時間分佈圖 44
圖 34. 不同排程機制下各節點工作負載示意圖 44

表 1. 不同排程機制具體分配工作量一覽表 7
表 2. 新增平行化假指令定義及用途 10
表 3. 新增平行化語法定義及用途 13
表 4. 專案檔中區段支援平行化語法一覽表 15
表 5. 流程式平行開發模型所支援執行方式一覽表 16
表 6. 新開發模型支援平行化方式整理 29
表 7. Source-to-source interpreter之巴克斯範式、動作符號及代符格式 32
表 8. 平行化實驗環境設定一覽表 37
表 9. 不同平行化方式執行時間對照表 40

[1] J.C. Giarratano, and G.D. Riley, Expert Systems: Principles and Programming, Fourth ed.: Course Technology, 2004.
[2] CLIPS. "CLIPS: A Tool for Building Expert Systems," http://clipsrules.sourceforge.net/.
[3] T. Amagasa, K. Kido, and H. Kitagawa, “Querying XML Data using PC Cluster System,” in 8th International Conference on Database and Expert Systems Applications, pp. 5-9, 2007.
[4] T. He, J. Ni, and G. Wang, “A Heterogeneous Windows Cluster System for Medical Image Reconstruction,” in Proceedings of the First International Multi-Symposiums on Computer and Computational Sciences, pp. 410-415, 2006.
[5] L. JaeDeok, C. ByeongCheol, P. SoHee et al., “A Study of Providing the Integrity on Cluster System,” in 10th International Conference on Advanced Communication Technology, pp. 1925-1928, 2008.
[6] O. Mori, S. Matunaga, and N. Waeda, “Research and development of tethered satellite cluster systems,” in Proceedings. 2000 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2000 (IROS 2000), pp. 1834-1840, 2000.
[7] E. Bartocci, D. Cacciagrano, N. Cannata et al., “An Agent-Based Multilayer Architecture for Bioinformatics Grids,” in IEEE Transactions on NanoBioscience, pp. 142-148, 2007.
[8] A. Chervenak, I. Foster, C. Kesselman et al., “The Data Grid: Towards an Architecture for Distributed Management and Analysis of Large Scientific Datasets,” in J. Network and Computer Applications, pp. 187-200, 2000.
[9] I. Foster, C. Kesselman, and S. Tuecke, “The anatomy of the Grid: Enabling Scalable Virtual Organizations,” in International J. Supercomputer Applications, pp. 200-222, 2001.
[10] F. Fox, and D. Gannon, “Computational grids,” in IEEE Computing in Science and Engineering, pp. 74-77, 2001.
[11] W. Li, M. V. P. Dib, and D. A. Cardoso, “Grid Service Agents for Real Time Traffic Synchronization,” in Proceedings of WI '04, pp. 619-623, 2004.
[12] L. Meng, L. Bai, and W. Yang, “A Grid Information Service Model Based on E-Learning Grid,” in Proceedings of ICNC'07, pp. 545-548, 2007.
[13] MPICH2. "MPICH2: High-performance and Widely Portable MPI," http://www-unix.mcs.anl.gov/mpi/mpich1/.
[14] MPI: Message Passing Interface Standard. http://www-unix.mcs.anl.gov/mpi/.
[15] C.C. Wu, L.F. Lai, and Y.S. Chang, “A Study of Designing a Grid-Enabled Expert System Language,” Journal of the Chinese Institute of Engineers, vol. 31, pp. 7, 2008.
[16] C.C. Wu, L.F. Lai, and Y.S. Chang, “Towards Automatic Load Balancing for Programming Parallel Fuzzy Expert Systems in Heterogeneous Clusters,” Journal of Internet Technology, vol. 10, no. 2, pp. 8, 2009.
[17] C.C. Wu, L.F. Lai, C.T. Yang et al., “Using Hybrid MPI and OpenMP Programming to Optimize Communications in Parallel Loop Self-Scheduling Schemes for Multicore PC Clusters,” Journal of Supercomputing, 2009.
[18] C.C. Wu, L.F. Lai, and Y.S. Chang, “Extending FuzzyCLIPS for Parallelizing Data-Dependent Fuzzy Expert Systems,” Journal of Supercomputing, 2010.
[19] C.C. Wu, L.F. Lai, J.Y. Ke et al., “Designing a Parallel Fuzzy Expert System Programming Model with Adaptive Load Balancing Capability for Cloud Computing,” Journal of Computers, vol. 21, no. 1, pp. 10, 2010.
[20] C.C. Wu, L.F. Lai, and Y.S. Chang, “Parallelizing CLIPS-based Expert Systems by the Permutation Feature of Pattern Matching,” in In Proceedings of the 2nd Computer Engineering and Applications, 2010.
[21] C.C. Wu, “Parallelizing a CLIPS-based Course Timetabling,” Expert System: Expert Systems with Applications, vol. 38, pp. 6, 2011.
[22] M. Ahfaz Khan, A.K. Sharma, and R.Saxena, “Expert System for Power Transformer Condition Monitoring and Diagnosis,” in Power Electronics, Drives and Energy Systems, pp. 1-6, 2006.
[23] M.A. Azadeh, S. Sharifi, and H. Izadbakhsh, “Integration of Expert System and Integer Programming for Optimization of Strategic Planning,” in IEEE International Conference on Industrial Informatics, pp. 966-973, 2006.
[24] B.R. Kumar, J. Shanmugam, S. Janarthanan et al., “Development of expert system for the design of airborne equipment,” in The 23rd Digital Avionics Systems Conference, 2004.
[25] M. Mahmoud, N. Algadi, and A. Ali, “Expert System for Banking Credit Decision,” in International Conference on Computer Science and Information Technology, pp. 813-819, 2008.
[26] K. Zalis, “Application of expert systems in diagnostics of high voltage insulating systems,” in Proceedings of the IEEE International Conference on Solid Dielectrics, pp. 691-694, 2004.
[27] FuzzyCLIPS. http://www.iit.nrc.ca/IR_public/fuzzy/fuzzyClips/fuzzyCLIPSIndex.html.
[28] H.J. Zimmermann, “Fuzzy set theory and its applications,” Kluwer Academic Publishers, vol. 2nd revised edition, 1991.
[29] Christopher A. Bohn, and Gary B. Lamont, “Load Balancing for Heterogeneous Clusters of PCs,” Future Generation Computer Systems, vol. 18, pp. 389-400, 2002.
[30] C.D. Polychronopoulos, and D. Kuck, “Guided Self-Scheduling: a Practical Scheduling Scheme for Parallel Supercomputers,” IEEE Trans. on Computers, vol. 36, pp. 1425-1439, 1987.
[31] S.F. Hummel, E. Schonberg, and L.E. Flynn, “Factoring, a Scheme for Scheduling Parallel Loops,” Communications of the ACM, vol. 35, no. 8, 1992.
[32] T.H. Tzen, and L.M. Ni, “Trapezoid Self-Scheduling: A Practical Scheduling Scheme for Parallel Compilers,” IEEE Trans. on Parallel and Distributed Systems, vol. 4, no. 1, pp. 87-98, 1993.
[33] C.T. Chen, “Extensions of the TOPSIS for group decision-making under fuzzy environment,” Fuzzy Sets and Systems, vol. 114, no. 1, pp. 1-9, 2000.
[34] S.J. Chen, and C.L. Hwang, “Fuzzy Multiple Attribute Decision Making: Methods and Applications,” Springer, Berlin, 1992.
[35] G.R. Jahanshahloo, F. Hosseinzadeh Lotfi, and M. Izadikhah, “Extension of the TOPSIS method for decision-making problems with fuzzy data,” Applied Mathematics and Computation, vol. 181, no. 2, pp. 1544-1551, 2006.
[36] Y.M. Wang, and T.M.S. Elhag, “Fuzzy TOPSIS method based on alpha level sets with an application to bridge risk assessment,” Expert Systems with Applications, vol. 31, pp. 309-319, 2006.
[37] T. Yang, and C.C. Hung, “Multiple-attribute decision making methods for plant layout design problem,” Robotics and Computer-Integrated Manufacturing, vol. 23, pp. 126-137, 2007.