Lockless-Spark98:
Lock-free Sparse Matrix Kernels for Shared Memory Systems

Philippas Tsigas, Yi Zhang

Lockless-Spark98 is a version of the shared memory Spark98 kernels where the locks used by the original Spark98 Kernels were replaced by non blocking synchronisation constructs.

Spark98 contains a set of sparse matrix kernels that perform a set of sparse matrix vector product (SMVP) operations. The multiplication of a sparse matrix by a dense vector is a dominant part of  many computer applications, including, scientific computing applications, scheduling applications based on linear programming and applications that simulate physical systems. Spark98 kernels were developed by David R. O'Hallaron at Carnegie Mellon University to facilitate building application
with a set of sparse matrix codes that are simple, realistic, and portable.

We developed the Lockless-Spark98 Kernels together with the Lockless-MiniSPLASH2 in order to:

• facilitate the understanding of the benefits of non-blocking synchronisation in realistic and simple parallel codes, expected to play a central role in many parallel applications.
• facilitate the understanding of  using nonblocking synchronisation instead of using lock-based one when building  cache coherent shared memory multiprocessors applications.

Availability

The source code of Lockless-Spark98 is developed under the GNU General Public License (GNU GPL). The source code of our implementation and some related files for our experiments can be downloaded.

Papers

Philippas Tsigas, Yi Zhang, "Integrating Non-blocking Synchronisation in Parallel Applications: Performance Advantages and Methodologies", in the Proceedings of the 3rd ACM SIGSOFT, SIGMETRICS Workshop on Software and Performance (WOSP ´02), pages: 55-67, ACM press. (pdf file)

Related Local Projects

There are a number of projects run by the group looking into non-blocking synchronisation from different aspects:

• NOBLE: A software library of shared data objects
• Lockless-MiniSPLASH2
• WARPing