SCIENTIA SINICA Informationis, Volume 51 , Issue 4 : 565(2021) https://doi.org/10.1360/SSI-2019-0113

Path similarity-based scheduling sequence sorting for multi-path coverage of parallel programs

More info
  • ReceivedJan 30, 2019
  • PublishedMar 12, 2021


Funded by




[1] Beizer B. Software Testing Techniques. India: Dreamtech Press, 2002. 3. Google Scholar

[2] Xie X Y, Xu B W, Shi L. J Software, 2009, 20: 3117-3136 CrossRef Google Scholar

[3] Shan J H, Wang J, Qi Z C. Survey on path-wise automatic generation of test data. Acta Electron Sin, 2004, 32: 109--113. Google Scholar

[4] Ahmed M A, Hermadi I. GA-based multiple paths test data generator. Comput Operations Res, 2008, 35: 3107-3124 CrossRef Google Scholar

[5] Chen G L. Parallel Computing — Structure, Algorithms, Programming. Beijing: Higher Education Press, 2011. 4--6 [陈国良. 并行计算-结构、算法、编程. 北京: 高等教育出版社, 2011. 4--6. Google Scholar

[6] Wang J X. Similarity-based testing for message passing parallel programs. Dissertation for M.S. Degree. Xuzhou: China University of Mining and Technology, 2017. Google Scholar

[7] Bianchi F A, Margara A, Pezze M. A Survey of Recent Trends in Testing Concurrent Software Systems. IIEEE Trans Software Eng, 2018, 44: 747-783 CrossRef Google Scholar

[8] Su X H, Yu Z, Wang T T, et al. A survey on exposing, detecting and avoiding concurrency bugs. Chinese J Comput, 2015, 38: 2215--2233. Google Scholar

[9] Cai Y, Lu Q. Dynamic Testing for Deadlocks via Constraints. IIEEE Trans Software Eng, 2016, 42: 825-842 CrossRef Google Scholar

[10] Liu W, Wang L, Du Y Y. Deadlock Property Analysis of Concurrent Programs Based on Petri Net Structure. Int J Parallel Prog, 2017, 45: 879-898 CrossRef Google Scholar

[11] Fei Y, Zhu H B, Wu X. Comparative modelling and verification of Pthreads and Dthreads. J Softw Evol Proc, 2018, 30: e1919 CrossRef Google Scholar

[12] Hilbrich T, de Supinski B R, Nagel W E, et al. Distributed wait state tracking for runtime MPI deadlock detection. In: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, Denver, 2013. 1--12. Google Scholar

[13] Cai Y, Cao L W. Effective and precise dynamic detection of hidden races for Java programs. In: Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, Bergamo, 2015. 450--461. Google Scholar

[14] Samak M, Ramanathan M K. Synthesizing tests for detecting atomicity violations. In: Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, Bergamo, 2015. 131--142. Google Scholar

[15] Yin L Z, Dong W, Liu W W. On Scheduling Constraint Abstraction for Multi-Threaded Program Verification. IIEEE Trans Software Eng, 2018, : 1-1 CrossRef Google Scholar

[16] Yu H B. Combining symbolic execution and model checking to verify MPI programs. In: Proceedings of the 40th International Conference on Software Engineering, Gothenburg, 2018. 527--530. Google Scholar

[17] Wang R, Ding Z H, Gui N. Detecting Bugs of Concurrent Programs With Program Invariants. IEEE Trans Rel, 2017, 66: 425-439 CrossRef Google Scholar

[18] Wu X Q, Wei J. Visual debugging concurrent programs with event structure. J Softw, 2014, 25: 457--471. Google Scholar

[19] Qi X F, Xu X J, Jiang Z L, et al. Slicing concurrent programs based on program reachability graphs with partial-order reduction. Chinese J Comput, 2014, 37: 568--579 DOI: 10.3724/SP.J.1016.2014.00568. Google Scholar

[20] Qi X F, He J, Wang P. Variable strength combinatorial testing of concurrent programs. Front Comput Sci, 2016, 10: 631-643 CrossRef Google Scholar

[21] Liao W Z. Test data generation based on automatic division of path. Acta Electron Sin, 2016, 44: 2254--2261 DOI: 10.3969/j.issn.0372-2112.2016.09.034. Google Scholar

[22] Liu F Q, Huang H, Hao Z F. Evolutionary algorithm with convergence speed controller for automated software test data generation problem. In: Proceedings of IEEE Congress on Evolutionary Computation, San Sebastian, 2017. 869--875. Google Scholar

[23] Huang H, Liu F Q, Zhuo X Y. Differential Evolution Based on Self-Adaptive Fitness Function for Automated Test Case Generation. IEEE Comput Intell Mag, 2017, 12: 46-55 CrossRef Google Scholar

[24] Panichella A, Kifetew F M, Tonella P. Automated Test Case Generation as a Many-Objective Optimisation Problem with Dynamic Selection of the Targets. IIEEE Trans Software Eng, 2018, 44: 122-158 CrossRef Google Scholar

[25] Arrieta A, Wang S, Markiegi U. Employing Multi-Objective Search to Enhance Reactive Test Case Generation and Prioritization for Testing Industrial Cyber-Physical Systems. IEEE Trans Ind Inf, 2018, 14: 1055-1066 CrossRef Google Scholar

[26] Hwang G H, Lin H Y, Lin S Y, et al. Statement-coverage testing for concurrent programs in reachability testing. J Inf Sci Eng, 2014, 30: 1095--1113. Google Scholar

[27] Ding Z H, Zhang K, Hu J L. A rigorous approach towards test case generation. Inf Sci, 2008, 178: 4057-4079 CrossRef Google Scholar

[28] Souza S R S, Souza P S L, Brito M A S. Empirical evaluation of a new composite approach to the coverage criteria and reachability testing of concurrent programs. Softw Test Verif Reliab, 2015, 25: 310-332 CrossRef Google Scholar

[29] Tian T, Gong D W. Model of test data generation for path coverage of message-passing parallel programs and itsevolution-based solution. Chin J Comput, 2013, 36: 2212-2223 CrossRef Google Scholar

[30] Gong D W, Zhang C, Tian T. Reducing scheduling sequences of message-passing parallel programs. Inf Software Tech, 2016, 80: 217-230 CrossRef Google Scholar

[31] Siegel S F, Zirkel T K. FEVS: A Functional Equivalence Verification Suite for High-Performance Scientific Computing. MathComputSci, 2011, 5: 427-435 CrossRef Google Scholar

[32] Lv X W, Huang S, Hui Z W. Test cases generation for multiple paths based on PSO algorithm with metamorphic relations. IET Softw, 2018, 12: 306-317 CrossRef Google Scholar

[33] Tian T, Gong D W. Evolutionary generation approach of test data for multiple paths coverage of message-passing parallel programs. Chin J Electron, 2014, 23: 291--296. Google Scholar

  • Figure 1

    A source code of calculating the maximum common divisor for 6 integers. (a) Process $S^0$; (b) process $S^1,S^2,S^3$; (c) process $S^4$

  • Figure 4

    APFD diagram for the sorted scheduling sequence set

  • Figure 5

    (Color online) APFD values for 9 programs

  • Figure 6

    (Color online) APFD diagrams for 9 programs. (a) T1; (b) T2; (c) T3; (d) T4; (e) T5; (f) T6; (g) T7; (h) T8; protectłinebreak (i) T9

  • Table 1   Scheduling sequence of the sample program
    Scheduling sequence $n_5^0$ $n_6^0$ $n_7^0$ Corresponding process Representation of
    execution orderscheduling sequence
    ${{\rm~SS}_1}$ $n_8^1$ $n_8^2$ $n_8^3$ ${S^1}{S^2}{S^3}$ $(1,2,3)$
    ${{\rm~SS}_2}$ $n_8^1$ $n_8^3$ $n_8^2$ ${S^1}{S^3}{S^2}$ $(1,3,2)$
    ${{\rm~SS}_3}$ $n_8^2$ $n_8^1$ $n_8^3$ ${S^2}{S^1}{S^3}$ $(2,1,3)$
    ${{\rm~SS}_4}$ $n_8^2$ $n_8^3$ $n_8^1$ ${S^2}{S^3}{S^1}$ $(2,3,1)$
    ${{\rm~SS}_5}$ $n_8^3$ $n_8^1$ $n_8^2$ ${S^3}{S^1}{S^2}$ $(3,1,2)$
    ${{\rm~SS}_6}$ $n_8^3$ $n_8^2$ $n_8^1$ ${S^3}{S^2}{S^1}$ $(3,2,1)$

Contact and support