inducer / inducer/pytato

Unused bindings remain in DAG when concatenating

Open
#559 2 comments 0 reactions 0 assignees Claimed by @majosm View on GitHub
Dominant language
Python
Stars
15
Forks
16
Avg merge
17m
Merged PRs (30d)
1

Description

With the current concatenation implementation (#477), a situation can arise where call bindings that are not needed by the computation are retained in the DAG.

From the perspective of a given function parameter, if the result of the computation depends on the bindings for that parameter uniformly for all calls (i.e., the computation either uses the binding from every call or none of them), then everything works as expected: either all of the bindings remain in the DAG or they are all dropped. However, if the computation depends on bindings for some of the calls and not others, then all of the bindings still remain in the DAG. This is not ideal, as it can lead to unnecessary computation (+ communication, in the case of MIRGE-Com).

Some sketches of this can be found [here](https://notes.tiker.net/UcVogAv0QaWd6syzT5cK2g). The DAGs represent a computation in which the first output of an outlined function depends on the first function parameter and the second output depends on the second parameter. The second output may or may not be used in the computation (and thus the second parameter bindings may not be needed). Case 1 is the situation where none of the second call results are used, and everything works as desired (the "recv"s are dropped). Case 2 shows that when the second output is used in one of the calls, the second parameter bindings are retained from all of the calls instead of just the one that is needed.

Potentially this can be fixed by modifying the function body concatenation processing to only include the needed calls. In other words, when applying concatenation to a given function output, it could look at which of the calls' corresponding outputs are actually needed by the computation and only concatenate those.

Contributor guide

No contributing guide indexed for this repository

Research direction

Review the concatenation implementation associated with #477 and the linked DAG sketches, starting with Case 2 where only one call uses the second output. Reproduce that situation and verify that concatenation retains bindings only for calls whose corresponding outputs are needed, without changing the cases that already drop unused bindings.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
compilers
Issue type
Bug
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.