有向图并行计算中一种新的结点调度算法

作     者：张爱清 莫则尧 ZHANG Ai-Qing;MO Ze-Yao

作者机构：北京应用物理与计算数学研究所高性能计算中心北京100094 

基　　金：国家"九七三"重点基础研究发展规划项目基金(2005CB321702) 国家自然科学基金(60533020 60603050 90718029)资助 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2009年第32卷第11期

页      码：2178-2186页

摘      要：在基于有向图的并行计算中,给定图剖分后,如何设计结点调度方案使得并行执行时间最短,是典型的NP完全问题.针对此问题,文中提出一种新的基于顺逆交替迭代技术的启发式调度算法,并给出该算法的并行实现.严格的理论推导证明,新算法在一定的假设条件下,从任何初始调度方案出发,均可以单调收敛.在数百个处理器上的并行数值实验表明,与常用的调度算法相比,新算法可在付出很少的开销代价下显著提高整体并行效率.

主 题 词：有向图 并行计算 结点调度算法 顺逆交替迭代技术 

学科分类：0810[工学-土木类] 0808[工学-自动化类] 0839[0839] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.3724/SP.J.1016.2009.02178

馆 藏 号：203140928...