計算機結構小記 v1

作者：   發佈於：  

Perfomance 與 ExecTime 為反比關係。

To retain the value of an individual instruction for its other four stages, the value read from instruction memory must be saved in a register. Similar arguments apply to every pipeline stage, so we must place registers between any two stages on the pipline datapath. Such register is called "Pipeline Register".

對一個指令而言，為了要在其他四個階段也都能夠讀取到指令本身的內容，於第 一個階段讀取 Instruction Memory 所得之值必定要存於某個暫存器之中。而每 一個 stage 也都有此需求。是故，在 pipeline datapath 上之 stage 分界處 必定要擺放若干長度的暫存器，即稱為「Pipeline Register」。

Pipeline Hazard 有三種：

由於部份功能單元沒有管線化，或是所需之資源沒有複製足夠多份，使oCPU 無 法支援某些次序指令的執行。

發生在會修改 Program Counter 的指令（Jump/Branch/else） 是最影響效能的 Hazard。解決方法有四種：

  1. flush the pipeline 2. branch predict taken 2. branch predict not taken 4. dealyed branch.

  2. Data Hazard

在連續數個指令都存取同一個暫存器時可能會發生的 Race Condition。會造成 執行時 read/write 指令的順序與在組語之中的順序不同。

Data Hazard 又分為 RAW, WAW, WAR 三種，其中以 RAW 最為常見，又，在 Pipeline stage 長度恆定的情況之下，很少會發 WAW 與 WAR data hazard。

由於製成、成本、經濟方面面的因素，記憶體單位不可能全部都使用最快速容量 又最大的硬體。一般說來，分級的記憶體是以金字塔狀從頂端排下來，越接近頂 端的記憶體單位速度越快，但相對地，容量也越小。越接近底端的記體單位速度 越慢，但容量也較大。每層大小的比例可能會在十倍與萬倍以上不等。

要使這樣的分級架構十分有效率地運作，「快取」機制便是解決之道。快取機制 可以存於相鄰兩層的記憶體單位之間，從上層較快速的記憶體單位的空間之中撥 出若干大小的容量專司暫存下層記憶體之內容。如此一來便可以上層之快速存 下層記憶體之資料。

在一般 i386 PC 的計算機結構之中，最高兩層的記憶體分別為 L1 與 L2 Cache， 也就是專門做為主記憶體之暫存單位之快取記憶體，L1 記憶體存在於 CPU 之中。 L2 Cache 則為主記憶體與 L1 之間，再之下則為主記憶體，更下層的儲存單位 則為硬碟機。

一般而言，直至主記憶體之存取與相關的快取記憶體管理 (L1 與 L2)都是由是 CPU 或相關的硬體直接實做，這是考量到上層記憶體十分的快速，即是 miss 也 影響不大。但虛擬記憶體之快取機制則必由作業系統方面以軟體實做。這是因為 通常硬碟機之 latency 遠大於主記憶體，因此需要非常完善的管理機制，盡可 能減低 Miss rate，以軟體實做彈性較大，也可以進行非常複雜的 Scheduling 演算法。

在記憶體層級架構之中，虛擬記憶體專司管理主記憶體與磁碟機之間的快取機制。 除此之外，亦可 _(1)_使單一程式之定址空間超越主記憶體的上限__ 。在近代 計算機結構之中，虛擬記憶體更 _(2)_使多行程得以共享部分的記憶體空間__ ，節省所需記憶體總量，同時，亦提供了多行程存取 _(3)_共享記憶體之保護 (Protection) 機制__。

對於記憶體與磁碟之間的快取而言，由於 Page fault 之代價非常昂貴，必須盡 量降低 Miss Rate。所以虛擬記憶體的快取機制訂為： Write-back 、 Fully-associative。

考慮單一 BUS 、單一記憶體、多處理器、每個處理器各自搭載各自的 cache 的 情況。由於某實體記憶體區塊可能會同時被一個以上的處理器同時進行存取，必 須避免發生資料在多個 cache 之間不同調的情況。

多處理器之間的 Cache Race Condition 主要是發生在有寫入動作的時候，如果 純粹只有讀取的動作並不會造成任何不協調的問題。

這種方式是對 Cache 以及 BUS 進行窺探的動作，從偷窺得知 Cache 的行為， 進而決定該採取的活動。因此對於每個 Cache Unit 都會有一個對應的 Snoop Unit。如果某個處理器對記憶體區塊 A 進行寫入動作，其他的 Snooper 會從 BUS 上面發現這個動作，並且進行類似這樣子的程序：

  1. 檢查自己的 Cache 是否也存有區塊 A 的資料

  2. 如果有，則採取以下某種策略 2.1 Write-invalidate , 將快取區塊 A 「無效」 2.2 Write-update , 直接「更新」快取區塊 A 的內容

  3. 根據策略不同，快取區塊 A 會有不同的更新方式 3.1 Write-invalidate: 由於只是設定成「無效」， 資料要等下一次 CPU 進行存取時重新從記憶體區塊取回。 3.2 Write-update: 資料會立刻更新。

  4. 多工管理

  5. 麵包店的排隊演算法

此一演算法之基本概念即是一般人去銀行「領號碼牌」之行為。只要確定每個人 都有一個號碼，便可藉由號碼之大小決定下一個可進入 Mutex section 的程序。 但與生活狀況的不同點在於，在銀行，兩個人並不會抽到同一個號碼，但在多工 作業系統的環境下，同時準備要進入 Mutex section