Condition for memory access conflict in memory-banked vector processors

Question

The Hennessy-Patterson book on Computer Architecture (Quantitative Approach 5ed) says that in a vector architecture with multiple memory banks, a bank conflict can happen if the following condition is met (Page 279 in 5ed):

(Number of banks) / LeastCommonMultiple(Number of banks, Stride) < Bank busy time

However, I think it should be GreatestCommonFactor instead of LCM, because memory conflict would occur if the effective number of banks you have is less than the busy time. By effective number of banks I mean this - let's say you have 8 banks, and a stride of 2. Then effectively you have 4 banks, because the memory accesses will be lined up only at four banks (e.g, let's say your accesses are all even numbers, starting from 0, then your accesses will be lined up at banks 0,2,4,6).

In fact, this formula even fails for the example given right below it. Suppose we have 8 memory banks with busy time of 6 clock cycles, with total memory latency of 12 clock cycles, how long will it take to complete a 64-element vector load with stride of 1? - Here they calculate the time as 12+64=76 clock cycles. However, memory bank conflict will occur according to the condition given, so we clearly can't have one access per cycle (64 in the equation).

Am I getting it wrong, or has the wrong formula managed to survive 5 editions of this book (unlikely)?

Answer 1

GCD(banks, stride) should come into it; your argument about that is correct.

Let's try this for a few different strides and see what we get, for number of banks = b = 8.

# generated with the calc(1) function
define f(s) { print s, "     |   ", lcm(s,8), "    |   ", gcd(s,8), "    |   ", 8/lcm(s,8), "      |   ", 8/gcd(s,8) }`

stride | LCM(s,b) | GCF(s,b) | b/LCM(s,b) |  b/GCF(s,b)
1      |    8     |    1     |    1       |    8     # 8 < 6 = false: no conflict
2      |    8     |    2     |    1       |    4     # 4 < 6 = true:  conflict
3      |    24    |    1     |   ~0.333   |    8     # 8 < 6 = false: no conflict
4      |    8     |    4     |    1       |    2     # 2 < 6 = true: conflict
5      |    40    |    1     |    0.2     |    8
6      |    24    |    2     |   ~0.333   |    4
7      |    56    |    1     |   ~0.143   |    8
8      |    8     |    8     |    1       |    1
9      |    72    |    1     |   ~0.111   |    8

x         >=8        2^0..3      <=1          1 2 4 or 8

b/LCM(s,b) is always <=1, so it always predicts conflicts.

I think GCF (aka GCD) looks right for the stride values I've looked at so far. You only have a problem if the stride doesn't distribute the accesses over all the banks, and that's what b/GCF(s,b) tells you.

---

Stride = 8 should be the worst-case, using the same bank every time. gcd(8,8) = lcm(8,8) = 8. So both expressions give 8/8 = 1 which is less than the bank busy/recovery time, thus correctly predicting conflicts.

Stride=1 is of course the best case (no conflicts if there are enough banks to hide the busy time). gcd(8,1) = 1 correctly predicts no conflicts: (8/1 = 8, which is not less than 6). lcm(8,1) = 8. (8/8 < 6 is true) incorrectly predicts conflicts.