一种并行扫描计算局部调度算法

An Local Scheduling Algorithm of Parallel Sweep

为了解决优先级调度算法的可扩展性问题,本文设计并实现了一种局部的深度优先扫描算法(PDFHDS)。该算法在计算初始优先级和计算最终优先级时,对每个结点只遍历一次,在这一次遍历中只访问该结点的全部直接前驱,避免了在PDFDS算法中每修改一个结点的优先级就要访问其全部前驱结点的情况,减少了一部分计算开销,消息传递过程使用单向传递,只向前邻处理器传递有多级外部后继的网格点信息,而不传递只具有一级外部后继的网格点信息,节省了通信开销。从实验数据可知,虽然在处理器个数少的时候性能比不上DFHDS算法,但对于多处理器的情况,PDFDS算法的性能可以比DFHDS算法的提高50%,甚至更多。

This paper designs and impletments a priority algorithm （PDFHDS） based on DFHDS algorithm to solve the scalability problem of scheduling algorithm. PDFHDS visits a grid only once when priority computing. During the visit, algorithm visits not all the ancestor but fathers of this grid, this saved cost of computing. Also, we send a message to neighbor processors only when this message has a son in another processor and the son has descendant in more another processor. The test results show that PDFHDS algorithm has the worser performance than DFHDS algorithm on smaller number of processors, while the performance of PDFHDS is improved 50% higher than that of DFHDS on the larger＇ number of processors.