On detecting parallelism in software

In the last decade a number of parallel algorithms for various kinds of scientific and real-time applications have been proposed. These algorithms need to be evaluated for both time and communication complexities. The evaluation should be machine independent and be able to identify common features in different algorithms. In this paper we review the performance-evaluation issues for parallel algorithms and present a simple model for comparative evaluation of these algorithms.