Path Similarity-based Multi-path Coverage Testing For Message-passing Parallel Programs

Large-scale scientific or engineering calculations,such as oil and gas exploration,Internet services,and weather forecasting,are usually implemented using parallel programs.A message-passing parallel program is an important class of parallel programs that typically contain a number of communication statements for passing information between processes.However,the uncertain communication statements existing in the message-passing parallel program make the process execution order uncertain,which increases the difficulty of testing the program.The scheduling sequence refers to the order in which processes are executed.Based on the performance of scheduling sequences,this thesis studies the method and implementation of test data generation of multi-path coverage for message-passing parallel programs.It mainly includes the following three contents:(1)The performance evaluation method of scheduling sequence under multi-path coverage criterion is given.Taking the influence of the uncertain process execution order on the difficulty of covering target paths into consideration,the method of sorting scheduling sequences in a message-passing parallel program for multi-path coverage is focused on in this paper.To fulfill this task,a parallel program is first executed against each sample under each scheduling sequence to generate a path coverage matrix.Then,a number of path similarity matrixes are formed based on the similarity between each path in the coverage matrix and each target one.Next,each scheduling sequence is evaluated according to the characteristics of these similarity matrixes,with which scheduling sequences are sorted.Finally,test data for multi-path coverage are generated by randomly sampling based on the sorted scheduling sequence set which is evaluated using the Average Percentage of Faults Detected index.(2)For multi-path coverage,an approach of generating test data based on multi-task optimization is proposed.In this part,we disassemble the original task,establishes an optimization model for each subtask,and combines them to form a multi-task optimization model.Firstly,based on the similarity between paths covered by the program input and the target paths under a certain scheduling sequence,a relation matrix between the target paths and the scheduling sequences is generated.Then,based on the relation matrix,the target paths are divided into several groups.Finally,for each group of target paths,each corresponding test data generation optimization model is established,and a unified strategy is employed to solve each model.(3)Based on the theory and method proposed above,a system for generating test data is designed.This part describes the three main functions included in this system: the scheduling sequence sorting,the test data generation and the running result display,and shows the user interface of the system.This thesis proposes the theory and method of test data generation of multi-path coverage for message-passing parallel programs,and designs the test data automatic generation system,which not only expands the research work of parallel program testing,but also expands the application field of evolutionary algorithms,including certain value.The thesis contains 26 figures,7 tables and 83 references.