Open anshumanmohan opened 1 year ago
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 }
...
avec
into 12 banks, avec_b0
through avec_b11
. 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.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.
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:
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 }
map
without reduce
. Use this to show how banking works. Not as nice as having one running example, but ah well.ref
cells. #1474 Done with 1 and 2 above. PR https://github.com/cucapra/calyx/pull/1473 is once again ready for review.
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.
@rachitnigam should we just close this as a wontfix? Or maybe convert it into a discussion or somesuch?
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.
A "low priority" label sounds about right to me!
Done deal!
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:
It interprets fine, but
mrxl test/sos.mrxl
givesIncreasing the parallelism factor of
reduce
is not an option, since that is not implemented. This means I'm left withwhich is a much weaker program to work with pedagogically.