Elsa CHOI

Elsa CHOI

02325-系統結構

3 minute read

Published:

02325計算系統結構溫習

  1. 計算機組成包括機器級內部的數據流和控制流的組成以及邏輯設計
  2. 計算機根據操作數據或信息存放的位置，分別有面向主存、面向寄存器和面向堆棧的尋址方式
  3. 總線按在系統中的位置分芯片級、板級和系統級
  4. CACHE是CPU和主存增設的高速的、小容量和每位價更高
  5. 標量流處理器的性能主要有吞吐率、加速率和效率
  6. 仿真指令系統、存儲系統和I/O系統和控制檯
  7. 陣列處理機的構形分分佈式存儲和集中式存儲
  8. 多處理機有緊耦合和鬆耦合
  9. 數據令牌處理方式不同，可把數據流計算機分成動態和靜態兩類
  10. 計算機系統設計的主要任務包括系統結構、組成和實現的設計

第一章

系統結構的層次結構

0 微程序機器

1 傳統機器

2 操作系統機器

3 滙編語言

4 高級語言

5 應用語言

系統結構

對計算機系統中各級界面的定義及其上下的功能分配

組成

計算機系統結構的邏輯實現，包括機器級內部的數據流和控制流的組成及邏輯設計

機器級內部各事件的排序方式與控制機構、各部件的功能及各部件間的聯系

實現

物理實現，包括處理機、主存等部件的物理結構、器件的集成度和速度、器件、模塊、插件、底板的劃分與連接專用器件的設計、微組裝技術、信號傳輸、電源、冷卻及整機裝配技術

系列機對計算機發展的意義

  • 可較好地解決軟件設計環境要求相對穩定和硬件、器件、組成等技術飛速發展的矛盾
  • 軟件可以豐富積累
  • 器件、硬件和組成能不斷更
  • 使之短期內應能提供性能更好、價格更便宜的新機器、有力地促進計算機的發展

軟件需要的穩定硬件、器件和組成矛盾→能更新→軟件多→短期內有競爭力的機器

器件的發展對系統結構和組成影響

  • 器件集成度高，使器件的速度迅速提高，機器主頻和速度也有數量級的提高
  • 高速、廉價的半導體存儲器的出現，使解題速度得以迅速提高的高速緩沖存存儲器和虛擬存儲器的概念真正實現
  • 現場型PROM器件，使微程序技術得以實現
  • 高速相聯存儲器的實現，促進相聯處理機這種結構的發展，推動向量機、數組機和數據庫的發展

軟件兼容的定義和系列機對軟件兼容的要求

  • 機器語言程序及編譯程序都能不加修改地通用於系列內各檔機器，則稱各檔機器是軟件兼容
  • 同一系列內的軟件向上兼容
  • 系列機軟件必須向後兼容，力爭向前兼容

軟硬件比例分配

  • 軟件
    • 提高軟件功能的比例可降低硬件成本
    • 提高系統的靈活性、適應性
    • 但解題速度會下降，軟件設計費用和所需存儲用器增加
  • 硬件
    • 提高硬件可提高解題速度，減少程序所需的存儲空間
    • 但會增加硬件成本、降低硬件利用率
    • 降低系統的靈活性、適應性

軟件移植中採用系列機的辦法和優點

  • 方法：
    1. 在軟、硬體介面上設定好一種系統結構
    2. 軟體設計者按照此設計軟體，硬體設計者根據機器速度、效能、價格的不同選擇不同器件、硬件和組成、實現科技，研製並提供不同檔次的機器
  • 優點：
    1. 較好地解決了軟件環境要求相對穩定和硬體、器件科技迅速發展的衝突；
    2. 軟件環境相對穩定就可不斷積累、豐富、完善軟件，使軟件產量、質量不斷提高
    3. 同時又能不斷採用新的器件和硬體技術，使之短期內即可提供新的、效能不斷提高的機器

位串字串，位並字串，位片申字並，全並行

  1. 位串字串,只能同時處理一個字的一位,無並行性,例如,位卑行計算機;(1分)
  2. 位並字串,同時可處理一個字的所有位,例如,簡單並行的單處理機;(1分)
  3. 位片申字並、同時處理多個字的同一位,例如,相聯處理機 STARAN、MPP等處理機;(2分)
  4. 全並行,同時處理多個字的全部或部分位組,例如,全並行陣列處理機 ILLIAC

模擬和仿真區別

  • 仿真：是使用微程序解釋，解釋程序存儲於控制存儲器
  • 模擬：是使用機器語言解釋，解釋程序存儲於主存中

透明性

  • 透明性概念:客觀存在的事物或屬性從某個角度看不到,稱這些事物和屬性對它 是透明的。(2分)
  • 對於計算機系統結構透明的有數據總線寬度,陣列運算部件,通道是採用結合 型還是獨立型, Cache存儲器,存儲器的模M交叉存取,串行、重疊還是流永控制方 式。(4分)

匯編語言透明不透明

P280

第二章

簡述指令字格式優化的措施

  • 指令碼
    • 採用擴展操作碼，並根據指令的頻度$p_i$的分佈狀況選擇合適的編碼管道，以縮短操作碼的平均碼長；
  • 尋址方法
    • 採用多種㝷址方式，以縮短地址碼的長度，並在有限的地址長度內提供更多的地址資訊
  • 地址碼
  • 採用0、1、2、3等多種地址制，以增強指令的功能；
  • 在同種地址制內再採用多種地址形式，讓每種地址字段可以有多種長度，且讓長操作碼與短操作碼進行組配；
  • 在維持指令字在記憶體中按整數邊界存儲的前提下，使用多種不同的指令字長度

擴展→多種尋址方式→多種地址制→長短操作混合→不同指令長度

指令重疊解釋的概念及實現重疊解釋必須滿足的要求

  • 指令的重疊解釋是在解釋第K條指令的操作完成前，就可以開始解釋第K+1條
  • 要求
    • 要解決分析和執操作的並行
    • 要解決分析與執操作上控制上的同步
    • 要解決指令間各種相關的處理

堆棧計算機概念和其特點

1）有堆棧數據表示的機器稱為堆棧機器；

2）有高速寄存器組成的硬體堆棧，使堆棧的存取速度是寄存器的，容量是主存的；

3）豐富的堆棧指令，直接對堆棧中的數據進行各種運算；

4）有力地支持高級語言程式的編譯；

5）有力地支持副程式的嵌套和遞迴調用。

ROM表單元數和字長，並說明規則

  1. ROM表共需$2^k$個單元,
  2. 地址用$k$位二進制碼錶示
  3. 每個存儲單元字長 $k-1$位
  4. 當存儲器k位地址碼之高$k-1$位爲全“1”時，對應單元內容填$k-1$位全“1”
  5. 餘情況按$k$位二進制地址碼最低位爲 “0”捨棄，爲“1”進1來填$k$位內容。

數據表示

  • 數據表示反映了各種數據元素或信息單元之間的結構關係數據結構
  • 要通過軟件映像變換成機器所具有的各種數據表示來實現。不同的數據表示可爲數據結構 的實現提供不同的支持,表現在實現效率和方便性上不同。
  • 數結構和數據表示 是軟件和硬件的交界面。(3分)

簡述引入數據表示的原則

  • 系統的效果是否有顯著提高。包括實現時間和存儲空間是否有顯減少；實現時間是減少又主要看主存和處理機之間傳遞的信量是否減少
  • 看引人這種數據表示後，其通用性和利用率是否提高，如果只對某種資料結構的實現效率高、而對其他資料結構的實現效率低，或應用較少，將導致性價比下降。

CISC 問題

  1. 指令龐大，多於200
  2. 指令操作繁雜，執行速度低
  3. 指令系統龐大，各種指令的使用頻度都不會太高，不但增加機器設計人員負擔，也降低性價比
  4. 使高級語言編譯程序選擇目標指令的範圍太大，難以優化生成高效機器語言程序，編譯程序也太長、太複雜

    RISC

  • 設計
    • 確定指令系統，只選擇使用頻度高的那些指令，和少量能有效支持操作系統、高級語言實現及其他功能的指令
    • 減少指令的尋址方式，一般不超過2種。全部指令都是相同長度
    • 所有指令在一週期完成
    • 擴大通用寄存器，一般不少於32個。盡量減少訪存，所有指令只有存、取指令訪存，其他指令一律只對寄存器操作
    • 精簡指令和優化設計編譯程序，簡單、有效地支持高級語言的實現
  • 優
    • 簡化指令系統設計，適合VLSI實現(多CACHE，增強CPU吞吐率)
    • 提高計算機的執行速度和效率(減少訪存次數，採用大量寄存器，多窗口；指令字節相同，合適流水)
    • 降低設計成本
    • 可直接支持高級語言的實現
  • 缺
    • 指令少，CISC上由單一指令完成的某些複雜功能需要多條RISC才能完成，加重匯編語言程序的負擔，增加機器語言程序的長度
    • 對浮點運算的執行和虛擬存儲器的支持雖有很大的加強，但仍顯得不足。
    • RISC的編譯程序比CISC難寫

第三章

\[B=\frac{m}{WT_m}\]

其中$B$為最大頻寬，$m$為主存模數，$W$為字數

總線形式

總線形式;(1分)環形互連形式;(1分)交互開美形式;(1分)多端口存儲器形式; 分)開關樞細結構形式。(2分

總線串聯鏈接

  • 優
    • 選擇算法簡單，用於解決總線控制線少，只需3根
    • 部件增減容易，可擴充性好
    • 邏輯簡單，容易通過重復設置提高可靠性
  • 缺
    • 總線可用線及其有關電路的失效敏感，如果某一部件$i$不能正確傳送總線可用信號，則$i$以後的部件都不可得到總線的使用權

集中式定時查詢

  • 優
    • 計數初始值和部件號可由程序制定，即優先次序可用程序控制，靈活性強
    • 不會因某個部件失效而影響其他部件對總線的使用，可靠性高
  • 缺
    • 控制線數較多，$2+log_2N$
    • 部件數受限於定時查詢數的線數，擴展性差
    • 控制複雜
    • 總線分配的速度決定於定時計數信號的頻率和部件數，不能很高

集中式獨位請求

  • 優
    • 總線分配速度快，所有部件的總線請求同時送到總線控制器，不用查詢
    • 控制器可用自設定方式靈活確定下一個使用總線的部件
    • 方便隔離失效部件的請求
  • 缺
    • 控制線過於多，$2N+1$
    • 總線控制器複雜

中斷分類根據和分類目的

  • 目的
    • 減少中斷處理程序的入口
    • 每一類給一個中斷服務程序總入口
    • 再由軟件分支轉入相應的中斷處部分
    • 可以減少中斷服務程序入口地址形成的硬件數量
  • 根據
    • 把性質相近、中斷處理過程類似的歸為一類

字節多路、數組多路和選擇

  • 字節
    • 字節適用於連接大量的像光電機等字符類低速設備。它們傳送一個字節的時間很短，但字符間的等待時間很多。
    • 通道數據寬度為單字節
    • 以字節交叉方式輪流為多臺低速設備服務
    • 字節多路通道適合於連接大量的字符類低速設備。滿負荷時,設備對通道要求 (的實際流量應是所在各設備的流量之和。(2分)
  • 數組
    • 適合連接多臺高速設備，傳送開始前的尋址輔助操作時間很長
    • 數據寬度為定長塊，傳送完K個字節數據後就重新選擇下個設備，再傳送該設備的K個字節
    • 以成組方式輪流交叉地為多臺服務
    • 某臺需要傳送N個字節， 需要先後經$\frac{N}{k}$次申請使用通道總線
    • 數組多路通道適合於連接高速設各。滿負荷時,設備對通道要求的實際流量應 是所在各設備中,流量最大的那個,(2分)
  • 選擇
    • 適合優先級高的高速設備，讓它獨佔通道，只能執行一道通道程序，
    • 數據寬度是可變長塊，一次對N個字節全部傳送
    • 數據傳送期內只選擇一次設備
    • 選擇通道適合於連接高優先級的高速設備。滿負荷時,設備對通道要求的實際 流量應是所在各設備中,流量最大的那個。(2分)

程序定態再定位和動態再定位的含義及實現方法

  • 靜態指程序在執行時物理地址不再改變的定位技術
  • 動態是指在執行每條指令時才成物理地址的定位技術

中斷請求

  • 機器校驗： 掉電、地址、數據、通道錯
  • 程序性中斷（訪管）：指令格式、數據格式、程序執行異常、各種溢出、除數為0，主存訪問方式保護
  • 外部中斷：各種定時、外部
  • 重啟中斷
  • IBM370有六種中斷（P105）

頁面失效

  • 由於堆梭型替換算法具有分配給該道程序的實頁數n增加,命中率H會單調上升這一特點,可對LRU算法加以改進。
  • 即根據各道程序運行中的主存頁面失效率,將內存實頁面由操作系統動態調節分配給各道程序,從而使整個系統總的主 存命中率和主存利用率得到提高。

第四章

CACHE 地址映像

  • 地址映像就是每個主存塊按某種規則裝入CACHE 中
  • 地址變換是每次訪CACHE 時怎樣將主存地址變成CACHE地址
  • 映像規則的選擇要求：
    • 除了看所用的地址映像和變換硬件是否速度高、價格低和實現方便外
    • 還要看塊沖突概率是否低
    • CACHE 空間利用率是否高

CACHE增大

  • 增大主存：對命中率$H_c$不影響。
  • 增大主存能使$t_m$有所增大，若$H_c$已很高，這種增大，對存儲週期$t_a$不會有明顯改變
  • 增大CACHE的塊數，而塊的大小不變，則CACHE容量增大，由於LRU是堆棧，$H_c$上升，使$t_a$縮短
  • P302

第五章

吞吐率、加速比和效率

  • P.183
\[\text{吞吐率}=\frac{\text{任務數}}{\text{流水用的時間}}\] \[\text{加速比}=S_p=\frac{\text{串聯用的時間}}{\text{流水用的時間}}\] \[\text{效率}=\frac{\text{設備使用的時間}}{\text{整個運行時間}}=\frac{\text{設備使用的時間}}{\text{時乘空的面積}}= \frac{S_p}{\text{處理器數}}\]

並行性三種途徑

  • 時間重疊：並行引入時間，讓多個處理過程在時間上錯開，輪流重疊地使用同一套硬件設備的各個部份
  • 資源重複：是在井行性概念中引入空間因素，通過重複設置硬件資源來提高可靠性
  • 資源共享：用軟件方法讓多個用戶按一定時間順序輪流使用同一資源來提高其利用率，相應也就提高系統的性能

超流水線

  • 方法
    • 注重開發時間並行性，在公共的硬件上採用較短的時鐘週期，深度流水來提高速度
  • 特點
    • 並行度高,充分利用公共的硬件，但是需要高速時鐘機制

全局性相關

全局性相關指轉移指令和後續指令的相關。如果轉移成功，則進入流水的後續指令失效，需要將轉移後的地址的下一條指令加載進流水線，這樣便造成了流水線性能的下降。

全局性相關的幾個應對方法

  1. 猜測法
  2. 加快或提前形成條件碼
  3. 延遲轉移
  4. 加速短循環程序的處理

第六章

CRAY-1

P.207

  1. $V_3 \leftarrow $存儲器, 時間$6T$
  2. $V_2 \leftarrow V_0+V_1 : B+C \rightarrow K$, 時間$6T$
  3. $V_4 \leftarrow V_2\times V_3 : K\times A \rightarrow D$, 時間$7T$
  • 1,2,3串: $1+6+1+N-1+1+7+1+N-1+1+6+1+N-1=22+3N$
  • 1,2並, 再執行3: $1+6+1+N-1+1+7+1+N-1=15-2N$
  • 采用鏈接技術(類似流水):$1+6+1+1+6+1+1+7+1+N-1=16+N$
    • 1{啟動訪存,送浮加部件}+6{訪存+浮加}+1{存$V_3,V_2$}+{送$V_3,V_2$浮乘}+7{浮乘}+1{存$V_4$}

脈動陣列

  • 原理
    • 每個處理單元(PE)結構相同，一般由一個加法/邏輯部件或加法/乘法運算部件再加上若干鎖存器構成
    • 所有處理單元的數據鎖存器都受同一時鐘控制
    • 運算時根據在陣列結構的各個處理單元間沿各自的方向同步向前推進
  • 特點
    • 結構簡單、規整，模塊化強，可擴充性好
    • PE間數據通信距離短、規則，使數據流和控制流的設計、同步控制等均簡單規整
    • 極高的計算機井行性，可通過流水獲得很高的運算效率
    • 陣列與外界的I/O通信量少，降低了系統主存與I/O系統頻寛的要求
    • 脈動陣列結構的構形與特定的計算機任務和算法密切相關，具有專用性

簡述SIMD系統的互連網絡的設計目標

  • 結構不要過於複雜，以降低成本；
  • 互連要靈活，以滿足算法和應用的需要；
  • 處理單元間資訊交換所需傳送步數盡可能少，以提高速度效能；
  • 能用規整單一的基本構件組合而成，或經多次通過或者經多級連接來實現複雜的互連，使模塊性好，以便於用VLSI實現並滿足系統的可擴充性。

陣列機與流水機分別

(1) 陣列機利用的是資源重復，和並行性中的同時性 (2) 對陣列機的利用率相對沒有多個功能流水部件那樣高。硬件價格下降及系統結構改進才能有高的性能價格比 (3) 陣列機提高速度主要靠增大處理單元數 (4) 陣列機處理機使用簡單、規整的互連網絡來確定處理單間的連接。 (5) 比單功能流水機靈活。比流水機專用性強很多，其結構和採用的並行算法緊密聯系。

互連函數

  • Cube
\[C_i(P_{n-1}\dots P_i \dots P_0)=P_{n-1}\dots\bar{P_i}\dots P_0\]

  • PM

    \[\text{PM}_{\pm i}(j)=j\pm 2^i \quad \text{mod} \quad N\]

  • Shuffle

\[S(P_{n-1}\dots P_0)=P_{n-2}\dots P_{0} P_{n-1}\]
  • Butterfly
\[B(P_{n-1}\dots P_0)=P_{0}P_{n-2}\dots P_{1} P_{n-1}\]

存儲分散

  • P229

$ n\times n$數組並行存儲器中同一列兩個相鄰元素地址錯開的距離為$\delta_1$,同一行相鄰元素地址錯開的距離為$\delta_2$,當 $m=2^{2p}+1$,實現無沖突訪問的充份條件是

\[\delta_1=2^p, \quad \delta_2=1\] \[j=(a\delta_1+b\delta_2+c) \quad \text{mod} \quad m\] \[i=a\]

其中, 任意$A_{ab}$在分配放在$A_{ij}$位置上,$c$是$A_{00}$所在體號地址，通常為0。

累加和

P（214）

  1. 放置全部$PE_i$為活躍狀態，$0\leq i \leq 15$,

  2. 放置全部$A(I)$從$PEM_i$的$\alpha$單元讀到對應$PE_i$的累加寄存器$RGA_i$中，$0 \leq i \leq 15 $

  3. 令$K=0$；

  4. 將全部$PE_i$的$RGA_i$，轉輸到傳送寄存器$RGR_i$，$0\leq i \leq 15$

  5. 將全部$PE_i$，$RGR_i$經過互連網絡各下傳$2^K$步距，$0\leq i \leq 15$

  6. 令$j=2^K-1$,放置$PE_0$-$PE_j$為不活躍狀態；

  7. 處理活躍狀態的所有$PE_i$，執行$（RGA_i）：=（RGA_i）+（RGR_i)$，$j\leq i \leq15$

  8. $K:=K+1$

  9. 若$K<4$，則轉回（4）

  10. 置全部$PE_i$，為活躍狀態，$0\leq i \leq 15$；

  11. 將全部$PE$的累加寄存器內容（$RCA_i$）存應$PEM_i$的$\alpha+1$單元中，$0\leq i \leq 15$。

第七章

多處理機與陣列機不同

  1. 井行等級的不同。
    • 陣列是向量指令的井行，是井行性中的同時性，資源重複
    • 多處理是任務間的井行，是井行性中的井發性
  2. 硬件中，多處理需要多個指令控制，通主共享主存或機間互網絡實現異步通信
  3. 算法中，不限於向量、數組，還要挖掘和實現更多算法隱性的井行性
  4. 系統管理上，要更多地依靠操作系統等軟件手段，有效地解法資源分析和管理，特別是任務調度、進程的同步和通信問題

羣集系統比起傳統並行系統優點

  • 系統有更高的性格比
  • 開發周期短
  • 可擴展性好
  • 資源利用率高
  • 用戶投資風險小
  • 用戶編程方便

先記性價比→投資小→擴展易→編程易→開發短→利用資源高

任務粒度的大小

  1. 粒度太小，輔助開銷大，系統效率低
  2. 粒度太大，井行性低，並行度低，性能不會太高
  3. 均勻任務粒度大小
  4. 採取措施減少輔助開銷，以保證系統性能隨處理機數目的增大能有較大的提高

MPP

  • 數百至數千個高性能、低成本的RISC微處理機可進行中粒度和細粒度大規模並行處理，構成SIMD 或MIMD 系統
  • 具性價比高和可擴展性好的優點
  • 專門的互連網絡互連
  • 特點
    • 都有本地存儲器，經網絡接口電路連到專門的互連網上，實現與其他結點的通信
    • MIMD型的MPP系統是一個異步系統，其每個處理結點使用商品化的微處器
    • 結點內使用物理上分佈的獨立編址的本地存儲器，

多處理機各自獨立型操作系統優缺點

  • 優
    • 將控制功能分散給多臺處理機，很適應分佈處理的模塊化結構特點，
    • 減少對大型控制專用處理機的需求：系統可靠性高，可取得較高的系統效率
  • 缺
    • 進程調度複雜，開銷加大，
    • 各處理機負荷的平衡比較困難，
    • 降低存儲器的利率

主從, 浮動和各自獨立操作系統

  • 主從
    • 優
      • 沒有系統管理控制表格的訪問沖突和阻塞
    • 缺
      • 對主處理機的可靠性要求很高
      • 不夠靈活

數據輸出相關

  • 兩個程序段之間若有先寫後讀的數據相關，不能並行，只在特殊情況下可以交換串行
  • 若有先讀後寫的數據反相關，可以並行執行，但必須保證其寫入共享主存時的先讀後寫次序，不能交換串行；
  • 若有寫-寫的數據輸出相關，可以並行執行，同樣需保證其寫入的先後次序，不能交換串行；
  • 若同時有先寫後讀和先讀後寫兩種相關，以交 換數據為目的時，必須並行執行，且讀、寫要完全同步，不許順序串行和交換串行；
  • 若沒有任何相關或僅有源數據相同時，可以並行、順序串行和交換串行。

第八章

數據流和控制流特點

  • 數據
    • 沒有共享變量的概念
    • 指令執行順序只受指令中數據相關性制約
    • 數據是以數據令牌方式直接在指令間傳遞
  • 控制
    • 通過訪問共享存儲單元讓數據在指令間傳遞
    • 指令執行順序隱含於控制流中，但可用專用的控制操作符來實現並行處理
    • 指令的順序受程序計數器控制

數據驅動和需要驅動

  • 需求驅動
    • 操作按數據需求所決定的次序進行
    • 是按需求值，只有當某一函數需要用到某一自變量時，才驅動對該自變量的求值操作，是一種滯後求值的策略
    • 不需不必要求值，輔助開銷少，有利提高系統效率
  • 數據驅動
    • 按輸入數據可用性決定的次序進行
    • 只要所要求的輸入數據全部就緒，即可驅動操作執行時，是一種提前求值的策略
    • 不需要程計數器，指令基本無序

數據流缺點

  • 數據相關性強，則並行性成分不多
  • 給數據建立、識別、處理標記，需要花費較多的輔助開銷和較大的存儲空間
  • 數據流計算機不保存數組
  • 變量代表數值，程序員無法控制存儲分配
  • 互聯網絡設計困難，I/O系統不夠完善
  • 沒有程序計數器，診斷和維護困難

靜態數據流和動態分別

  • 靜態數據流計算機的數據令牌未加標記，不支持遞歸的並發激活，只能支持一般的循環
  • 動態數據流計算機讓令牌帶有標記，通過對令牌的配對來支持遞歸的井發激活

歸約機

  • 歸約機採用需求驅動，執行的操作序列取決於對數據的需求。在歸約機中，對數據的需求又來源於函數式程序設計語言對表逹式的歸約
  • 結構特點
    • 面向函數式語言的非控制流計算機，採用需求驅動或數據驅動方式
    • 有大容量的存儲器或虛擬存儲器，有高級動態存儲分配和管理的軟、硬件
    • 有多個處理器(機)，可高度井行
    • 採用適合於函數式程序運行的處理器(機)間互連結構，特別是樹形或多層次複合互連結構
  • 有串歸約機和圖歸約機

You May Also Enjoy