jserv
, homework
tina0405
除了 Spatial and Temporal Locality 我曾在書上看過外,有一個新的名詞 Non-temporal
,意思是資料最近被用到後,在未來的時間內不會再被用到
SW prefetch + HW prefetch 會有 Traning-effect :依照邏輯猜測,是需要去校正兩個方法做何用的誤差所做的調整,造成效能低落
SW prefetcher 在於短陣列及連續記憶體配置中,減少 L1 Cache miss
會有最佳效能
理解GHB(Global History Buffer)
: Global History Buffer 是最新的技術去實做 Prefetch Cache data 機制在現代的 CPU 上,有兩個顯著的優點
first in first out
history buffer 可以增進Correlation prefetching精確度藉由排除 Table 上的 stale data.經由一個議題 content-based pefetch
而去找了相關資料去了解它,於是找到 Computer Architecture
Lecture 24: Prefetching 的資料去闡述 prefetch
也對相關機制做介紹
Prefetching useless data 浪費資源如下幾項:
以下是準確度的算式:
有同學提問 stride
是什麼,針對參考連結中的 stride
做解釋:
To inhence preformance and we want to reduce compulsory cache miss
. We still have Conflict
,Capacity cache miss
.The prefetch technology can reduce both of Miss rate,Miss latency.
為何減少 Cache miss 如此重要?以 branch 指令做解釋,經過 Instruction fetch, Instruction decode, Excution, Memory access, Write back
五個週期指令,當發現抓取資料錯誤時,需要 flush 其他已經載入的指令,這樣是非常耗成本,所以抓對資料的重要性可顯而知
The place where will prefetch work
Prefetch data in cache
:
cache pollution
Prefetch data in separate prefetch buffer
:
Cache
或用不到的,造成有用的資料被置換到 Lower level cache,降低效能,e.g 在 Multi-core processor 的情況下,有可能現在在運作核心,被其他 core replace 他正要用的 block from cache.Software prefetching
:可是在白算盤書中有提到 Cache coherence problem 問題,不知道是否有不同點?
不要把 SMP 遇到的問題 (如 cache coherence protocol) 和這邊上述議題混而一談
"jserv"老師,這裡對這個問題作查詢後得到資料的理解清楚自己對問題點的了解不夠深入,導致混為一談
- Cache coherence problem (快取一致性的問題) : 是多重處理器會遇到的問題,因為多重處理器經常需要將許多份相同備份的資料存放在不同的快取記憶體中,而每一個處理器都可以對此備份做存取
- Cache coherence protocol (快取一致性協定) : 用來維持多重處理器的資料一致性,有兩種方法
- 一是 Snooping
- 二是 Directory based
"williamchangTW"
Opcode | Instruction | 64-Bit Mode | Compat/Leg Mode | Description |
---|---|---|---|---|
0F 18/1 | PREFETCHT0 m8 | Valid | Valid | Move data from m8 closer to the processor using T0 hint. |
0F 18/2 | PREFETCH1 m8 | Valid | Valid | Move data from m8 closer to the processor using T1 hint. |
0F 18/3 | PREFETCH2 m8 | Valid | Valid | Move data from m8 closer to the processor using T2 hint. |
0F 18/0 | PREFETCHNTA m8 | Valid | Valid | Move data from m8 closer to the processor using NTA hint. |
改用 HackMD 的表格重新排版
"jserv"已改進,謝謝
"williamchangTW"
Hardware prefetching
:由 HW monitor processor access
自動生成 prefetch address
memorizes or finds patterns or strides
想法 :藉由使用特定目的的硬體去觀察 load / store 之前的習慣去 prefetch
優點:
缺點:
方法一:Next-line Prefetcher
方法二:Stride Prefetcher
Instruction programe counter
Load Inst PC
Load Inst | Worst-case running time | Last | Confidence |
---|---|---|---|
PC(tag) | Referenced | Stride | |
… | … | … | |
… | … | … |
有個問題存在於此方法中
解決方式:
Excution-baesd
prefetchers:上述組合語言對 SW prefetcher 的影響,Direct more two instruction than Indirect
依照文中所得的資料可得出
- 處理 常規性存取,e.g streams,HW prefetcher 會太過於浪費,使用 SW prefetch 會比較有效率
- Prefetch distance 只要夠大,效能就會比較好
- SW prefetching 可以用來訓練 HW prefetcher 因此能夠獲得效能上的提升,在某些情況下會下降
這裡對 Machine cycle & Instruction cycle 定義不是很清楚,所以去找了這篇 What is clock cycle, machine cycle, and instruction cycle in a microprocessor? 以下做出解釋
Clock cycle
Machine cycle :
Four steps of Machine cycle :
Step 1
擷取(Fetch) - 從記憶體中取出指令Step 2
解碼(Decode) - 解譯指令看是那一系列的機器指令Step 3
執行(Execute) - 執行機器指令Step 4
儲存(Store) - 結果回寫回記憶體Instruction cycle :
文中參考資料 : perf stat 輸出解讀 歸納及整理
context-switches
及cpu-migrations
之間的差異,發生 cpu-migration
一定會發生 context-switches
可是反向不一定成立,有可能還是在同一個 CPU 上執行,只是被置換出等待在執行的時間點在抓取進來執行L1 D-cache
: Level-1 資料快取記憶體L1 I-cache
: Level-1 指令快取記憶體MMU(Memory Management Unit)
: 記憶體管理單位元TLB(Translation Lookaside Buffer)
: 轉譯後備緩衝區(個人偏好:索引快取
較能表達其用處)L2 cache
: Level-2 快取記憶體L3 cache
: Level-3 快取記憶體數字越大代表越下層,也越大越便宜,詳情見:Wikipedia-Memory hierarchy
Cache line
包含數據,TAG (地址訊息)以及狀態訊息
cache line
,硬體資源非常有限
1 KHz = 103Hz
1 MHz = 106Hz
so ,
意謂著:200,000,000 ~ 300,000,000 clock cycle per second
這裡實證上面的理論,兩個處裡器只差在時脈下作比較:
- Intel® Celeron® 處理器 600 MHz,128K 快取記憶體,66 MHz 前端匯流排
- Intel® Celeron® Processor 300 MHz, 128K Cache, 66 MHz FSB
證明:
想先證明時脈越高,stall cycle increased
考慮以下公式:
- clock rate = 300MHz:
–
- clock rate = 600MHz:
–
Execute time per instruction 相差兩倍,再套用第一個公式
assume Miss rate & Miss penalty are same
and then we already knowExecute time per instruction
two times between 300MHz and 600MHz
so , we assume Memory accesses = N for 300MHz
驗算如下:
- 300MHz:
- 600MHz:
明顯地知道 clock rate 越大,Stall cycle increased
- N way Set-Associative:
-
- Fully-Associative:
-
naive_transpose
, sse_transpose
, sse_prefetch_transpose
之間的差異
naive_transpose = naive
sse_transpose = sse
sse_prefetch_transpose = sse prefetch
看得出來
sse_prefetch_transpose
的搜尋速度較快與sse_transpose
差別近兩倍navie_transpose
差別近三倍
naive_transpose
, sse_transpose
, sse_prefetch_transpose
之間的效能差異,以及 prefetcher 對 cache 的影響Makefile
,產生新的執行檔,分別對應於 naive_transpose
, sse_transpose
, sse_prefetch_transpose
(學習 phonebook 的做法),學習 你所不知道的 C 語言:物件導向程式設計篇 提到的封裝技巧,以物件導向的方式封裝轉置矩陣的不同實作,得以透過一致的介面 (interface) 存取個別方法並且評估效能perf stat
的 raw counter 命令