当前位置：文档库 › Abstract Efficient Load Balancing for Wide-Area Divide-and-Conquer Applications

Abstract Efficient Load Balancing for Wide-Area Divide-and-Conquer Applications

Ef?cient Load Balancing for Wide-Area Divide-and-Conquer Applications

Keywords:work stealing,clustered wide-area systems,Java,DAS

Rob V.van Nieuwpoort,Thilo Kielmann,Henri E.Bal Faculty of Sciences,Vrije Universiteit,Amsterdam,The Netherlands

rob,kielmann,bal@cs.vu.nl

Abstract

Divide-and-conquer programs can be automatically parallelized by letting the programmer annotate poten-tial parallelism in form of spawn and sync constructs. To achieve ef?cient program execution,however,the generated work load has to be balanced ef?ently among the available CPUs.For homogeneous(single clus-ter)systems,random work stealing(RWS)is known to achieve optimal load balancing.However,RWS is inef?cient when applied to hierarchical wide-area sys-tems where multiple clusters are connected via wide-area networks(W ANs)with high latency and low band-width.

In this paper we compare RWS with three existing load balancing strategies that are believed to be ef?-cient for multi-cluster systems,but in practice gain at best mediocre results.We introduce a new load bal-ancing algorithm,Cluster-aware Random Work Steal-ing(CRWS).We show that CRWS is highly ef?cient and easy to implement.CRWS adapts itself to net-work conditions and job granularities.Although CRWS sends much more data across the W ANs,it outperforms its competitors for11out of12test applications with various W AN scenarios.

1Introduction

Meta-computing platforms as used,for example,in computational grids are hierarchically structured.Mul-tiple supercomputers or clusters of workstations are connected via wide-area links,forming systems with a two level hierarchy.A third hierarchy level is added when multiple clusters of SMPs are connected. When running parallel applications on top of such multi-cluster systems,ef?cient execution can only be achieved when the hierarchical platform structure is carefully taken into account.In previous work,we demonstrated that various kinds of parallel applications can indeed be ef?ciently executed on wide-area systems [13,16].However,applications have to be optimized individually in order to reduce the utilization of the scarce wide-area bandwidth or to hide the large wide-area latencies.We extracted some of these optimiza-tions into speci?c runtime systems like MPI’s collective communication operations(the MagPIe library)[8],or our Java-based object replication mechanism RepMI [10].In general,however,it is hard for a programmer to manually optimize parallel applications for hierarchical wide-area systems.

The ultimate goal of our work is to create a pro-gramming environment in which parallel applications for hierarchical systems are easy to implement.The divide-and-conquer model lends itself well for hierar-chically structured platforms because tasks are created by recursive subdivision.This leads to a hierarchically structured task graph which can be implemented with excellent communication locality,especially on hierar-chical platforms.Of course,there are many kinds of problems that can not be implemented by a divide-and-conquer algorithm.However,we believe the class of divide-and-conquer algorithms to be suf?ciently large to justify its deployment for programming hierarchical wide-area systems.

Throughout this paper we use our Satin system [15],which has been designed for running divide-and-conquer programs on distributed-memory architectures, targeting at hierarchical wide-area systems.Satin’s pro-gramming model has been inspired by the C-based Cilk system[4].Satin extends the Java language with three simple primitives for divide and conquer programming: spawn,sync,and satin.Figure1shows how Satin’s an-notations can be used for implementing a parallel pro-gram to compute the Fibonacci numbers.The Satin compiler and runtime system cooperate to implement these primitives ef?ciently on a hierarchical wide-area

system.Thus,speci?c wide-area optimizations in the application code can be avoided.

We have implemented Satin by extending the Manta native Java compiler[11].In total?ve load balancing algorithms were implemented in the same runtime sys-tem,in order to investigate their behavior on hierarchi-cal wide-area systems.Random work stealing,as used in single-cluster environments,does not perform well on wide area systems.We found that hierarchical load balancing,as proposed for example by the Atlas project [2],performs even worse for?ne-grained applications. Hierarchical load balancing does send as few messages as possible over the wide area links.However,we show that a novel algorithm we implemented,Cluster-aware Random Work Stealing(CRWS),achieves good speedups,for a large range of bandwidths and latencies. We tested latencies up to100milliseconds,and band-widths down to100KBytes/s.Our results are counter intuitive,because CRWS sends many more messages than previously known load balancing methods,while obtaining better speedups.We also compare CRWS with two other algorithms,Random Work Pushing and Cluster-aware Load-based Work Stealing.Both ap-proaches are believed to obtain ef?cient execution on multi-cluster systems.We show,however,that CRWS outperforms both in almost all test cases.

We discuss the performance of the?ve load-balancing algorithms using twelve applications that run on four Myrinet-based clusters,connected by wide-area links,the DAS system.1We also describe the impact of different bandwidth and latency parameters.

The remainder of the paper is structured as follows. Section2brie?y introduces the Satin system.In Sec-tions3and4,we present the?ve load balancing al-gorithms,and their performance with twelve example applications.Section5discusses related approaches. Section6concludes our work.

2The Satin System

Satin’s programming model is an extension of the single-threaded Java model.To achieve parallel exe-cution,Satin programs do not need to use Java’s multi threading,or the Remote Method Invocation mecha-nism.Instead,they can use the much simpler divide-and-conquer primitives.Additionally,Satin provides shared objects via Manta’s object replication mecha-nism,RepMI[10].class Fibonacci{

SATIN int fib(int n){

if(n<2)return n;

int x=SPAWN fib(n-1);

int y=SPAWN fib(n-2);

SYNC;

return x+y;

}

public static void main(String[]args){

Fibonacci f=new Fibonacci();

int result= f.fib(10);

System.out.println("Fib10="+result);

}

minimize the overhead for work done locally.Because copying all parameter objects(i.e.,using call-by-value) in the local case would be prohibitively expensive,pa-rameters are passed by reference when the method in-vocation is local.Therefore,the Satin programmer can neither assume call-by-value nor call-by-reference se-mantics for satin methods.Normal methods are un-affected and keep the standard Java semantics.

With these parameter semantics,Satin methods can be implemented very ef?ciently.Whenever a method is spawned,only its invocation record(containing refer-ences to the parameter objects)is inserted into the local work queue.In the case of local execution,the param-eters are used call-by-reference.In the case of remote execution,the parameters are actually copied and seri-alized to the remote machine,resulting in call-by-value semantics.A detailed description of Satin’s implemen-tation can be found in[15].

3Load Balancing in Wide-Area Systems

We now discuss the?ve load balancing algorithms we implemented in Satin’s runtime system.They all use a double-ended work queue,containing the invocation records of the jobs that were spawned but not yet exe-cuted.Divide-and-conquer programs progress by split-ting their work into smaller pieces.In Satin,the jobs are inserted at the head of the queue.Each proces-sor fetches work from the head of its own queue.This scheme ensures that the most?ne-grained jobs run lo-cally,while the jobs at the tail of the queue are the most coarse grained ones available.They are ideal candidates for load balancing purposes.All algorithms described here use the jobs at the tail of the queue for balancing the work load.

We have chosen the?ve implemented load balancing algorithms because they span the spectrum of possible design alternatives.Properties of the implemented algo-rithms are summarized in Table1.Shivaratri et al.[14] give an excellent overview of load balancing algorithms in locally distributed systems.

3.1Random Work Stealing(RWS) Random work stealing is a well known load-balancing algorithm,used both in shared-memory and distributed-memory systems.In RWS,when a processor?nds its

own work queue empty,it attempts to steal a job from a randomly selected peer,repeating steal attempts un-til it succeeds.RWS is provably ef?cient in terms of time,space,and communication for the class of fully strict computations[5,19];divide-and-conquer algo-rithms belong to this class.An advantage of random work stealing is that the algorithm is stable:Commu-nication is only initiated when nodes are idle.When the system load is high,no communication is needed, causing the system to behave well under high loads.

On a single-cluster system,random work stealing is, as expected,Satin’s best performing load-balancing al-gorithm.On wide-area systems,however,this is not the case.With clusters,in average of all steal requests will go to a node in a remote cluster,forcing the stealing processor(the“thief”)to wait a wide-area round-trip latency for a result,while there may be work available inside the local cluster.With four clusters,this already affects75%of all steal requests.Also,when the jobs are large,the limited wide-area bandwidth be-comes a bottleneck.

3.2Random Work Pushing(RWP) Random work pushing also is a well known load bal-ancing algorithm.In RWP a processor checks,after in-sertion of a job,whether the queue length exceeds a cer-tain threshold value.If this is the case,a job from the queue’s tail is pushed to a randomly chosen peer proces-sor.One might expect RWP to work well in a wide-area setting,because its communication is asynchronous and thus less sensitive to high wide-area latencies than work stealing.A problem with RWP,however,is that the algorithm is not stable.Under high work loads,pro-cessing the pushing messages causes useless overhead, because all nodes already have work.

Also,with clusters,in average of the pushed jobs will be sent across the wide-area net-work,causing bandwidth problems.Unlike random work stealing,random work pushing does not adapt to bandwidth and latency because it lacks a bound for the number of messages that may be sent,i.e.there is no inherent?ow control mechanism.Finally,the thresh-old value must be found that speci?es when jobs will be pushed away.A single threshold value is not likely to be optimal for all applications,or not even for one application with different wide-area bandwidths and la-tencies.

Table1:Properties of the Implemented Load Balancing Algorithms.

algorithm uses heuristics asynchronous

Random Work Stealing no no

sender no no Cluster Aware Hierarchical Work Stealing no no

receiver no yes Cluster Aware Random Work Stealing no only wide-area

can continue computing while the message is in transit. This allows to hide the possibly high wide-area latency. The amount of prefetching(and thus the amount of wide-area communication)may be adjusted by tuning the load threshold for wide-area stealing.A value of’1’initiates inter-cluster communication only when there are no jobs left in the local cluster.This minimizes the number of wide area messages,at the cost of load im-balance.This compares to hierarchical work stealing,

which also waits until the entire cluster becomes idle, before sending wide-area steal messages.One impor-tant difference is that with hierarchical work stealing, the entire cluster is traversed sequentially,while in the load-based approach,the idle nodes immediately con-tact their coordinator node.

3.5Cluster-aware Random Work Stealing

(CRWS)

Cluster-aware random work stealing is a novel load-balancing algorithm,designed for hierarchical wide-area systems.The idea is straightforward:just do ran-dom work stealing,but when the victim is located in a remote cluster,try to do something useful until the reply arrives.The implementation is also simple,the algorithm simply selects a victim at random.When the victim is located within the local cluster,a normal,syn-chronous work-stealing attempt is performed.When the victim resides in a remote cluster,however,an asyn-chronous message is sent across the wide-area network. While waiting for the result to arrive,the thief issues additional,cluster-local steal attempts.Per node,there is at most one wide-area steal attempt in progress at any point in https://www.wendangku.net/doc/e817245473.html,pared to RWS,this signi?cantly re-duces the number of messages sent across the wide-area network.CRWS has the advantages of random work stealing,but hides the wide-area roundtrip time by ad-ditional,local stealing.The?rst job to arrive will be executed.No extra load messages are needed,and no parameters have to be tuned.Pseudo code for the new algorithm is shown in3.On one cluster,CRWS is iden-tical to RWS.

4Performance Evaluation

We evaluated Satin’s performance using12application kernels.All measurements were performed on a clus-ter of the Distributed ASCI Supercomputer(DAS),con-taining200MHz Pentium Pros running Linux that are

Figure3:Pseudo code for Cluster-aware Random Work Stealing.

connected by Myrinet.Our results have been measured on a real parallel machine;only the wide-area links are simulated over some of the Myrinet links by letting the communication subsystem insert delay loops into mes-sage delivery.

The run times of the twelve application kernels is shown in Figure4,for all?ve load-balancing algo-rithms we described.The?rst(white)bar in each graph is the run time on a single cluster of64nodes(e.g.with-out wide-area links).The following four bars indicate runs on four clusters of16nodes each,with different wide-area bandwidths and latencies in between.Ma-trix multiplication is the only application that does not perform well,because it sends very much data.The ap-plication already has scaling problems on one cluster: the speedup on64nodes is only25.On multiple clus-ters,CLWS performs best for matrix multiplication,but even then,the speedup is only11on four clusters with a latency of10milliseconds,and a throughput of one MByte/s.We conclude that Matrix multiplication is not very well suited for wide-area systems.

The performance of randon work stealing(RWS) degrades considerably when wide-area latencies and bandwidths are introduced,because75%of all steal messages are now sent to remote clusters.

Random work pushing(RWP)shows varying per-formance.Its results shown in Figure4use threshold values that were manually optimized for each applica-tion separately.For some applications(i.e.adaptive integration,knapsack and prime factors),RWP outper-forms random work stealing with high wide-area la-tencies,which is due to asynchronous communication. For the other applications,however,it performs worse than RWS.Moreover,our results indicate that one sin-gle threshold value(specifying which jobs will be exe-cuted locally,and which ones will be pushed away)is 5

not optimal for all cluster con?gurations.

The cluster-aware hierarchical work stealing (CHWS)algorithm sends the fewest messages over the wide-area network.However,this comes at the cost of some load imbalance,which is visible in the run time graphs:for all applications,RWS outperforms CHWS. As with RWP,the results for cluster-aware load-based work stealing(CLWS)in Figure4use manually optimized threshold values.CLWS sends more mes-sages over the wide-area network than CHWS,but per-forms much better,because it prefetches work from re-mote clusters when the cluster load drops below the threshold.We found that one threshold was suf?cient for all cluster con?gurations.

Our novel load balancing algorithm,cluster-aware random work stealing(CRWS)performs best for all ap-plications except matrix multiplication.This is counter intuitive,because it sends more wide-area messages than CHWS and CLWS(but far less than RWS and RWP).The CRWS algorithm is very simple to imple-ment,and does not require parameter tuning,yet it out-performs the other load balancing schemes for eleven out of twelve applications.The results show that these eleven applications have within95%of the performance of a single,large Myrinet cluster,even with wide-area bandwidths of100KBytes/s and latencies of100mil-liseconds.

5Related Work

We have discussed load balancing in Satin,a divide-and-conquer extension of Java.Satin has been designed for wide-area systems,without shared memory.The Java classes presented in[9]can also be used for divide and conquer algorithms.However,they are restricted to shared-memory systems.

Most other divide-and-conquer systems are based on the C language.Among them,Cilk[4]only supports shared-memory machines,CilkNOW[3]and DCPAR[7]run on local-area,distributed-memory systems,however without support for shared data. SilkRoad[12]is a version of Cilk for distributed mem-ory that uses a software DSM to provide shared mem-ory to the programmer,targeting at small-scale,local-area systems.Alice[6]and Flagship[18]offer speci?c hardware solutions for parallel divide-and-conquer pro-grams.Satin is purely software based,and does not require,or provide,a single address space.Instead,it uses Manta’s object replication mechanism to provided

shared objects.Another(hierarchical)parallel divide-and-conquer system is HyperM[17].Here,a single primitive,called the sandwich annotation,was used to indicate parallelism in a functional language.

Another divide-and-conquer system based on Java is Atlas[2].Atlas is not a Java extension,but a set of Java classes that can be used to write divide-and-conquer programs.Like Satin,Atlas is designed for wide-area systems.While Satin is targeted at ef?ciency,Atlas was designed with heterogeneity and fault tolerance in mind.Atlas uses a hierarchical scheduling algorithm, while we found that Cluster-aware Random Work Steal-ing performs better.

Backschat et al.[1]describe a form of hierarchical scheduling for a system called Dynasty,which targets at large workstation networks.The algorithm is based on economic principles,and requires intensive param-eter tuning.However,the best performing,wide-area load-balancing method in Satin is not hierarchical,and requires no parameter tuning.It is hence much simpler to implement and achieves better performance.

6Conclusions

We have described our experience with?ve load bal-ancing algorithms for parallel divide-and-conquer ap-plications on hierarchical wide-area systems.Our ex-perimentation platform is Satin which builds on the Manta high-performance Java system,running on our DAS cluster https://www.wendangku.net/doc/e817245473.html,ing12example applica-tions,we have shown that the traditional load balanc-ing algorithm from shared-memory systems and work-station networks,random work stealing,achieves only mediocre results in a wide-area setting.

We have demonstrated that hierarchical work steal-ing,proposed in the literature for load balancing in wide-area systems,performs even worse than random work stealing for?ne-grained applications.Two other alternatives,random work pushing and load-based work stealing,only work well after careful,application-speci?c,tuning of their respective threshold values.

We introduced a novel load balancing algorithm, called Cluster-aware Random Work Stealing.With this new algorithm,11out of12applications achieve a per-formance which is within95%of a large single-cluster system,while running on a wide-area system combin-ing four small clusters.