spcl / spcl/dace

How to optimize DaCe SpMV? (unoptimized version 20x slower than SciPy sparse dot)

Open
#715 9 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
593
Forks
163
Avg merge
2d 23h
Merged PRs (30d)
60

Description

## Problem description

In the [DaCe paper](https://arxiv.org/abs/1902.10345), it is stated that DaCe SpMV is as fast as MKL:

> We observe similar results in SpMV, which is more complicated to optimize due to its irregular memory access characteristics. SDFGs are on par with MKL (99.9% performance) on CPU, and are successfully vectorized on GPUs.

However, I found it 20x slower than `scipy.sparse.csr_matrix.dot`. 1.4s vs 60ms for the problem size used in the DaCe paper.
- **Full code to reproduce**: https://gist.github.com/learning-chip/1ef56f6ea707b063c3177e9f143f0905
- The SpMV code was taken from https://github.com/spcl/dace/blob/v0.10.8/samples/simple/spmv.py
- **DaCe version**: 0.10.8
- **Hardware**: Intel Xeon 8180 CPU

It is probably because I did not apply any transformations to optimize performance. But I could not find more words in the paper about SpMV optimization, except this short paragraph:

> Using explicit dataflow is beneficial when defining nontrivial data accesses. Fig. 4 depicts a full implementation of Sparse Matrix-Vector multiplication (SpMV). In the implementation, the access x[A_col[j]] is translated into an indirect access subgraph (see Appendix F) that can be identified and used in transformations.

I also tried this sample code from the paper, slightly different from the GitHub version. But got `TypeError: dtype must be a DaCe type, got __map_8_b0` at runtime.
```python
# From DaCe paper fig.4
@dace.program
def spmv(A_row: dace.uint32[H+1], A_col: dace.uint32[nnz],
A_val: dace.float32 [nnz], x: dace.float32 [W],
b: dace.float32[H]):
for i in dace.map[0:H]:
for j in dace.map[A_row[i]:A_row[i+1]]:
with dace.tasklet :
a << A_val[j]
in_x << x[A_col[j]]
out >> b(1, dace.sum)[i]
out = a * in_x
```

## Environment
Conda `environment.yml` is

```
name: dace
dependencies:
- python=3.7.5
- pip
- pip:
- jupyterlab
- scipy==1.6.2
- dace==0.10.8
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.