GSOC 2020 - Native Distributed Linear Algebra Implementations

ChapelLinearAlgebra-GSOC2020.md

Project: Native Distribute Linear Algebra Implementations

Organization: CHAPEL

Rahul Ghangas

Email: rahulghangas0@gmail.com
Phone: +61 0426126128

Index

1. Introduction
2. Outcome of contributions
3. Design Discussions
4. Code Contribution (Merged Pull requests)
5. Code Contribution (Open Pull requests)
6. Further Work

Introduction

Until now, Chapel has depended on external libraries like BLAS and LAPACK to provide access to standard linear algebra functions. Furthermore, Chapel does not support linear algebra functions for distributed computation. The world is becoming increasingly connected, from the Internet of Things and social networks, to ‘big data’ and cloud computing. Networked systems are not just relevant to information technology; they are already moving into the engineering and cyber-physical systems domains. With clusters and networked systems being commonplace, distributed computing offers magnitudes of faster performance for the large amount of data we deal with today.

This project aims to extend the LinearAlgebra module to support distributed implementations of existing procedures. Another goal is to improve the performance of existing native implementations of standard linear algebra functions and provide native implementations for procedures that currently depend on external libraries.

Worked on:

• #15976 #16077 Improving local LinearAlgebra.dot() to perform competitively to CrayBLAS

  • Performance improvement based on loop tiling cache optimization
  • Performance can be tracked at https://chapel-lang.org/perf/1-node-xc/?startdate=2020/07/24&enddate=2020/08/30&graphs=linearalgebradotperformance20482048matrix

• #15835 Implemented a new version of distributed matrix-matrix multiplication for PRK (Parallel Research Kernels)

  • Based on SUMMA

• #16107 Implemented Distributed LinearAlgebra.dot()

  • Generalized to any distribution supported by Chapel

• #16106 Include error generation for procedures that do not support distributed arrays (matrices/vectors)

• #16160 Improved local LinearAlgebra.diag() to support matrices with any generalized domain

• #16147 Implemneted distributed LinearAlgebra.diag()

  • Overloads for the user to
    • pass in a output distributed array
    • let the procedure decide the output distribution

• #16206 Implemented distributed LinearAlgebra.transpose()

  • Supports inversion of distributed domain to support faster transpose

• #16205 Implemented local LinearAlgebra.svd()

  • Work on parallelizing reference implementation from Numerical Recipes Ch-2 Section-6

• #16255 Implemented local LinearAlgebra.inv()

  • Gauss-Jordan Elimination

Design Discussions

• Design Discussions

Code Contribution (Merged Pull requests)

• Merged Pull Requests

Code Contribution (Open Pull requests)

• Open Pull Requests

Further Work

• Distributed Singular Value Decomposition
• Distributed Matrix Inverse
• Distributed Sparse Matrix-Matrix Multiplication
• Distributed Sparse Singular Value Decomposition