What do the B,a, and P parameters refer to on the controller tree

[Ben Ghaem]

Hi, when reading the memory information in the controller_tree.html file, what do the banking parameters B,a,P refer to? Thanks, Ben

[Matt F]

Those are the parameters used in the bank resolution equations.  Writing an easy-to-read tutorial on how banking works in spatial is still on my todo list, but here is the high level summary of banking, which should give insight about what the parameters mean.

Banking is how the compiler lets you access data in parallel from an SRAM when the underlying resource only has 1 (or maybe 2) ports).  It constructs the logical SRAM in the source code by composing it from smaller SRAMs and laying out the math to handle the address virtualization.

Banking is either done multi-dimensionally (you have a bank address per-dimension of your memory), or flat (the bank address is a scalar).    In the flat case, N and B are scalars, otherwise they are vectors with as many elements as dimensions of the memory.  a and P are always vectors with as many elements as dimensions of the memory.

In short, here are the definitions, which don't mean too much until you see the equations below.

N = number of banks

B = blocking factor

a = partitioning vector

P = neighborhood partitioning

Given some multidimensional address (x) to a memory, we resolve that to a bank address (BA) that tells us which physical memory contains the element, and a bank offset (BO) that tells us which offset within that memory the actual element is stored in.  The equations for flat banknig are:

R stands for "Region" and C stands for "Correction."  The vast majority of the time, B = 1 so you can pretend the correction doesn't exist.  Essentially, bank address is a MAC + mod operation and bank offset is a mix of divisions, multiplications, and additions.  Bank offset basically divides the logical memory into neighborhoods with dimensions P, then numbers them and figures out which "neighborhood" your address lives in.  For B = 1, each neighborhood has one element from each bank, so they can all have the same bank offset.  There are all kinds of tricks that the compiler plays to avoid expensive multiply, divide, and mod operations.  For example, when N, a, P, and B are powers of 2, the arithmetic can be done with bitwise ops.

For the multi-dimensional banking case, just treat each dimension as its own 1-dimensional access pattern and use the equations above to get a BA per-dimension, and a scalar value for BO.

The report should also give you read/write histograms, which are useful for understanding how resource-intensive schemes are for the patterns you have in your app.  For a lot of cases, after your app is fully unrolled, certain readers/writers to the memory can only "see" certain banks based on the equations above (i.e. alpha = 2, N = 4, B = 1, no matter what x is, this access will only ever see banks 0 or 2).  The histogram gives you a sense of how big the crossbars have to be to serve all of the accesses, where each access knows how many banks it can "see"

I'm skipping all the details about how to actually choose N, B, a, and P but I can talk about that if you want to dig deeper into this.  

I think the best way to understand what these equations really mean is to sit for a minute with a simple example of banking parameters and just write out the BA and BO starting from the origin.  It is much simpler than it may seem at first.  For example:

N = 4, B = 1, alpha = <1,2>, P = <2,2> for a 4x4 memory

Banks:

0..2..0..2
1..3..1..3
2..0..2..0
3..1..3..1

Offsets:

0..0..1..1
0..0..1..1
2..2..3..3
2..2..3..3

Then overlay your access pattern on this and prove to yourself that no accesses will ever ask for the same bank at the same time.   Here is what the access pattern may have looked like to get this banking scheme:

Foreach(4 by 1, 4 by 1 par 2){(i,j) => x(i,j) = ...}

x..x..-..-

-..-..-..-

-..-..-..-

-..-..-..-

Foreach(4 by 1 par 4, 4 by 1){(i,j) => ... = x(i,j)}

x..-..-..-

x..-..-..-

x..-..-..-

x..-..-..-

[Ben Ghaem]

Thank you Matt. This is super helpful.