Parallel Algorithm Scalability Issues in PetaFLOPS Architectures
Abstract
The projected design space of petaFLOPS architectures entails exploitation of very large degrees of concurrency, locality of data access, and tolerance to latency. This puts considerable pressure on the design of parallel algorithms capable of effectively utilizing increasing amounts of processing resources in a memory and bandwidth constrained environment. This aspect of algorithm design, also referred to as scalability analysis, is a key component for guiding algorithm designers as well as hardware architects. By quantifying the performance of an algorithm on larger machine configurations, scalability analysis guides parallel algorithm development. By identifying bottlenecks to scalability and machine parameters that influence these bottlenecks, scalability analysis influences hardware design. In this paper, we motivate the need for, and benefits of scalability analysis in the context of petaFLOPS systems. We present sample analyses of selected computational kernels from dense linear algebra, fast Fourier transforms, and data intensive applications (association rule mining). The objective of this analysis is to demonstrate the analysis framework and its use in identifying desirable architectural features as well the ability of these selected kernels to scale to petaFLOPS systems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 26, 2001
- Accession Number
- AD1020007
Entities
People
- Ananth Garma
- Anshul Gupta
- Euihong S. Han
- Vipin Kumar
Organizations
- University of Minnesota