Direct/Associative Cache question

CASTalk.com
Discussion of DSP, FPGA, storage and embedded system.

FAQ

Memberlist

Profile

Direct/Associative Cache question

CASTalk.com Forum Index -> Computer Architecture

Author

Message

Guest

Posted: Sat Dec 11, 2004 6:15 am Post subject: Direct/Associative Cache question

Hi everyone, I'm trying to do a review problem for an upcoming final in my architecture class. However, I'm at a loss on how to solve the question and couldn't find anything relevant in my notes, book, or google. The question is: "A computer system has 16MB of MM (main memory) and an 8K set assocative cache. The cache block size is 16 bytes and the TAG field of the MM address is 14bit wide. If the same cache were direct mapped then the MM address will have a 11bit TAG field. Determine the total data bytes in the cache as well as cache set associativity. " I seem to be stuck because I don't know if its 2-way or 4-way etc. Can anyone give me some hints or an explanation?

Dennis M. O'Connor
Guest

Posted: Sat Dec 11, 2004 10:51 am Post subject: Re: Direct/Associative Cache question

<xinocard@hotmail.com> wrote ...

Quote:

I could, but I won't., because at this stage in your architecture
class, if you don't already know how to solve this easy problem,
then you don't understand caches at all, and you deserve to fail.

That said, the question itself is incompetently phrased.
Still, it contains everything you need to get the answer.
--
Dennis M. O'Connor dmoc@primenet.com

xino
Guest

Posted: Sat Dec 11, 2004 12:13 pm Post subject: Re: Direct/Associative Cache question

Dennis M. O'Connor wrote:

Quote:

xinocard@hotmail.com> wrote ...
I'm trying to do a review problem for an upcoming final in my
architecture class. However, I'm at a loss on how to solve the
question
and couldn't find anything relevant in my notes, book, or google.
The
question is:

"A computer system has 16MB of MM (main memory) and an 8K set
assocative cache. The cache block size is 16 bytes and the TAG
field of
the MM address is 14bit wide. If the same cache were direct mapped
then
the MM address will have a 11bit TAG field. Determine the total
data
bytes in the cache as well as cache set associativity. "

I seem to be stuck because I don't know if its 2-way or 4-way etc.
Can anyone give me some hints or an explanation?

I could, but I won't., because at this stage in your architecture
class, if you don't already know how to solve this easy problem,
then you don't understand caches at all, and you deserve to fail.

That said, the question itself is incompetently phrased.
Still, it contains everything you need to get the answer.
--
Dennis M. O'Connor dmoc@primenet.com

Can you rephrase the question because I think thats the stumbling
block.
If your going to flame, please don't respond. Regarding the class it
was more of a digital logic/design class (also used no book). For my
project
I simulated and implented on an FPGA a RISC processor was a small
instruction set while you were implenting a carry ripple adder. So,
please rephrase the question or give some instruction/tips instead of
being an ass.

Thanks,

Jouni Osmala
Guest

Posted: Sat Dec 11, 2004 2:34 pm Post subject: Re: Direct/Associative Cache question

Quote:

I'm trying to do a review problem for an upcoming final in my
architecture class. However, I'm at a loss on how to solve the

question

and couldn't find anything relevant in my notes, book, or google.

The

question is:

"A computer system has 16MB of MM (main memory) and an 8K set
assocative cache. The cache block size is 16 bytes and the TAG

field of

the MM address is 14bit wide. If the same cache were direct mapped

then

the MM address will have a 11bit TAG field. Determine the total

data

bytes in the cache as well as cache set associativity. "

I seem to be stuck because I don't know if its 2-way or 4-way etc.
Can anyone give me some hints or an explanation?

I could, but I won't., because at this stage in your architecture
class, if you don't already know how to solve this easy problem,
then you don't understand caches at all, and you deserve to fail.

That said, the question itself is incompetently phrased.
Still, it contains everything you need to get the answer.
--
Dennis M. O'Connor dmoc@primenet.com

Can you rephrase the question because I think thats the stumbling
block.
If your going to flame, please don't respond. Regarding the class it
was more of a digital logic/design class (also used no book). For my
project
I simulated and implented on an FPGA a RISC processor was a small
instruction set while you were implenting a carry ripple adder. So,
please rephrase the question or give some instruction/tips instead of
being an ass.

Thanks,

Okay I'll answer your schoolwork question traditional comp.arch way
You have 2^20 words of main memory, and you map it to n words that some
are shared in y locations. Easiest way to solve the problem is to build
it in FPGA and experiment with different n and y. I'd recommend you to
use VHDL for it's really easy.

Jouni Osmala
Helsinki University of Technology
Student
-People with more industry experience can give you more clever answer.

Magnus Ekman
Guest

Posted: Sat Dec 11, 2004 2:56 pm Post subject: Re: Direct/Associative Cache question

On 10 Dec 2004 xinocard@hotmail.com wrote:

Quote:

Hi everyone,

Hi, I hope that my explanation below helps. Perhaps I violate some
unwritten rule that we should not help students in this forum but I can't
see why that would be wrong.

Quote:

It seems to me that the total number of address bits is 24 (2^24=16MB).
We know that the tag is 14 bit. The block offset is 4 bit (2^4=16B). Thus,
the number of index bits seem to be 6:

tag index blockoffset
ttttttttttttttiiiiiibbbb

We also know that a direct mapped cache would have 11 tag bits. That is:
tag indes blockoffset
tttttttttttiiiiiiiiibbbb

When going from direct mapped to set associative we reduce the number of
index bits by 9-6=3. Thus the associativity is 2^3=8.

The size of the direct mapped cache is
(2^index)*block_size=(2^9)*16=512*16=8K. (or if you want to calculate it
from the associative cache (2^(index+log2associativity))*block_size
=(2^(6+3)*16=8K).

/Magnus

Jouni Osmala
Guest

Posted: Sat Dec 11, 2004 4:09 pm Post subject: Re: Direct/Associative Cache question

Magnus Ekman wrote:

Quote:

The rule goes, thou shall willingly give answer with a nice grin in your
face. Most Usenet groups are openly hostile for answering homework
questions. But comp.arch is not. We are HAPPY to give a nice answers ;)

Here is example:

Quote:

Where can I find information on the deign of a simple architecture
machine instruction set for a 32-bit processor with 16 registers r0 to
r15 and with 24-bit memory addressing

It surely looks like VAX to me, VAX is 32bit processor with 16
registers from r0-r15 and I'm not absolutely sure about the memory
addressing should fit the discription but the processor design looks
like the simpliest possible. It even avoids some of current complexity
of making branches by putting program counter as a standard register.

http://fakkir.net/~elzubeir/papers/vax.pdf
http://portal.acm.org/citation.cfm?doid=285930.285934
http://www.vaxarchive.org/hw/full.html

Some history of it.
http://www.internet-tips.net/Misc/VAXhistory.htm

After reading these you should have some ideas how to make a simple
32bit architecture with 16 registers.

---------------------------------------------------------------------

-> can anyone help me in the solving the Q.s below:

Yes! We haven't had one of these in a few weeks now, lots of people here
have been waiting for the chance to help out.

Quote:

1. In 50x CDROM, what 20 and x means?

That this CDROM will attempt to overwrite all destinations at least 50
(or 20?) times, to make sure that the CD data is copied correctly.

Quote:

2. what is the best computer arch. book?

Probably the one I'm currently writing, if you send me a small advance,
I'll make sure you'll get an early copy!

Quote:

3. when computer start,a DMI pool message is appeared, what this
message mean and what is DMI pool?

A cross between British and American pool, played with slightly longer
queues. (Queuing theory was based on this work!)

Quote:

4. what are the differeneces between SCSI and IDE arch.s?

None that really matter.

Quote:

5. what raw devices mean, can you give me some exampls?

The opposite of cooked, i.e. a device which hasn't so far been left
exposed on the dashboard of a car parked in the sun.

Quote:

6. How many RAID level are availabe and can you give me a breif
descriptions about each one?

RAID is a trademark bug spray, as far as I know they only make one or
two different kinds (but there's probably several sizes, which might
count!).

Glad to help!
---------------------------------------------------------------
These should give you some hint what todo for homework questions the
comp.arch way.
It has been discussed here and the discussion can be found in
groups.google.com . As both of my examples are from there.

Jouni Osmala

xino
Guest

Posted: Sat Dec 11, 2004 4:43 pm Post subject: Re: Direct/Associative Cache question

Thank you so much,
I understand the concept and usefulness of caches.
I just get lost in the details of computation without
proper notes or examples.

Magnus Ekman wrote:

Quote:

On 10 Dec 2004 xinocard@hotmail.com wrote:

Hi everyone,

Hi, I hope that my explanation below helps. Perhaps I violate some
unwritten rule that we should not help students in this forum but I
can't
see why that would be wrong.

I'm trying to do a review problem for an upcoming final in my
architecture class. However, I'm at a loss on how to solve the
question
and couldn't find anything relevant in my notes, book, or google.
The
question is:

"A computer system has 16MB of MM (main memory) and an 8K set
assocative cache. The cache block size is 16 bytes and the TAG
field of
the MM address is 14bit wide. If the same cache were direct mapped
then
the MM address will have a 11bit TAG field. Determine the total
data
bytes in the cache as well as cache set associativity. "

I seem to be stuck because I don't know if its 2-way or 4-way etc.
Can anyone give me some hints or an explanation?

It seems to me that the total number of address bits is 24
(2^24=16MB).
We know that the tag is 14 bit. The block offset is 4 bit (2^4=16B).
Thus,
the number of index bits seem to be 6:

tag index blockoffset
ttttttttttttttiiiiiibbbb

We also know that a direct mapped cache would have 11 tag bits. That
is:
tag indes blockoffset
tttttttttttiiiiiiiiibbbb

When going from direct mapped to set associative we reduce the number
of
index bits by 9-6=3. Thus the associativity is 2^3=8.

The size of the direct mapped cache is
(2^index)*block_size=(2^9)*16=512*16=8K. (or if you want to calculate
it
from the associative cache (2^(index+log2associativity))*block_size
=(2^(6+3)*16=8K).

/Magnus

del cecchi
Guest

Posted: Sun Dec 12, 2004 8:32 am Post subject: Re: Direct/Associative Cache question

"xino" <xinocard@hotmail.com> wrote in message
news:1102749238.447597.158080@z14g2000cwz.googlegroups.com...

Quote:

Dennis M. O'Connor wrote:
xinocard@hotmail.com> wrote ...
I'm trying to do a review problem for an upcoming final in my
architecture class. However, I'm at a loss on how to solve the
question
and couldn't find anything relevant in my notes, book, or google.
The
question is:

"A computer system has 16MB of MM (main memory) and an 8K set
assocative cache. The cache block size is 16 bytes and the TAG
field of
the MM address is 14bit wide. If the same cache were direct mapped
then
the MM address will have a 11bit TAG field. Determine the total
data
bytes in the cache as well as cache set associativity. "

I seem to be stuck because I don't know if its 2-way or 4-way etc.
Can anyone give me some hints or an explanation?

I could, but I won't., because at this stage in your architecture
class, if you don't already know how to solve this easy problem,
then you don't understand caches at all, and you deserve to fail.

That said, the question itself is incompetently phrased.
Still, it contains everything you need to get the answer.
--
Dennis M. O'Connor dmoc@primenet.com

Can you rephrase the question because I think thats the stumbling
block.
If your going to flame, please don't respond. Regarding the class it
was more of a digital logic/design class (also used no book). For my
project
I simulated and implented on an FPGA a RISC processor was a small
instruction set while you were implenting a carry ripple adder. So,
please rephrase the question or give some instruction/tips instead of
being an ass.

Thanks,

Trick question. the question says the cache is 8k, then proceeds to ask
to determine bytes in cache. Even a circuit designer can figure out the
answer is 8k. What's the next question, who is buried in Grant's tomb?

del cecchi
>

Dennis M. O'Connor
Guest

Posted: Sun Dec 12, 2004 9:43 am Post subject: Re: Direct/Associative Cache question

"del cecchi" <dcecchi.nojunk@att.net> wrote

Quote:

"xino" <xinocard@hotmail.com> wrote in message
news:1102749238.447597.158080@z14g2000cwz.googlegroups.com...

Dennis M. O'Connor wrote:
xinocard@hotmail.com> wrote ...
I'm trying to do a review problem for an upcoming final in my
architecture class. However, I'm at a loss on how to solve
the question and couldn't find anything relevant in my notes,
book, or google. The question is:

"A computer system has 16MB of MM (main memory) and an 8K set
assocative cache. The cache block size is 16 bytes and the TAG
field of the MM address is 14bit wide. If the same cache were direct
mapped then the MM address will have a 11bit TAG field. Determine
the total data bytes in the cache as well as cache set associativity. "

I seem to be stuck because I don't know if its 2-way or 4-way etc.
Can anyone give me some hints or an explanation?

I could, but I won't., because at this stage in your architecture
class, if you don't already know how to solve this easy problem,
then you don't understand caches at all, and you deserve to fail.

That said, the question itself is incompetently phrased.
Still, it contains everything you need to get the answer.
--
Dennis M. O'Connor dmoc@primenet.com

Can you rephrase the question because I think thats the stumbling
block. If your going to flame, please don't respond.

Oh, like I'm going to do or not do anything
just because this dweeb asks me.

Quote:

Regarding the class it was more of a digital logic/design class
(also used no book). For my project
I simulated and implented on an FPGA a RISC processor was a small
instruction set while you were implenting a carry ripple adder.

What a bozo. I don't know who he thinks I am, but I doubt he
thinks I am microprocessor architect working for Intel Corporation.
Which, as it happens, I am.

Quote:

So, please rephrase the question or give some instruction/tips
instead of being an ass.

Wow, talk about gall.

Quote:

It also has lots of irrelevant data: main memory size (as opposed
to maximum addressable memory, a totally different thing) and
the cache block (as opposed to line, BTW) size. Neither is needed.
--
Dennis M. O'Connor dmoc@primenet.com

xino
Guest

Posted: Mon Dec 13, 2004 1:07 am Post subject: Re: Direct/Associative Cache question

Quote:

What a bozo. I don't know who he thinks I am, but I doubt he
thinks I am microprocessor architect working for Intel Corporation.
Which, as it happens, I am
Lol, no wonder AMD has been kicking your ass so much lately.

Dennis M. O'Connor
Guest

Posted: Mon Dec 13, 2004 5:42 am Post subject: Re: Direct/Associative Cache question

"xino" <xinocard@hotmail.com> wrote ...

Quote:

What a bozo. I don't know who he thinks I am, but I doubt he
thinks I am microprocessor architect working for Intel Corporation.
Which, as it happens, I am

Lol, no wonder AMD has been kicking your ass so much lately.

I don't work on IA32, idiot. AMD doesn't make any products
that compete with the processors my group makes.

Now folks, do you see another reason why you
shouldn't answer homework questions ? The kind
of punk loser that would come here and ask is almost
always a cheating sleazebag and total asshole.
We WANT them to fail, because we don't want
them working in the cube next to ours.
--
Dennis M. O'Connor dmoc@primenet.com

David
Guest

Posted: Mon Dec 13, 2004 1:25 pm Post subject: Re: Direct/Associative Cache question

On Sat, 11 Dec 2004 10:56:39 +0100, Magnus Ekman wrote:

Quote:

On 10 Dec 2004 xinocard@hotmail.com wrote:

Hi everyone,

Hi, I hope that my explanation below helps. Perhaps I violate some
unwritten rule that we should not help students in this forum but I can't
see why that would be wrong.

I'm trying to do a review problem for an upcoming final in my
architecture class. However, I'm at a loss on how to solve the question
and couldn't find anything relevant in my notes, book, or google. The
question is:

"A computer system has 16MB of MM (main memory) and an 8K set
assocative cache. The cache block size is 16 bytes and the TAG field of
the MM address is 14bit wide. If the same cache were direct mapped then
the MM address will have a 11bit TAG field. Determine the total data
bytes in the cache as well as cache set associativity. "

I seem to be stuck because I don't know if its 2-way or 4-way etc.
Can anyone give me some hints or an explanation?

It seems to me that the total number of address bits is 24 (2^24=16MB).
We know that the tag is 14 bit. The block offset is 4 bit (2^4=16B). Thus,
the number of index bits seem to be 6:

tag index blockoffset
ttttttttttttttiiiiiibbbb

We also know that a direct mapped cache would have 11 tag bits. That is:
tag indes blockoffset
tttttttttttiiiiiiiiibbbb

When going from direct mapped to set associative we reduce the number of
index bits by 9-6=3. Thus the associativity is 2^3=8.

The size of the direct mapped cache is
(2^index)*block_size=(2^9)*16=512*16=8K. (or if you want to calculate it
from the associative cache (2^(index+log2associativity))*block_size
=(2^(6+3)*16=8K).

/Magnus

Perhaps I'm missing the humour in this post (maybe the sarcasm is too deep
for me before my first coffee). The data size is 8k - the question tells
us this, so no work is needed. Telling us that the tag would be 11 bit
for a direct-mapped cache is redundant, since 16M/8k = 11bit. The
associativity is simply 14bit/11bit = 3bit = 8. The question requires no
understanding of "cache" beyond a comprehension of the term "set
associative", and merely tests some basic powers-of-two arithmetic.

Magnus Ekman
Guest

Posted: Mon Dec 13, 2004 4:43 pm Post subject: Re: Direct/Associative Cache question

On Mon, 13 Dec 2004, David wrote:

Quote:

Well, I had a bad hangover and nothing useful to do. That probably
explains why I bothered to answer but also that I missed that it said 8k
in the question (and also the lack of humour).

I haven't reflected much about the discussion regarding homework questions
before and frankly I don't really see the problem with them. I don't read
90% of the posts anyway but only the posts with subjects that seem
interesting to me. However, since other people seem to care about the risk
of being spammed with homework questions I'll respect that.

That said, I think that the discussion about if it is cheating to ask for
help is rediculous. Are there really serious universities out there that
grade people on that kind of home assignments?

/Magnus

George Neuner
Guest

Posted: Tue Dec 14, 2004 12:01 pm Post subject: Re: Direct/Associative Cache question

On Sat, 11 Dec 2004 11:09:33 GMT, Jouni Osmala <josmala@cc.hut.fi>
wrote:

Quote:

6. How many RAID levels are available and can you give me a brief
descriptions about each one?

RAID is a trademark bug spray, as far as I know they only make one or
two different kinds (but there's probably several sizes, which might
count!).

RAID levels:
1 - ant killer
2 - flea killer
3 - flying insect killer
4 - roach killer (includes RAID level 1)
5 - wasp & hornet killer
6 - house & garden bug killer

http://www.killsbugsdead.com/fop.asp

George
--
for email reply remove "/" from address

	CASTalk.com Forum Index -> Computer Architecture	All times are GMT
Page 1 of 1

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum