View Question
Q: Computer Organization and Design ( Answered ,   1 Comment )
 Question
 Subject: Computer Organization and Design Category: Computers > Hardware Asked by: cengineer1-ga List Price: \$50.00 Posted: 04 May 2004 21:32 PDT Expires: 03 Jun 2004 21:32 PDT Question ID: 341280
 ```Given the series of address references given as word address: 1, 16, 8, 0, 22, 19, 12, 15, 46, 10, 32, 18, 14, 32, 9, 20, 0. Show the hits and misses and the final contents of the cache for a 3 way set associative cache with 3 word blocks and a total size of 27 words.```
 ```Hello cengineer1, I'm basing my answer to this problem on my understanding of set associative cache as learned from this useful course URL: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/ If I understand the terminology of your question correctly, each set in the cache contains three slots (as the term is used in the aforementioned notes), and each slot is the size of 3 words. (I'm assuming that "blocks" in your question is not another term for "slots" as used above, because then the question description is redundant.) So our empty cache, with unused slots as underscores, starts out like this: _, _, _| _, _, _| _, _, _| The one thing your question does not specify is how we associate addresses with a particular set. Given that your stated addresses range from 0 to 46, we can't just take the first decimal digit, as we only have three sets to choose from. We could convert to binary and take two digits in the middle, but with 3 slots per set and 3 word blocks in each slot, that just doesn't map out nicely. We could map 0-19 for the first set, 20-39 for the second, 40-59 for the third, but that will cause a lot of collisions in the first set based on your address hits. However, we need our set mapping to divide nicely into blocks of 3 words each. Let's say that set one is 0-17, set two is 18-35, set three is 36-53. So our first address lookup, address 1, isn't found, because the cache is empty of course. We load the 3-word block that contains the address into set one, and have our pick of three slots, so we'll toss it into the first one. 0-2, _, _| _, _, _| _, _, _| Address 16 isn't found in the cache either, so we load it into set one: 0-2, 15-17, _| _, _, _| _, _, _| Address 8 isn't found, so we load it: 0-2, 15-17, 6-8 | _, _, _| _, _, _| Address 0 is found in set one, hooray we've saved time! No change to the cache. We look for address 22 in set two, based on our associative scheme, and do not find it, so we load it there: 0-2, 15-17, 6-8 | 21-23, _, _ | _, _, _ | We look for address 19 in set two, and do not find it, so we load it up: 0-2, 15-17, 6-8 | 21-23, 18-20, _ | _, _, _ | We look for address 12 in set one, and it's not there. We want to load it up, but we've got to kick another 3-word block out of a slot first. Here's another design choice: are we doing first-in-first-out (FIFO), least recently used, or some other wacky scheme? I like least recently used, so let's boot out the second slot: 0-2, 12-14, 6-8 | 21-23, 18-20, _ | _, _, _ | Aww geez, we just booted out the next address we were looking for. Oh well, them's the breaks. Moving right along, we boot out the third slot in set one and load it up there: 0-2, 12-14, 15-17 | 21-23, 18-20, _ | _, _, _ | Address 46 is not yet loaded in set three, so we'll drop it in: 0-2, 12-14, 15-17 | 21-23, 18-20, _ | 45-47, _, _ | Address 10 isn't in set one - collision again. Least recently used is now the first slot, so let's replace it: 9-11, 12-14, 15-17 | 21-23, 18-20, _ | 45-47, _, _ | Address 32 isn't in our cache either. Set two still has a vacant slot, though, so no collision. 9-11, 12-14, 15-17 | 21-23, 18-20, 30-32 | 45-47, _, _ | We look for address 18 in our cache in set two - success! No change to the cache. Address 14 is found in set one, so again no change (and we do a little happy dance because we've saved some time). We look for address 32 in set two, and again we find it there. No change. Address 9 is found in set one, success again, and no change. Likewise for address 20 (hey, we're on a roll here, finally). Address 0 is not found in set one. Least recently used is the second slot: 9-11, 0-2, 15-17 | 21-23, 18-20, 30-32 | 45-47, _, _ | And that's the final state of our cache! Now keep in mind, there were two design decisions made along the way here which could have played out differently. Choosing how we map our association of address ranges to cache sets will make a big difference. In fact, the choice I did make is not analogous to how this is usually done in hardware, but is sort of bad practice. Hardware designers know that memory use tends to get grouped into a region of memory, just as we had many more addresses in the lower ranges than we did in the upper range. Our third set within the cache went almost entirely unused! When using binary, the middle digits are generally chosen to decide set association for this reason. We could've done that here and still mapped things cleanly by using a base 3 number system, I suppose, but that's sort of painful to spend time figuring out! The other key decision left open by your question was how we choose which slot within a set to kick out of the cache. FIFO would have worked just fine, and who knows, there might be some other scheme which would work even better. Least recently used isn't a bad choice, though. Search strategy: 3 way set associative cache References: Set Associative Cache (course notes for Computer Organization, cmsc311, University of Maryland Department of Computer Science) http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Memory/set.html http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/ I hope this helps your understanding of set associative caches, it certainly did mine! Have a great day, - josh_g-ga```
 ```One little remark to your answer... In the document you said your answer was based, there was this note : "You can have N-way set-associative caches, where each set contains N slots (where N is a power of 2). " I guess that's why it didn't map correctly with a 3 power set. With regards.```