【作者】 张晨；

【导师】 巩敦卫；

【作者基本信息】 中国矿业大学 ， 控制科学与工程， 2016， 硕士

【摘要】 与串行程序不同,并行程序不仅存在大量不同类型的通信语句,而且执行过程具有不确定性。这使得许多已有的串行程序测试方法不适用于并行程序。随着社会的发展,并行程序的应用日趋广泛。因此,研究适用于并行程序的测试方法是非常迫切和有意义的。本文针对一类重要的并行程序——消息传递并行程序,面向测试数据生成问题,研究基于调度序列选择的测试数据生成方法及其实现。主要包括以下3个内容:(1)提出了并行程序语句覆盖的调度序列选择方法。调度序列对并行程序的执行产生影响,选择的调度序列不同,目标语句覆盖的难度也不同。因此,本部分期望采用合理的方法选择最优的调度序列,使得在该调度序列下,目标语句覆盖的难度尽可能的低。首先,基于调度序列与目标语句执行之间的关系,确定影响目标语句的调度序列;然后,根据目标语句的执行情况,将影响目标语句的调度序列分成若干等价类;最后,选择最优调度序列,该过程分成如下2个阶段:第1阶段,建立评价目标语句覆盖难度的指标体系,并基于此从诸多等价调度序列类中,选择1个最优的等价类;第2阶段,建立覆盖目标语句程序执行一次所需时间的评价指标体系,并基于此从最优的等价类中,选择1个最优的调度序列。(2)研究基于调度序列选择的语句覆盖测试数据进化生成方法。消息传递并行程序本身具有的不确定性和存在的众多调度序列,使得已有的串行程序语句覆盖测试数据生成方法不再适用。本部分借鉴串行程序语句覆盖测试数据生成问题的模型,并针对并行程序的特点,建立并行程序语句覆盖测试数据生成问题的数学模型,通过固定调度序列,并采用遗传算法求解建立的模型,生成覆盖语句的测试数据。(3)基于前面2部分的研究成果,给出语句覆盖测试数据进化生成的实现过程。将实现过程分为如下3个模块:程序处理、遗传算法,以及存储,其中,程序处理模块对被测程序进行预处理;遗传算法模块生成覆盖语句的测试数据;存储模块用于程序执行过程中的信息保存。本文基于调度序列的选择,采用遗传算法生成并行程序语句覆盖的测试数据,不但丰富了并行程序测试理论,也扩大了遗传算法的应用范围,提高了采用遗传算法生成测试数据的效率,具有重要的理论意义和应用价值。更多还原

【Abstract】 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.更多还原