о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999ꡡ3610ڡVol.36No.101999



Զплڴ洢תƵͨŻ
ףժף
ժҪй2000ϵPVMΪԶʶϵͳ(AutoPar)ʵֵģܵռCollect㷨ŻԼԭ㷨ĽṹԸĽҪ˼ǽ洢ת뵽ռ㷨УӶʡȥ˴估ȡֹɴ˲ռ.֪ͨڲлϵͳǹؼ⣬ˣCollectЧʵĸߵֱӹϵAutoParļٱ.ñ㷨Чʳɱ.
ؼʡлAutoParPVMռ㷨洢ת
ͼšTP314
COMMUNICATION OPTIMIZATION OF PARALLEL LIBRARY BY
STORE-AND-FORWARD MECHANISM
ZHU Ming, HU Yong-Gang, ZHU Ming-Fa, and ZHANG Zhao-Qing
(National Research Center of Intelligent Computing Systems, Institute of Computing Technology,
Chinese Academy of Sciences, Beijing 100080)
(Research Center of High Performance Computers, Institute of Computing Technology,
Chinese Academy of Sciences, Beijing 100080)
AbstractThe work in PVM's environment on the Dawning-2000 system is realized for the automatic parallel recognition system(AutoPar). Introduced here is the data collection function Collect's algorithm and its design optimization and the structure improvement of the original algorithm.Collect algorithm and its design in AutoPar's parallel communication library based on PVM are studied,and a new algorithm and store and forward mechanism are found to implement Collect,which is faster than its original one.Because it emphasizes particularly the communication among processors, Collect will influence the speedup of AutoPar at Dawning-2000. Its major idea is to introduce the save-transmit mechanism into the data collection algorithm, reducing a large number of data fills-in and draws-out operation and preventing the data collection mistakes from being produced. As everyone knows, the communication problem in running parallel machine system is a vital problem, so the height of Collect's efficiency directly concerns how the quickening of AutoPar is compared. After the algorithm is used, its efficiency is doubled through real testing.
Key wordsparallelization, AutoPar, PVM, collect algorithm, store and forward
1
ܼһٵӲϵͳΪ, ϵͳܵں̶ܴȴȡܵ. Ϊ˳ַӸܼṩĸټ, ԶعѳΪҪо.һ, ԵϵͳУRice ѧ FPPS, Illinois ѧ PARADIGMIBM PTRAN, StanfordѧSUIF . 20, ԲعоFortran ԴģҪΪFortran Ϊһֿѧԣ˴Ӧó. ԴеFortran ԴԴ-Դ任תΪдչFortran Դ. 2000ϵͳõԶʶϵͳ(AutoPar)ǶFortran ԴԴ-Դ任. 2000ϵͳõԶʶϵͳΪоҪPVM1ݲͨſУ2Ҫռܺ㷨.SPMDг˴洢ת˼룬ʹ㷨еĹؼ·̣Чʱ˴Żǰ㷨3ݳɱ. ĶռCollect Ż㷨ϸĽ.
2ڴ洢תƵCollect㷨
2.1Collect㷨ͼ
ûл4ݣƱҪѭָ㣬͵¸ڵֻвݲμ㣬ݵҪڵϵõռ. 㷨ͼ.
2.1.1ԭ㷨ͼ
ͼ1ԭ㷨ͼпԿ㷨̵Ĺؼ·ϣн϶ĵȴӳٺͨӳ٣ˣӰԭ㷨Ż. 㷨ͼУӳٴ.


ͼ1ԭ㷨ͼ
2.1.2㷨ͼ
㷨ǻڴ洢ת˼룬ѸӻЧݴ洢䶯̬ڴУȻٽ㲥ӻ. Ӷʡȥǰ㷨Ķη-ղԼϵ䣬ɴ(μͼ2).


ͼ2㷨ͼ
2.2Collect㷨
range informationǡ硱copy the data modified by itself to a data bufferǡ鼯ɡ.fill in the data to its local array for the newest statusǡ䡱.
2.2.1Collectԭ㷨
ռCollect 㷨
int AUTOPA R_COLLECT()
{
(1)if this process is master
{
١receive the range information of array data from all other nodes;
ڡbroadcast all range information received from all other nodes;
ۡreceive the data of array from all other nodes;
ܡfill in the data to its local array for the newest status;
ݡcalculated the minimum and maximum range information for every dim of the whole array, and then copy the data of the specified range of the array to a data buffer;
ޡbroadcast the data buffer to all other nodes;
}
(2)else // this process is a slave
{
١send its range information of array data to the master;
ڡreceive all range information from the master;
ۡcopy the data modified by itself to a data buffer;
ܡsend the data buffer to the master;
ݡreceive the newest data of the whole array from the master;
 fill in the newest data to its local array to keep the newest status of the array;
}
}
ڴ㷨Уؼ·Ϲ4sendreceiveã2 Collectlocaldata() 2Filldata()Ӻ㷨˴Ľ4ݣƵĵúͨţܵ½. ڷ㷨̺˴洢תƣ󽵵ͨſӶʹЧʳɱ. 㷨.
2.2.2Collect㷨
ȣҪһ㷨ݽṹ.

ݳά߽Ϣ

ݽṹ벢ʹãӻݷ͵ӻݰݽṹƴװƴװϺ㲥ӻӻٸݡšӻ䵽.
ô㷨߼Ͽ֪Чʽɱ, ʵЧҲȷʵ.
New algorithm:
{
(1)if this process is a master;
{
١malloc a large memory as the data buffer and copy its local newest data to data buffer
(meantime, fill its processornum to the correspondent position.)
ڡreceive the range information and the modified data of the array from all other nodes;
ۡaccording to the range information of every node, fill in its newest data to its local array for its newest status;
ܡbroadcast the data buffer which includes all newest range information of data of every node;
}
(2)else // this process is a slaver;
{
١copy its newest range information and data of its array to a little data buffer;
(meantime, fill its processornum to its correspondent position in the buffer.)
ڡsend the message in data buffer to the master;
ۡmalloc a large memory as the data buffer;
ܡreceive the broadcast message from the master;
ݡaccording to the range information and processornum in the broadcast message, fill in the newest data to its local array to keep its data validate;
}
} 
ڴ㷨Уؼ·ϣ2sendreceiveã1 Collectlocaldata() 2Filldata(). ɼ洢תãʹͨſ󽵵. Ӷ߳лЧ. 
2.2.3㷨Ч
һ100100100άΪԹܻĵ1000 Plus.
ԴԴ任100100100άĲFortranд룬кжAUTOPARCOLLECTĵã
S = 0
DO 120 M=1,50
S = S+1.0D+00
CALL FAUTOPARLOOPSPLIT(99,2,FAUTOPARLOOPSTART,& FAUTOPARLOOPEND)
DO 130 J=FAUTOPARLOOPSTART,FAUTOPARLOOPEND
DO 140 I=1,100
A(I,J,M) = 1010.0
140 CONTINUE
130 CONTINUE
CALL FAUTOPARSETRANGED(2,1,100)
CALL FAUTOPARSETRANGEUD(1,0,0)
CALL FAUTOPARSETRANGED(0,M,M)
CALL FAUTOPARLAYOUT(A)
CALL FAUTOPARCOLLECT(A)
ʱͳƶԱ1ʾ 
1

㷨()ԭ㷨()ٱ
324502.1
211201.8

СӾͿԿ㷨Чʽԭ㷨Ѵ. ңʹӣƸܵõ. 2ʾһЩBENCHMARK(ΪPVM3.3ڵΪ2.)  
2

BENCHMARK㷨()ԭ㷨()ٱ
B7325067002.0
W.SR293058282.0
W.LG4299472.2

ע
 BENCHMARK 7B7NUMBER OF STEPSΪ5.
 W.SR SOLVES THE EULER EQUATIONS IN GENERALIZED CURVILINEAR COORDINA USING AN IMPLICIT FINITE DIFFERENCE ALGORITHM WITH APPROXIMATED FACTORIZATION AND A DIAGONALIZATION OF THE IMPLICIT OPERATORS
 W.LG IS PURE GAUGE SU(3) MONTE CARLO 
3ᡡ
ڽ洢ת뵽ռ㷨Уʡȥ˴估ȡֹɴ˲ռ󣬶Ҵ󽵵ͨſ.ñ㷨Чʱ2000 AutoPar Ħ汾˺ܶ࣬Ϊ2000 AutoPar ʵû춨˻.
õҸ߼Ŀ.
߼飺ףУ19685оԱ˶ʿҪ¼㡢ٵ·緽о.
գУ196411оԱ˶ʿҪԶбʶ𹤾ߺNTȺϵͳо.
ףУ19455оԱҪ¸ܲмо.
죬Ů19381оԱҪԶбʶ𹤾ߵо.
ߵλףף졡йѧԺ㼼оܻоġ100080
աйѧԺ㼼оܼоġ100080
ο
1PVM3 User's Guide and Reference Manual. Department of Computer Science, University of Tennessee, Knoxville, 1994
2ASPARAn Automatic Parallelizer for C Programs. Parasoft Corporation, Pasadena, 1991
3Cytron R. Compile-time scheduling and optimization for asynchronous machinesPh D dissertation. University of Illinois at Urbana-Champaign, Illinois, 1984
4Wolfe M. Data dependence and program restructuring. The Journal of Supercomputer, 1990, 4(4): 591601
ԭյڣ1997-12-18
޸ĸյڣ1998-05-05.
