A programming model for block-structured scientific calculations on smp clusters
Stephen J. Fink, Scott B. Baden · 1998
Multi-tier parallel computers such as clusters of symmetric multiprocessors (SMPs) offer both new opportunities and new challenges for high-performance computation. Although these computer platforms can potentially deliver unprecedented performance for computationally intensive scientific calculations, realizing the hardware's potential remains a formidable task. To achieve high performance, the programmer must coordinate several levels of parallelism and locality to match the hardware's capabilities. Current programming languages and software tools do not directly facilitate this task, and the resultant difficulties hinder efficient implementations of scientific calculations on SMP clusters. We present a concise set of programming abstractions that simplify implementation of efficient algorithms for block-structured scientific calculations on SMP clusters. The software infrastructure, KeLP, provides intuitive geometric mechanisms to help the programmer coordinate data layout, data motion, and parallel control. The KeLP constructs abstract away many low-level programming details of message-passing, thread management, synchronization, scheduling, and storage allocation. Nevertheless, KeLP still provides enough expressive power to implement effective multi-tier algorithms for a broad class of computationally-intensive scientific applications. Most importantly, the KeLP implementation adds little overhead to lower-level primitives, and KeLP performance usually matches or exceeds performance for comparable programs using lower-level primitives. The dissertation presents solutions to varied technical challenges in the realization of a concise, abstract, expressive, and efficient programming model for multi-tier computers. In particular, the dissertation extends the structural abstraction programming model to manage three levels of parallel control and data structures to match the multi-tier hardware. KeLP presents a new communication orchestration model which combines structural abstraction with ideas from the inspector/executor paradigm. In application studies, we present new multi-tier algorithms for several applications, including multigrid, matrix multiplication, and dense matrix factorization. Experimental results on several platforms expose bottlenecks that limit performance and trade-offs for algorithmic and hardware design. Finally, this research has resulted in the KeLP 2.0 implementation, a C++ class library which has been used successfully in a number of computational science research projects.