title: Condition for memory access conflict in memory-banked vector processors
body: <p>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):</p>
  
  <p>(Number of banks) / LeastCommonMultiple(Number of banks, Stride) &lt; Bank busy time</p>
  
  <p>However, I think it should be GreatestCommonFactor instead of LCM, because memory conflict would occur if the <strong>effective number of banks</strong> 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).</p>
  
  <p>In fact, this formula even fails for the example given right below it. <em>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?</em> - 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).</p>
  
  <p>Am I getting it wrong, or has the wrong formula managed to survive 5 editions of this book (unlikely)?</p>