о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 9 Vol.36 No.9 1999



гʱ
ϡ桡Żԡе
ժҪгĴɷΪ̼(inter-process fault)ͽڲ(intra-process fault)., ڲɿɵ, ̼ɽ̼Ĳʱϵɵ. Ҫ̽˹ڲг(ԻϢݵķֲʽгΪ)ʱеһϵйؼ.Ϊܹݡ걸طӳг,ȹһͬģ,ڴģ͵ĻϽ. Ϊ˼ֲʽгͬеĺϷ,йЧͬеʽ淶.Ϊʹ, ṩ͵ľ͹㲥鲢Чͬеʽ淶, ܽеĸͬ¼ʱԼ.ӴʱʹòгĲʵ, һʵеĲԲԡԭ¼Է, ˼뷽Իͬʹɴеԭͬ¼ɣӶﵽֶ֮Ŀ.
ؼʡʱ,г,ͬ¼,ͬ,ԭ¼Բ
ͼšTP311.5
TIMING-SEQUENCE TEST OF PARALLEL PROGRAMS
LIANG Yu, LI Shu, ZHANG Hui, and HAN Cheng-De
(National Research Center of High Performance Computers, Institute of Computing Technology,Chinese Academy of Sciences, Beijing 100080)
AbstractTesting of parallel programs involves two partstesting 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 operationcombine 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 strategyatomic 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.
Key wordstiming-sequence test, parallel programs, SYN-event, SYN-sequence,atomic-event test
1
ڶԲг(̻߳)Ĳ, ǲҪýڲִ(ȷ̻߳̾Ŀ), һöԸ̻̼߳䲻ͬʱϵĲɳ̶( Ա֤벢мĸ̻̼߳໥ʱϵʱ).ڽڵĿ̲(control-flow testing), ǿôгõһϵҵѳļ1,2, ڱв׸;ڲгʱ(timing-sequence testing)һ, δйϵĽΪЧķ, ĽԴΪҪо.
ʱԵ˲гĲԸӶ, ͬʱҲ˶и(trace)(debug)Ѷ, ΪƵҪƿ֮һ. ĴʵõĽǶȳ, ȹһܷӳгʱ̵ģͬ͡ģ, Ȼڴ˻϶ʱеһϵйؼ, 粢гйʱ̵ĺϷԷгĲԷ, ˽Ϊ롢ϸµо.
2гģ
ڲм, ໥Լ໥Эͬ, һ걸ĲгԹӦþܷ߱ӳ̼ʱϵĻ. Ϊ, Ľף3ͬ}ģ. һֲʽгʱ̿һϵаһʱȺϵ֯ͬ¼Сͬ(SYN-sequence). , ͬ¼(SYN-event)ʾͨйصĻ. ԻϢݵĲгΪо, ôȵͬ¼ģ, Ϣһη-Ϊͬ¼. ͬʱ, ͬ¼ķͺͽΪͬ(SYN-action).ͬ¼ģͿɲμף3., ͬ¼ռõͨý(ͨŵڴ)Ϊͬ (SYN-object).ڲг, ͬ¼ӦǼ¼(computing occurence),ǶһζĲͬĳִ, ʱжԼ¼κδ.
֮, õͬģص:ԻϢݵĲгΪо, ͬ¼ʾһϢķ-,վ(blocking)ʽ;ڲ̾Ǿ̬;ͬӦ, ߽ӳչ, ߽ӦӳΪһ¼;ܶڲгеĵ, ѭеĽ̺, 轫ѭչ;ͬ¼ʱԷʱΪ׼, Ǽȷ͵ϢҲȱ, ԡʾڷԡʾڷ.
ͬͼ (SYN-graph)4ݿԽΪ׼ȷгͬģ. ڱͬͼһԪʸ(quadruple)T,N,Ec,Esʾ, TʾĽ̼, N ʾͬļ, Ecʾ,Esʾͬ¼., »ϢݵĲг(ȥйؼ, ͬΪsend( )|recv( )):
1. 򵥵ĻϢݵĲгα
process a
begin
for (i=0; i<2; i++) recv(-1, msgid,data, MAXDATALEN);
/* a0, a1 */
send(b, msgid, data, datalen); /* a2 */
send(c, msgid, data, datalen); /* a3 */
send(c, msgid, data, datalen)/* a4 */
recv(c, msgid, data, MAXDATALEN);/* a5 */
end
process b
begin
send(a, msgid, data, datalen); /* b0 */
recv(a, msgid, data, MAXDATALEN);/* b1 */
end
process c
begin
send(a, msgid, data, datalen); /* c0 */
recv(a, msgid, data, MAXDATALEN);/* c1 */
send(a, msgid, data, datalen); /* c2 */
recv(a, msgid, data, MAXDATALEN);/* c3 */
end
ͬͼͼ1ʾ.ͼ1еĽʼ(B)ս(E)ʾĿʼս,ʾͬ(receive()send()); ʵΪ(computing action);(dashed line)Ϊͬ¼;ͼеֱ߱ʾ̵Ĳֹ;ֵһͼеԲ, a0a1b0c0ĸͬ޷γȷͬ¼, ڳймȿܲͬ¼b0a0c0a1, ֿܲͬ¼c0a0b0a1, ͼнרűʶ.

ͼ1гģ
ڱԻϢݵĲгΪо, ͬ¼ԪʸV, S, R, Mʾ., Vʾͬ¼;SʾϢͷ(sender), Ϣͽ̡Ͳڳеλõ;RʾϢշ(receiver), Ϣս̡ղڳеλõ;Mʾͨ(mail box), ʵóһʶ.Ϊ, ڱĵʣಿͬ¼һͷ-շżʾ.
ʵ, ݲ(testing granulality)Ĳͬ, ͬ¼Բòͬݽṹʾ.ͬ¼ݽṹЧԽһ֮: һͷͽշ, ͨż.
3гģ
3.1ȷжԭ
ڲгִйʱϵĲȷ(nondeterminacy),ڷֲʽгȷҲ˲ͬڴгµжԭ.һֲʽгP, ΪXʱ, һͬпԱִв, гΪе(feasible); ΪXʱ, һͬзϳPĶ淶, ɳ֮ΪЧ(valid)., ĵĳ淶һϵƫϵɵĹͬ¼ִ˳Լ(constraints).
: Feasible(P,X) ΪΪ X ʱڷֲʽг Pеͬм;  Valid(P,X) ΪΪ X ʱڷֲʽг PЧͬм.
1. ΪX ʱгPȷ, ҽ:
 Feasible(P,X) = Valid(P,X) ; 
 X Ϊ, ÿִP ܵõȷĽ.
, еP ȷִ, P ȷ.
2. ΪXʱгPǴ,ҽ:
 Feasible(P,X)  Valid(P,X) ; 
 X Ϊ, ĳһִлĽ, ʹͬЧ (ȻҲǿе).
, ڶ2, , ˵ֽ̼(inter-process fault); , ζųֽڲ(intra-process fault).
ͬе뽫ΪǶԲгԸʡ걸ԺͲԲʶṩȫ桢׼ȷӽ, ϸݲμף3.
ҪжFeasible(P,X)  Valid(P,X) Ƿ, Ϊʵİ취ǲһԲ(conformance testing)[5].νһԲָǼʵ(implementation)Ƿ淶(specification).Ĺ淶Ҫָʽ淶(formal specification).½ڵҪνЧͬеʽ淶, ӶʹԶؼ𱻲йͬǷЧ.
3.2ͬй淶ʽ
ֲʽгĳ̶ֳһĲг,ĳһֲʽг,ܿӦͼִйеͬ¼Լ., ֲʽгĹ淶ͼ.﷨(޹ķ, BACKUSʽ)ֱ۵г, Ҳֲʽгͬй淶.
3. Valid(P,X) ΪΪ X ʱڷֲʽг PЧͬм,Valid(P,X) ԪʸVT, VN, O,F.,
սVT ={:,;,s,r,,(,),,}.srֱʾͷ(sender)ͽշ(receiver);:͡;ǹϵӷ, Ƿֱʾ(sequential)ƽйϵ(parallel);ֱ͡ʾѭĿʼս,(͡)ΪշеĽ, ۡ͡ݡΪͷеĽ. շбʾɾͬͽ̵Ľշɵ,ͷбʾɾͬս̵ķͷɵ.
ڷս VN = {E, R, S}.Eʾͬ, Rʾշ, Sʾͷ.
۳ʼ״̬ O, ʾͬ.
ܲʽ FΪ

ڽķľ֮ǰ, бҪҪ:ͬ¼Ĵкƽ.
4.Valid(P,X)ΪXʱֲʽгPЧͬм, ͦΪΪXʱйеͬ¼.Valid(P,X) һЧͬ, ڦ»ߦ, ΪXʱͦ´(serial, á;ʾ); ΪXʱͦ ƽ(parallel, á:ʾ).
, ͼ1ʾг: {b0a01:c0a01}, {a4c3:c2a5}, {a2b1;a3c1}.
3ķӦ:ȷ, йиͬ¼ֹܴϵ:(sequential)ƽ(parallel). , ͬ¼ѭʾʽ;, ѭͬейؽ̺Ŵӳϵ, 򲻿ɲEEʾ, ʱ뽫ѭչ.򵥵öԪʸs,rʾͬ¼, rΪϢս, sΪϢͽ.ķṹ, s,rֱʾʽ:s(r)rs, ߷ֱΪͷȺͽշģʽ., ǰڹ㲥, ڹ鲢.۷ͷȺͽշȱʽɽǶ(nest). ӿɲμ2.4.ܸݲгл,÷ͷģʽʱ, ʽΪs(r0;r1;:rn), Ϊͬ¼;ýշģʽʱ, ʽΪrs0:s1::sm, Ӧͬ¼ƽ.
3.3ͬͷͬг
ִйͬе, гԷΪͬгͷͬг.
5. ڲгP, ΪX, Valid(P,X)һͬ, ͬ¼, ΪXʱPͬ(linear synchronization); ΪXʱPͬ(nonlinear synchronization).еPΪͬ, PΪͬ.
1. ΪXʱPͬҽ|Valid(P,X)|=1(|set| ʾsetԪظ).
1ɶ5ֱӵõ.
ͬͬ¼ȷ˳ִж־(race)ͻ(conflict), (ĳЩ̷˳м), ͬеĲг򲻻.ֻаͬеĲгпܲ(deadlock),ͼl, ͬ¼a4c3c2a5ǲ֮һ, ԭ{a4c3:c2a5}.
ʵ, ʵõĲг, ͬһ㶼ǳԻϳԵ. ɲгı. Ϊڴг, (data dependency)ֵͨ; ڲг, ̼ͨͨʵֵ, ;˲гйиͬ¼ӦΪйϵ.
ڶԲгķ, ԸǴ˺ܴĲ. , ʱ򽫷ԳԻ(linearlization)ͱúбҪ.ԻҪ:ٶͼlͬa4c3:c2a5,ͨͬԻ; ڶڽΪӵķͬ, ɹ㲥µƽйϵ,ԭͬ¼(atomic SYN-event)}һ, һϵصĻᵼ·Եͬ¼Ϊԭͬ¼, Ȼٷֱԭͬ¼. ʵʵĲг, ԭͬ¼Ҫе-ͨ(point-to-point)(broadcastcombine)ͬƲ(barrier).
, ͼlĲг򾭹Ի, Чͬй淶ab:c;a(b;c);a(c):c(a)Ϊcombine(a);broadcast(a);a(c);c(a).
3.4͵ľ㲥͹鲢
(collective operation)ʾͬʱ漰Ͻ̵ͨŲ.͹㲥͹鲢ǱȽдԵķԾ.ڲг, ӦԴ½ṹص:Ӧѭ, ѭͬеĽ̺Ŵһӳϵ.ڵ3.2ᵽͼԷӳֲʽиͬ¼Լϵ.ͼ2ڲͨŵĽΪ9÷֧Ϊ3˽ṹ(topology)й㲥͹鲢ͼ,ͼнʾ̣߱ʾͬ¼. ͼʵϷӳ˸ͬ¼ʱϵ.

ͼ2;㲥(a)鲢(b)ͼ
ͼͬ¼ֱϵѪ׹ϵ, ĳһͬ¼ʼһֱ()ִܵһͬ¼. ͼ2ͬ¼0335ֱϵѪ.ͬ¼Ϊֵ, ͼͬ¼Ӧ߾Դͬһ.ͼ2ͬ¼3435ֵ.
ö3ķԺܷ͹㲥Чͬй淶., ͼ2a㲥Чͬй淶ԱʾΪ:0(0(0;1;2) ; 3(3;4;5) ; 6(6;7;8)) ͬ¼ִ˳Ϊڽ, ͹㲥ͬй淶ֳΪı(centripetal table).
ıһҪ:ͬ¼ͦ,ͦΪֱϵѪ, ͦΪֵ, ߦͦµķͷΪͬһ,´.
ö3ķҲԺܷ͹鲢Чͬй淶. , ͼ2(b)㲥Чͬй淶ԱʾΪ:000:1:2 : 33:4:5 : 66:7:8ݣ ͬ¼ִ˳Ϊ, ͹鲢ͬй淶ֳΪı(centrifugal table).
ıһҪ:ֻдֱϵѪ׹ϵͬ¼Ŵڴйϵ.ııҪʽڲԸʵļҪ.
4ԭ¼Բ
гʱԵѵҪԴԲгӴʱ.1г˲֧ͬĽΪ9͹㲥鲢Чͬ. ݱʹ9-㲥鲢򵥵Ĳг, ЧͬҲǷǳ.Ϊ,  ԭ¼(atomic-event testing), ͬģ, ԭ¼ԷΪ:Իԭʼͬ, ʹɴصԭͬ¼ (μ3).ڷֱԸԭͬ¼в.ĳһԭͬ¼(atomic SYN-event), ȷԲԷԭͬ¼ʱ̶̹, Ӷеضв, ҲɿרŵģԴԭͬ¼ģִ.
1;ĿɲԱȽ

֧Чͬй淶Чͬ
2㲥0(0(0(0(0,1),2(2,3)),
4(4(4,5),6(6,7))),8)80
鲢00000:1:22:3ݣ:
444:5:66:7ݣݣ:82520
3㲥0(0(0;1;2);3(3;4;5);6(6;7;8))126
鲢 000:1:2:33:4:5:66:7:8ݣ4480
4㲥0(0(0,1,2,3),4(4,5,6,7),8)35
鲢000:1:2:3:44:5:6:7:810080

ԭ¼걸ԺͿɿԷܲ¼, нϸߵĲЧ, ͬʱܹ¼¼ļռĿռ., ͬģһֽΪʵõĲԲ., ԭ¼ԲԵ˲гʱеһϵмʹʵֳΪ, 粢гʱĲԸʷͬе(replay)¼(record)гĲԲ(test generation)ȷ(testability analysis)Լͬģ֮ϵĹ(deadlock)Ķ̬4ݵ. Щȡһչ, ڱƪ,ǽԺмԽ. 
עõʵǼƻĿ.
߼飺,У19683ʿ,ҪоΪдϵṹݴ.
,У19743ʿо, ҪоΪдźŴ.
Ż,У197312˶ʿо, ҪоΪϵṹͼ.
е,У19404оԱ, ʿʦ, ҪоΪϵṹдý弼.
ߵλйѧԺ㼼оҸܼ̼ġ100080
ο
1Beizer B. Software Testing Techniques.New York Van Nostrand Reinhold Company,1983
2Ferguson R, Korel R, Software test data generation using the chaining approach. In: Int'l Test Conf, 1995. 703709
3Tai K C, Carver H. Testing of distributed programs. In: Parallel Distributed Computing Handbook, Series on Computer Engineering. New York: McGraw-Hill, 1996. 955978
4Masticola P,Gyder G.Static Infinite Wait Anomaly Detection in Polynomial Time.In:Int'l Conf on Parallel Processing,II.1990.7887
5Linn J, Uyar U.Conformance Testing Methodologies E Architecture for OSI(Open System Interconnection)Protocols. California: IEEE Computer Sociaty Press, Los Alamitos
ԭյڣ1997-11-26޸ĸյڣ1998-02-12.
