最优并行算法评价标准的研究

RESEARCH ON EVALUATION CRITERIA FOR OPTIMAL PARALLEL ALGORITHMS

加速比是判断一个并行算法是否最优的依据，但播送类问题是针对并行机提出的，不存在串行算法，加速比标准对之无能为力．通过对几种不同并行计算模型上播送算法的研究，文中提出了一个不依赖于具体模型的一般化的评价标准ｍｉｎＣ２，用以判断播送类算法是否最优，为这类问题的进一步研究开辟了新的思路．

Speedup is considered as the criterion of determining whether a parallel algorithm is optimal. But broadcasting class problems, existing only on parallel computer systems, have no sequential algorithms. The speedup becomes invalid here. Through researhing on broadcasting algorithms in several typical parallel computation models, a model independent evaluation criterion min C 2 is developed, which can be used to determine an optimal broadcasting algorithm, and a new approach to broadcasting class problems is given.