一种基于平衡划分的集合差并行算法  

A Parallel Set Difference Algorithm Based on Balanced Partitioning

作　　者：沈燕芬[1] 颜启华[2] 

机构地区：[1]广东建设职业技术学院计算机系,广东广州510440 [2]华南师范大学计算机学院

出　　处：《计算机时代》2010年第11期46-49,共4页Computer Era

摘　　要：基于精确划分的思想提出了一种新的集合差并行算法DIFF-DL。利用DL子算法查找最终全局序列中等分位置上的划分点,将数据平均划分并分配给所有处理机,使每个处理机具有相同的工作负载。给出了网络并行计算环境下的实验结果,并与DIFF-S、DIFF-NS算法进行了对比。理论分析和实验的结果都表明,DIFF-DL算法具有很高的并行效率和扩展性,原因是划分类算法的性能和划分后区间数据量的平均程度正相关。Based on the idea of precise division, a new parallel set difference algorithm DIFF-DL is proposed. It uses sub algorithm DL to locate the dividing points which equally divide the final global sequence, then partitions the data averagely and distributes them to all processors, makes each processor has same workload. The experimental result under network parallel computing environment is given, and is compared with those of DIFF-S and DIFF-NS algorithms. Both the theoretical analysis and experimental result show that DIFF-DL algorithm has very high parallel efficiency and scalability, which attribute to the positive correlation between the performance of division-based algorithms and the average level of data amount in divided sections.

关 键 词：集合差 划分点 DL算法 DIFF-DL算法 

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