异构机群系统上基于多轮分配方式的近似串匹配并行算法  

Parallel Algorithms for Approximate String Matching with Multi-Round Distribution Strategy on Heterogeneous Cluster Computing Systems

作　　者：钟诚[1] 范大娟[1] 

机构地区：[1]广西大学计算机与电子信息学院,南宁530004

出　　处：《计算机研究与发展》2008年第z1期105-112,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60563003)

摘　　要：在给定正文串分配轮数的前提下,考虑处理机节点具有不同计算速度、不同通信能力的情形,根据从处理机是否允许重叠执行计算和通信操作,提出异构机群计算环境下的最优正文串多轮分配策略;同时提出一种周期性的正文串多轮分配策略并给出了相应的正文串多轮分配的闭合解,此策略可以求出最优的分配轮数.实验结果表明,正文串多轮分配策略比正文串单轮分配策略大大缩短了近似串匹配并行处理的时间,并且在正文串多轮分配策略中,当近似串匹配应用的规模较小时,分配轮数比参与近似串匹配并行处理的从处理机数更能影响近似串匹配并行处理的完成时间,反之,从处理机数对近似串匹配并行处理的完成时间影响更大.For a given round number of text distribution, an optimal text multi-round distribution strategy is presented on the heterogeneous cluster computing systems in which processors have different computing speeds and communication capabilities according to whether the slave processors can execute overlapped computing and communication. Furthermore, a periodic text multi-round distribution strategy is also proposed and its corresponding closed-form expressions are given. For the periodic distribution strategy, an optimal round number is obtained. The experimental results on the cluster of personal computers show that the two text multi-round distribution strategies decrease the required parallel processing time to a large extent compared with the text single-round distribution strategy, and the number of distribution rounds have a more effect on the required parallel processing time for the small-scale approximate string matching applications and the number of slave processors have a more effect on the time for the large-scale approximate string matching applications respectively under the contrary condition.

关 键 词：近似串匹配 并行算法 异构机群系统 分配策略 多轮分配 

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