This paper defines a new relation--little strong happened-before（LSHB） and presents the algorithm for LSHB. Compared with strong happened-before （SHB） and weak happened- before （WHB）, LSHB supports keeping-read-...This paper defines a new relation--little strong happened-before（LSHB） and presents the algorithm for LSHB. Compared with strong happened-before （SHB） and weak happened- before （WHB）, LSHB supports keeping-read-result and ensures definite sufficiency of testing. Equivalence partitioning the set of SYN-sequences based on LSHB can efficiently reduce the number of testing SYN-sequences. The case studies prove that LSHB has high practicability.展开更多
Reachability testing is an approach to testing concurrent programs, which can systematically exercise every partially ordered SYN-sequence without constructing the static model. In fact, not all the SYN-sequences need...Reachability testing is an approach to testing concurrent programs, which can systematically exercise every partially ordered SYN-sequence without constructing the static model. In fact, not all the SYN-sequences need to be tested. This paper proposed a SYN-sequence selection strategy for reachability testing, which can reduce the number of SYN-sequences generated without decreasing the effectiveness of detecting programs＇ errors. We described a simple algorithm to implement the strategy, and then discussed several optimizations to the algorithm. Experiments have been carried out in a case study to verify the efficacy of the strategy.展开更多
Testing of parallel programs involves two parts-testing of controlflow within the processes and testing of timing-sequence. This paper focuses on thelatter, particularly on the timing-sequence of message-passing parad...Testing of parallel programs involves two parts-testing of controlflow within the processes and testing of timing-sequence. This paper focuses on thelatter, particularly on the timing-sequence of message-passing paradigms. Firstlythe coarse-grained SYN-sequence model is built up to describe the execution of distributed programs. All of the topics discussed in this paper are based on it. Themost direct way to test a program is to run it. A fault-free parallel program shouldbe of both correct computing results and proper SYN-sequence. In order to analyzethe validity of observed SYN-sequence, this paper presents the formal specification(Backus Normal Form) of the valid SYN-sequence. Till now there is little workabout the testing coverage for distributed programs. Calculating the number of thevalid SYN-sequences is the key to coverage problem, while the number of the validSYN-sequences is terribly large and it is very hard to obtain the combination lawamong SYN-events. In order to resolve this problem, this paper proposes an efficienttesting strategy- atomic SYN-event testing, which is to linearize the SYN-sequence(making it only consist of serial atomic SYN-events) first and then test each atomicSYN-event independently. This paper particularly provides the calculating formulaabout the number of the valid SYN-sequences for tree-topology atomic SYN-event(broadcast and combine). Furthermore, the number of valid SYN-sequences also,to some degree, mirrors the testability of parallel programs. Taking tree-topologyatomic SYN-event as an example, this paper demonstrates the testability and communication speed of the tree-topology atomic SYN-event under different numbersof branches in order to achieve a more satisfactory tradeoff between testability andcommunication efficiency.展开更多
基金Supported by the National Pre-research Foundation Project of China (513150402)
文摘This paper defines a new relation--little strong happened-before（LSHB） and presents the algorithm for LSHB. Compared with strong happened-before （SHB） and weak happened- before （WHB）, LSHB supports keeping-read-result and ensures definite sufficiency of testing. Equivalence partitioning the set of SYN-sequences based on LSHB can efficiently reduce the number of testing SYN-sequences. The case studies prove that LSHB has high practicability.
基金Supported by the "Tenth-Five Years" National Science Pre-Research Foundation of China (41315.9.2)the Natural Science Founda-tion of Hubei Province (2005ABA266)
文摘Reachability testing is an approach to testing concurrent programs, which can systematically exercise every partially ordered SYN-sequence without constructing the static model. In fact, not all the SYN-sequences need to be tested. This paper proposed a SYN-sequence selection strategy for reachability testing, which can reduce the number of SYN-sequences generated without decreasing the effectiveness of detecting programs＇ errors. We described a simple algorithm to implement the strategy, and then discussed several optimizations to the algorithm. Experiments have been carried out in a case study to verify the efficacy of the strategy.
文摘Testing of parallel programs involves two parts-testing of controlflow within the processes and testing of timing-sequence. This paper focuses on thelatter, particularly on the timing-sequence of message-passing paradigms. Firstlythe coarse-grained SYN-sequence model is built up to describe the execution of distributed programs. All of the topics discussed in this paper are based on it. Themost direct way to test a program is to run it. A fault-free parallel program shouldbe of both correct computing results and proper SYN-sequence. In order to analyzethe validity of observed SYN-sequence, this paper presents the formal specification(Backus Normal Form) of the valid SYN-sequence. Till now there is little workabout the testing coverage for distributed programs. Calculating the number of thevalid SYN-sequences is the key to coverage problem, while the number of the validSYN-sequences is terribly large and it is very hard to obtain the combination lawamong SYN-events. In order to resolve this problem, this paper proposes an efficienttesting strategy- atomic SYN-event testing, which is to linearize the SYN-sequence(making it only consist of serial atomic SYN-events) first and then test each atomicSYN-event independently. This paper particularly provides the calculating formulaabout the number of the valid SYN-sequences for tree-topology atomic SYN-event(broadcast and combine). Furthermore, the number of valid SYN-sequences also,to some degree, mirrors the testability of parallel programs. Taking tree-topologyatomic SYN-event as an example, this paper demonstrates the testability and communication speed of the tree-topology atomic SYN-event under different numbersof branches in order to achieve a more satisfactory tradeoff between testability andcommunication efficiency.
