I'm studying for my Computer Architecture exam next week, and I'm having problems understanding how a set associative cache works and how to solve related problems like this one :

"A set-associative cache memory uses a set of 8 words. A replacement procedure based on FIFO algorithm is implemented by means of 3-bit counter associated with each word in the set. A value in the range 0-7 is thus recorded for each word. When a hit occurs, the counter associated with the referenced word is set to 1; those with values originally lower than the referenced one are put in its place and put all others in reverse order. If a miss occurs the algorithm implemented the new word put in its place, show that this procedure works with this message "start ABCDEFGHIJKABCDEFLMNGHD end". Start with initial 8 words. then compute the miss ratio."

here is what I've tried so far ... I've inserted the first 8 letters into the cache, and then checked the following 15 letters for hits and misses whenever there is a miss I remove the oldest letter in the cache and replace it with the new one... not sure if my solution is correct to this point or not and I can't figure out the part about the counter and the part about the reverse order

I greatly appreciate any time taken to explain this to me as I don't understand the wording of the problem, and need a general guideline on how to solve such problem. Thank you very much in advance.

  • 1
    $\begingroup$ Please re-read my comment; I already understood all that when I wrote it. The issue is not whether it is a homework or an assignment; the issue is that it is a dump of a problem statement, which our policies consider unsuitable for this site. We expect you to make a serious effort on your own, show us what you have tried, and where you got stuck, tell us what you do and don't understand, and find a way to craft a specific technical question about something specific that you don't understand. Bottom line: re-read my comment and the links there; they apply to your question. $\endgroup$ – D.W. May 29 '14 at 0:03
  • 2
    $\begingroup$ When you say you don't understand the wording of the question, which part don't you understand? A general explanation of set-associative caches is beyond the scope of this site but it should be in your text book, in books in your library and on Wikipedia. $\endgroup$ – David Richerby May 29 '14 at 0:05
  • 2
    $\begingroup$ Without a definition of word size (32-bit? 16-bit?) relative to character size (8-bit utf-8? 16-bit utf-16?) the question is unanswerable. It is only implied that there is only 1 set. The explanation of the replacement policy is very unclear. (I would guess that a hit is supposed to set the counter to 0 not 1 [unless a line fill sets the counter to 0] and that the victim is the line with the highest number. It also seems the lower counter values are replaced with the counter value for the hit line, but this could result in 7 lines having highest counter with no way to choose a victim.) $\endgroup$ – Paul A. Clayton May 29 '14 at 12:36
  • 1
    $\begingroup$ I am tempted to speculate that the question is attempting to describe a clumsy implementation of LRU replacement (that the counter is an access ordering), but the description is not consistent with LRU (or MRU). If this was a problem you were actually required to solve, I would suggest describing your interpretation of how the replacement policy actually works and then solving the problem. $\endgroup$ – Paul A. Clayton May 29 '14 at 12:46
  • 1
    $\begingroup$ If I were answering such on an exam, I would explain what I thought was meant (including assuming a typo/thought-o for "referenced word is set to 1", size(character)=size(word), one set, etc.), and my explanation of LRU seems to make the most sense (to me). However, assuming a typo is probably not a good idea as a grader is even less likely to give partial credit when changing stated (not just implicit) properties. A reasonable grader would give at least partial credit to an answer consistent with "reasonable" assumptions, but reasonable grading seems unlikely given unreasonable questions. $\endgroup$ – Paul A. Clayton May 30 '14 at 15:09

Your Answer

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

Browse other questions tagged or ask your own question.