并行扫描计算的局部调度方法

A Local Scheduling Method for Parallel Computing Scan

使用确定论方法并行求解输运方程需要通过并行扫描计算完成,局部调度方法是实现高效并行扫描计算的关键,而传统的调度问题是NP完全问题,是并行计算领域的难点之一。文中对多离散方向并行扫描计算给出了明确的描述,给出了对局部调度方法的性能要求,对并行扫描计算的调度问题和传统调度问题的区别进行了分析。设计了一种基于任务优先级的局部调度方法,利用相邻处理机任务间依赖信息,结合并行扫描计算的一般计算框架,在机群系统上进行了性能测试,测试结果表明文中设计的调度方法具有良好的并行计算加速效果。

Paralllel computing scan method is used to solve the particle transport equations on parallel computers by the discrete ordinate(Sn) method on the unstructured grids.Parallel computing scan problem belongs to the precedence constrained scheduling problem which is NP-complete,and it is a hard work in the f ield of parallel computing.This paper gives the specific definition of parallel computing scan along many sweep directions,the demands for the local scheduling method and the differences between the parallel sweep scheduling problem and the traditinal scheduling problem.Then,based on the task priority ordering,a local scheduling method is designed,which using the dependent informantion of tasks among the neighboring processors.Combined with the parallel algorithm frame of sweep computation,the local scheduling method is tested on the cluster.Performance results show that the method has better parallel performance.