[理工] [計組] cache

[wheels ()]

台大電機丙95年第2題的(E)選項

http://www.lib.ntu.edu.tw/exam/graduate/95/412.pdf

張凡給的答案會增加。

我的想法是：

增加set associative的degree為n倍，則LRU要檢查的block數變n倍，

所以作LRU implementation 變為c*n倍，

其中c是constant為對每個block作LRU實作的cost。

但是這樣看的話complexity不會變。

如果要變的話應該是degree變為n倍，但implementation需要c*n^2 or c*n^3..等，

這樣才算是complexity會變動。


請問哪裡出錯了呢？感謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.249.8.59
※ 編輯: wheels          來自: 111.249.8.59         (01/22 12:14)
→ P568912:我覺得應該不是要考慮時間複雜度耶
→ P568912:只是考慮有沒有變複雜而已 沒有對n的時間複雜度做討論
→ P568912:個人想法 也不知道對不對@@
→ wheels:好像有道理...題目沒有說是time complexity@@
→ wheels:或許是我太鑽牛角尖吧XD
推 metalalive:樓上指的 Complexity 是指實作上的複雜嗎?
→ P568912:恩 你比較TAG數變多 硬體的多重選擇器都會變得較複雜吧