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.