[理工] 計組 習題

看板Grad-ProbAsk作者 (MUDA)時間7年前 (2017/01/18 17:10), 7年前編輯推噓4(4推 0噓 56→)
留言60則, 5人參與, 最新討論串1/1
https://imgur.com/gallery/aCjuZ 如圖，我要問的是第二小題。我是覺得B[I][0]也會使用到temporal locality 因為在內圈B的位址其實不會改變，會一直去存取。 可是答案沒有給。 請各位大大幫忙解惑 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.18.57 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484730620.A.1F6.html
→
01/18 17:10, , 1F
答案只給I J
01/18 17:10, 1F
※ 編輯: lingege32 (42.72.18.57), 01/18/2017 17:18:56
推
01/18 17:40, , 2F
推 有同樣疑問
01/18 17:40, 2F
推
01/18 17:59, , 3F
請問答案是什麼呢？
01/18 17:59, 3F
※ 編輯: lingege32 (42.72.18.57), 01/18/2017 18:06:56
→
01/18 18:08, , 4F
使用到 temporal的是 I J
01/18 18:08, 4F
→
01/18 18:08, , 5F
使用到spatial的是 A[I][J]
01/18 18:08, 5F
→
01/18 18:08, , 6F
我想問的是第二題ˊˋ
01/18 18:08, 6F
→
01/18 18:08, , 7F
剛剛我有打錯 重新編輯了
01/18 18:08, 7F
※ 編輯: lingege32 (42.72.18.57), 01/18/2017 18:08:50
推
01/18 18:17, , 8F
Cache 很小 沒有辦法裝下全部的B[i][0]，意思是 當你用
01/18 18:17, 8F
→
01/18 18:17, , 9F
完B[7][0]要找B[0][0]的時候，B[0][0]已經不在cache中了
01/18 18:17, 9F
→
01/18 18:17, , 10F
，因此沒有用到temporal locality
01/18 18:17, 10F
推
01/18 18:18, , 11F
那這樣我有跟原po一樣的疑問，雖然B[I][0]沒有I,J的
01/18 18:18, 11F
→
01/18 18:18, , 12F
temporal locality那麼久，可是也算有
01/18 18:18, 12F
→
01/18 18:30, , 13F
好吧我上面推文的時候好像看錯了，然後我也被你們說服了
01/18 18:30, 13F
→
01/18 18:31, , 14F
xu大 可是在內圈的時候 B[0][0]會存在在cache內 在內
01/18 18:31, 14F
→
01/18 18:31, , 15F
圈會一直用這個block 不算用到temporal嗎
01/18 18:31, 15F
→
01/18 18:31, , 16F
為什麼B[i][0]沒有temporal＠＠
01/18 18:31, 16F
→
01/18 18:32, , 17F
歡迎xu大一起加入有疑問的行列
01/18 18:32, 17F
→
01/18 18:32, , 18F
摁我也在思考這個問題惹
01/18 18:32, 18F
→
01/18 18:52, , 19F
我也有疑... 我先看個題目
01/18 18:52, 19F
→
01/18 19:00, , 20F
這題答案 2.a i,j,B[J][0] b. i,j
01/18 19:00, 20F
→
01/18 19:02, , 21F
額 抱歉我只回成紅算盤的題目
01/18 19:02, 21F
→
01/18 19:15, , 22F
慘 我也要加入你們了@@
01/18 19:15, 22F
→
01/18 19:16, , 23F
疑惑行列越來越多了QAQ
01/18 19:16, 23F
→
01/18 19:24, , 24F
我推測 因為 B[i][0] 它總共需要用到八次而已
01/18 19:24, 24F
→
01/18 19:24, , 25F
只是這八次的每次都是 J=1 to 8000 的總共時間
01/18 19:24, 25F
→
01/18 19:25, , 26F
這部分紅算盤也有類似題目 將i放在外圍時 B[i][0]
01/18 19:25, 26F
→
01/18 19:26, , 27F
也就是我上面打的ans b. i,j
01/18 19:26, 27F
→
01/18 19:31, , 28F
感覺 temporl 不能將「連續使用」算在內
01/18 19:31, 28F
→
01/18 19:32, , 29F
喔喔哦！ 根據k大讓我感覺到
01/18 19:32, 29F
→
01/18 19:32, , 30F
其實內圈是B[0][0]這個數字一直被用到，而不是這個“
01/18 19:32, 30F
→
01/18 19:32, , 31F
而是間段性的被reference，否則太浪費時間去access了
01/18 19:32, 31F
→
01/18 19:32, , 32F
變數”一直被用到 而B[I][0]是要過很久才會再一次用到
01/18 19:32, 32F
→
01/18 19:37, , 33F
但是如果照k大的說法 是不是I也沒有用到temporal的好
01/18 19:37, 33F
→
01/18 19:37, , 34F
處 因為他也一直都是同一個數字
01/18 19:37, 34F
→
01/18 20:03, , 35F
不行 我剛剛那種說法也無法說服我@_@
01/18 20:03, 35F
→
01/18 20:09, , 36F
繼續疑惑Orz
01/18 20:09, 36F
→
01/18 20:24, , 37F
看完Stackoverflow 瞬間通了
01/18 20:24, 37F
→
01/18 20:25, , 38F
對於 i 而言，每次在B[i][0] & A[I][J] 都會使用到i
01/18 20:25, 38F
→
01/18 20:25, , 39F
的相同 i 的value
01/18 20:25, 39F
→
01/18 20:25, , 40F
對於 j 而言，同上
01/18 20:25, 40F
→
01/18 20:27, , 41F
對於 A[I][J] 而言 , 並不會有某個時刻再被使用
01/18 20:27, 41F
→
01/18 20:27, , 42F
A[I][J] 進入相同的 address
01/18 20:27, 42F
→
01/18 20:27, , 43F
對於A[J][I] 而言 ，同上
01/18 20:27, 43F
→
01/18 20:28, , 44F
對於 B[I][J] 而言，也不會有某個時刻再使用相同的
01/18 20:28, 44F
→
01/18 20:28, , 45F
B[I][0]
01/18 20:28, 45F
→
01/18 20:29, , 46F
B[I][0] 進入相同的 address
01/18 20:29, 46F
→
01/18 20:40, , 47F
ken大是看哪一篇stackoverflow的文章呢？
01/18 20:40, 47F
→
01/18 20:40, , 48F
我看了這篇文章：https://goo.gl/zpzDol
01/18 20:40, 48F
→
01/18 20:41, , 49F
我看得跟你一樣
01/18 20:41, 49F
→
01/18 20:41, , 50F
他寫的概念跟po想的很像
01/18 20:41, 50F
→
01/18 20:43, , 51F
他說we could say that references to j and a[i] are
01/18 20:43, 51F
→
01/18 20:43, , 52F
temporally local
01/18 20:43, 52F
→
01/18 20:46, , 53F
而我覺得那篇文章中a[i]的角色就跟這裡的B[I][0]很像
01/18 20:46, 53F
→
01/18 20:47, , 54F
都是inner loop在跑的時候不會變動的記憶體位址
01/18 20:47, 54F
→
01/18 22:37, , 55F
還是不太懂K大的意思，B[I][0]不是會在內圈一直被進入
01/18 22:37, 55F
→
01/18 22:38, , 56F
相同的address拿取資料嗎
01/18 22:38, 56F
→
01/19 09:07, , 57F
剛睡醒腦袋可能不清楚 我想表達的是 不會有另一個變
01/19 09:07, 57F
→
01/19 09:08, , 58F
數 B[i][0] 除了在 A[I][J]=B[I][0]+A[J][I] 被使用
01/19 09:08, 58F
→
01/19 09:25, , 59F
不對我在講甚麼@_@ B[I][0]就跟昨天我一開始說的一樣
01/19 09:25, 59F
→
01/19 15:21, , 60F
我大概懂那個意思了 謝謝各位神人qq
01/19 15:21, 60F
‣ 更多 lingege32 的文章
文章代碼(AID): #1OVp3y7s (Grad-ProbAsk)