多目标测试用例预优化方法及其在GPU上的应用研究

摘要

在软件回归测试中，由于客观因素(例如时间、成本等)的制约，庞大的测试用例集不可能全部被执行。测试用例预优化是一种通过调整测试用例的执行顺序来优化回归测试过程的技术。传统的测试用例预优化技术主要针对单一测试准则进行优化排序研究，以及研究不同测试准则和平均错误检测率之间的相关性。然而，在实际的回归测试环境中，测试人员可能会同时考虑多个测试准则和多种客观因素，从而综合地作出测试用例预优化方案，传统的测试用例预优化技术很显然不能满足这样的需求。
　　 另外，进化算法是一类以达尔文进化论为依据的智能算法，广泛应用于不同领域里的实际优化问题中，但由于它是一个以种群为单位进行大规模遗传迭代的过程，所以执行效率必然会随着种群大小和测试用例集规模的增大而急剧下降，这己成为进化算法发展的一大软肋。
　　 针对上述两个问题，本论文首先提出了一种基于NSGA-Ⅱ算法的多目标测试用例预优化方法，该方法可以同时将多个测试准则和客观因素作为优化目标;在此基础上，本论文一方面针对方法中最耗时的适应度评估部分，给出了一种基于CPU+GPU异构模式的并行适应度评估策略;另一方面，针对遗传操作中最复杂且最耗时的交叉操作部分，本论文探讨了三种基于CPU+GPU异构模式的并行交叉策略，即序列编码并行交叉策略、顺序编码并行交叉策略和基于scan操作的并行交叉策略。
　　 实验结果表明本论文提出的基于NSGA-Ⅱ算法的多目标测试用例预优化方法在所有的被测程序上都可以获得测试用例的最优排序方案集合，并且在规模较大的space程序上得到了较好的Pareto前沿。表明该方法可以有效地解决符合实际回归测试需求的测试用例预优化问题。此外，几种并行策略的实验结果显示适应度评估部分可以获得50倍以上的加速，而三种并行交叉策略也可以获得不同程度的加速效果，其中基于scan操作的并行交叉策略加速效果最为明显。因此，这几种并行策略确实可以有效地提高基于NSGA-Ⅱ算法的多目标测试用例预优化方法的执行效率，可以应用于一些对时间要求苛刻的软件回归测试过程中。

目录

声明

学位论文数据集

摘要

第一章 绪论

1．1 课题来源

1．2 课题研究背景及意义

1．3 国内外相关研究介绍

1．3．1 优化技术在回归测试中的应用研究

1．3．2 进化算法在优化问题中的应用研究

1．3．3 基于CPU+GPU异构并行进化算法的应用研究

1．4 论文主要贡献

1．4．1 多目标测试用例预优化问题及其解决方法

1．4．2 多目标测试用例预优化算法的并行化改进

1．5 论文组织结构

1．6 本章小结

第二章 回归测试用例预优化技术及进化算法

2．1 回归测试

2．2 回归测试用例预优化技术

2．3 进化算法在测试用例预优化中的应用

2．4 进化算法的并行化改进

2．5 本章小结

第三章 GPGPU及CUDA计算平台

3．1 GPGPU发展历程

3．2 CUDA计算平台概述

3．3 CUDA硬件体系结构

3．3．1 NVIDIA GPU硬件设计

3．3．2 计算能力

3．4 CUDA编程模型

3．4．1 CPU+GPU异构并行模式

3．4．2 线程结构

3．4．3 存储器层次模型

3．5 CUDA编程规范

3．6 本章小结

第四章 多目标测试用例预优化方法设计与实现

4．1 基于进化算法的多目标测试用例预优化方法研究

4．1．1 多目标测试用例预优化问题定义

4．1．2 优化目标的选取

4．1．3 个体编码方案

4．1．4 选择算子

4．1．5 交叉算子

4．1．6 变异算子

4．2 NSGA-II的算法的实现细节

4．3 测试用例预优化实验及结果分析

4．3．1 实验环境及被测对象

4．3．2 实验方案

4．3．3 最优解在目标空间的分布

4．3．4 方法的耗时统计及影响因素分析

4．4 本章小结

第五章 CPU+GPU异构并行多目标测试用例预优化方法研究

5．1 并行多目标测试用例预优化方法概述

5．2 CPU+GPU异构并行方案设计

5．3 适应度评估的GPU并行策略

5．3．1 并行任务划分

5．3．2 适应度评估的kernel函数设计

5．4 交叉操作的GPU并行策略

5．4．1 序列编码交叉操作的GPU并行策略

5．4．2 顺序编码交叉操作的GPU并行策略

5．4．3 基于scan操作的GPU并行交叉策略

5．5 本章小结

第六章 并行多目标测试用例预优化方法的实验研究

6．1 实验研究问题

6．2 软、硬件环境搭建

6．3 加速比实验的结果及分析

6．3．1 并行适应度评估策略的加速比

6．3．2 序列编码并行交叉策略的加速比

6．3．3 顺序编码并行交叉策略的加速比

6．3．4 基于scan操作的并行交叉策略的加速比

6．3．5 不同并行交叉策略的比较

6．3．6 NSGA-II遗传参数对加速性能的影响

6．4 本章小结

第七章 结束语

7．1 论文的主要工作

7．2 未来进一步工作

参考文献

致谢

研究成果及发表的学术论文

作者和导师简介

硕士研究生学位论文答辩委员会决议书