| Accompanying the potential increase in power offered by parallel computers is an increase in the complexity of program design, implementation, testing and maintenance. It is important to understand the logical complexity of parallel programs in order to support the development of concurrent software. Measures are needed to quantify the components of parallel software complexity and to establish a basis for comparison and analysis of parallel algorithms at various stages of development and implementation.; A set of primitive complexity measures is proposed that collectively describe the total complexity of parallel programs. The total complexity is separated into four dimensions or components: requirements, sequential, parallel and communication. Each proposed primitive measure is classified under one of these four areas. Two additional possible dimensions, fault-tolerance and real-time, are discussed.; The total complexity measure is expressed as a vector of dimensions; each component is defined as a vector of primitive metrics. The method of quantifying each primitive metric is explained in detail. Those primitive metrics that contribute to the parallel and communications complexity are exercised against ten published summation algorithms and programs, illustrating that architecture has a significant effect on the complexity of parallel programs--even if the same programming language is used. The memory organization and the processor interconnection scheme had no effect on the parallel component, but did affect the communication component. Programming style and language did not have a noticeable effect on either component.; The proposed metrics are quantifiable, consistent, and useful in comparing parallel algorithms. Unlike existing parallel metrics, they are general and applicable to different languages, architectures, algorithms, paradigms, programming styles and stages of software development. |
