基于反馈的片上多处理器系统层次负载平衡算法  

Hierarchical Load Balance Algorithm Based on Feedback in Chip Multiprocessors System

作　　者：王鹏[1] 董渭清[1] 王甜[1] 

机构地区：[1]西安交通大学计算机科学与技术系,西安710049

出　　处：《西安交通大学学报》2008年第2期179-183,共5页Journal of Xi'an Jiaotong University

摘　　要：针对现有负载平衡算法未能有效利用片上多处理器系统线程级并行性,没有考虑线程间数据共享与通信以及产生颠簸等问题,提出了一种基于反馈的层次负载平衡算法.采用层次式调度,将属于同一进程的多个线程静态调度到特定规模的内核子集上,并在此基础上根据系统实时负载情况在特定内核子集内动态迁移线程,以降低同一进程的多个线程之间的通信代价.在线程迁移过程中,引入反馈机制,即以系统颠簸情况为反馈信息,实时调整迁移数目,最终使系统较快地达到平衡.实验表明,基于反馈的层次负载平衡算法能使系统的平衡程度达到较高的水平,引入的反馈机制可使系统平衡速度提高28%,并在系统平衡前使'颠簸'数目减少54%.Focusing on the problem that existing load balance algorithms failed to make full use of chip multiprocessors （CMP） system＇s thread level parallelism （TLP） and did not take data sharing, communication, and excessive transformation among threads into account, a hierarchical load balance algorithm based on feedback is proposed. Hierarchical schedule algorithm is adopted in order to reduce the cost of communication. Thus, threads of the same process are assigned into the same set of cores and then migrated into the range of its assigned core set dynamically. Feedback is used during the migration of threads according to the number of excessive transformation that could be computed through information feedback mechanism. The experiment shows that the algorithm is capable of achieving high balancing degree. Moreover, the balancing speed of hierarchical load balance methods with feedback mechanism is increased by 28%, and the excessive transformation is reduced by 54%.

关 键 词：片上多处理器 多线程 负载平衡 反馈 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]