Reducing software overheads in parallel linear algebra libraries

Abstract

Software overheads can be a significant cause of performance degradation in parallel numerical libraries. This paper examines the nature and extent of software overheads in an implementation of parallel LAPACK on distributed memorymultiprocessors, where block-partitioned algorithms with a general block-cyclic matrix distribution scheme present special challenges. It then describes various techniques that have been used to reduce these overheads, and evaluates their effectiveness. While there is a tradeoff between the software engineering properties of high data and procedural abstraction, modularity and portability (which are particularly important in parallel programming) and achieving low software overheads, it is shown that a good balance can be achieved in the case of parallel LAPACK, at least for important classes of computations.