Research

Research Interests:

programming languages and compilers, software testing, Chinese medical engineering

Research Projects:

Programming Languages and Compilers:

One of our main research fulfillments for recent years is the design and implementation of adaptive GCC compilers [1, 2, 3, 4]. Compilers usually provide a large number of optimization options for users to fine tune the performance of their programs. For example, the GCC version 4.1.2 provides more than one hundred optimization options. This large number of optimization options gives users a good potential to generate more efficient code. These optimization options are, however, rarely used because most users are not familiar with compiler optimizations and the interactions between compiler optimizations are too complex. Compilers hence usually provide a number of optimization levels each of which pre-selects a group of optimization options for users. For example, the GCC version 4.1.2 provides optimization levels: O1, O2, O3, and Os. Although optimization levels provide good efficiency for most programs, they exploit only a portion of the available optimization options.
This research proposes a new genetic algorithm, called a gene weighted genetic algorithm, to search for the optimal optimization options for a specific source code [1]. This research also investigates the effectiveness of three optimization algorithms: the random algorithm, the basic genetic algorithm, and the gene weighted genetic algorithm. The experiments show that the two genetic algorithms significantly outperform the random algorithm and the gene weighted genetic algorithm notably outperforms the basic genetic algorithm in most benchmarks. This demonstrates that the gene weighted genetic algorithm evolves notably faster than the basic genetic algorithm in most benchmarks. This research also investigates the effectiveness of using local search algorithms such as the hill-climbing algorithm [2]. The experiments show that the hill-climbing algorithm can achieve an improvement rate comparable with the basic genetic algorithm with much less execution time. This research also investigates the effectiveness of using two search space reduction techniques [4]. The first technique checks whether each optimization option has an effect on the source code. The experiment shows that there is no observable performance degradation by eliminating 46.62% optimization options on average. The second technique partitions the search process into three stages according to the optimization phases on different intermediate languages. Using these two techniques, on average the search time is reduced 71.53%, while the performance is only degraded 2.7%.
The execution order of the selected optimization phases may also affect the performance. This research extends the GCC compiler to have the capability of dynamically ordering the optimization phases [3]. This research also implements a phase sequence generator that can adaptively generate an optimization phase sequence suitable for the input program. The phase sequence generation contains optimization phase selection and optimization phase ordering. The optimization phase selection and the optimization phase ordering can be uniformly performed at the same time, called the hybrid phase ordering, or the optimization phase selection can be performed first and followed by the optimization phase ordering, called the separate phase ordering. The preliminary experiments show that the average improvement rate is 8.12% for the hybrid phase ordering, while the average improvement rate is very low for the separate phase ordering.
References:
1. S.-C. Lin, C.-K. Chang, N.-W. Lin, "Automatic Selection of GCC Optimization Options Using A Gene Weighted Genetic Algorithm," Proceeding of 2008 International Symposium on Frontiers in Computer Architecture Design, 2008.
2. Y.-L. Hu, C.-K. Chang, N.-W. Lin, "Automatic Selection of Optimization Options Based On Local Search," Proceedings of the 10th International Conference on High-Performance Computing in Asia-Pacific Region, 2009.
3. C.-H. Lin, C.-K. Chang, N.-W. Lin, "Adaptive Optimization Phase Ordering in GCC," Proceedings of the 10th International Conference on High-Performance Computing in Asia-Pacific Region, 2009.
4. T.-K. Chang and N.-W. Lin, "Speeding up Automatic Compiler Optimization Option Selection Using Search Space Reduction," Proceedings of Workshop on Software Engineering and Programming Language, National Computer Symposium, 2011, pp.1- 10.

Software Testing:

One of our main research fulfillments for recent years is the design and implementation of several semiautomatic and automatic test case generators [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Software testing is the main activity to ensure the quality of software. However, test case generation is still performed manually at present. This research has developed several semiautomatic and automatic test case generators based on the model-based approach. These test case generators use Unified Modeling Language (UML) and Object Constraint Language (OCL) to specify the dynamic behaviors of Java methods or classes. The test cases generated are executed on the JUnit/ JFCUnit testing framework.
There are four semiautomatic test case generators developed. The first supports method level unit testing and is based on UML activity diagrams [1]. The second supports integration testing and is based on UML sequence diagrams [2, 5]. The third supports GUI testing and is based on UML use case diagrams and activity diagrams [3]. This tool supports the testing of GUI that uses the Java Swing library on the JFCUnit testing framework. The fourth semiautomatic test case generator is a test oracle and is based on UML state diagrams, sequence diagrams, and Asml language [4]. A test oracle consists of a group of UML simulators.
We have also extended some of these semiautomatic test case generators into automatic test case generators [6, 7, 8, 9, 10]. The automatic generation of test cases is based on the unification mechanism and the powerful constraint solving mechanism of constraint logic programming. A novel characteristic of this approach is that the test input and its corresponding expected output of a test case are simultaneously generated in a unified fashion. We have developed automatic test case generators for method-level unit testing [6, 8] and class-level unit testing [7, 9]. We have also extended our test case generators to generate test classes for multiple test platforms, e.g., Java/JUnit and C++/Cute [10].
References:
1. T.-H. Liu and N.-W. Lin, "A Semiautomatic Test Case Generator Based on UML Activity Diagrams and Object Constraint Language," Proceedings of 2008 International Computer Symposium, 2008, pp. 391-395. (The Best Paper Award)
2. Y.-C. Lei and N.-W. Lin, "Semiautomatic Test Case Generation Based on Sequence Diagrams," Proceedings of 2008 International Computer Symposium, 2008, pp. 345-355.
3. T.-C. Cheng and N.-W. Lin, "A Test Case Generator for Java Swing," Proceedings of the 19th Workshop on Object-Oriented technology and Applications, 2008, pp. 209-214.
4. C.-J. Wei and N.-W. Lin, "A Test Oracle Based on UML and ASML," Proceedings of the 19th Workshop on Object-Oriented technology and Applications, 2008, pp. 215-221.
5. Y.-C. Lei and N.-W. Lin, "Test Case Generation Based on Sequence Diagrams," Proceedings of the Fourth Taiwan Conference on Software Engineering, 2008, pp. 81-86.
6. Y.-T. Hu and N.-W. Lin, "Au Automatic Testing Tool Based on Object Constraint Language and Constraint Logic Programming," Proceedings of the Fifth Taiwan Conference on Software Engineering, 2009, pp. 341-347.
7. T.-F. Hu and N.-W. Lin, "A Class-Level Unit Testing Tool for Java," Proceedings of 2010 Joint Conference on 21st Object-Oriented technology and Applications and 6th Software Engineering, 2010, pp. 300-307.
8. Y.-T. Hu and N.-W. Lin, "Automatic Black-Box Method-Level Test Case Generation Based on Constraint Logic Programming," Proceedings of 2010 International Computer Symposium, 2010, pp. 977-982.
9. T.-F. Hu and N.-W. Lin, "Automatic Black-Box Class-Level Test Case Generation Based on Constraint Logic Programming," Proceedings of the 17th Workshop on Compiler Techniques for High-Performance and Embedded Computing, 2011.
10. C.-K. Chang, M.-B. Ho, and N.-W. Lin, "A Model-Based Test Case Generator for Multiple Test Platforms," Proceedings of Workshop on Software Engineering and Programming Language, National Computer Symposium, 2011, pp.143- 150.

Chinese Medical Engineering:

我們過去幾年對中醫診斷資訊化做了一些初步的研究[1, 2, 3, 4, 5, 6, 7]。中醫診斷學是研究如何應用中醫理論體系來診斷疾病的學科。我們研究的第一個議題是評估診斷輔助儀器的測量穩定度[1]及應用[2, 3, 4]。我們先利用經絡能量檢測儀(MEA我們過去幾年對中醫診斷資訊化做了一些初步的研究[1, 2, 3, 4, 5, 6, 7]。中醫診斷學是研究如何應用中醫理論體系來診斷疾病的學科。我們研究的第一個議題是評估診斷輔助儀器的測量穩定度[1]及應用[2, 3, 4]。我們先利用經絡能量檢測儀(MEAD)以間隔五分鐘的方式進行三次24個經穴的測量。以皮耳森相關係數再測法和走勢分析法進行分析。皮耳森相關係數再測法分析的結果是左右經脈平均相關係數為0.87，走勢分析法之平均走勢符合率為80.7%，顯示MEAD之測量具有高度的再現性。
我們接著利用MEAD測量24個經穴值來回區分乳癌病患與非病患[2]。實驗顯示用支援向量機分類技術的平均準確率達到78.33％。實驗並顯示右京骨穴值在13.5以下者，有88％是乳癌患者，在49.3以上者，有83％是非患者。在中醫文獻中，尚未出現京骨穴與乳癌有關的記載，本實驗顯示京骨穴與乳癌有顯著的相關性。我們也利用穴道檢測儀(EDSD)測量20個相關經穴，觀察是否可以使用經穴值來區分常年性鼻炎患者及非患者，及區分常年性鼻炎之嚴重度[3]。第一項實驗顯示，使用支援向量機分類技術平均準確率達到97.78%，使用最近K個鄰居分類技術平均準確率達到93.26%。第二項實驗顯示，使用K個中心點及華氏階層群聚技術將資料分成三群時，第一群包含所有非常年性鼻炎患者，且綜合鼻腔症狀評分表(TNSS)沒有症狀出現。第二群及第三群為常年性鼻炎患者，且第二群的TNSS有輕度鼻炎症狀出現，而第三群的TNSS有中重度鼻炎症狀出現。觀察三群組的經穴平均總值時發現，平均總值越高的群組，TNSS顯示的常年性鼻炎相關的症狀也越嚴重。進而發現中重度症狀的常年性鼻炎群組的肝脾兩經的經穴值顯著高於其他兩個群組，這和馬光亞醫師所提出的臨床經驗相符。
我們也利用因素分析來觀察過敏性鼻炎患者20個經穴間的相關性[4]。因素分析是一種降低資料向度或形成少數構面的統計方法，使得相關性強的變項群可以形成有意義的構面，而且構面間盡可能的互斥。本研究用因素分析所萃取出的三個經穴群也印證了馬光亞醫師所提出的臨床經驗。因此，除了要瞭解表面因素的呼吸系統構面之外，潛在因素的肝脾構面應是治療的重要準則。
我們探索的第二個主題是中醫症狀的標準化[5, 6, 7]。中醫症狀目前尚未標準化，一般的症狀描述常出現一詞多義或多詞一義的情形，中醫症狀標準化嘗試提出一個症狀集合，其中每個症狀都只有一個意義，任何兩個症狀的意義沒有交集，這個集合的症狀又含括了所有可能的症狀意義。我們根據李洪成醫師的《中醫證候學》，用人工的方式建立了一個初步的標準化症狀集合，並研製了一個將症狀描述對應到標準化症狀的芻形系統[5]。為了能更廣泛地將未處理過的症狀描述對應到標準化症狀，我們也分別嘗試使用近似字詞比對[6]及自然語言處理[7]的技術來強化這個芻形系統。
References:
1. M.-H. Yeh, M.-J. Tsai, N.-W. Lin, Y.-M. Lan, C.-C. Yeh, Z.-Y. Chen, "Study of Stability of the Instrument Analyzing Electric Resistance of Acupuncture Points," The Journal of China Clinical Traditional Medicine, Vol. 14, No. 2, June 2008, pp. 107-115.
2. M.-H. Yeh, C.-W. Huang, C.-C. Yeh, C.-K. Ting, Z.-Y. Chen, N.-W. Lin, "Analysis of Breast Cancer Using Meridian Energy," The Journal of China Clinical Traditional Medicine, Vol. 15, No. 3, September 2009, pp. 229-235.
3. H.-F. Luo, Analysis of Perennial Rhinits Symptoms Based on Meridian Electrical Properties, Master Thesis, National Chung Cheng University, 2009.
4. 陳仁義, 簡志瑋, 簡佑任, 林迺衛, 葉家舟, 葉明憲, 過敏性鼻炎的表裡因素分析, Proceedings of 2009 Intelligent Technologies and Applied Statistics Conference, 2009, pp. 106-111.
5. L.-Y. Lin, N.-W. Lin, M.-H. Yeh, C.-C. Yeh, and Z.-Y. Chen, "A Preliminary Study on the Standardization of Traditional Chinese Medicine Symptoms," Proceedings of Workshop on Artificial Intelligence, Fuzzy Systems, and U-learning, National Computer Symposium, 2011, pp.36- 47.
6. Y.-H. Lee, N.-W. Lin, M.-H. Yeh, C.-C. Yeh, and Z.-Y. Chen, "Assisting the Standardization of Symptoms in Traditional Chinese Medicine Based on Approximate Pattern Matching," Proceedings of Workshop on Artificial Intelligence, Fuzzy Systems, and U-learning, National Computer Symposium, 2011, pp.149- 157.
7. T.-Y. Ko, N.-W. Lin, M.-H. Yeh, C.-C. Yeh, and Z.-Y. Chen, "Design and Implementation of Standardization of Traditional Chinese Medicine Symptomes Based on Nature Language Processing," Proceedings of Workshop on Artificial Intelligence, Fuzzy Systems, and U-learning, National Computer Symposium, 2011, pp.48- 57.