The study on the static and dynamic load balancing algorithms has a history over three decades and it is stilla promising field. But because of the uncertainties between the dependencies of the parallel tasks and thei...The study on the static and dynamic load balancing algorithms has a history over three decades and it is stilla promising field. But because of the uncertainties between the dependencies of the parallel tasks and their communi-cation during the compile-time, researchers are more inclined to study the dynamic load balancing algorithms(DLB).There are almost four kinds of DLB algorithms including the centralized DLB, distributed DLB, global DLB and LocalDLB, all of them have their pros and cons. This paper addresses a new dynamic load balancing model based on theMain Load Information Table (MLIT) and its dynamic load balancing algorithm, it not only has the advantages thefour models above mentioned have, but it overcomes some of their disadvantages which lead to a poor performance,thus it boasts a better stability and security and in the end it can improve the performance of the system.展开更多
A new static task scheduling algorithm named edge-zeroing based on dynamic critical paths is proposed. The main ideas of the algorithm are as follows: firstly suppose that all of the tasks are in different clusters; s...A new static task scheduling algorithm named edge-zeroing based on dynamic critical paths is proposed. The main ideas of the algorithm are as follows: firstly suppose that all of the tasks are in different clusters; secondly, select one of the critical paths of the partially clustered directed acyclic graph; thirdly, try to zero one of graph communication edges; fourthly, repeat above three processes until all edges are zeroed; finally, check the generated clusters to see if some of them can be further merged without increasing the parallel time. Comparisons of the previous algorithms with edge-zeroing based on dynamic critical paths show that the new algorithm has not only a low complexity but also a desired performance comparable or even better on average to much higher complexity heuristic algorithms.展开更多
文摘The study on the static and dynamic load balancing algorithms has a history over three decades and it is stilla promising field. But because of the uncertainties between the dependencies of the parallel tasks and their communi-cation during the compile-time, researchers are more inclined to study the dynamic load balancing algorithms(DLB).There are almost four kinds of DLB algorithms including the centralized DLB, distributed DLB, global DLB and LocalDLB, all of them have their pros and cons. This paper addresses a new dynamic load balancing model based on theMain Load Information Table (MLIT) and its dynamic load balancing algorithm, it not only has the advantages thefour models above mentioned have, but it overcomes some of their disadvantages which lead to a poor performance,thus it boasts a better stability and security and in the end it can improve the performance of the system.
文摘A new static task scheduling algorithm named edge-zeroing based on dynamic critical paths is proposed. The main ideas of the algorithm are as follows: firstly suppose that all of the tasks are in different clusters; secondly, select one of the critical paths of the partially clustered directed acyclic graph; thirdly, try to zero one of graph communication edges; fourthly, repeat above three processes until all edges are zeroed; finally, check the generated clusters to see if some of them can be further merged without increasing the parallel time. Comparisons of the previous algorithms with edge-zeroing based on dynamic critical paths show that the new algorithm has not only a low complexity but also a desired performance comparable or even better on average to much higher complexity heuristic algorithms.
