電路的分析是很難的， 因為模擬電路大量經驗參數是需要流片試出來，實體層面許多數據根本沒法計算。 電腦系統明明都是人造的東西， 但是當部件足夠多的時候， 對系統的效能進行分析也並不是一件簡單的事情。這門課主要就是學習如何進行分析，你需要明確哪些參數，不知道參數的時候怎麽進行假設。學習專業知識需要自己花時間看ppt和思考, 上課老師可以教授"道"。
Folks, you CANNOT be so sloppy in your descriptions at this stage of your career. You can be a programming wizard, you can be the next coming in AI, or you can even be the best Python coder in the world, but the way you present your solutions and you phrase your answers can be a show stopper in the next stage of your career if you are not careful. I will forgive this because of the exam and time pressure and all that, but PLEASE, in the future, make sure that you communicate your answers clearly and well. And remember, half the job of a computer scientist is COMMUNICATIONS.
第一周
存取L1 cache , 2-5 cycles; L2, 12 cycles; 記憶體 200-300cycle，
普通的CPU 有幾十個寄存器, 有個人提出用60K個寄存器 , 問題在哪裏?
- bandwidth to memory不夠
- 線很長, latency很大.
- compiler沒法使用好這麽多寄存器. 分配寄存器是 np compele 問題. 有個編譯器專家調查了一年, 結論是64個寄存器已經很難利用好了.
GPU 和CPU 共用 MEM可以嗎? 蘋果, 輝達grace hopper就是這麽做的. intel, IBM 這麽做失敗了, 因為power技術不行,只好用weak 處理器. 技術原因:
- GPU 記憶體 bandwidth 很大, CPU記憶體需要latency小.
- Data movement 用了非常多power.
- AMD 有能力把GPU 和CPU 共用 MEM, 但是沒有這麽做, 為了輝達的軟體相容性.
6 cycles, 需要24 bytes 記憶體. 頻率3GHz. 那麽1s 存取12 GB 記憶體, 但是memory bus只有6GB/s. 會成為bottleneck.
vector instructions. 4way 可以一次處理4個數.
HBM 是一種立體空間記憶體. 難點是 發熱嚴重 , 立體的存取慢.
高級產品, 可能沒有價效比,但是可以樹立品牌形象,有廣告作用.
每個core一個bus可以嗎?
對於stream的數據, 因為只處理一次, cache 幾乎沒啥用, 甚至有害.
simulations
functional, vs cycle-accurate .
stochastic vs. deterministic . deterministic 開銷大, 因為要存big trace data來得到有用的結果.
Event-based vs time based
event queue vs multithreaded
中國人喜歡riscv , 因為沒有license.
多個queue, 一對一 resource好. 還是一個queue, 多個resource好?
一個queue, 多個resource: 適合有個很慢,可以分給一個resource 後面的不用等. resource肯定越多越好.
多個queue, 一對一 resource, 需要優秀的load balancing schduler. 最簡單的用shortest queue,哪個短放哪個.
測量不準確怎麽辦?
- 多次測量, 用不同的random seeds
- 報告平均, 標準差和置信區間.
總共1TB 數據, 伺服器用 32 GB 還是64GB雙倍價格 的記憶體?
設計方案之前先要問 metrics是什麽?
考慮有多少client, client 很多的話, 要多買一些伺服器, 所以要買單價低的.
討論可以每個人都參與, 但是課程就進行的非常慢, 一個小時就講一兩個知識點.
因為使用者存取量隨時間變化非常大, 所以需要雲端運算,彈性計算.
如果沒有自己的超算,用別人的雲端運算80k美元發一篇文章.如果要一直用就需要有自己的機器.
如果要用外部庫, 你需要 recompile dynamic lib with debug flag.
以前晶體管不斷變小 -> faster switching, 現在不能無限提高頻率了, 因為熱效應過大, 晶體管會melt.
讀main memory ,需要50-60 ns.
L1 有32KB.
同步, lock都交給上層硬體. 原則就是, 應該把最底層的東西, 硬體, 做的 as simple as possible, 復雜的都交給上層. 而不是最底層提供大量復雜的功能. 這些功能可能上層用不到.
硬體多執行緒的影響：
優點:
- 充分利用cache
缺點
- 競爭cache
- tolerate memory latency
- more state-> more power
- 增加memory Bandwidth.
第二周
vector processor 是非常昂貴的.
very large instruction , 可以嗎? intel 曾經有個processor 做了, 但是行不通.
load vector register, 需要非常多 power .
execution units 不用線性增長, 但是state, bandwidth, 芯片面積,power 都會隨thread數量線性增長.
multithread
here we talk about hardware multithread !
•What?
•Abstractions of independent instruction streams implemented in hardware, equivalent to a CPU from a software perspective
User thread, kernel thread (也就是作業系統的 thread), hypervisor thread, hardware thread. 這四個都是不一樣的. 一層層往下都要對映.
一個core 可能有多個 hardware thread. 大部份都是1個或者2個thread. 有的單核有4個thread, IBM 有過單核8 thread.
•Implications for the operating system: Scheduling
•Implications for performance: More throughput, but not faster!
•Implications for the software writer: May want to exploit by assist threads, etc.
•A confusing concept: Program level threads can be multiplexed on the hardware threads
loop unrolling
HPC 常用的技術, 為了減少bubble. 迴圈步長不為1, 而是在迴圈中修改變量i. 可以在迴圈中省下一兩條指令的時間.
第三周
五個階段: IF ID Reg EX L/S
data從寄存器到ALU也需要一個cycle.
Control induced bubble. 不知道要不要跳轉.
多執行緒可以 填補bubble
structural hazard 的解決方案: 增加資源. 比如 two ported register file
現在實際上有200多個寄存器, 指令集的32個寄存器會對映過去.
single-ported integer register file , file就是寄存器array.
第四周
arm(包括Apple) , risc, 和 power pc 都屬於risc, no translation.
x86 , 是intel 和amd 用的, 有translator, 把 cisc 轉譯成 risc.
pipeline 不能太深, 否則時鐘電平有問題.
標準的REG stage, 可以同時讀兩個寫一個.
這門課的reg不能同時read write.第三個是read reg, 最後是write back.
st操作,st r3, (r6) 需要讀兩個, r3和r6都要讀reg.
superscalar (multi-issue) pipeline
需要增加更多資源
亂序執行
可以把下一個loop 前幾個cycles 和前一個loop overlap起來.
如果memory fault了怎麽辦? 前面的都寫入記憶體了,撤不回了怎麽辦? IBM的解決辦法是把前面的寫入一個buffer, 比如寫入register33, 如果整個完成了再commit.
寄存器重新命名
加速和亂序執行差不多, register renaming works better with larger codes.
實際上的register比 32個architecture register多很多, 用來 renaming 或者暫存 etc.
IF, ID 之後, instruction issue & scheduling 是非常重要的,
pipeline 有n 個stage, 就有n個control register, 課程project 需要implement it. 有一個active的control register.
L05 Virtual memory and TLB
vector 聲明的陣列在heap, 普通的變量在stack. heap：是由malloc之類函式分配的空間所在地。 地址是由低向高增長的。 stack：是自動分配變量，以及函式呼叫的時候所使用的一些空間。 地址是由高向低減少的 。
Buddy Allocation : 分配記憶體, 不斷減半, 直到最小的一塊, smallest block its size 滿足需求.
TLB, 就是虛擬地址的cache
實體位址比虛擬地址空間大或者小都行, 是獨立的.
頁表
用MMU來轉譯, 從virtual page map 到 實際page.
對於每個frame 還會存protection bits 和reference bit.
如果只有一個頁表, 2^52次 * 6Byte, 6Byte 48bit 是physical address , 這需要的virtual address太大了.
8bit , Index1, 找到page table level1
尋找下一級的頁表基地址. Index2 6bit, Index3 6bit, offset 12bit.
large page, 1個頁有2MB. 之前都是在HPC用, AI 可能推動很大的page, 因為數據非常多非常大.
表示large 頁表的方法
- 可以加indicator, 表現page有多大
- 專門用index 1 來索引大page.
tlb找到了, 就讀一次記憶體就可以了.
TLB 的存取時間是多少? 和L1 cache一樣還是和 memory一樣?
頁表也能進cache. 那怎麽知道哪些頁表進cache呢?
TLB miss 的代價是非常大的. 需要page walk,查整個page table, page table可能有6level.為什麽說代價大呢? 因為page table是存在memory中的, 你需要存取多次memory.
由於頁表儲存在主記憶體中，則程式每個訪存請求至少需要兩次訪存。一次獲得實體位址，一次訪存獲得數據. 多級頁表就要多次. 當我們在使用中間級的page directory時，我們透過虛擬記憶體地址中的L1部份完成索引。接下來會走到最低階的page directory，我們透過虛擬記憶體地址中的L0部份完成索引。在最低階的page directory中，我們可以得到對應於虛擬記憶體地址的實體記憶體地址。
現在好像有科研做並列存取的架構, 用的cuckoo hash , Radix tree - >hash
TLB可能存在cache中.
what if a page is swapped out?
先cache, 再TLB, 可以更多吞吐. 因為可能不用經過TLB. 而且可以用id, 標記是哪個行程在用.
增加 associativity：存取時間hit 時間增加， miss 時間減少。
全相連fully associate: 增加了hit時間,減小了miss rate
組相連:
直接連線:
random :cheap ,
LRU: 成本高.
有指令TLB和 Data TLB .
Solution 1: Multi-Level Page Tables
context table 在MMU中.
誰轉譯這個地址?
Solution 2: zero-Level Page Table
•Only a TLB inside processor
•No page table support in MMU
•On a TLB miss, trap to software and let the OS deal with it (MIPS 3000/4000)
Advantages: Simpler hardware , Flexibility for OS
Disadvantages: Trap to software, may be slow
The MIPS architecture used to have this feature. This enabled maximum flexibility to the software and simplified the implementation of the hardware. Unfortunately, the cost of a TLB miss can be substantial (although you may argue that it is not much better if done in hardware because of the memory accesses).
問題
•What to do on a context switch? 每次switch都要flash TLB. 有的一個thread一個TLB, 有的多個thread共享一個TLB
•What if we run out of entries? What is the replacement policy? LRU, or random
•How to handle the page size issue? (e.g., Intel specifies 4K, 2MB and 1GB as valid page sizes)
•Do we differentiate between instruction and data?
•Should the operating system have the right to invalidate the TLB?
在上下文切換時：您可清空TLB， 然而，這可能非常昂貴。可以添加一個表示轉譯上下文的識別元，允許不同執行緒的多個轉譯共存於TLB中。這通常在TLB具有第二級（類似於第二級緩存）時非常有用。
如果我們的入口用盡，大多數情況下我們會隨機替換。LRU（最近最少使用）是個好方法，但在硬體中實施它相當困難。其他可以使用的演算法包括迴圈輪詢。關鍵問題在於實施的速度和復雜性。沒有時間使用類似作業系統的復雜演算法，同樣，在硬體中實施復雜演算法可能會有很大問題。
處理不同頁面大小是一個棘手的問題。通常，不同的TLB專用於不同的頁面大小。某些系統將非常大的頁面限制為分配在虛擬地址空間的特定區域內。這樣，虛擬地址中的一些位可以用於將轉譯導向用於轉譯的特定TLB。
TLB可以合並，為指令和數據提供服務。然而，由於這兩者是記憶體中的兩個獨立流，因此從指令和數據分別使用一個單獨的TLB是有利的。
是的，作業系統應該有權使TLB失效。例如，如果一個行程被交換出，或者一個頁面被對映到不同的幀，所有這些特殊情況都需要由TLB正確處理。因此，作業系統應該有能力根據需要使一個或多個TLB條目失效。
英特爾架構似乎在完全關聯模式下使TLB工作超過8個條目存在問題。這並不令人意外。請註意，第二級TLB沒有使用完全關聯結構。好像它在一個縮小的地址範圍內有256個完全關聯的TLB。
scoreboard , 可以看電腦體系結構-Tomasulo演算法 - 天外飛仙的文章 - 知乎 https:// zhuanlan.zhihu.com/p/49 9978902
week 6 memory architecture and caching
L1 分別有I cache 和D cache.
只有高端系統才配備L3緩存。有時，L3緩存位於單獨的芯片中，而有時它與處理器一起安裝在多芯片模組中。
L1緩存通常在數據和指令之間進行劃分。
一個受害者緩存儲存所有從L1/L2組合中逐出的緩存行。其思想是，在從行程P1切換到行程P2的上下文切換時，後者將開始清除P1的緩存行，以便為引入P2的緩存行騰出空間。然而，在未來的某個時刻，P1將再次切換回來。在這種情況下，擁有受害者緩存將確保屬於P1的所有計畫可以從附近的位置（當需要時）載入到緩存中。當然，沒有從L3到L2或L1的數據的大規模傳輸。受害者緩存與包容性緩存之間的決定並不明確。包容式(inclusive)L3緩存設計的支持者指出，L3緩存的大尺寸將使包容式緩存在漸進情況下與受害者結構幾乎相同。 原文 : A victim cache stores all the cache lines that are evicted from the L1/L2 combo. The idea is that upon a context switch from process P1 into process P2, the latter will start depopulating the P1 cache lines in favor of bringing the cache lines of P2. At some point though in the future, P1 will be switched back. In this case, having a victim cache will ensure that all the items that belong to P1 can be brought into the cache from a nearby location (on demand, of course. There is no bulk transfer of data from L3 to L2 or L1). The verdict of victim vs. inclusive cache is not clear cut. Proponents of the inclusive L3 cache design point out that the large size of the L3 will make an inclusive cache asymptotically identical to that of a victim structure.
L2 通常是inclusive的. 包含 L1的所有數據.
表示緩存行狀態的位包括：M（修改），E（獨占），V（有效）。如果V=1且E=0，表示其他核心或芯片上的緩存擁有該緩存行的副本。這些位在緩存一致性協定的執行中起著重要作用（詳見第7講）。它們還在替換演算法中起作用。例如，具有V=0（空槽位）的緩存行將被視為替換的首選候選項。接下來是V=1且M=0的緩存行，因為我們無需將該緩存行完全重新整理到記憶體。依此類推。
緩存行大小一直是一個引人入勝的問題，因為沒有明確的答案來確定最佳大小。較大的緩存行將需要較小的地址標簽，較少的取操作，並且如果遵守局部性原則，每次取操作將使用更多的數據。這可以降低緩存結構的開銷。但這也是有代價的。如果程式碼沒有顯示出良好的存取局部性，較大的緩存行效能將較差。實際上，您可能會將不太可能使用的數據放入緩存。它還增加了匯流排操作的壓力，因為我們需要每次獲取更多的數據，這可能需要更寬的匯流排，或者我們將不得不在多個記憶體匯流排周期內拆分獲取。較大的緩存行還可能會逐出更多的行，這可能會降低效能。
需要註意：在一些文獻中，有時將緩存行稱為「緩存塊」。
需要註意：不合理大的緩存行可能會加劇「虛假共享」的問題，請參見第7講。
我們在地址標簽中儲存多少位？數據項中用於表示行內偏移的位與比較無關。因此，最好只儲存必要的內容，以節省空間、功耗和時間。有人可能會質疑我們是否真的在位操作中深入探討這個問題。答案是否定的。考慮一個具有64字節緩存行的44位元地址空間。偏移量的6位大約占地址的14%。在地址標簽陣列中節省這個量將減少14%的面積和功耗。這是一個很大的收益。
Cache size 一般都是Simulate 出來的, 都是工程偵錯, 沒有準則.
directly associative
只對一個item比較
set associative
44 bit address space
7 bit offset
fully associative
Any line can be stored In any address
Need to compare all items
Write Through 場景中，數據同時更新到緩存和記憶體（ simultaneously updatedTime to cache and memory ）
write back
支持回寫的緩存實作起來比較復雜，因為它需要跟蹤哪些位置已被覆蓋，並將它們標記為變臟，以便稍後寫入memory中。出於這個原因，回寫緩存中的讀取未命中（需要一個塊被另一個塊替換）通常需要兩次記憶體存取來服務：一次將替換的數據從緩存寫回儲存，一次檢索所需的數據。
page coloring
"在這個範例中，作業系統最好保持2的9次方，也就是512個空閑頁面佇列，並以輪詢的方式從這些頁面佇列中為請求的行程分配頁面。這樣，頁面分配是均衡的。當可用記憶體開始變得緊缺時，一些這些佇列可能會變為空。然後，新的分配變得不夠理想。過度分配記憶體的系統執行通常不是一個好主意。"
memory
儲存芯片通常是根據儲存的位數與讀取的位數相乘來報的。例如，一個4Gb×1是一款非常流行的DRAM芯片（約2020年左右），它表示該芯片具有4G位，並且一次讀取或寫入操作在1位單位上進行。還有其他配置，比如4Gb×4等。
請註意，單獨的儲存芯片通常是以位（b）而不是字節（B）為單位報價。
請註意，為了形成一個字節的儲存，我們通常會將8個xxMb×1位的芯片組合在一起，這就是所謂的DIMM（雙排記憶體模組）
請註意，通常會添加額外的芯片到陣列中以儲存奇偶校驗。它本質上是8個芯片上所有數據的異或值。奇偶校驗可以檢測到由宇宙射線或周圍環境中的雜訊引起的記憶體內容損壞的情況。在高海拔地區執行的電腦更容易出現記憶體錯誤。
有時，在高端系統或任務關鍵系統中，會添加額外的芯片以提供更多的保護。2個漢明碼排列可以檢測兩個同時發生的錯誤並糾正單位錯誤。
實際上，宇宙射線不會挑剔，它們可能同時影響多個芯片，引發災難性錯誤。我們稱這些為瞬態錯誤。
實際上，瞬態錯誤要麽被檢測到，此時作業系統通常會發出「緊急」訊息並關閉系統，要麽瞬態錯誤未被檢測到，此時我們將面對「靜默錯誤」。靜默錯誤可能會影響到我們當前未使用或即將覆蓋的儲存區域，這是幸運的情況。不幸的情況是，瞬態錯誤可能導致數據損壞，而這種損壞很難（如果有可能）恢復。"
記憶體控制器
記憶體控制器負責執行記憶體匯流排事務。事務可以是原子事務，也可以是分割(split)事務。原子事務在完成之前不會釋放匯流排。分割事務透過將事務分成每個都是原子執行的子事務，從而提供了更高的效能。分割事務的實作可能會很復雜。匯流排協定在實施和驗證方面非常困難。您會發現，在行業中，記憶體匯流排技術在設計方面變化非常緩慢，盡管受益於匯流排寬度和頻率的增加。設計新匯流排的復雜性是設計新協定的障礙，更改協定通常需要更改連線到匯流排的所有裝置，這是一項非常昂貴的操作。
Memory Architecture
廣播匯流排是連線的最簡單形式。早期的共享記憶體多處理器系統，以保持處理器之間的記憶體一致性，都是采用廣播匯流排技術實作的。所有參與者都能監聽所有事務，這簡化了緩存協定的實作，同時還允許透過釘選匯流排進行同步，以使處理器能夠同時與多個實體通訊。匯流排不像需要復雜路由的更復雜結構那樣復雜。匯流排結構的問題既存在於效能方面，也存在於物理方面。在效能方面，匯流排頻寬被所有參與者共享，這意味著隨著我們在匯流排上添加更多參與者，每個參與者的頻寬份額將減少。在物理方面，匯流排的長度有限，訊號衰減會使其操作變得不切實際。這限制了匯流排結構的可延伸性，通常只能支持少數處理器，如果要獲得良好的效能，通常不會超過十幾個處理器。
NUMA
NUMA（非統一記憶體存取）結構與支撐所有已知演算法和理論發展的RAM（隨機存取機器）模型的抽象存在巨大差異。當我們編寫程式時，我們通常假設所有數據都能以相同效能均勻存取。然而，NUMA系統違反了這一原則，具體取決於記憶體分配給行程的方式。作業系統需要付出一些努力，以確保將記憶體分配給行程，使得所有數據來自同一節點。然後，作業系統會安排這些行程在最接近記憶體的芯片上執行。一般來說，在NUMA系統中編寫具有可預測性效能的程式碼是困難的。
需要註意的是，Elnozahy等人在21世紀初的一篇論文中提出，使用NUMA系統的正確方式是將每個具有獨立記憶體的芯片視為獨立單元，並在程式級別的節點之間使用訊息傳遞。然後，共享記憶體用於加速訊息傳遞的效能。他們證明，采用這種方式使用的系統可以優於將記憶體暴露給程式設計師的系統。
此外，NUMA系統通常以比例形式參照，如1:2 NUMA，這意味著遠端記憶體在存取周期數上比本地記憶體遠兩倍。
NUMA issue
•Memory allocation policies
•Process scheduling
•Cache affinity
•Performance stability
New Concept: Memory Interleaving
Memory interleaving指的是記憶體尋址，使得連續的字節分布在多個模組（DIMM）上，而不是來自同一個DIMM。這樣，如果我們想讀取緩存行，我們可以在獲取大量字節時實作並列，而不是一次拉取一個字節。
High Bandwidth Memory
HBM可以作為緩存系統的擴充套件，提供非常大的L3緩存。這樣，不需要程式設計師或作業系統智慧來從HBM中獲益。或者，它們可以被提供給程式設計師作為臨時儲存區。這類似於早期系統使用的一種稱為page-0-addressing的地址模式。這使軟體變得復雜，不易移植，並且使虛擬化和上下文切換變得昂貴或不可能。第三個選擇是將HBM視為地址空間的一部份，並讓作業系統控制如何分配這些頁面。這種技術的理論基礎是，作業系統可以智慧地使用這寶貴的記憶體，優先考慮某些行程，或儲存效能敏感的資訊，如頁表或內核數據結構。然而，使作業系統能夠勝任執行這些功能所需的修改遠非簡單。
Persistent memory
持久記憶體允許以字節級別存取記憶體中的數據，並可以與載入和儲存指令一起使用。這與以磁盤塊大小存取的快閃記憶體儲存裝置不同。寫入仍然很昂貴，因為它們需要燒掉材料以留下無法忘記的銘印。這使得這些裝置非常適合讀取。計劃使用良好尺寸的緩存來吸收大多數寫入，以便這項技術的寫入挑戰不會對效能產生嚴重影響。
Lec7 Cache consistency and coherence
在20世紀80年代，指令級並列性被提出作為一種能讓程式設計師編寫順序程式碼並透過指令級並列性提取效能的靈丹妙藥。20世紀80年代的人們並不愚蠢。典型系統的參數鼓勵了這種思路：記憶體存取在延遲方面與今天差不多，而當時的處理器周期是以亞微秒為單位衡量的，而不是納秒。因此，緩存未命中並沒有構成今天的大問題。同樣，當時的TLB的設計與今天非常不同。
總之，到了20世紀90年代初，很快就清楚了記憶體子系統開始主導大多數實際套用的效能。多年來記憶體延遲並沒有多大改善，而處理器在2002年到2003年左右繼續變得更快，然後進展停滯。典型系統的當前平衡更加強調TLB和緩存效能。GPU是一個顯著的例外，但這來自於一類強調整數/浮點效能的應用程式。然而，編寫這些系統的程式並不特別容易，而且在功耗方面非常低效。當頻率改進停滯不前時，矽片改進轉化為在大約1至3GHz左右切換的電路的更多領域。
工程師們首先將這一改進轉化為更大的緩存，但投資報酬率在某個特定大小之後會減少。在一個合適的傳統中，該行業開始向處理器芯片添加更多核心，開啟了多核處理器時代。責任被轉移到程式設計師身上，他們必須編寫能夠明確表達應用程式中並列性的程式碼（如果有的話）。這被證明是一項艱巨的任務。編寫並列應用程式，更不用說偵錯它們，都被證明非常困難。如今，擁有多核處理器的大多數好處來自於在雲端運算環境中將芯片劃分為不同的處理領域。
新一代更多處理器使大氣處理單元格的大小可以變得更小（幾年前5公裏是標準，而且這一標準不斷提高）。這是弱擴充套件的一個例子：我們沒有更快地執行問題，但我們獲得了其他好處（例如更精確的建模）。
強擴充套件是指更快地解決相同的問題。如今，這是一項非常具有挑戰性的任務。總的來說，強擴充套件將所有壓力都放在互連和程式設計師身上。增加更多處理器不會有幫助，除非互連按比例擴充套件（甚至以更快的速度，因為存在一些控制行程間通訊的非線性排隊效應）。
Consistency and Coherence
順序一致性被定義為：並行執行執行緒以產生與按順序一個接一個地執行這些執行緒等效的結果。當然，如果執行緒按順序執行，我們就不需要任何同步或擔心數據競爭。這將是最簡單的編程模型，但效能會非常糟糕。關鍵是要並列執行執行緒，利用多核和多處理器，同時確保結果與某些執行緒的順序交錯完全等效。幸運的是，透過利用硬體，特別是緩存，這是可能的。
今天，大多數系統采用緩存一致性協定，確保某種一致性（Intel提供順序一致性，IBM提供一種更快的模型稱為處理器一致性）。處理器一致性模型雖然比順序一致性更快，但被證明對程式設計師來說很難掌握。因此，程式設計師變得非常保守，他們在整個程式碼中插入同步原語，有效地阻礙了更快一致性機制的好處。重要的是要理解，如果代價是更多的編程復雜性，那麽追求效能將通常不會取勝。但有一些很好的線性代數演算法展示了研究人員所稱的令人尷尬的並列性（意味著高度的並列性）。這激發了像NVIDIA這樣的公司，他們只需在GPU上執行緩存，而無需一致性協定。
執行並行程式很困難，偵錯它們幾乎是不可能的。像事務處理系統或不共享記憶體的訊息傳遞演算法這樣的受限編程模型，在這種情況下可能會非常有用，但它們的效能不如共享記憶體編程。為什麽呢？因為事務處理執行操作的排程，以提供並列性，而不會讓程式設計師負責管理並列性。但正如你可以想象的，這意味著排程（NP完全問題）不會總是像經驗豐富的程式設計師那樣充分利用並列性。類似地，訊息傳遞需要程式設計師深思熟慮互動，除了訊息的打包和解包效能開銷。共享記憶體編程更簡單，但同步錯誤極難發現，而且通常不可重復（有時被稱為Heisenbugs，取名自量子物理學中海森堡不確定性原理的概念）。
Snoop-Based Protocols
基於Snoop的協定在芯片數量較少時使用。連線芯片的匯流排成為一種實際且廉價的解決方案。您會發現Snoop協定在低端系統中使用較多。Snoop協定也有可能在芯片內部以及核心之間使用。在圖片中，顯示了一個共享緩存。但另一種選擇是為每個核心提供私有的L2緩存，在這種情況下，它們將與系統中所有緩存執行同步協定，無論這些緩存位於同一芯片上還是其他芯片上。
Cache Structure
緩存的目錄包含了每個緩存行中被緩存的地址。通常還包含3到4個狀態位：M表示修改（Modified），E表示排他（Exclusive），V表示有效（Valid）。當從記憶體中將緩存行載入到緩存中時，M位為0。如果緩存行被更新（任何字節），硬體會自動將M位設定為1。如果E位為1，則表示該緩存行在系統中沒有其他緩存副本。當E=1時，處理器通常可以寫入該緩存行。但是，如果E=0，則寫操作無法繼續，因為必須在其他緩存中緩存的副本無效或並列寫入。V位為1表示緩存行有效。當從主記憶體中載入緩存行時，V位被設定為1，當該行無效時，V位被設定為0。通常，還會添加一個稱為S的第四位。如果該行在其他地方沒有被緩存，則S=0。如果系統中的其他緩存中存在其他副本，則將其設定為1。如果S=1，則不能進行寫操作。S=1表示唯讀共享模式。
緩存行的大小是一個重要的設計決策。如果程式碼顯示高度局部性，較大的緩存行效果最好，因為它減少了從記憶體中獲取數據的開銷（開銷分攤到更多的數據上）。它還意味著緩存中的行數較少，因此目錄結構較小。另一方面，較大的緩存行可能會引入復雜性，因為匯流排可能無法在單個周期內行動資料，此時我們稱該緩存行為分段（sectored）。分段實際上是對一個否則較大的緩存行進行分區的一種方式。較大的緩存行在存在偽共享（後面會提到）的情況下也可能會引發問題。
緩存目錄directory通常包含被緩存的行的實體位址。由於目錄directory是由昂貴的（面積和功耗）靜態電路設計出來的，我們希望減少所需的儲存量。這就是為什麽我們不儲存緩存行的偏移量offset的原因。換句話說，如果實體位址空間是44位元，而行大小是64字節，那麽在目錄結構中儲存最低的6位（定義了行內的哪個字節）是沒有意義的。因此，目錄的條目只有38位元寬度（是的，我們盡量節省盡可能多的位，沒有舍入到字節）。
緩存目錄可以以直接對映或集合關聯的方式組織。這完全取決於用於尋找緩存中元素的哈希函式。在直接對映緩存中，與某個哈希值對應的只有一個條目。在集合關聯緩存中，哈希函式指向整個集合。在集合內部，它是完全關聯的，這意味著我們在集合內對相同的標簽進行所有比較。
緩存目錄是一種內容尋址記憶體（Content Addressable Memory，CAM）的範例，因為我們根據其內容存取記憶體。這是一個次要的細節。
Snoop-Based Protocol: Invalidate
在多處理器時代初期，存在一場關於是更好地使其他緩存中的副本無效還是簡單地更新它們的爭論。因為當時的系統規模較小且速度較慢，這種差異並不明顯。然而，隨著系統規模和速度的不斷增長，很明顯嘗試不斷更新所有共享副本將不會擴充套件，並且效能會受到影響。今天，幾乎所有的處理器在希望寫入共享緩存時都使用使其他副本無效的方法。寫操作會通知擁有相同緩存行的所有其他持有者使其無效，以便它可以自行進行寫入而不受幹擾。
為了避免偽共享，可以使用技術如緩存行填充（cache line padding）來確保執行緒之間的數據不會存在於同一緩存行中。這可以透過在數據結構的末尾添加填充來實作，使每個執行緒的數據都位於不同的緩存行中，從而減少了不必要的緩存行無效。了解和解決偽共享問題對於最佳化多執行緒應用程式的效能非常重要。
如果L2緩存管理一致性協定，那麽如何確保L1級別的緩存保持一致呢？現在復雜性增加了，因為L2緩存的控制器在無效的情況下也會使L1中的副本無效，而L1必須模仿相應的L2的狀態。在這裏，擁有包含L2緩存是值得的。
如果存在L3緩存，那麽L2緩存還必須傳播系統中的無效請求和其他緩存請求。在這裏，inclusive L3緩存比a victim cache更容易處理。通常，a victim cache必須直接參與一致性協定，這會引入許多復雜性。
bus的問題
bus有存在兩個問題：由於頻寬在多個處理器之間被分割，它們不具備可延伸性。此外，在物理上，匯流排不能超過一定長度，因為如果匯流排長度超過一定限度，訊號衰減可能會成為一個問題（本質上，它變成了一個帶來許多麻煩的傳輸線，電子工程的學生可能會理解這一點.)
對於作業系統而言，重要的是 讓執行緒靠近 將要被這些執行緒存取的數據 (原文是 schedule the threads near that data that will be accessed by these threads.)。存取本地記憶體的芯片將體驗較低的延遲，而不像從遠端記憶體庫獲取數據那樣，這需要數據透過互連傳輸，而本地記憶體則使用附加的記憶體匯流排。如今的大型伺服器實際上都是NUMA系統。
Week10 同步support
在多處理器系統的歷史早期就已經認識到基於匯流排的系統可延伸性的限制。如今，匯流排僅限於芯片內部連線結構（甚至這些也受到挑戰）。效能隨著節點數量的增加而下降。
不用bus 用什麽?
早期就認識到了轉向NUMA（非均勻記憶體架構）的重要性。其他結構取代了匯流排。這些互連結構的範例包括：
- 交叉開關（Cross-bar），基本上充當n x n連線，或者說是完全圖，允許系統中的任何一對進行點對點通訊。速度快、靈活但耗電多且昂貴。不具備良好的可延伸性。
- 環形結構（Ring），基本上允許每個參與者有兩個直接連線，並使用轉發進行通訊。速度較慢、繁瑣但節能且便宜。在效能方面可延伸性差，但允許不斷添加節點。
- 交換機（Switch），具備靈活性但路由和爭用成為問題。速度快、繁瑣、耗電多且昂貴。在可延伸性和效能方面表現最佳。 通常，互連結構以階層的方式組織，用於芯片內部通訊的結構較簡單（例如匯流排），隨著系統規模擴大，會使用更復雜的結構。例如：在芯片內部，可以使用匯流排，然後四個芯片可以透過匯流排連線，而這四個芯片元件又可以透過交換機連線到其他四個芯片元件。 請註意，一些現代芯片變得非常復雜，甚至在芯片內部也使用了一些復雜的互連結構。
大型coherence會導致系統很慢而且很復雜.
option1 Limiting Coherence Domain 把coherence範圍變小.
不過現在一個chip可能64cores, L1到L2可能都很復雜了.
每個cc-NUMA系統都應該配置這個選項。如今，許多系統作為雲環境的一部份使用分區，所以這個選項，實際上也或多或少地發揮了作用。請記住，並非所有應用程式都能擴充套件到大型cc-NUMA系統。一個有趣的問題是，當只有少數特定使用者（主要是傳統資料庫系統）能夠使用它時，所有關於緩存一致性和連貫性的工作是否物有所值
Option 2: Use Broadcast to implement cc-NUMA cc就是cache coherence
在這個選項中，透過使用1對多的訊息在系統中傳播來維護緩存一致性，這實際上是建立在互連之上的。例如，如果互連是一個交換機，訊息會被發送到交換機，然後透過所有下行鏈路復制給接收方。對於互連的不同拓撲結構，其他實作方式也是可行的。這種方法曾在IBM的大型基於POWER的伺服器上使用（帶有一些實際變體）。這裏的邏輯是，大多數使用者的應用程式不會擴充套件到大型伺服器的程度。因此，根據這種思維模式，將系統分割成子一致性域將成為常態。
優點: 簡化硬體
缺點: scalability 不好 ,對 擴充套件到伺服器全部能力的應用程式 的效能不佳。
Option 3: Directory-Based cc-NUMA
怎麽實作spinlock :
L1: tstst (r0)
jnz L1
每個廠商都有做 transcation memory , 就是別的thread不能存取 這個thread的transcation memory. read 都不行.
transcation 在程式碼中不能太長, 否則就沒法scaleable.
虛擬機器
hypervisor 怎麽控制os的記憶體
觸發一個bus error
在虛擬機器 new 一個陣列, 引發brk(); 引發trap, 會去 os還是hypervisor?
答: os 在user mode run,
- trap先到hypervisor.
- hypervisor 告訴os.
- os allocate memory.
- os update page table, 嘗試寫入 hypervisor memory. os 做不到,os 告訴hypervisor,
- hypervisor 寫hypervisor memory.
一些思考題
quiz0
Brad 聲稱該程式碼可以實作大約 1 個每周期指令 (IPC) 的說法並不準確，並且有多種原因可以解釋為什麽使用給定的程式碼和硬體配置無法實作這一點。
-
記憶體存取限制：該程式碼涉及 2.56 億 (0x10000000) 個條目的大型陣列。該陣列比緩存所能容納的要大得多，並且與 ALU 操作相比，記憶體存取時間要慢得多。在流水線處理器中，記憶體存取是一個主要瓶頸，並且可能需要多個周期才能完成。高記憶體存取延遲會顯著降低 IPC。 (如果有優秀的提前讀取就可以,在給定的程式碼中，記憶體存取是隨機的（因為它取決於 的結果
random()），預取可能無法有效工作) - 數據依賴性：程式碼執行記憶體讀取和寫入，並且寫入取決於從記憶體讀取的值。這會產生數據依賴性，並可能限制並列發出多個指令的能力。在雙發射處理器中，如果指令之間存在數據依賴性，則可能會導致流水線停頓。
-
隨機記憶體存取：程式碼使用隨機記憶體存取（使用函式
random()）來存取陣列元素。隨機記憶體存取模式對緩存系統不友好，可能導致緩存未命中，進一步增加記憶體存取延遲。 - 記憶體頻寬限制：即使使用四埠寄存器檔，在存取如此大的陣列時，記憶體頻寬也可能成為瓶頸，特別是在同時進行多個存取的情況下。
- 有限的並列性：雖然處理器能夠進行雙發射，但每個周期實作兩條指令需要程式碼中具有高度的指令級並列性 (ILP)。由於隨機記憶體存取和數據依賴性的性質，所提供的程式碼沒有表現出明顯的 ILP。
實際上，由於記憶體存取延遲和依賴性，程式碼可能會在流水線中遇到嚴重的停頓，從而無法實作 IPC 為 1，更不用說每個周期兩條指令了。實際的 IPC 會低得多，並且很大程度上取決於特定處理器的架構和記憶體階層。
quiz1
-
A good assembly programmer can potentially obtain a factor of 1.5 to 2 performance improvement over optimized C code. Why don’t we program in assembler if performance is important?
因為編程速度太慢, 很多場景不是計算密集型. ( 還有就是可維護性太差, 要考慮 performance/$ , 效能/ 成本) -
A server is showing excessive performance degradation. Outline a methodology for solving the problem.
先檢查CPU, 記憶體, 硬碟和網路占用情況, 如果哪個高, 檢查為啥會高, 如果是CPU高 ,(說明 code is flawed or CPU 不夠用了) . 如果是記憶體占用大, (會換入換出多, 傷害效能)嘗試cache hit rate更大的程式 . ( back storage不夠導致IO bottleneck) , 換更強大的硬體總是可以解決問題.
(檢查bottleneck, profile code 理解哪裏花的時間最多, 應該檢查盡可能多的system components, ) - A big problem in the supercomputing field is the difficulty of writing code that can exploit the parallel architecture. Not only writing multithreaded and message-passing codes is difficult, but also the performance debugging phase can often be very frustrating. Therefore, it has been argued that a better metric is to measure the 「time-to-solution」 to evaluate a system. The time-to-solution includes the time to write a program to solve the problem, and the running time of the machine to produce an answer. Critique this metric and consider its practical use.
答案: Time to solution is a useful metric in some situations where the programmer’s time is a large component in the time to arrive to a solution. 不過, 如果每天都要執行這個程式, 很久也不會改程式, 那麽running time就很重要了, the time to solution converges to simply the runtime of the program, given that the initial programmer’s time will be a small component of the overall time to solution
quiz2
- Consider adding hardware multithreading to a core. What is the impact on throughput as measured by instruction per cycle, and what is the impact on latency as measured by the time a thread can finish a certain number of instructions?
(可以keep processor busy, 分享same pipeline cache 和memory頻寬, 所以code locality好的話, 可以充分exploiting pipeline bubbles, ) 吞吐量會上升. latency可能上升. (但是competition 可能會slow down each thread , 所以latency 可能會變大)
2 Consider Amdahl’s law. There is some code that consists of a sequential part and then a recursive function. How do you apply the law in this case?
(A recursive function can be converted into a loop and vice versa, 但是其實編譯器不知道怎麽deal with recursive functions , 如果可以那就可以用這個law. 並列 recursive function, 可以express a limit on the improvement)就是並列定律, sequential part 是不能被並列的, 這一部份時間沒法縮短
3 A system shows utilization of 60% at the network interface, 60% in the memory bus, and 15% at the CPU. If you increase the capacity of the network and memory, what would be the impact on performance
沒(太大)變化, 因為都不是瓶頸.
quiz3
1 可以並行嗎？
add R1, R2, R0
ld R3, (SP)
add R1, #4
add R6, R3, R4
答案: only the first and second can be issued concurrently. The third instruction needs the outcome of instruction 1, and also instructions 3, 4 and 5 are dependent in a sequential manner.
2
A pipeline consists of 10 stages. What is the maximum number of instructions that can be running concurrently?
答案: 可以用10個, 但是這是沒有bubble的情況, 最大可能性, This is not very common.
3
Six arithmetic instructions are followed by a jump instruction. Do you foresee any effect of the jump instruction on the pipeline performance?
答案:
The jump instruction will require getting an instruction that may not be in sequential order with the flow. This could precipitate a cache miss in the instruction cache. This can lead to a bubble in the pipeline. If the jump instruction is conditional, then a big bubble may ensue 接著發生 because the miss instruction cache , miss TLB , distrub the pipeline.
4
ld R3, (SP)
add R0, R3, R4
sto R0, (SP) ld R3,(SP+4)
add R1, R3, R4
sto R1,(SP+4)
Is it possible to issue instructions 1 and 4 simultaneously? If so, show how. If not, argue why.
誤區： 不能, 因為 sp 依賴instruction 3 . 3 依賴2, 2 依賴1 .
答案: 可以, r3就是一個臨時變量, 用寄存器重新命名就可以.
Using simulation, you discover that the workload in problem 1 now finds its data in the L3 98% of the time. What is the average time to load an item from memory as seen by the processor. If the addition of the L3 will increase the cost of the processor by 50%, do you believe that this is worth doing?
答案： 添加 L3 緩存是否值得處理器成本增加 50% 取決於應用程式的具體要求和限制。如果應用程式對數據存取時間高度敏感，並且效能改進證明了成本的合理性，那麽它可能是值得的。但是，如果成本效益更為關鍵，或者效能提升對於應用程式的需求來說並不顯著，則額外的成本可能不合理。此決策通常取決於特定用例、預算限制和效能要求等因素。
