Proposal for DeMux ops and RSink ops in Handshake

Incubator CIRCT
#1

In CIRCT, MLIR IR is lowered to handshake dialect to show the data path of synthesized circuits at abstraction level. Branch-like and merge-like ops are used to present the control flow the code.

However, there are some limits in using existing ops to describe certain code patterns like switch (arbitration in hardware) and floating inputs. Here I propose two new ops for handshake dialect:

  1. DeMux op

Existing conditional branch ops in handshake can only have two results. The data is forwarded to the first output if the condition is true (1), otherwise it is forwarded to the second output.

DeMux is common in hardware designs like arbitration logic. It also corresponds to switch in high-level language. The behavior is that for a given N output, the data is forwarded to the kth output if the select input has a value of k (k <= N). This is different from the behavior of conditional branch ops.

  1. RSink op

The behavior of RSink op is opposite to the Source op. It can be considered as a dead signal that never produce any invalid signal. It can be used to model floating input while satisfies the condition where each value has exactly one use in Handshake dialect.

I plan to make a patch for that, but I am not sure if it is the right thing to do. It would be nice to have any comments from others. Thanks!

#2
  1. DeMux op

I am all in favor of generalizing the existing ConditionalBranchOp to handle more than two results and more than a single bit for select. Is it required to create a new op for this? Why not just generalize the implementation of ConditionalBranchOp? Is there a fundamental difference between ConditionalBranchOp and the proposed DeMux op?

  1. RSink op

Is this op any different than a SinkOp?

#3

Thanks for the comments.

  1. DeMux Op

Yes, generalizing ConditionalBranchOp is possible, but the behavior is slightly different:

In an N-output ConditionalBranchOp, the data goes to the (N-k)th output when the select is k.
In an N-output DeMuxOp, the data goes to the kth output when the select is k.
In an N-output MuxOp, the kth data input goes to the output when the select is k.

My experience on using ConditionalBranchOp and MuxOp as pairs is quite painfulā€¦ especially when dealing with cascaded ops.

  1. RSinkOp

A SinkOp has an input and no output, and a RSinkOp has an output but no input. They are quite similar - that is why I named it as RSinkOpā€¦

#4

Iā€™m not a big fan of ā€œRSinkā€ as a name. I avoid abbreviations whenever possible, and by itself is not very descriptive. Maybe ā€œNeverā€ would be better choice? Or something else that better describes the behavior?

1 Like
#5

@JianyiCheng thanks for illustrating the difference between the proposed DeMux and the existing ConditionalBranch. I guess my question about this is really: if you add DeMux, what in StandardToHandshake (or other passes) will lower to ConditionalBranch, and what will lower to DeMux? If the point of DeMux is to be a more intuitive, flexible op to lower to, would we eventually deprecate ConditionalBranchOp? Or do you forsee both ops co-existing?

About the RSink I agree that the name is not intuitive. In fact, Iā€™m still not seeing what this op would be used for. Itā€™s like a source, but the output is always known to be invalid? You mentioned it ā€œcan be used to model floating inputā€. I take it you meant floating as in a wire that isnā€™t connected (as opposed to floating as in floating point)? Maybe a better question is this: how would this op lower to FIRRTL or some other HDL?

#6

Hi @mikeurbach,

Regarding your questions:

if you add DeMux, what in StandardToHandshake (or other passes) will lower to ConditionalBranch, and what will lower to DeMux?

For instance, when lowering high-level code to handshake, if statements are lowered to ConditionalBranches, and switch statements are lowered to DeMuxes.

DeMuxes or ConditionalBranches with more than two outputs have not been used in CIRCT, because the MLIR code for test does not have any switch statement. (There may be cascaded if statements, but there is no optimization pass for merging them to a single ConditionalBranchOpā€¦)

DeMuxes are more useful at handshake level for hardware specific operations, such as resource sharing and arbitration in memory partitioning. This is actually what I am interested now.

If the point of DeMux is to be a more intuitive, flexible op to lower to, would we eventually deprecate ConditionalBranchOp? Or do you forsee both ops co-existing?

My suggestion is that we keep ConditionalBranchOp the same (which only allows two outputs) and add DeMuxOp as a new op.

Maybe a better question is this: how would this op lower to FIRRTL or some other HDL?

Thanks for the clarification. Yes, NeverOp/RSinkOp is basically a disconnected wire. I have not looked into FIRRTL yet, but I think a NeverOp/RSinkOp should be lowered into a high impedance ā€˜Zā€™ in RTLā€¦

This is useful when we restrict an op with certain constraints. For instance, when I only use 2 inputs of a 4-input MergeOp, the unused inputs should connect to NeverOp/RSinkOps. (For JoinOp, the unused inputs should connect to SourceOp.)

#7

I guess what Iā€™m trying to push on is why have two separate ops for ConditionalBranch and DeMux, when one appears to be strictly more expressive than the other? Is it to keep backwards compatibility?

From what youā€™ve said, it seems like every use-case that ConditionalBranch handles could be handled by the proposed DeMux. If thatā€™s the case, why not deprecate ConditionalBranch, or add the proposed functionality to ConditionalBranch op in the first place (and possibly rename it). I would much rather have one op for ā€œbranchingā€ that we can deal with generically, rather than keeping two ops that are really similar but differ in minor ways

Thanks, that makes sense. I donā€™t want to get bogged down on the naming, but please choose something that makes this clear, and spell out the name (for example, I still have no idea what the R in RSink stands for).

1 Like
#8

Thanks. Yes, I agree that ConditionalBranchOp may not be necessary once we have DeMuxOp.

The R stood for ā€œreversedā€ as the op looks opposite to SinkOp. I think the name of NeverOp is better. :slight_smile:

#9

:+1: sounds good to me on both fronts.