A3: a simple and asymptotically accurate model for parallel computation

A. Grama, Vipin Kumar, S. Ranka, V. Singh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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 A3 (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 A3 can make algorithm design much faster and simpler.

Original languageEnglish (US)
Title of host publicationFrontiers of Massively Parallel Computation - Conference Proceedings
Editors Anon
PublisherIEEE
Pages60-69
Number of pages10
StatePublished - Dec 1 1996
EventProceedings of the 1996 6th Symposium on the Frontiers of Massively Parallel Computing, Frontiers'96 - Annapolis, MD, USA
Duration: Oct 27 1996Oct 31 1996

Other

OtherProceedings of the 1996 6th Symposium on the Frontiers of Massively Parallel Computing, Frontiers'96
CityAnnapolis, MD, USA
Period10/27/9610/31/96

    Fingerprint

Cite this

Grama, A., Kumar, V., Ranka, S., & Singh, V. (1996). A3: a simple and asymptotically accurate model for parallel computation. In Anon (Ed.), Frontiers of Massively Parallel Computation - Conference Proceedings (pp. 60-69). IEEE.