A³: A Simple and Asymptotically Accurate Model for Parallel Computation

Many parallel algorithm design models have been proposed for abstracting a large class of parallel architectures. However, all of these models potentially make inaccurate asymptotic performance predictions that may be too optimistic or too pessimistic depending on the circumstances. We propose a new, simpler parallel model called A³ (Approximate Model for Analysis of Aggregate Communication Operations) that provides asymptotically accurate time estimates for a wide class of parallel programs that are based on aggregate communication operations. Accuracy is attained (1) by making the model sensitive to the structure of aggregate data communication operations and (2) by classifying these aggregate communication operations into those that are cross-section bandwidth sensitive and those that are not. We note that algorithms expressed exclusively using those aggregate communication operations that are cross-section bandwidth insensitive have the same time complexity across a wide range o..