Why is mutual exclusivity analysis done per-proc and not per-channel per-proc?

[schilkp]

Hi!

Out of curiosity I have been digging into a few different parts of the code base and have a super implementation-specific questions about the restriction on "one channel interaction per channel per proc activation".

Baseline

My current understanding is as follows:

XLS can only support one channel interaction per channel per proc activation. From the docs:

!!! NOTE
    This example will not work as written until DSLX supports multiple I/O
    operations per channel per activation.

Seems logical to me: A send inside a proc pipeline could "trigger" up to once per clock cycle, so if you have multiple sends to the same channel that becomes physically impossible.

This means that once code reaches scheduling, there must be at most be one send per channel.

There are many things done to "hide" this from the user. For example the mutual_exclusion_pass converts multiple, mutually-exclusive, sends to one channel into a single send with a select.

Another example of one such "workaround" is @grebe 's channel_legalization_pass which replaces multiple sends to one channel with multiple channels and an arbiter proc.

The test TwoSequentialSends in mutual_exclusion_pass_tests matches my expectations from the above. Given this input:

package test_module

chan test_channel(
  bits[32], id=0, kind=streaming, ops=send_only,
  flow_control=ready_valid)

top proc main(__state: bits[1], init={0}) {
  not.1: bits[1] = not(__state)
  literal.2: bits[32] = literal(value=50)
  literal.3: bits[32] = literal(value=60)
  __token: token = literal(value=token, id=1000)
  send.4: token = send(__token, literal.2, predicate=__state, channel=test_channel)
  send.5: token = send(send.4, literal.3, predicate=not.1, channel=test_channel)
  next (not.1)
}

The pass is able to reduce the two sends to one:

EXPECT_THAT(RunMutualExclusionPass(proc), IsOkAndHolds(true));
EXPECT_EQ(NumberOfOp(proc, Op::kSend), 1);

Question: Why are the mutual exclusion checks not per-channel?

However, I came across the test TwoSequentialSendsWithInterveningIO in mutual_exclusion_pass_tests, which has the following input:

package test_module

chan test_channel(
  bits[32], id=0, kind=streaming, ops=send_only,
  flow_control=ready_valid)

chan other_channel(
  bits[32], id=1, kind=streaming, ops=send_only,
  flow_control=ready_valid)

top proc main(__state: bits[1], init={0}) {
  not.1: bits[1] = not(__state)
  literal.2: bits[32] = literal(value=50)
  literal.3: bits[32] = literal(value=60)
  __token: token = literal(value=token, id=1000)
  send.4: token = send(__token, literal.2, predicate=__state, channel=test_channel)
  send.5: token = send(send.4, literal.2, channel=other_channel)
  send.6: token = send(send.5, literal.3, predicate=not.1, channel=test_channel)
  next (not.1)
}

From my understanding above, I would expect the pass to fold the two sends to test_channel together since they are again mutually exclusive. However, the pass does not, and the test verifies that it does not:

EXPECT_THAT(RunMutualExclusionPass(proc), IsOkAndHolds(false)); // not mut. exc.!!
EXPECT_EQ(NumberOfOp(proc, Op::kSend), 3); // None removed !!

I played around with this, and AreStreamingOutputsMutuallyExclusive from bdd_io_analysis behaves the same. It reports the first snippet to be mutually exclusive, but not the second snippet.

Looking into bdd_io_analysis, it seems that this is because the mutual exclusion analysis is done on all sends in the proc, instead of all the sends to one channel in one proc. Since there is both a send without predicate and a send with predicate, AreStreamingOutputsMutuallyExclusive directly aborts:

if (streaming_send_count != send_predicates.size()) {
  return false;
}

To my actual question: Why is mutual exclusivity analysis being done once per proc for all sends, instead of for each output channel's set of sends? Why does it matter that there is a send to other_channel?

Is this just a limitation of the mutual exclusivity detection, or are there downstreams problems if cases like the second snippet were allowed?

Cheers!

[proppy]

Related #1899 #1900

[ericastor]

The quick version (at least from the MutualExclusionPass's perspective), since we've accidentally let this sit a while (sorry about that!): if you have an operation on channel X, then an operation on channel Y, and then an operation on channel X again, with a token dependency forcing this order... then you can't merge the two operations on channel X without violating the order guarantee, even if their predicates happen to be mutually exclusive. This analysis/legalization pass enforces that, saying that these operations are not in the same "mergeable class".

P.S. ... okay, technically, it could be possible to merge the channel-X operations if we added a restriction that the result must happen simultaneously with the intervening channel-Y operation, which would respect the ordering requirements. We don't currently handle that. Also, the definition of simultaneity could end up making things complicated pretty fast!

P.P.S. I'm not sure about the bdd_io_analysis. I'll let someone else weigh in on that... but I'll also point out the TODO in that file that mentions that it's currently using a very conservative analysis.

[schilkp]

The quick version (at least from the MutualExclusionPass's perspective), since we've accidentally let this sit a while (sorry about that!): if you have an operation on channel X, then an operation on channel Y, and then an operation on channel X again, with a token dependency forcing this order... then you can't merge the two operations on channel X without violating the order guarantee, even if their predicates happen to be mutually exclusive. This analysis/legalization pass enforces that, saying that these operations are not in the same "mergeable class".

Ahhh!!!

That make sense of course. I was tunnel-visioned on the exclusivity of the predicates and did not think through what merging these channels would actually look like.

Thanks!