Utilization and Implementation of Dynamic Load Balancing Algorithms on Clusters of Computers.pdf

1、The cost effectiveness is an essential motivation to search for a low-cost high performance parallel computing platform,since the traditionally supercomputer is costly to buy and to use for scientific research or as an e

2、ducational tool to use for teaching the parallel and distributed computing.The rapid growth of the interconnected high performance workstations and PCs has produces a new computing paradigm called clustered of computers

3、model (cluster of workstations or cluster of PCs). In these systems,load balance problem is a serious impediment to achieve good performance.Load balancing involves assigning to each workstation of PC work that is propor

4、tional to its performance which minimizing the execution time of the program.For some of applications the assignment of tasks to the workstations or PCs can be done before the program execution.This strategy is called st

5、atic load balancing.This approach yields good performance and introduces no overhead.Static load balancing is definitely not suitable for irregular computations that generate unpredicable and imbalanced workload such as

6、the parallel tree computation which is generated by Depth-First search and Best-First search algorithms(DFS,BFS).To keep the workload of the tree computation blanced among the workstations or PCs during the run-time,we h

7、ave developed a distributed dynamic load balancing algorithm on the promising low-cost high performnace parallel platform computing.To study centralized and distributed dynamic load balancing algorithms we have built a d

8、istributed dynamic load balancing algorithm directly to the parallel tree application.We argued that,since the dynamic load balancing integrated within the application,there is a potential to optimize for the parallel tr

9、ee application.Our experimental work is based on the assumption that the workload of the tree computation generated by (DFS,BFS) is evolves is an ideal manner that increases consistently,followed by a consistent decrease

10、 in the total workload.Due to these phenomena the computation can be divided into distinct phases and each phase needs the dynamic load balancing algorithm.We also developed a parallel implementation of the centralized d

11、ynamic load balancing Master-Slave model.This model has been built directly for the Mandelbrot application which argues that the dynamic load balancing,when integrated within the application,may improve the performance o

12、f the application.Experimental work has been conducted on two separate clusters of computers,one is called a cluster of heterogeneous Sun workstations (COHW) and the second is a cluster of homogenous 10 Dell PCs(COPCs).T

13、he parallel programming model used in our clusters of computes (COHW and COPCs) is the massage passing which is consist the Massage Passing Interface (MPI) and Parallel Virtual Machine (PVM).These two libraries allow the

14、 parallel execution of the parallel tree application and the Mandelbrot application on COHW and COPCs.The operating systems of two cluster of computers model are UNIX(Solaris 2.5 and 2.6 versions) and Linux Red hat 7.0.T

15、he results of the experiments have shown that the performance of testdbed applications with different dynamic load balancing algorithms and different parallel platfom computing is significantly improved.The improvement o

16、f the performance of the applications is due to the efficient distributed dynamic load balancing algorithm,which could distribute the parallel application's tasks among the workstations or PCs as evenly as possible.The g

17、oal of the distribution workload is to maximize the load balancing and minimize the idle time for each workstation or PC involved in the computation.We have demonstrated the dynamic load balancing in COHW and COPCs as an

18、 approach to utilize the clusters of computers as an alternation to expensive parallel computers.The results have shown that high performance is possible on COHW and COPCs by a proper selection of the parallel algorithm

19、and the efficient implementation.An addition to the above mentioned points of the contribution of this dissertation to the current dynamic load balancing research are:(1)Defines a conceptual framework for dynamic load ba

20、lancing for the parallel tree computation and explored the concept of a three-phase workload for the parallel tree computation generated by the DFS and BFS algorithms based on clusters of workstations.(2)Investigated and