微信服务号

微信订阅号

2025年7月19日 7:30 星期六
首页 > 过刊浏览>2016年第27卷第4期 >943-954. DOI:10.13328/j.cnki.jos.004968
PDF HTML阅读 XML下载 导出引用 引用提醒
面向CPU+GPU异构计算的多目标测试用例优先排序
作者:
基金项目:

国家自然科学基金(61170082,61472025);教育部新世纪优秀人才计划(NCET-12-0757)


CPU+GPU Heterogeneous Computing Orientated Multi-Objective Test Case Prioritization
Author:
Fund Project:

National Natural Science Foundation of China (61170082, 61472025); Program for New Century Excellent Talents in University of Ministry of Education of China (NCET-12-0757)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [24]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    测试用例优先排序是一种基于整个测试用例集以寻找最优测试用例执行序列的软件回归测试技术.由于其能够尽早地发现错误,同时应用灵活度高、不会漏掉重要测试用例等,在实际软件测试过程中可以有效提高测试效率.多目标测试用例优化排序是寻找同时覆盖多个测试准则的用例执行序列,通常采用演化算法优化求解,但执行时间较长,严重影响了在实际软件测试中的应用.采用先进的GPU图形卡通用并行计算技术,提出了面向CPU+GPU异构计算下的多目标测试用例优先排序技术,在NSGA-Ⅱ算法中,实现了基于序列编码的适应度函数计算和交叉操作的GPU并行计算,在近6万行有效代码的工业界开源程序上实现了30倍的计算效率提升.同时,实验验证了不同并行策略的计算加速比,提出了切实可行的CPU+GPU异构计算模式,并提供了相应的原形工具.

    Abstract:

    Test case prioritization is a type of technique that aims at searching for the test case execution sequence to find faults early based on the whole test case suite. This technique is flexible and barely can miss important test cases, which contributes much benefit to regression testing. Multi-objective test case prioritization, where evolutionary algorithms have been widely used, aims to find a test case execution sequence that suits multiple test criteria. However, the drawback of large computation cost of the algorithms can greatly reduce the value of industrial application. This article proposes a CPU+GPU heterogeneous Computing orientation based multi-objective test case prioritization technique that utilizes advanced general purpose graphic process unit(GPGPU) technique to accelerate the process of test case prioritization. In experiment based on parallel structure, the sequential based parallel fitness and crossover operation computation is designed on NSGA-II and at last achieves 30 times speed-up rate on a well-known industrial open source project. Based on the systematic study on the benefit of different types of parallel strategies, a CPU+GPU heterogeneous computing framework is proposed and a prototype of tools is developed and available online.

    参考文献
    [1] Jiang B, Chan W. On the integration of test adequacy, test case prioritization, and statistical fault localization. In:Proc. of the 10th Int'l Conf. on Quality Software(QSIC). IEEE, 2010. 377-384.[doi:10.1109/QSIC.2010.64]
    [2] Zhang XF, Xu BW, Nie CH, Shi L. Approach for optimizing test suite based on testing requirement reduction. Ruan Jian Xue Bao/Journal of Software, 2007,18(4):821-831(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/20070404.htm
    [3] Gejian D, Yanni Z, Lu Z. Study of test suite minimization based on ant colony algorithm. Computer Engineering, 2009,35(6):213-218(in Chinese with English abstract).
    [4] Yoo S, Harman M. Regression testing minimization, selection and prioritization:A survey. Software Testing, Verication and Reliability, 2012,22(2):67-120.[doi:10.1002/stv.430]
    [5] Wong WE, Horgan JR, London S, Mathur AP. Effect of test set minimization on fault detection effectiveness. In:Proc. of the 17th Int'l Conf. on Software Engineering(ICSE'95). IEEE, 1995. 41.[doi:10.1145/225014.225018]
    [6] Chen X, Chen JH, Ju XL, Gu Q. Survey of test case prioritization techniques for regression testing. Ruan Jian Xue Bao/Journal of Software, 2013,24(8):1695-1712(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4420.htm[doi:10.3724/SP.J. 1001.2013.04420]
    [7] Li Z, Harman M, Hierons RM. Search algorithms for regression test case prioritization. IEEE Trans. on Software Engineering, 2007, 33:225-237.[doi:10.1109/TSE.2007.38]
    [8] Hla KHS, Choi YS, Park JS. Applying particle swarm optimization to prioritizing test cases for embedded real time software retesting. In:Proc. of the IEEE 8th Int'l Conf. on Computer and Information Technology Workshops(CIT Workshops 2008). IEEE, 2008. 527-532.[doi:10.1109/CIT.2008.Workshops.104]
    [9] Singh Y, Kaur A, Suri B. Test case prioritization using ant colony optimization. ACM SIGSOFT Software Engineering Notes, 2010, 35(4):1-7.[doi:10.1145/1811226.1811238]
    [10] McMinn P. Search-Based software testing:Past, present and future. In:Proc. of the IEEE 4th Int'l Conf. on Software Testing, Verification and Validation Workshops(ICSTW). IEEE, 2011. 153-163.[doi:10.1109/ICSTW.2011.100]
    [11] Harman M, McMinn P, de Souza JT, Yoo S. Search based software engineering:Techniques, taxonomy, tutorial. In:Empirical Software Engineering and Verification. LNCS 7007, 2012. 1-59. http://www0.cs.ucl.ac.uk/staff/mhaman/laser.pdf
    [12] Srinivas N, Deb K. Multi-Objective function optimization using non-dominated sorting genetic algorithms. IEEE Trans. on Evolutionary Computation, 1994,2(3):221-248.[doi:10.1162/evco.1994.2.3.221]
    [13] Li H, Zhang Q. Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-Ⅱ. IEEE Trans. on Evolutionary Computation, 2009,13(2):284-302.[doi:10.1109/TEVC.2008.925798]
    [14] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast elitist multi-objective genetic algorithm:NSGA-Ⅱ. IEEE Trans. on Evolutionary Computation, 2000,1917:849-858.[doi:10.1109/4235.996017]
    [15] Nucci DD, Panichella A, Zaidman A, Lucia AD. Hypervolume-Based search for test case prioritization. Lecture Notes in Computer Science, 2015,9275:157-172.[doi:10.1007/978-3-319-22183-0_11]
    [16] Yuan F, Bian Y, Li Z, Zhao R. Epistatic genetic algorithm for test case prioritization. In:Proc. of the Search-Based Software Engineering. Springer-Verlag, 2015. 109-124.[doi:10.1007/978-3-319-22183-0_8]
    [17] Srinivas M, Patnaik LM. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Trans. on Systems, Man and Cybernetics, 1994,24(4):656-667.[doi:10.1109/21.286385]
    [18] Yoo S, Harman M, Ur S. Highly scalable multi objective test suite minimisation using graphics cards. In:Proc. of the Search Based Software Engineering. Springer-Verlag, 2011. 219-236.[doi:10.1007/978-3-642-23716-4_20]
    [19] Epitropakis MG, Yoo S, Harman M, Burke EK. Empirical evaluation of Pareto efficient multi-objective regression test case prioritization. In:Proc. of the 2015 Int'l Symp. on Software Testing and Analysis. ACM, 2015. 234-245.
    [20] Walcott KR, Soffa ML, Kapfhammer GM, Roos RS. Timeaware test suite prioritization. In:Proc. of the 2006 Int'l Symp. on Software Testing and Analysis. ACM Press, 2006. 1-12.[doi:10.1145/1146238.1146240]
    附中文参考文献:
    [2] 章晓芳,徐宝文,聂长海,史亮.一种基于测试需求约简的测试用例集优化方法.软件学报,2007,18(4):821-831. http://www.jos.org. cn/1000-9825/20070404.htm
    [3] 丁革建,郑燕妮,张璐.基于蚁群算法的测试用例集最小化研究.计算机工程,2009,35(6):213-215.
    [6] 陈翔,陈继红,鞠小林,顾庆.回归测试中的测试用例优先排序技术述评.软件学报,2013,24(8):1695-1712. http://www.jos.org.cn/1000-9825/4420.htm[doi:10.3724/SP.J.1001.2013.04420]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

边毅,袁方,郭俊霞,李征,赵瑞莲.面向CPU+GPU异构计算的多目标测试用例优先排序.软件学报,2016,27(4):943-954

复制
分享
文章指标
  • 点击次数:5228
  • 下载次数: 7083
  • HTML阅读次数: 2612
  • 引用次数: 0
历史
  • 收稿日期:2015-06-24
  • 最后修改日期:2015-10-15
  • 在线发布日期: 2016-01-14
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第20260096位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号