Test Data Generation For Statement Coverage Of Parallel Programs Based On Scheduling Sequence Selection And Genetic Algorithms

Different from serial programs, parallel programs contain numerous communication statements with different types and have uncertain execution, resulting in that previous testing approaches for serial programs have difficulties in applying to parallel programs. Parallel programs have been widely used with the development of society. Therefore, researching testing approaches suitable for parallel programs is very urgent and valuable. This thesis focuses on message-passing parallel programs, one kind of representative parallel programs, and studies the method of test data generation for statement coverage based on scheduling sequence selection and its implementation from the following three aspects.(1)An approach to select scheduling sequence of parallel programs based on statement coverage is proposed. The difficulties of generating test data to cover the target statement are different under different scheduling sequences, because scheduling sequences will affect the execution of parallel programs. In view of this, this thesis expects to propose a reasonable approach to select the optimal scheduling sequence, which has the least difficulty covering the target statement. At first, the scheduling sequences that affect the target statement are determined based on the relation between a scheduling sequence and the execution of the target statement. Then, these scheduling sequences are divided into a number of equivalent classes according to the execution of the target statement. Finally, the optimal scheduling sequence is selected. This process can be divided into the following two phases:(1) establish an index system to evaluate the difficulty of covering a target statement, and select the optimal one from all the equivalent classes of scheduling sequences;(2) establish an index system to evaluate the program execution time needed to cover the target statement, and select the optimal scheduling sequence from the optimal equivalent class.(2)Research the approach of test data generation for statement coverage based on scheduling sequence selection and genetic algorithms. Message-passing parallel programs have uncertain execution and many scheduling sequences, which make the approaches of test data generation based on statement coverage for serial programs cannot be applied to them. This part builds a model of test data generation for message-passing parallel programs, and realizes the test data generation to cover statement by fixing scheduling sequence and using genetic algorithm to solve this model.(3)According to the research of previous 2 parts, the implementation procedure of test data generation for statement coverage based on genetic algorithms is provided. The process of implementation is divided into three modules: program processing, genetic algorithm, and storage. Among them, program processing module is mainly to preprocess the program. The genetic algorithm module is to generate test data to cover the target statement. Storage module is to automatically save the information needed.This thesis uses genetic algorithms to generate test data for statement coverage of parallel programs based on scheduling sequence selection. It enriches the theory of testing parallel programs, extends the applied range of genetic algorithms, and improves the efficiency of generating test data. So this thesis has significant theory and application value.