Parallel Algorithm Scalability Issues in PetaFLOPS Architectures

Abstract

The projected design space of petaFLOPS architectures entails exploitationof very large degrees of concurrency, locality of data access, and toleranceto latency. This puts considerable pressure on the design of parallelalgorithms capable of effectively utilizing increasing amounts of processingresources in a memory and bandwidth constrained environment. This aspect ofalgorithm design, also referred to as scalability analysis, is a keycomponent for guiding algorithm designers as well as hardware architects.By identifying bottlenecks to scalability and machine parameters thatinfluence these bottlenecks, scalability analysis provides insights toalleviating the bottlenecks in the context of the specific algorithm.In this paper, we motivate the need for, and benefits of scalabilityanalysis in the context of petaFLOPS systems. We overview variousscalability metrics and study their suitability to petaFLOPS system.We also present sample analysis of selected computational kernels fromdense linear algebra, fast fourier transforms, and data intensive applications(association rule mining). The objective of this analysis is to demonstratethe analysis framework and its use in identifying desirable architecturalfeatures as well the ability of these selected kernels to scale to petaFLOPSsystems.