Customized Dynamic Load Balancing for a Network of WorkstationsSlide 2Dynamic Load Balancing StrategiesSlide 4Slide 5Strategy TradeoffsDLB Modeling & Decision ProcessDLB Modeling & Decision Process (cont.)Slide 9Slide 10ExperimentSlide 12Modeling ResultsConclusionsCustomized Dynamic Load Balancing for a Network of WorkstationsTaken from work done by:Mohammed Javeed Zaki, Wei Li, Srinivasan ParthasarathyComputer Science Department, University of RochesterJune 1997Presenter:Jacqueline EwellStatic vs. Dynamic Load Balancing Static Load Balancing:• allows the programmer to delegate work before runtime• can accommodate for heterogeneous processor and non-uniform loops• avoids runtime scheduling overheads• needs to know all information about Workstations ahead of timeDynamic Load Balancing:• ability to delegate work based on runtime performance of a Network of Workstations (NOW)• transient external loads by multiple-users, heterogeneous processors, memory availability, network bandwidths and contentions, and software leads to a more logical choice of dynamic load balancingDynamic Load Balancing Strategies• Task Queue Model: a centralized queue of work• Diffusion Model: • all work is delegated to each processor, • when an imbalance is detected between it and its neighbor, work is moved • Predict future performance from past performance: Exchange of performance information • Global Distributed Scheme• Global Centralized Scheme• Local Distributed Scheme• Local Centralized SchemeWork queueLocal GlobalDistributedCentralizedDynamic Load Balancing StrategiesGlobal - all load balancing is done on a global scaleCentralized - the load balancer is located on one processorLocal - processors are divided into groups (size = K) and load balancing decisions are done within a groupDistributed - the load balancer is replicated on every processorDynamic Load Balancing StrategiesGlobal CentralizedLoad BalancerP1 P2 P3 Pn...Global DistributedLocal DistributedP1P2 P3 Pn...Load BalancerLoad BalancerLoad BalancerLoad BalancerLocal CentralizedLoad BalancerP1 P2 P3Pn...P4G1G2Pn...Load BalancerP3Load BalancerP3Load BalancerP1 P2Load BalancerLoad BalancerG1G2Strategy TradeoffsGlobal vs. Local• Global information is available at synchronization time; therefore work distribution is optimal• Global scheme - synchronization and communication cost is much higher• Local scheme - groups may sit idle while other groups are overloaded Centralized vs. Distributed• Centralized scheme - one load balancer will hurt scalability• Centralized scheme - distribution calculations are on one processor; therefore, done sequentially• Distributed - “all-to-all” exchange of performance profile; therefore, network contention could be a problemDLB Modeling & Decision ProcessModeling Parameters:• number of processors• normalized processor speed• number of neighbors• data size• number of loop iterations• work per iteration• # of bytes to be comm./iteration• time per iteration• network latency & bandwidth• network topology• maximum load• duration of persistence of loadProcessorParametersProgramParametersNetworkParametersExternal LoadModelingDLB Modeling & Decision Process (cont.)Total DLB Cost: Synchronization Cost + Cost of Calculating New Distribution +Cost of Sending Instructions* +Cost of Data Movement*only applies to centralized schemesDLB Modeling & Decision Process (cont.)Synchronization Cost:• GCDLB: one-to-all(P) + all-to-one(P)• GDDLB: one-to-all(P) + all-to-all(P )• LCDLB: one-to-all(K) + all-to-one(K)• LDDLB: one-to-all(K) + all-to-all(K )22Cost of Calculating New Distribution: Usually very smallCost of Sending Instructions: Number of send Messages * LatencyCost of Data Movement: Number of Message * Latency +Number of Iterations Moved *Number of Bytes that need to be communicated per iteration /BandwidthDLB Modeling & Decision Process (cont.)Initially: work will be divided equally among all processorsSynchronization: 1/Pth work has been done load function is known average effective speed is knowPerformance Metric: (number of iteration per second)load function and other parameters are plugged into the model to select the beststrategyWork Movement: if amount of work to be moved is above a thresholdProfitability Analysis - move work only if there is a 10% improvement in execution timeExperiment• Global Schemes are best ; computation/communication ratio is high • More Processors -> More Synchronization Cost ; favors Local Scheme• Global is still better at 16-processors• Centralized master, sequential redistribution, instruction sends, and delay factors add sufficient overheads to Centralized schemeExperiment• Amount of work/iteration is small; Local Distributed is favored• As data size increases; Global Distributed does better• On 16-processors, Local Distributed is the best • Local is better than Global; since computation/comm. Ratio is small• Distributed is better than CentralizedModeling ResultsConclusions• Different Schemes are best for different applications• Customized Dynamic Load Balancing is essential when transient external loads are introduced• Given the model, it is possible to select a good scheduling schemeFuture Work• Other Dynamic Load Balancing Schemes need to be incorporate into the model (not lying on the extremes)• Instead of Local Central, have one master per group• Local schemes, work should be exchanged between different groups• Dynamic Group