| Author |
Message |
Chad
Guest
|
 Posted:
Thu Oct 20, 2005 8:15 am Post subject:
I need a general idea how to solve this problem. |
|
|
neend a general idea how to solve the following:
Array A contains 256 elements of 4 bytes each. Its first element is
stored at physical address 4,096.
Array B contains 512 elements of 4 bytes each. Its first element is
stored at physical address 8,192.
Assume that only arrays A nd B can be cached in an intitially empty
physically address, physically tagge, direct-mapped, 2k-byte cache with
an 8-byte block size. The following loop is then executed.
for (i=0; i < 256; i++)
A[i] = A[i] + B[2*i];
I)During the execution of the loop, how many bytes will be written to
memory if the cache has write-through policy?
II)During the execution of the loop, how many bytes will be written to
memory if the cache has a write-back policy? |
|
| Back to top |
|
 |
Amitabha Roy
Guest
|
| Posted:
Thu Oct 20, 2005 8:15 am Post subject:
Re: I need a general idea how to solve this problem. |
|
|
Since the cache is direct mapped[2k], it seems A (@ memory 4k -5k) and
B (@ memory 8k-9k) will conflict with each other.
All accesses to A and B will be compulsory misses (other that locality on
the same cache line).
I) I think for a write through cache the entire A array will be written out.
So that is 256*4=1024bytes
II) This is harder (IMHO).
A[i] = A[i] + B[2*i] ... I'm assuming first the access to B is done.
Then a Read for Ownership is sent out for A. In that case the access
pattern is 4*i for A and 8*i for B.
A B
0 0 i=0
4 8 i=1 (no need to evict line 0)
8 16 i=2 (no need to evict line 1)
......
So, since B is always at an ever increasing stride distance from A
dirtied lines by A never need to be evicted (since 8*i -4*i =4*i > 8 when i > 2)
It seems there would be no writebacks at all.
Chad wrote:
| Quote: | neend a general idea how to solve the following:
Array A contains 256 elements of 4 bytes each. Its first element is
stored at physical address 4,096.
Array B contains 512 elements of 4 bytes each. Its first element is
stored at physical address 8,192.
Assume that only arrays A nd B can be cached in an intitially empty
physically address, physically tagge, direct-mapped, 2k-byte cache with
an 8-byte block size. The following loop is then executed.
for (i=0; i < 256; i++)
A[i] = A[i] + B[2*i];
I)During the execution of the loop, how many bytes will be written to
memory if the cache has write-through policy?
II)During the execution of the loop, how many bytes will be written to
memory if the cache has a write-back policy?
|
|
|
| Back to top |
|
|
Del Cecchi
Guest
|
| Posted:
Fri Oct 21, 2005 8:09 am Post subject:
Re: I need a general idea how to solve this problem. |
|
|
"Chad" <cdalten@gmail.com> wrote in message
news:1129781853.488457.62070@g43g2000cwa.googlegroups.com...
| Quote: | neend a general idea how to solve the following:
Array A contains 256 elements of 4 bytes each. Its first element is
stored at physical address 4,096.
Array B contains 512 elements of 4 bytes each. Its first element is
stored at physical address 8,192.
Assume that only arrays A nd B can be cached in an intitially empty
physically address, physically tagge, direct-mapped, 2k-byte cache with
an 8-byte block size. The following loop is then executed.
for (i=0; i < 256; i++)
A[i] = A[i] + B[2*i];
I)During the execution of the loop, how many bytes will be written to
memory if the cache has write-through policy?
II)During the execution of the loop, how many bytes will be written to
memory if the cache has a write-back policy?
Why don't you do a pencil and paper simulation of the first few steps. |
Then the pattern should become clear |
|
| Back to top |
|
|
David Kanter
Guest
|
| Posted:
Fri Oct 21, 2005 8:15 am Post subject:
Re: I need a general idea how to solve this problem. |
|
|
| Quote: | Why don't you do a pencil and paper simulation of the first few steps.
Then the pattern should become clear
|
Del, you're losing your edge. Usually you're very good at coming up
with 'innovative' and wrong answers to such problems...where has the
artistry in comp.arch gone?
And what the hell was up with the guy who actually answered in the
first place...
David |
|
| Back to top |
|
|
Del Cecchi
Guest
|
| Posted:
Fri Oct 21, 2005 4:15 pm Post subject:
Re: I need a general idea how to solve this problem. |
|
|
David Kanter wrote:
| Quote: | Why don't you do a pencil and paper simulation of the first few steps.
Then the pattern should become clear
Del, you're losing your edge. Usually you're very good at coming up
with 'innovative' and wrong answers to such problems...where has the
artistry in comp.arch gone?
And what the hell was up with the guy who actually answered in the
first place...
David
Sorry, I was having an off day. And it was hard to come up with a hook |
for the wrong answer.
--
Del Cecchi
"This post is my own and doesn’t necessarily represent IBM’s positions,
strategies or opinions.” |
|
| Back to top |
|
|
David Kanter
Guest
|
| Posted:
Sat Oct 22, 2005 1:31 pm Post subject:
Re: I need a general idea how to solve this problem. |
|
|
| Quote: | Sorry, I was having an off day. And it was hard to come up with a hook
for the wrong answer.
|
Apology accepted : )
FWIW, that's the part I really have trouble with, something plausible
enough but actually at least 70% bullshit (TM). That's why I let those
with more practice handle such things...
DK |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in