Metrics for the comparison of parallel algorithms and their design methodologies

摘要

The purpose of this research is to ascertain the impact that the additional information required to specify parallel algorithms, such as synchronization and resource sharing, will have on their structural complexity. With this in mind, a set of metrics are developed that extend the traditional metrics for sequential algorithms to the parallel domain. Both sequential and parallel algorithms can be described in this more general framework.These metrics are then used to compare the structure of a sequential bisection root finding algorithm and its parallel counterpart. Through this comparison we see that the major increases in complexity occur in the sequential segments of the parallel code. This phenomenon, designated subsidization, is discussed in detail and its implications for the design of parallel algorithms are given.