2
$\begingroup$

Here's a screenshot of a diagram from my computer architecture course. You don't need to understand the technical terms here. It's essentially mapping locations from one piece of memory to locations in another piece of memory.

According to the book, we determine the mapping based on the following formula:

$\text{cacheLineNumber} \equiv \text{memoryAddress} \pmod{\text{numberOfLinesInCache}}$

For example, if we're looking at $\text{memoryAddress} = 00001$, and we have $\text{numberOfLinesInCache} = 8$ as in this diagram, then we have $1 \equiv 1\pmod{8}$. Thus, that memory address should map to the cache line numbered $001$.

enter image description here

Below the diagram is an explanation noting that this is the equivalent of using the lower $3$ bits of the given memory address. But I don't understand what the mathematical motivation is for this discovery. I see that it's true, but I don't get it.

$\endgroup$

2 Answers 2

1
$\begingroup$

Note that a number $$N = b_{n} b_{n-1} \cdots b_{4}b_{3}b_{2}b_{1}{}_{\text{two}} = b_1 + 2b_2 +4b_3 +8(b_4+2b_5+\cdots+2^{n-3}b_n).$$ Therefore, $$N \equiv b_1 + 2b_2 + 4b_3 +0 \equiv b_3 b_2 b_1 {}_{\text{two}}\pmod{8}.$$ Following the above procedure, it is easy to observe that $$b_{n} b_{n-1} \cdots b_{4}b_{3}b_{2}b_{1}{}_{\text{two}} \equiv b_{m} b_{m-1} \cdots b_{1}{}_{\text{two}} \pmod{2^{m}},$$ where $m \le n$.

$\endgroup$
4
  • $\begingroup$ I'm not sure I follow. Could you break down your reasoning in the steps? I've never been good at following math. $\endgroup$
    – AleksandrH
    Aug 3, 2018 at 17:38
  • $\begingroup$ @AleksandrH Can you please inform me which point is difficult to understand. I considered $N$ which has $n$-bit binary representation. The RHS is the decimal value of $N$. The term $8(b_4+2b_5+\cdots+2^{n-3}b_n)$ is a multiple of $8$. Therefore, $8(b_4+2b_5+\cdots+2^{n-3}b_n) \equiv 0 \pmod{8}$. $\endgroup$
    – Math Lover
    Aug 3, 2018 at 17:41
  • $\begingroup$ I don't understand how that last term suddenly became a $0$. $\endgroup$
    – AleksandrH
    Aug 3, 2018 at 17:53
  • $\begingroup$ @AleksandrH Note that $8 \times x \equiv 0 \pmod{8}$, where $x$ is an integer. For example, $8 \times 2 \equiv 0 \pmod{8}$. $\endgroup$
    – Math Lover
    Aug 3, 2018 at 18:47
0
$\begingroup$

I felt the other answer still didn't clear up my confusion, but messing around with the numbers on paper, I managed to arrive at an explanation (I think this is somewhat similar to what @Math Lover was saying, but the answer he/she gave was a bit confusing):

If I consider $00101$, that's:

$0*2^4+0*2^3+1*2^2+0*2^1+1*2^0$

And we can isolate $2^3 = 8$ from the two frontmost terms (in fact, from all terms in front of $2^3$, no matter how many bits there are in the string:

$2^3 (0) + (1*2^2 + 0*2^1 + 1*2^0)$

And that matches the format of:

$n = dq + r$

Where $r$ is the remainder.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.