daphne-project / daphne-project/daphne

Additional sparse matrix representation: COO

Open
#528 0 comments 0 reactions 0 assignees View on GitHub
LDE summer 2023 LDE winter 2023/24 student project
Dominant language
C++
Stars
81
Forks
83
PR merge metrics
No merged PRs in 30d

Description

**Motivation:** Many real-world applications in data science are characterized by the prevalence of sparse data, where almost all cells of a matrix are zero. Instead of storing and processing all cells in a dense representation, it is common to use sparse representations, which only store the non-zero values. That way, the storage requirement and runtime can be improved significantly. DAPHNE already supports CSR (compressed sparse row) as a sparse matrix representation. However, there are other representations with unique characteristics. Examples include (a) MCSR (modified CSR), which is more update-friendly as the values of each row are stored in a separate array, (b) CSC (compressed sparse column), which benefits column-major access patterns, and (c) COO (coordinate-based), which is better suited for ultra-sparse data. None of these sparse representations is the most suitable one in all situations. Therefore, being able to freely choose the format has the potential of better adapting to the circumstances at hand.

**Task:** This project is about extending DAPHNE by the additional sparse matrix representation **COO**, which represents a sparse matrix by three arrays of the same length: *row indexes*, *column indexes*, and *values*. Each non-zero element in the matrix is represented by three corresponding elements in these arrays, i.e., described by its row and column position and the value. Typically, the triples are sorted by row index (primary) and column index (secondary). For instance, the matrix
```
0 0 0 1 0 0
0 2 0 0 0 0
0 0 0 0 0 0
0 0 3 0 0 0
```
would be represented as
```
row indexes: 0, 1, 3
col indexes: 3, 1, 2
values: 1, 2, 3
```

Addressing this task includes:
1. the implementation of `COOMatrix`, the corresponding subclasses of the `Matrix` class, including all required methods like `get()`/`set()`/`append()` and slicing
2. the implementation of new kernels (physical operators) tailored to the respective representation for a few decisive operations (e.g., elementwise unary/binary, matrix multiplication, transposition, full/row-wise/column-wise aggregations, …)
3. strategy to select COO over a dense matrix representation (e.g., based on the estimated sparsity and physical size in bytes)

Implementation in C++.

**Hints on approaching this task:**
- Get familiar with (1) the existing dense and sparse matrix representations in DAPHNE, (2) the kernels for `DenseMatrix` and `CSRMatrix`, and (3) the characteristics of the COO sparse representation mentioned above.
- Design the new sparse matrix representation as well as algorithms/kernels operating on them.
- Optionally, also develop concepts for supporting the new sparse representations for the inputs and outputs of DAPHNE’s vectorized pipelines to support multi-threaded and cache-conscious processing.
- Implement your design, including tests and documentation.
- Think of meaningful experiments which highlight the strengths and weaknesses of the COO representation compared to dense (and optionally CSR) in terms of memory consumption and performance. Graph algorithms like connected components and PageRank could be used for the experiments. Conduct the experiments, visualize and interprete the results.

Contributor guide

Open the contributing guide

Research direction

Start by reading the existing DenseMatrix and CSRMatrix representations, their Matrix subclasses, and the corresponding kernels. Define the COO representation and implement its methods, kernels, representation-selection strategy, tests, documentation, and performance experiments; completion should include meaningful comparisons with dense and CSR formats.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
data, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.