MrXL: allow different commands on the same memory to have different banking factors

[anshumanmohan]

This probably would have been picked up along the way to #1414 anyway, but I'd like it sooner for tutorial purposes (#1457).

I currently cannot compile the following sum of squares program:

input avec: int[4]
output sos: int[4]
squares := map 2 (a <- avec) { a * a }
sos := reduce 1 (acc, i <- squares) 0 { acc + i }

It interprets fine, but mrxl test/sos.mrxl gives

...
Exception: Previous use of `squares` had banking factor 2 but current use has banking factor 1

Increasing the parallelism factor of reduce is not an option, since that is not implemented. This means I'm left with

input avec: int[4]
output sos: int[4]
squares := map 1 (a <- avec) { a * a }
sos := reduce 1 (acc, i <- squares) 0 { acc + i }

which is a much weaker program to work with pedagogically.

[anshumanmohan]

I gave it some more thought. I think an array needs to be banked per the LCM of the various parallelism factors that ever parallelize the array. For example,

input avec: int[24]
squares := map 4 (a <- avec) { a * a }
add5 := map 3 (a <- avec) { a + 5 }
...

• In the data file we need to convert avec into 12 banks, avec_b0 through avec_b11.
• When squares is being computed, we sorta re-group those 12 banks into 4, not via any actual re-banking but just by considering avec_b0, avec_b1, and avec_b2, to be contiguous, avec_b3, avec_b4, and avec_b5, to be contiguous, and so on.
• Similarly, when add5 is being computed, we re-group into 3 banks.

I've laid out the general case, but in practice array-lengths and parallelism factors will probably all be powers of 2, so this will be easier: just bank per the finest parallelism factor, and then re-group as necessary.

[anshumanmohan]

After the meeting we just had, it appears I have arrived at the need for arbitration logic. Rachit thinks that this is going to be hard, harder possibly than going the whole hog and implementing reduction trees (#1414).

Resolutions:

1. Tweak the tutorial so that it starts with the less-good (because fully-sequential) example:

    input avec: int[4]
    output sos: int[4]
    squares := map 1 (a <- avec) { a * a }
    sos := reduce 1 (acc, i <- squares) 0 { acc + i }
   

2. Later in the tutorial, introduce a new example that does map without reduce. Use this to show how banking works. Not as nice as having one running example, but ah well.

3. Meanwhile, try out a small arbitration logic using ref cells. #1474

[anshumanmohan]

Done with 1 and 2 above. PR https://github.com/cucapra/calyx/pull/1473 is once again ready for review.

[anshumanmohan]

I'm taking this off the tutorial milestone; the new in-milestone target is #1474. I will incorporate some of the discussion above into my educational slide/handout so that they can see how the sample code created by #1474 will lead them to the solution to this issue.

[anshumanmohan]

@rachitnigam should we just close this as a wontfix? Or maybe convert it into a discussion or somesuch?

[rachitnigam]

Maybe the "Low Priority" tag is in order? The task does seem pretty actionable but probably not critical for anyone's use. However, I think in the past @sampsyo has voted in favor keeping issues like this open as a way to onboard new people.

[sampsyo]

A "low priority" label sounds about right to me!

[anshumanmohan]

Done deal!