《分布式与并行计算 课件英语论文 3kwong》由会员分享，可在线阅读，更多相关《分布式与并行计算 课件英语论文 3kwong（11页珍藏版）》请在金锄头文库上搜索。
1、Abstract In this paper we propose to use a duplication based approach in scheduling tasks to a heterogeneous cluster of PCs In duplication based scheduling criticaltasksareredundantly scheduled to more than one machine in order to reduce the number of inter task communication operations The start ti
2、mes of the succeeding tasks are also reduced The task duplication process is guided given the system heterogeneity in that the critical tasks are scheduled or replicated in faster machines The algorithm has been implemented in our prototype program parallelization tool for generating MPI code execut
3、able on a cluster of PentiumPCs Ourexperimentsusingthree numericalapplicationshaveindicatedthat heterogeneity of PC cluster being an inevitable feature isindeedusefulforoptimizingthe execution of parallel programs Keywords Scheduling task graphs algorithms parallel processing heterogeneous systems P
4、C clustercomputing taskduplication resource management 1 Introduction Recently we have witnessed an increasing interest in employing a network of PCs connected byahigh speednetworktotacklemany computationally intensive parallel applications 9 18 Parallelprocessingusingaclusterof machines alsocommonl
5、ycalledclustercomputing enablesamuchlargercommunityofusersthanever beforetoefficientlytacklemanydifficult optimization problems on a readily available platform 9 18 However realizing the goal of efficient cluster computing entails handling a number of resource management chores 18 One of the most im
6、portant problems is the scheduling of tasks Indeed to effectively harness the aggregate computingpowerofsuchaheterogeneouscluster it is crucial to judiciously allocate and sequence the tasks on the machines In a broad sense the scheduling problem exists in two forms dynamic and static In dynamic sch
7、eduling few assumptions about the parallel program can be made before execution and thus scheduling decisions have to be made on the fly The goal of a dynamic scheduling algorithm as such includes not only the minimization of the program completion time but also the minimization of scheduling overhe
8、ad which represents a significant portion of the cost paid for running the scheduler In a cluster of PCs environment such dynamic scheduling algorithms usually employ the so called idle cycle stealing approach 5 whichattemptstodynamically balance the work load evenly across all the machines However
9、whentheobjectiveof scheduling is to minimize the execution time of a parallel application such dynamic scheduling strategies are not suitable On the other hand the approach of using static scheduling algorithms 11 12 22 which can afford to use longer time to generate an optimized schedule off line i
10、s particularly effective for many scientificapplicationssuchastheadaptive simulation of N body problem object recognition using iterative image processing algorithms and This research was jointly supported by a research initia tion grant from HKU CRCG under contract number 10202518 a research grant
11、from the Hong Kong Research Grants Council under contract number HKU 7124 99E and a seed funding grant from HKU URC under contract number 10203010 Parallel Program Execution on a Heterogeneous PC Cluster Using Task Duplication YU KWONGKWOK Department of Electrical and Electronic Engineering The Univ
12、ersity of Hong Kong Pokfulam Road Hong Kong Email ykwok eee hku hk 0 7695 0556 2 00 10 00 2000 IEEE some other numerical applications 1 3 4 13 14 19 25 because the characteristics of such applications can be determined at compile time Aparallelprogram therefore canbe represented by a directed acycli
13、c task graph 3 in which the node weights represent task processing timesandtheedgeweightsrepresentdata dependencies as well as the communication times between tasks 3 6 The static scheduling problem is in general NP complete 5 8 and there have been many heuristics suggested in the literatureforsched
14、ulingaparallelmachine However the problem of scheduling tasks to a clusterisarelativelylessexploredtopic Specifically there are two difficult research issues to be tackled in the scheduling problem for cluster computing 1 Communicationoverhead The communication overhead in a network of PCs is still
15、very signifi cant relative to the processing power of the machines 9 Thus toavoidoffsettingthegainfrom parallelization by excessive communication overhead the tasks should be scheduled in suchamannerthatthenumberof communications is kept small 2 Heterogeneity InaPCcluster which typically undergoes c
16、ontinual upgrading heterogeneity in the hardware confi guration is unavoidable Heterogeneity can be a potential problem for some highly regular applications e g somedataparallel problems However ithasbeen demonstrated that heterogeneity is useful for furtherenhancingtheperformanceof irregularly structured parallel application 7 21 by exploiting the affi nity of different tasks to different machines In this study we propose to use a duplication approach to scheduling the tasks to the cluster In d
