基于多层k路划分的三维网格并行任务分配策略  

Parallel task distribution strategy in 3D mesh based on multilevel k-way partitioning

作　　者：于方[1,2] 郑晓薇[1] 孙晓鹏[1] 

机构地区：[1]辽宁师范大学计算机与信息技术学院,辽宁大连116029 [2]包头师范学院信息科学与技术学院,内蒙古包头014030

出　　处：《计算机工程与设计》2010年第2期287-290,294,共5页Computer Engineering and Design

基　　金：辽宁省教育厅高等学校科研基金项目(05L209);浙江大学CAD&CG国家重点实验室基金项目(A0602);辽宁省智能信息处理重点实验室基金项目(2006-2)

摘　　要：为解决传统任务划分方法在三维网格并行计算任务分配阶段产生的通信开销大的问题,提出了一种基于多层k路划分算法的并行任务分配策略。首先利用多层k路划分算法划分三维网格,将任务划分问题转化为图划分问题,然后基于图划分结果给出一个任务映射并行算法将计算任务分配到各计算结点。在深腾1800上求解三维网格模型最短路径问题的实验结果表明,相比于传统的行列划分任务分配策略,该策略在保证负载平衡的同时有效地降低了通信开销,算法的运行时间减少,加速比得到提高。To resolve the problem of large communication cost created from task distribution by using traditional partitioning method in 3D mesh parallel computing, a parallel task distribution strategy based on multilevel K-way partitioning algorithm is presented. Firstly, partitioned 3D mesh by using multilevel K-way partitioning algorithm, treating task partitioning as graph partitioning, and then took a task mapping parallel algorithm to map computing task on every computing node. Finally, some experiments of computing shortest path problem in 3D mesh are done on ShenTeng 1800 clusters, the results indicate that compared with traditional row-column task mapping strategy, this strategy effectively reduce communication cost and ensure load balance at the same time, running time decrease and speedup increase.

关 键 词：多层k路划分 并行任务分配 图划分 三维网格 通信开销 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]