spcl / spcl/dace

Bad dependency resolution in nested map

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

Description

The simple program
```python
@dace.program
def bug(mat: dace.int32[N,N]):
buff = np.zeros_like(mat)
for i in dace.map[0:N]:
for j in dace.map[0:N]:
buff[i, j] = mat[i, j] * 2
for j in dace.map[0:N-1]:
mat[i, j] = buff[i, j]
```
will result in the following wrong simplified sdfg:
![image](https://github.com/spcl/dace/assets/54279461/c1a396c6-9350-4e12-9fdf-9f8a9b241df1)
where the assign tasklet is a simple assignment operator, copying buff to mat

The issue does not happen if the two ranges of the internal maps (the ones with variable j) iterate over the same range. In the unsimplified nested sdfg representing the scope of the outer map (variable i) both buff and mat have two different names -> the state fusion fails to detect the data dependency, and ultimately one of the two maps is discarded.

Contributor guide

Open the contributing guide

Research direction

Reproduce the issue with the Python program and inspect the unsimplified nested SDFG for the outer map. Trace state fusion and dependency handling for the two inner maps, then verify that simplification preserves the dependency between buff and mat and does not discard either map.

Written by the indexing model from the issue text.

Assessment

Tech stack
numpy, python
Domain
compilers, hpc
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.