基三分层互连网络中负载平衡的研究与仿真

Study and Simulation of Load Balancing in Triplet-based Hierarchical Interconnection Network

体系结构和负载平衡策略是影响并行处理系统性能的两个重要因素。基三分层互连网络(THIN)是一种具有高可扩展性、高层次性和低网络复杂度的并行处理体系结构。针对THIN中的负载平衡问题,提出一种分布式控制、发送者驱动的动态负载平衡算法,该算法能够根据THIN的结构特点和负载失衡的实际情况,将负载迁移目标节点的搜索范围从低层THIN向高层THIN逐层扩展,并借助消息传递机制、向量负载指数和负载迁移因子提高负载平衡的效率和合理性。实验结果证明该算法能有效提高THIN系统处理计算密集型任务的性能。

Architecture and load balancing strategy are two important factors that influence the performance of parallel processing systems. Triplet-based hierarchical interconnection network (THIN) is a type of parallel processing architecture, which has high expansibility, good hierarchy characteristic and low network complexity. A distributed controlled and sender initiated dynamic load balancing algorithm was proposed aiming at the load balancing problem in THIN. According to the structure characteristics of THIN and the practical load unbalance situations, the proposed algorithm could expand the searching range of load migration destination from lower to higher level THIN in steps. And it made use of the message transferring mechanism, the vector load index and the load migration operator to improve the efficiency and rationality of load balancing. Experimental results show that the proposed algorithm can effectively improve the performance of THIN systems in dealing with great scale compute–intensive tasks.