Algorithmic optimizations of a conjugate gradient solver on shared memory architectures

Abstract

OpenMP is an architecture-independent language for programming in the shared memory model. OpenMP is designed to be simple and powerful in terms of programming abstractions. Unfortunately, the architecture-independent abstractions sometimes come with the price of low parallel performance. This is especially true for applications with an unstructured data access pattern running on distributed shared memory systems (DSM). Here, proper data distribution and algorithmic optimizations play a vital role for performance. In this article, we have investigated ways of improving the performance of an industrial class conjugate gradient (CG) solver, implemented in OpenMP running on two types of shared memory systems.

We have evaluated bandwidth minimization, graph partitioning and reformulations of the original algorithm reducing global barriers. By a detailed analysis of barrier time and memory system performance, we found that bandwidth minimization is the most important optimization reducing both L2 misses and remote memory accesses. On a uniform memory system, we get perfect scaling. On a NUMA system, the performance is significantly improved with the algorithmic optimizations leaving the system dependent global reduction operations as a bottleneck.

Keywords:

• OpenMP
• Shared memory programming
• Iterative solvers
• Conjugate gradients
• Bandwidth minimization
• Reversed Cuthill-McKee

Notes

There might still be false-sharing effects in the OpenMP runtime system. As an example, the final stage of a reduction, which must be performed serially, should use padded arrays to minimize false sharing.

To only achieve load balance, one can use a sequence partitioning method for the rows.

In our case, the resource management system used was Sun Grid Engine.