о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.6P.705-711



ʽ»ڲηֽĲб任
ΰͮ
ժҪԴͳб任ڵĲ㣬һֽʽ»ڲηֽĲб任ҪѭⲢгɷֵȡǿû벢б任ýΪȼԷӶ˲б任ĸӶȣһ̶˳Ĳж.
ؼʣCFG, HTG, ֽ, ʽ, PCFG, б任
ţTP311
A TECHNOLOGY OF PARALLEL TRANSFORMATION
BASED ON HIERARCHY AND DECOMPOSITION IN AN
INTERACTIVE ENVIRONMENT
HE Wei-MinLI TongLIU JianJIN Zhao
(Department of Computer Science, Yunnan University, Kunming 650091)
AbstractIn order to improve the traditional technology of parallel transformation, a new technology of parallel transformation based on hierarchy and decomposition in an interactive environment is presented. It focuses on the extraction of non-loop parallelism and emphasizes the interaction of users. It can decrease the complexity of parallel transformation and make the extraction of functional parallelism more effective to some extent.
Key wordscontrol flow graph, hierarchical task graph, task decomposition, interactive environment, parallel control flow graph, parallel transformation
1
Ϊ߼ϵͳЧʣ޶ȵھϵͳǱмоΪһȵ㣬б뼼еѵ֮һ.б任ǲбеһҪɲ֣Դеȼع˳ȡгɷ֣ʹøĲл1.
ĿǰĲб任Ҫ.һҪѭԵĿøѭмѭعΪиಢлʽ2,3.ѭ任Уѭѭֲѭۺϣloop fusionѭ루loop peelingȵȣ4,5.ѭ任ѭУ˴ѭ֮ǱڲԵĿ.ʱѭĲԾͿԻܺܺõĿ룬ʹһǱڵĲԣܸҲ.϶ʱѭ޷ʹдڡæ״̬ʲߣ6.һַǰһֽ˸ĽѭⲢԵĿȵĵ֮ͬԷȫϵͳԶɣû޷Ԥ.ϵͳ̶ܻޣõȴСԷ룬Ӷ˳Ĳжȣ7.
ֲб任Ĳ㣬һֽʽ»ڲηֽĲб任.ּҪѭⲢгɷֵȡǿû벢б任ýΪȼԷ.ѭڲгɷֵȡеѭ任мɣĲϸ.
2HTGĹ
˳ԴĿͼCFGԹһͲͼHTG.HTGеÿһһֿ԰.HTGĸrootд˳ԴCFGл֣Եõһм㣬ÿмֿɽƵĻֱ֣ٻΪֹʱҶΪ.͵õһݹṹͼHTG.
CFGHTGķ£
CFG=VEVΪ㼯EΪ򻡼.
HTG=HVHEHVΪ񼯣HEΪ򻡼.
1. CFGУyǽxҴxyڻxy,򻡣xyΪѭΪxycycle.


I(x)ΪCFGxΪ㣬yΪյѭļ.

C(G)ΪCFGļ.
2. xC(G)yVxstopÿһ·yyʹôxstopÿһ·y䣬yyȣôyΪxĽ.


ͼ1˳ԴĿͼCFG
J(x)=ȣC(x,y) (C(x,y)ΪxΪ㣬yΪxJ(x)ΪCFGxΪ㣬yΪյļ.
տɵHV={I(x):xH(G)}{J(x):xC(G)}root{V}
HV׵HE.㷨ԣ
ĳ˳Դ£֮ӦCFGͼ1ʾӦHTGͼ2ʾ.begin
for i=1 to n do
read(firsti)
endfor
for i=1 to n do
read(secondi) 
endfor
for i=1 to n do
read(thirdi)
endfor
if (first0<second0 and first0<third0)
begin
process-block(first)
if (second0<third0)
begin
process-block(second)
process-block(third)
end
else
begin
process-block(third)
process-block(second)
end
end
else
if (second0<first0 and second0<third0)
begin
process-block(second)
if (first0<third0)
begin
process-block(first)
process-block(third)
end
else
begin
process-block(third)
process-block(first)
end
end
else
begin
process-block(third)
if (first0<second0)
begin
process-block(first)
process-block(second)
end
else
begin
process-block(second)
process-block(first)
end
end
end
end
/* Start of node T1 */
/* BS0 */
/* End of node T1 */
/* Start of node T2 */
/* BS1 */
/* End of node T2 */
/* Start of node T3 */
/* BS2 */
/* End of node T3 */
/* Start of node T4 */

/* BS3 */
/* Start of node T41 */

/* Start of BS4 */
/* End of BS4 */



/* Start of BS5 */
/* End of BS5 */
/* End of node T41 */


/* Start of node T42 */

/* BS6 */
/* Start of node T421 */

/* Start of BS7 */
/* End of BS7 */



/* Start of BS8 */
/* End of BS8 */
/* End of node T41 */



/* BS9 */
/* Start of node T422 */

/* Start of BS10 */
/* End of BS10 */



/* Start of BS11 */
/* End of BS11 */
/* End of node T422 */
/* End of node T42 */
/* End of node T4 */


ͼ2ͼ1ʾCFGӦĲͼHTG
3HTGŻ
3. ָ֮Ĳݵ໥ϵ8.SklSkrֱʾTk󲿱ҲTiTj֮ǰִУ3عϵ
(1) SilSjr,TiTjΪTiTj
(2) SirSjl,TiTjΪTiTj
(3) SilSjl,TiTjΪTiġTj.
HTGУTiTjʱ֮веǱڣԲֽ⼼HTGŻ.
3.1Ż˼
HTGĳһTx={T1, T2,,Tm}, Ti,TjTxTiTjTjTiδֽ֮ǰTiTj֮ǰִ.ֽ⼼ǶTjʵԽTj񻮷Ϊ3ϣTj1Tj2Tj3.Tj1еTi޹أTj1ص⣬TjTj2δTj1Tj2Tj3⣬ΪԭеӵҲTj3.Tj1еTiִУͼ3ʾ.HTGнTj1Tjзһ.ֽ֮ǰTx={T1,T2,,Ti,Ti+1,,Tj-1,Tj,,Tm},Tj={Tj1,Tj2,Tj3};ֽ֮Tx={T1,T2,,Ti,Ti+1,,Tj-1,Tj1,Tj,,Tm},Tj,={Tj2Tj3}.Tj2TiأTj1޹أTiִʱTj1δִ꣬Tj2Tj1ִ.Tj2صŻֻڳִйж̬УڶHTGľ̬Ż׶ǲ迼.


ͼ3ֽ⼼
3.2㷨
ʵHTGŻĹؼνTjеֽTj1Tj2Tj3.ֽ㷨Tjе񻮷Ϊѡ˷ֽ.ЩTiԣΪ3ࣺ
(1) Bound: Tiأ
(2) Linked: Ti޹أBoundLinked.LinkedϸΪ Needsbound:BoundNeedsboundأ Generatelinked:BoundࡢNeedsboundGeneratelinkedأ Readlinked:Linked࣬Generatelinkedأ
(3) Free: .
ж󣬽ֱTj1,Tj2,Tj3.
㷨1. TjеֱֽTj1,Tj2,Tj3
룺Tj={T1,T2,,Tm} , Ti
Tj1,Tj2,Tj3
BEGIN
FOR (j=1 TO m) DO
IF (TjFreeTjGeneratelinked)
THEN TjTj1
ELSE IF (TjBoundTjNeedsbound)
THEN TjTj3
ELSE TjTj1лTjTj3
END.
4ûʽ
ڴͳĲб任УгɷֵȡִĻöϵͳԶɵģ9
.CFGԤȶõģĿҪôǹ̶ģҪôϵͳԶ.ĳִʱϢڱʱ޷ã̵еʵʲֵԼѭ߽ϢֻɱΪصĹ.ϵͳ̶ܳȵƣԶʽб任һ̶ϻήͳĲжȣرǶڱȽϸӵĴͳ򣬸ǻʹб任Чʴۿۣ10.б任ԸӵĴͳģ򵥵Сͳûвб任ıҪ˽ϵͳɲб任ЧǺܲ.Ϊ˽һ߳ĲжȣǲһûЭĽʽHTGһŻ.
ڽʽ£ûȨһЩĹ
(1) ҪѡȵĴС
(2) ϵͳعϵ
(3) ΪعϵԼյ֪ʶ;飬ʵԴ޸ģ
(4) HTGŻУܹתƵHTGĲͬУ̬޸ĿȴСȷЩֽ⣬Щ᣻
(5) Թִʱ䣬ȷĳЩȻԲУǷвеıҪĳЩԲеִʱ̣ܶеĿʱ䷴ȴеִʱҪĲоͺ壩.
ǲýʽ˵ʵûHTGŻ.
˵ɣΪѡҲΪǰCFG.
ѡ6ܣ
(1) Control Dependence Graph (ɵǰCFGĿͼ)
(2) Data Dependence Graph ɵǰCFGͼ
(3) Modify Source Code ʵ޸˳Դ룩
(4) Move to Next Level תǰһ㣩
(5) Move to Previous Level תǰһ㣩
(6) Dependence Test ֮عϵ
ûͨṩ6ʵֶHTGŻ.
5HTGPCFGĲб任
ŻHTGǿԹ첢гĿͼPCFG.
PCFG=PVPEPVΪ񼯣PEΪ򻡼.
PCFGʣ
(1) (Ti,Tj)PETiӦTj֮ǰִУ
(2) TiPVTi={T1,T2,,Ts},(s2)T1,T2,,TsԲִ.
4. HTGĳһҶrootΪT1T2TmCT+i={Tr|Tr=Tj1jm((TsCT+isr)TrTs޹)}(1im)CT+iΪrootĲհ.
CT+iĶ֪CT+iе޹.
CT+i㷨£
㷨2. HTGнrootĲհCT+i
룺root
CT+i
BEGIN
i:=1; total:={T1 , T2 ,, Tm}; count:=m
WHILEcount>1DO
BEGIN
j:=0;CTji=totalеһ;
REPEAT
Tb;
/* Tb={T|TtotalTCTji(TqCTji)(TTq޹)}; */
CTj+1i:=CT(j)iTb;
j:=j+1;
UNTIL(CTj-1i=CTji)
CTi:=CTji;
total:=totalCT+i;
count:=totalеĸ
i:=i+1;
END
END.
㷨2rootĲհֱΪCT+1CT+2CT+n(1nm).
㷨2ĻϿԹPCFG㷨㷨3PCFGֻпʼstartrootͽstop.
㷨3. HTG첢гͼPCFG
룺root /* rootΪǰHTGĸ */
PCFG
BEGIN
rootΪ㷨2CT+1CT+2CT+n
PCFGCT+1CT+2CT+nroot
FORi:=1 TO n-1DO
CT+iCT+i+1֮򻡣CT+iCT+i+1
FORi:=1 TO nDO
IF (CT+iֻһTjTjǻ)
THEN TjΪݹ㷨3;
END.
6
б任ǲб뼼Ҫɲ֣Ĳб任ҪͨHTGֽ⼼ûķʽŻŻHTG첢гĿͼPCFG.һ̶˳Ĳжȣܹñȴͳб任õĲЧ.ⷽ滹кܶĹֵȥ.磬ûĲȻһ̶˳ĲжȣûҲܶеʱĹƣб任ں̶ܴϻֻͣھ̬ˮƽϣͲʹѵĲЧ.⣬Ƕ׽϶ĳ򣬲б任ñȽϸӣҲӦӣԭеı任ҪӦ޸Ĳ.ЩⶼдһоǽڽĹжЩԽ.
ĿõʡȻѧʡѧͼͷʡ.
߼飺ΰУ19732˶ʿоҪ̡дȷġо.
ͮУ196312ڣҪ̡дϵͳȷ桡о.
У19761˶ʿоҪ̡Զȷġо.
ȣУ19773˶ʿоҪ̡CASE߼ɵȷ桡о.
ߵλΰϴѧѧϵ650091
ͮϴѧѧϵ650091
ϴѧѧϵ650091
ȣϴѧѧϵ650091
οף
1Ƽ壬֣.һֻڷֽ任Ĳл¼.ѧ199825(1) 8183
(Chen Qingpin, Li Xiaofeng, Zheng Shirong. A new technology of split-based transformation in parallelization compile. Computer Science (in Chinese) 1998,25(1): 8183)
2Koelbel C, Mehrotra P. Compiling global name space parallel loops for distributed execution. IEEE Trans on Parallel and Distributed Systems, 1991, 2(10): 463481
3Kennedy K, McKinley K S Tseng C. Interactive parallel programming using the parascope editor. IEEE Trans on Parallel and Distributed Systems, 1991, 2(7): 329341
4Lilja D J. Exploiting the parallelism available in loops. Computer, 1994, 27(1): 1326
5Rogers A, Pingali K. Compiling for distributed memory architectures. IEEE Trans on Parallel and Distributed Systems. 1994, 5(3): 281298
6Girkar M, Polychronopoulos C D. Automatic extraction of functional parallelism from ordinary programs. IEEE Trans on Parallel and Distributed Systems, 1992, 3(3): 166178
7Mukherjee N, Das P K. An approach towards parallelisation of sequential programs in an interactive environment. Information and Software Technology , 1997, 39(2): 7789
8Ferrante J, Ottenstein K J, Warren J D. The program dependence graph and its use in optimization. ACM Trans on Programming Languages and Systems, 1987, 9(7): 319349
9ѧɣͬ.д.ѧ磬1994
(Li Xuegan, Xu Jiatong. Parallel Processing Technology(in Chinese). Beijing:Beijing Polytechnic University Press, 1994)
10磬Դ.г.ϺϺѧ׳磬1994
(Li Yuqian, Yang Zongyuan. Parallel Programming(in Chinese). Shanghai:Shanghai Science and Technology Literature Press, 1994)
ոڣ1998-09-14
޸ڣ1999-02-01
