TIMING\|SEQUENCE TEST OF PARALLEL PROGRAMS

Testing of parallel programs involves two parts——testing of control\|flow within the processes and testing of timing\|sequence. The paper here focuses on the latter,particularly on the timing\|sequence of message\|passing paradigms.In order to simply and precisely describe the execution of distributed programs,the coarse\|grained SYN\|sequence model is proposed,on which all of the topics discussed in the paper are based.In order to analyze the validity of observed SYN\|sequence,this paper constructed the formal specification （Backus normal form）of the valid SYN\|sequence.With two typical collective operation——combine and broadcast as instances, the paper further clarified the significance of formal specification for valid SYN\|sequence in the testing of distributed programs.In practice the number of the distinct timing\|sequence combination for distributed programs is so large that it is almost impossible to test them directly.Therefore, an efficient and practical testing strategy——atomic SYN\|event testing is proposed, which is to linearize the SYN\|sequence（enabling it to consist only of serial atomic SYN\|events）at first and then test each atomic SYN\|event independently.