TOWARDS AN ARCHITECTURE-INDEPENDENT ANALYSIS OF PARALLEL ALGORITHMS

被引：172

作者：

PAPADIMITRIOU, CH ^{[1
]}

YANNAKAKIS, M ^{[1
]}

机构：

[1] AT&T BELL LABS,MURRAY HILL,NJ 07974

来源：

SIAM JOURNAL ON COMPUTING | 1990年 / 19卷 / 02期

关键词：

D O I：

10.1137/0219021

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A simple and efficient method for evaluating the performance of an algorithm, rendered as a directed acyclic graph, on any parallel computer is presented. The crucial ingredient is an efficient approximation algorithm for a particular scheduling problem. The only parameter of the parallel computer needed by our method is the message-to-instruction ratio τ. Although the method used in this paper does not take into account the number of processors available, its application to several common algorithms shows that it is surprisingly accurate.

引用

页码：322 / 328

页数：7