Tutorial: toy arbitration logic

[anshumanmohan]

Try out a small arbitration logic using ref cells.

This will be a component that takes two ref cells as input, but itself exposes the interface of one memory. Internally, it logically bridges the two as needed.

In pseudocode:

a = [0,1,2,3]
b = [4,5,6,7]
as_one = wrapper(a,b)
assert (as_one[0] == 0)
assert (as_one[4] == 4)

Note that wrapper has not actually made new components.
When asked for index 0 it knows it can just read off a.
When asked for index 4 it knows it must skip over a and read off b.

Originally posted by @anshumanmohan in #1472 (comment)

[sampsyo]

Pretty solid idea!

[anshumanmohan]

I've made some progress and hit a few roadblocks. Some are likely silly and some deep, but it's time to get y'all involved, I think. The code to look at is here; run it with python test/arbitration.py.

I have a bunch of inline comments, and the ones tagged "AM" could use some love. Many thanks!

[anshumanmohan]

Here's what I'd like to have by the time the tutorial rolls around:

 component wrap2 (i: int32, j: int32) -> int32 {
    // You pass six memories of length 4 each and then get to pretend they are two memories of length 12 each.
    // 0 <= i < 2
    // 0 <= j < 12
    // Returns the j-th element of the i-th memory.
    
    ref mem1 = std_mem_d1(32, 4);  // Six memories that will be passed by reference.
    ...
    ref mem6 = std_mem_d1(32, 4);
    
    ... hella math ...
 }

component wrap3 (i: int32, j: int32) -> int32 {
    // You pass six memories of length 4 each and then get to pretend they are three memories of length 8 each.
    // 0 <= i < 3
    // 0 <= j < 8
    // Returns the j-th element of the i-th memory.
    
    ref mem1 = std_mem_d1(32, 4);  // Six memories that will be passed by reference.
    ...
    ref mem6 = std_mem_d1(32, 4);
    
    ... hella math ...
 }
 
component main () {
    A = std_mem_d1(32, 4);   // Six memories.
    ...
    F = std_mem_d1(32, 4);

    as_two = wrap2();
    as_three = wrap3();
    
    invoke as_two[mem1 = A, ..., mem6 = F](i = 1, j = 11);
    invoke as_three[mem1 = A, ..., mem6 = F](i = 2, j = 6); 
}

[anshumanmohan]

Perhaps this would overfitted to this problem, but I can imagine a whole bunch of quality-of-life improvements in the builder library in service of this task. Partial-application of invoke seems like a really nice one, for example. Then I could have:

component main () {
    A = std_mem_d1(32, 4);   // Six memories.
    ...
    F = std_mem_d1(32, 4);

    as_two = wrap2();
    as_three = wrap3();
    
    as_two_ = partially_invoke as_two[mem1 = A, ..., mem6 = F];
    as_three_ = partially_invoke as_three[mem1 = A, ..., mem6 = F];
    
    invoke as_two_(i = 1, j = 11);
    invoke as_three_(i = 2, j = 6); 
}

[sampsyo]

This looks like the right ballpark to me. FWIW, I think your idea for "partial application" for invokes there could fortunately be not too hard to write as a plain ol' Python function within the MrXL compiler… that is, you could prototype a utility like that (takes the ref-cell bindings, returns a function to "finish" constructing the invoke with input ports) and see how it works here. If it does seem cool and reusable, we could move it to the builder library.

[rachitnigam]

@anshumanmohan I would make sure that you can handwrite a version of the arbiter in Calyx before attempting to implement it through the builder library. Otherwise, one failure mode is discovering limitations in Calyx and having to refactor your python code.

[anshumanmohan]

I've begun work on the handwritten version and I have a question about invoke. I've looked at:

1. https://docs.calyxir.org/lang/ref.html?highlight=invoke#invoke
2. https://docs.calyxir.org/lang/ref.html?highlight=invoke#ref-cells
3. https://docs.calyxir.org/lang/memories-by-reference.html

And I'm not sure why, in 3, we seem to be clobbering the invoked component's outputs.

As you can sorta see from my "dream" example in pseduo-Calyx above, I'd like to echo the invoked component's outputs.

[anshumanmohan]

Alrighty, here is my handwritten file!

Run it by changing to this branch, changing to calyx/calyx-py/test/, and running:

fud exec arbitrage_handrwitten.futil --to dat --through verilog -s verilog.data arbitrage.data

It goes forever, and help re: that is much appreciated.

Further, the question re: invoke is blocking me.

Once we get this running, the dream is not far!

[rachitnigam]

Can you explain what you mean by clobbering the outputs? The invoked component in the example doesn’t have any outputs but if it did, you could just forward them.

[anshumanmohan]

Whoops the link went to the page, not the section. I wanted you to look at this.

The component copy has three inputs and four outputs. It has no ref cells. In component main, we invoke copy0 by:

1. Passing any ref cells using a [foreign = local] syntax. There are no ref cells in copy, so there is no [] block in this invocation.

2. Passing inputs using the (foreign = local) syntax, which is what you're doing below. I understand this, I think.

    (dest_done=d.done, src_read_data=s.read_data, length=length.out)
   

3. Now the output stuff was confusing me; it felt to me like some kind of clobber. However, now that I think about it, maybe it's just that you kept the (foreign = local) syntax but I implicitly expected a (local = foreign) syntax. The specific thing you have is:

    (dest_write_data=d.write_data, dest_write_en=d.write_en, dest_addr0=d.addr0, src_addr0=s.addr0) 
   

To make sure I'm getting this right:

• I originally thought that we received some value in dest_write_data and then clobbered it with d.write_data, following the right-to-left assignment notation.
• Actually, we are taking dest_write_data's value and putting it into d.write_data. It's just a left-to-right assignment.

Is that right? And, relatedly, is this what you mean by forwarding?

[rachitnigam]

Yup, you are correct. For the inputs, the syntax is sane, for the outputs, it is not but it does the expected things. For example:

invoke foo(in = p)(out = q)

Is the same as:

group inv_foo {
  foo.go = 1'd1;
  foo.in = p;
  q = foo.out;
  inv_foo[done] = foo.done;
}

An easy way to figure out what the generated code will do is to compile away the invokes:

calyx -p validate -p compile-refs -p compile-invoke <file>

[rachitnigam]

One annoying problem with the above is that the q = foo.out assignment is only active when the invoke is executed. If you want the semantics that std_mem_* give you for reads (which is not a good semantics), you'd need something more complicated to allow for combinational reads.

An alternative is switching to seq_mem_* which provide sequential reads in addition to sequential writes which means that the output port of the memory is guaranteed to hold the value after the invoke is executed.

[anshumanmohan]

Ah nice nice. Thanks for the example, and for the pointer re: compiling away the invokes. Tomorrow I'll work on this and get closer to my goal. I'll ponder re: the semantics I want and play with your suggestions.

One option that occurred to me was to:

1. Have the invoked group have no output.
2. Have the invoked group have a ref ans memory in addition to the other memories I need.
3. When invoking the group, pass the memories I need by reference, plus a local, zeroed-out, ans_holder cell for the ref ans. Plus any inputs, as usual.
4. After the invoke is done, hey presto, the answer is sitting in my local ans_holder.

Sound okay, or known to be bad idea?

[anshumanmohan]

Quick update: I went with the proposal above and a baby version works great. Now on to the dream.

[sampsyo]

FWIW, the ans_holder approach outlined here is not too different from @rachitnigam's suggestion to match the behavior of seq_mem_*, which essentially have an ans_holder register built in. (The difference, of course, is that it's passed in from the outside instead, which has its own advantages.)