ѧ
JOURNAL OF SOFTWARE
1999 1 No.1 1999



һڻȺϵͳ̬ȷ*
ǿ֣γ
ժҪǻȺϵͳʵֲмҪҪ֮һ.ж̬ĲӦó,ں׼ȷ,ܵ¸ʧ,ϵͳ½.,Ҫͨٷάָƽ.һٷ䷽,ͨӳִпʼʱ,ٷʱ˽Ǩ,ʹĵȿС.ʵ,÷ܹЧ߲г.
ؼʡ,Ⱥϵͳ,м,,ƽ.
ͼšTP316
A Dynamic Task Scheduling Method in Cluster of Workstations
FU QiangZHENG Wei-min
AbstractTask scheduling is an important issue in the research of parallel computing in cluster of workstations. Because it is difficult to make precise decision of task allocation when running parallel applications that dynamically spawn tasks, load imbalance maybe occur and the performance of whole system will decrease dramatically. So task reallocation is necessary for load balancing. A method for task allocation and reallocation is presented in this paper. By deferring the task's real start-time, it avoids process migration in task reallocation. Therefore, the overhead is greatly decreased. Analysis and experiments show that this method can effectively improve the performance of parallel applications in many cases.
Key wordsScheduling, cluster of workstations, parallel computing, task allocation, load balancing.
,Źվܼ۸ȵѸߺͿپĳ,վȺϵͳ(Cluster of Workstations)ѳΪмһҪչ.ڻȺϵͳϽвм,Ҫ֧.ĿǰѾ㷺ӦõĲPVM(parallel virtual machine)1,MPICH(message-passing interface).
ڻϢģʽĻȺϵͳм,ĵȷӰӦó.ʵӦ,ڻȺϵͳṹͳĲȷ,Ҫʱж̬.̬޷ĸȺ໥ͬͨŹϵ׼ȷϢ.,׼ȷ,Ҫʵʱٷάָϵĸƽ.һЩϵͳPVM,һִ,Ҫʵٷ,ֻܲȡǨƵķʽ.ǨƲ칹ʵ,俪ҲʮӴ,ƽ.
һֻϢݲлġԡȷ,ԲǨƶʵֵͿٷ.صУ(1) ÷ʽʽ,Ӧʱ.(2) öִл,ֻδʼִеٷ,С.(3) 估ٷʱȡػ㷨,һСȿ,һ»Сͨſ.(4) κִһٷ,.
,ȸ㷨,Ȼܸ㷨ʵַ,ܷģʵĽ.
1㷨
ԡȷ㷨ִٷ,ͼ1ʾ.,㷨ӦӦó򷢳,״ִлƾںʱк,һ¶ѷе,ٷ.

ͼ1
1.1㷨
ʵĵͿٷ,ʵͨǨơδִеʵֵ.Ҫڷִ,ǽ뱾صľ.ϵͳLIFO(last in first out)˳Ӷͷȡִ,ֻеȴδִݶʱȡһִ.ڵCPUUNIXϵͳʱƬֻû,ִֶеʱ벢ִͬ.
Ĳõ㷨£
If (Receive(SPAWN,taskname)) { ӵtaskname
ID=GetID(taskname) ӦtasknameΨһʶ
Insert(Q,ID,HEAD); ID뱾ؾQĶͷ
Ack(ID);   Ӧ󲢷ID
}
Ƚڱ,ĿǼٵȿ,ʹͨžػ.ִ,Ӧ,ʹĽִܹ.
1.2ִٷ
ִлֻڵǰе̽ȴδִݶʱű.Ȳ鿴ؾQ,Qǿ,ȡͷִУQΪ,ٷ䣺.Qǿ,򷵻ضβ.
If (Endtask(currentTask) or Block(currentTask)) { û
If (not empty(Q))
 currentTask=Get(Q,HEAD); ȡͷIDΪǰ
else
 currentTask=RequestTask(otherNode); 
Run(currentTask); ִи
}
If (Receive(REQUESTTASK)) 
If (not empty(Q))
 Ack(Get(Q,TAIL)); ضβ
,ִлбʱֱõLIFOԺFIFO(first in first out).ϵԿһ.ڱִLIFOʽ,άֽСľ.ǨơFIFOʽ,Ǩߵϸ,Ҳ˵,Ӷͨŵıػ.Blumofeķ2ݱ,ڴģ̬м,ַʽܹýӽԵļٱ.
ıؾΪ()ʱ,ý.ַʽҲReceiver-Initiatedʽ(RI-).ؽе˷ٷĿ,,RIϵͳƽؽصܹЧؼٵȿ.3
Ĺ̾ٷĹ.ִи,ͱ֤һ౻ٷһ.
2ʵַ
ͨPVMAPIԿ,㷨PVMϵͳϼʵ.Ե˵,ǽӹPVM3ԭPVMSPAWN,PVMSENDPVMRECEIVE.ͼ2ʾ.

ͼ2
ϵͳµݽṹQͷϢQs.
ڽӹܺ3ԭ£
.PVMSPAWN
ϵͳӦó򷵻һʶID,Q;
.PVMSEND
鿴Q;
if (ĿѼ)
PVMϢԭзͣ
else if (Qs) {

ִбصȣ
}
else
Qs;
.PVMRECEIVE
鿴ؽϵĶQ;
if (ĿѼ)
PVMϢԭнգ
else {

ִбصȣ
}
3ܷ
ȵĿҪﵽƽ,Ӷ̲гʱ,øߵļٱ.,ͨԱPVMϵͳ۱ٷ䷽.
ͨʱ,Ӧón,ȷֱΪgi,i{1,...,n}.ϵͳmCPUվ,ֱΪcj,j{1,...,m}.
jִiӦʱΪtj(gi)=gicj.
PVMRound-RobinתַһԷ,ݳԭ,䵽ÿϵNj(j{1,...,m}ڣ֮.䵽񼯺ϵȿܴ,ʱܶ,ܱ֤ƽ.jз䵽NjʱΪTj,мٱSĽӦóʱ벢ִʱĽʱıֵ

зӲһ,ΪC.,мзϵԶԶʱ,ɵ,cfastcslowֱΪļ,lΪϵӦó֮.Կ,ȺϵͳϴȲʱ,PVMܻԶԶС1ٱ,Ҳ˵,ʱܲһе.
濴һ²ñ㷨ʱ.ȿ֤,ĽaʱTaĽbʱTb֮tslow(gmax),gmaxӦó,tslow(gmax)Ľgmaxʱ.
֤÷֤.覤tslow(gmax),򵱽aнʱ,bеĲһ(Ҳ˵,Qлδʼе),Ϊκxִʱtb(gx)Сڵtslow(gmax).㷨,ʱ,ab.ζŽaδн,ǰì.
Ľ۱֤˸ʱ䲻̫,Ӷʵ˸ƽ.
,Ӽٱ,Ľе񼯵Ӽ,ʱ䲻ᳬC.ۿɵã

Ҳ˵,,ʱһϴ൱.
ģʵ,ǽĵȷPVMԽϵıȽ.ʵģ»
(1) 4ĻȺϵͳ,ļıֵΪ4:2:2:1
(2) Ϊ,kʱ,kԽ,ʾļԽ,k=1ʾƽʱƽȣ
(3) пܴͨŻͬϵ,cͨϵ,cԽ,ͨԽǿ,c=1ʾ䶼ͨŹϵ,c=0֮.
ͼ3ΪģʵĲԽ,ͼÿһݵһζԱģ⣺ʾʹPVMȲԵʱñĵȷʱ֮.Ϊ,ʵͨŵʱӼϵͳĿ.

ͼ3
ͼпԿ,ʹñĵĵȷ߳Ĳ.,Կ,÷ͨŹϵϼ򵥡ƵȽϸߵӦó,ЧΪ.
4С
ԻȺϵͳмʵָƽ,һͿȷ.÷áԡִл,ڲӰ첢Եǰ¾ӳپʵִ,Աڲмжδִе·.ʵ,÷һ¿ԴﵽϺõ.,÷PVMϵͳʵ.
оõƼԤл
߽ܣǿ,1970,ʿ,ҪоΪд,ƽ⡣
֣γ,1946,,ʿʦ,ҪоΪ/ֲ.
ͨѶϵˣǿ, 100084,廪ѧѧ뼼ϵӦý
ߵλ:ǿ֣γ廪ѧѧ뼼ϵ100084
ο
1 Geist A, Beguelin A, Dongarra et al. PVM: Parallel Virtual Machine. Cambridge: The MIT Press, 1994. 119
2 Blumofe R D, Park D S. Scheduling large-scale parallel computations on networks of workstations. Technical Report, 
Massachusetts Institute of Technology, 1994. 14
3 Willebeek-Lemair H, Reeves A P. Strategies for dynamic load balancing on highly parallel computers. IEEE Transactions 
on Parallel and Distributed Systems, 1993,4(9):979993
1997-11-05յԭ,1998-01-23յ޸ĸ
