存储受限异构机群系统的多目标串近似匹配并行算法

Parallel Algorithm for Approximate Multiple Object Strings Matching on Heterogeneous Cluster Computing Systems with Limited Memory

针对处理机节点具有不同的计算能力、通信延迟和存储容量的情形,考虑计算和通信启动开销,给定处理机分配顺序,基于可分负载理论,分别建立单层和两层树结构模型的存储受限异构机群系统的目标串最优分配线性规划模型,给出相应的目标串最优分配方法,并讨论了处理机最优分配顺序.实验结果表明,本文提出的基于最优分配方法的多目标串近似匹配并行算法优于平均分配算法,获得了较好的加速并具有良好的可扩展性.

Based on taking into account computation and communication loads and the assigned processor distribution order and divisible load principle, two linear programming models and methods for optimal object string distribution are presented on the single-tier and double-tier tree heterogeneous cluster computing systems that processors have different computing speeds and communication capabilities and memory sizes. The experimental results on the cluster of heterogeneous personal computers show that the parallel algorithm for approximate multiple object string matching with the presented optimal distribution method is superior to one with the even distribution strategy, and it obtains good speedup and scalability.