A3: 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 of architectures. Other algorithms (using aggregate communication operations sensitive to cross-section bandwidth) may have different time complexity but their implementations may still be portable and possibly optimal across a wide range of architectures as long as they use a library of aggregate communication operations customized to each architecture. We note that the simpler, asymptotically accurate algorithm analysis facilitated by A³ can make algorithm design much faster and simpler.