基于占优关系的并行程序通信覆盖约减方法

doi:10.11772/j.issn.1001-9081.2020091369

计算机应用 ›› 2021, Vol. 41 ›› Issue (6): 1741-1747.DOI: 10.11772/j.issn.1001-9081.2020091369

所属专题：先进计算

基于占优关系的并行程序通信覆盖约减方法

张辰¹, 田甜¹, 杨秀婷¹, 巩敦卫²

1. 山东建筑大学计算机科学与技术学院, 济南 250101;
2. 中国矿业大学信息与控制工程学院, 江苏徐州 221116

收稿日期:2020-09-07 修回日期:2020-11-13 出版日期:2021-06-10 发布日期:2020-11-26
通讯作者: 田甜
作者简介:张辰(1995-),男,山东烟台人,硕士研究生,CCF会员,主要研究方向:并行软件测试;田甜(1987-),女,山东德州人,副教授,博士,CCF会员,主要研究方向:程序分析与测试;杨秀婷(1997-),女,山东济南人,硕士研究生,主要研究方向:并行软件测试;巩敦卫(1970-),男,江苏徐州人,教授,博士,CCF会员,主要研究方向:基于搜索的软件工程、智能优化。
基金资助:
国家自然科学基金资助项目（61773384）。

Communication coverage reduction method of parallel programs based on dominant relation

ZHANG Chen¹, TIAN Tian¹, YANG Xiuting¹, GONG Dunwei²

1. School of Computer Science and Technology, Shandong Jianzhu University, Jinan Shandong 250101, China;
2. School of Information and Control Engineering, China University of Mining and Technology, Xuzhou Jiangsu 221116, China

Received:2020-09-07 Revised:2020-11-13 Online:2021-06-10 Published:2020-11-26
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61773384).

摘要/Abstract

摘要： 针对通信规模的增大及不确定通信使得消息传递接口（MPI）并行程序通信测试难度增大的问题，提出了基于占优关系的通信覆盖约减方法。首先，基于通信与通信语句间的对应关系，将通信约减问题转换为通信语句的约减问题；然后，利用语句占优关系求解通信语句集的约减集；最后，选择与约减集相关的通信作为覆盖目标，使得覆盖这些目标的测试数据能够覆盖全部通信。将所提方法应用到7个典型被测程序中。实验结果表明，在不降低通信覆盖率的前提下，相较于以全部通信作为覆盖目标的测试数据生成方法，所提方法减少的测试数据的生成时间最高达95%，提高了通信覆盖测试数据生成的效率。

关键词: 并行程序, 通信覆盖, 通信约减, 占优关系, 测试数据

Abstract: The increase of communication scale and non-deterministic communication make the communication test of Message-Passing Interface (MPI) parallel programs more difficult. In order to solve the problems, a new method of reducing communication coverage based on dominant relation was proposed. Firstly, based on the correspondence between communications and communication statements, the reduction problem of communications was converted into a reduction problem of communication statements. Then, the dominant relation of statements was used to solve the reduction set of communication statement set. Finally, the communications related to the reduction set were selected as the targets to be covered, so that the test data covering these targets covered all the communications. The proposed method was applied to 7 typical programs under test. Experimental results show that, compared with the test data generation method with all communication as coverage targets, the proposed method can reduce the generation time of test data by up to 95% without reducing the coverage rate of communications, indicating that the proposed method can improve the generation efficiency of communication coverage test data.

Key words: parallel program, communication coverage, communication reduction, dominant relation, test data

中图分类号:

TP311

张辰, 田甜, 杨秀婷, 巩敦卫. 基于占优关系的并行程序通信覆盖约减方法[J]. 计算机应用, 2021, 41(6): 1741-1747.

ZHANG Chen, TIAN Tian, YANG Xiuting, GONG Dunwei. Communication coverage reduction method of parallel programs based on dominant relation[J]. Journal of Computer Applications, 2021, 41(6): 1741-1747.

参考文献

[1] ITOH E, KAWAGUCHI Y, FURUKAWA Z, et al. Ordered sequence testing criteria for concurrent programs and the support tool[C]//Proceedings of the 19941st Asia-Pacific Software Engineering Conference. Piscataway:IEEE,1994:236-245.
[2] LU S,JIANG W,ZHOU Y. A study of interleaving coverage criteria[C]//Proceedings of the 2007 6th Joint Meeting of the European Software Engineering Conference/the 2007 ACM SIGSOFT Symposium on the Foundations of Software Engineering. New York:ACM,2007:533-536.
[3] ŞERBĂNUŢĂ T F,CHEN F,ROŞU G. Maximal causal models for multithreaded systems:UIUCDCS-R-2008-3017[R]. UrbanaChampaign:University of Illinois at Urbana-Champaign,2008.
[4] VAKKALANKA S S,SHARMA S,GOPALAKRISHNAN G,et al. ISP:a tool for model checking MPI programs[C]//Proceedings of the 2008 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York:ACM, 2008:285-286.
[5] VO A,VAKKALANKA S,DELISI M,et al. Formal verification of practical MPI programs[C]//Proceedings of the 2009 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York:ACM,2009:261-270.
[6] SIEGEL S F,ZIRKEL T K. Automatic formal verification of MPIbased parallel programs[C]//Proceedings of the 2011 16th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York:ACM,2011:309-310.
[7] SIEGEL S F,ZIRKEL T K. FEVS:a functional equivalence verification suite for high-performance scienti fi c computing[J]. Mathematics in Computer Science,2011,5(4):427-435.
[8] GOTOVOS A, CHRISTAKIS M, SAGONAS K. Test-driven development of concurrent programs using Concuerror[C]//Proceedings of the 2011 10th ACM SIGPLAN Workshop on Erlang. New York:ACM,2011:51-61.
[9] SOUZA P S L,SOUZA S S,ROCHA M G,et al. Data flow testing in concurrent programs with message passing and shared memory paradigms[J]. Procedia Computer Science,2013,18:149-158.
[10] HUANG J. Stateless model checking concurrent programs with maximal causality reduction[C]//Proceedings of the 2015 36th ACM SIGPLAN Conference on Programming Language Design and Implementation. New York:ACM,2015:165-174.
[11] TERRAGNI V, CHEUNG S C. Coverage-driven test code generation for concurrent classes[C]//Proceedings of the 2016 IEEE/ACM 38th IEEE International Conference on Software Engineering. Piscataway:IEEE,2016:1121-1132.
[12] NGUYEN T L,SCHRAMMEL P,FISCHER B,at al. Parallel bug-finding in concurrent programs via reduced interleaving instances[C]//Proceedings of the 201732nd IEEE/ACM International Conference on Automated Software Engineering. Piscataway:IEEE,2017:753-764.
[13] MELO S M,DE SOUZA S D R S,SARMANHO F S,et al. Contributions for the structural testing of multithreaded programs:coverage criteria,testing tool,and experimental evaluation[J]. Software Quality Journal,2018,26(3):921-959.
[14] 姚香娟, 巩敦卫. 基于目标语句占优关系的软件可测试性转化[J]. 电子学报, 2013, 41(12):2523-2528.(YAO X J,GONG D W. Testability transformation based on dominant relation of target statements[J]. Acta Electronica Sinica,2013,41(12):2523-2528.)
[15] 张功杰, 巩敦卫, 姚香娟. 基于统计占优分析的变异测试[J]. 软件学报, 2015, 26(10):2504-2520.(ZHANG G J,GONG D W, YAO X J. Mutation testing based on statistical dominance analysis[J]. Journal of Software,2015,26(10):2504-2520.)
[16] 田甜, 郭庆, 张辰. 基于占优关系的MPI并行程序死锁检测[J]. 聊城大学学报(自然科学版), 2018, 31(4):104-110.(TIAN T, GUO Q,ZHANG C. Deadlock detection of parallel programs based on dominance relation[J]. Journal of Liaocheng University (Natural Science Edition),2018,31(4):104-110.)
[17] NASA Advanced Supercomputing Division. NAS parallel benchmarks[CP/OL].[2020-07-03]. https://www.nas.nasa.gov/publications/npb.html.
[18] ALETI A, MOSER I, GRUNSKE L. Analysing the fitness landscape of search-based software testing problems[J]. Automated Software Engineering,2017,24(3):603-621.
[19] AHMED M A,HERMADI I. GA-based multiple paths test data generator[J]. Computers and Operations Research,2008,35(10):3107-3124.

基于占优关系的并行程序通信覆盖约减方法

Communication coverage reduction method of parallel programs based on dominant relation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈田, 左永生, 安鑫, 任福继. 基于三态信号的测试数据相容压缩方法[J]. 计算机应用, 2019, 39(6): 1863-1868.
[2]	王曙燕, 温春琰, 孙家泽. 基于自适应粒子群优化算法的测试数据扩增方法[J]. 计算机应用, 2016, 36(9): 2492-2496.
[3]	徐炜珊, 于磊, 冯俊池, 侯韶凡. 基于软件层次化模型的软件测试数据生成[J]. 计算机应用, 2016, 36(12): 3454-3460.
[4]	丁蕊, 董红斌, 冯宪彬, 赵佳华. 基于烟花爆炸优化算法的测试数据生成方法[J]. 计算机应用, 2016, 36(10): 2816-2821.
[5]	熊壬浩, 刘羽. A^*算法的改进及并行化[J]. 计算机应用, 2015, 35(7): 1843-1848.
[6]	董跃华, 戴玉倩. 混合粒子群算法的软件测试数据自动生成[J]. 计算机应用, 2015, 35(2): 545-549.
[7]	潘烁王曙燕孙家泽. 基于K-均值聚类粒子群优化算法的组合测试数据生成[J]. 计算机应用, 2012, 32(04): 1165-1167.
[8]	周绮姜淑娟赵雪峰. 改进的量子遗传算法及其在测试数据生成中的应用[J]. 计算机应用, 2012, 32(02): 557-560.
[9]	任君赵瑞莲李征. 基于禁忌搜索算法的可扩展有限状态机模型测试数据自动生成[J]. 计算机应用, 2011, 31(09): 2440-2443.
[10]	张美花姜瑛. 基于变异的Web复合服务测试数据选择方法[J]. 计算机应用, 2011, 31(09): 2444-2448.
[11]	冯丽云洪玫杨秋辉周洪宇臧康. 基于逆向查询处理算法的数据库系统测试数据生成方法[J]. 计算机应用, 2011, 31(04): 948-951.
[12]	赵青孙济州崔辰州于策肖健. 面向海量数据的并行天文交叉证认[J]. 计算机应用, 2010, 30(8): 2056-2059.
[13]	孙佩刚谈利群赵利军吴景坡. 基于数据处理模型的软件测试方法[J]. 计算机应用, 2009, 29(10): 2827-2829.
[14]	付崇国徐胜超. WAPM:适合广域分布式计算的并行编程模型[J]. 计算机应用, 2009, 29(08): 2161-2166.
[15]	黄小城王希武常东升何刚. 改进的差分演化算法在测试数据生成中的应用[J]. 计算机应用, 2009, 29(06): 1722-1754.