Parameterized algorithm decomposition and performance analysis

A decomposition model using two-task replacement sets is used to model algorithm decomposition and algorithm performance. This technique provides a parametric representation of decomposition and performance analysis that is more general and powerful than previous methods. The model is used to investigate the performance of algorithms for MIMD architectures, and the results include statistical descriptions of task and synchronization penalty behavior under decomposition, and analytical representations of algorithm performance. The analysis provides insight into the effect of decomposition on performance at both the local task and the global algorithm levels