异构机群系统上并行计算双序列的最长公共子序列  

Parallel algorithm for pair-wise sequence LCS problem on heterogeneous cluster computing systems

作　　者：许莉莉[1] 魏鹰[2] 罗海鹏[3] 张林才[4] 

机构地区：[1]广西电力工业勘察设计研究院,南宁530023 [2]广西经济管理干部学院,南宁530007 [3]广西科学院,南宁530003 [4]辽宁石油化工大学计算机与通信工程学院,辽宁抚顺113001

出　　处：《计算机应用研究》2010年第5期1669-1671,1682,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(60563008)

摘　　要：针对处理机节点具有不同计算速度、不同通信能力的情况,考虑计算和通信启动开销,给定处理机分配顺序,基于可分负载理论,提出一种存储受限异构机群系统的序列串最优分配线性规划模型,给出相应的序列串最优分配方法。实验结果表明,基于最优序列串分配方法的双序列最长公共子序列并行算法优于平均分配序列串算法,获得了较好的加速,并具有良好的可扩展性。Based on the optimality principle of divisible load theory, and the assumption that the distribution of processors in a fixed order,this paper presented an optimal sequence distribution strategy and gave its corresponding closed-form expressions on the more practical heterogeneous cluster computing systems that processors had different computing speeds and communication capabilities. Algorithm analysis and experimental results show that the required based on the optimal sequence distribution strategy the parallel processing time for pair-wise sequence LCS problem reduces significantly and obtain a good acceleration and scalability using the optimal sequence distribution strategy compared to the average allocation strategy.

关 键 词：双序列的最长公共子序列 并行算法 异构机群系统 可分负载 分配策略 

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