Dynamic load balancing based on restricted multicast tree in triplet-based hierarchical interconnection network

To solve the load balancing problem in a triplet-based hierarchical interconnection network (THIN) system, a dynamic load balancing (DLB) algorithm - THINDLBA, which adopts multicast tree (MT) technology to improve the efficiency of interchanging load information, is presented. To support the algorithm, a complete set of DLB messages and a schema of maintaining DLB information in each processing node are designed. The load migration request messages from the heavily loaded node (HLN) are spread along an MT whose root is the HLN. And the lightly loaded nodes (LLNs) covered by the MT are the candidate destinations of load migration; the load information interchanged between the LLNs and the HLN can be transmitted along the MT. So the HLN can migrate excess loads out as many as possible during a one time execution of the THINDLBA, and its load state can be improved as quickly as possible. To avoid wrongly transmitted or redundant DLB messages due to MT overlapping, the MT construction is restricted in the design of the THINDLBA. Through experiments, the effectiveness of four DLB algorithms are compared, and the results show that the THINDLBA can effectively decrease the time costs of THIN systems in dealing with large scale compute-intensive tasks more than others.