Abstract: Based on the optimality principle of divisible load theory and the fixed sequence of text distribution, an optimal text distribution strategy is presented and its corresponding closed-form expressions are given in the heterogeneous cluster computing systems that processors have different computing speeds and communication capabilities. A linear programming model for the optimal text distribution is constructed for the cluster system that processors have different computing speeds, communication capabilities and memory capacities. The optimal text distribution sequence for special cases is studied. Experimental results show that the required parallel processing time for approximate string matching by applying the optimal text distribution strategy decreases 10%~40% and 5%~20% respectively compared with dividing the text equally and dividing the text according to the computing speeds of processors.

Key words: approximate string matching, parallel algorithm, heterogeneous cluster computing systems, divisible load, distribution strategy

摘要： 基于可分负载理论的最优原则，在假定正文串分配顺序固定的前提下，考虑处理机节点具有不同计算速度、不同通信能力的情况，提出一种异构机群计算环境下的最优正文串分配策略，给出最优正文串分配的闭合解。对于节点具有不同计算速度、通信能力、存储容量的异构机群系统，建立正文串最优分配的线性规划模型。针对几种特殊情况讨论正文串的最优分配顺序。实验结果表明，与平均分配正文串策略以及按照从处理机能力分配正文串策略相比，利用该策略进行近似串匹配并行处理所需时间分别缩短了10%~40%和5%~20%。

关键词: 近似串匹配, 并行算法, 异构机群系统, 可分负载, 分配策略

CLC Number: 

• TP393