并行分治计算中的一种Work-stealing策略  

Hierarchical Work-stealing Strategy for Parallel Divide-and-conquer Computation

作　　者：杨际祥[1,2] 谭国真[1] 王荣生[2] 江德[1] 

机构地区：[1]大连理工大学计算机科学与工程系,辽宁大连116024 [2]燕山大学计算机科学与工程系,河北秦皇岛066004

出　　处：《小型微型计算机系统》2010年第3期408-412,共5页Journal of Chinese Computer Systems

基　　金：国家"九七三"重点基础研究发展规划项目(2005CB321904)资助;河北省科学研究计划项目(2007492)资助

摘　　要：在机群尤其是共享式多用户机群环境中提高非规则问题的并行计算效率是一项具有挑战性的工作.给出了一种适于多核处理器节点构成的机群的层次Work-stealing负载均衡策略(简称HWS),它能够有效利用节点的动态变化的可用计算资源.分析了分治计算问题中的动态性与非规则性,并使用HWS策略对分治计算问题进行了动态负载均衡(DLB)实验.实验表明,HWS在加速比、CPU利用率和负载分布等性能指标上均优于Work-sharing和Satin-CRS策略.It is a challenging problem for solving non-uniform problems to improve the efficiency of parallel computing in PC cluster system,especially in non-dedicated and multi-user cluster environment,among which dynamic load balancing（DLB） is essential for the efficient use of parallel systems.A hierarchical work-stealing strategy for load balancing is proposed for PC clusters based on multi-core processors,which can make the most of available resources,even if such availability will change dynamically.Some dynamic and non-uniform characteristics of divide-and-conquer computation are discussed,and experiments with scheduling divide-and-conquer programs by work-stealing strategy for load balancing are carried out.Experimental results are provided,and the results show that HWS outperforms work-sharing and Statin-CRS algorithms in a number of performance metrics such as speedup,CPU utilization,load distribution and so on.

关 键 词：动态负载均衡(DLB) 层次Work-stealing策略(HWS) 多核 分治法(D&C) 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]