1、7.1.1 并行計算機(jī)體系結(jié)構(gòu)的分類1. 按照Flynn分類法，可把計算機(jī)分成 單指令流單數(shù)據(jù)流（SISD） 單指令流多數(shù)據(jù)流（SIMD） 多指令流單數(shù)據(jù)流（MISD） 多指令流多數(shù)據(jù)流（MIMD）7.1 引 言第章 多處理機(jī)2. MIMD已成為通用多處理機(jī)體系結(jié)構(gòu)的選擇，原因： (1) (1) MIMDMIMD具有靈活性；具有靈活性； (2) (2) MIMDMIMD可以充分利用商品化微處理器在性能價格可以充分利用商品化微處理器在性能價格 比方面的優(yōu)勢。比方面的優(yōu)勢。3. 根據(jù)系統(tǒng)中處理器個數(shù)的多少，可把現(xiàn)有的MIMD 機(jī)器分為兩類 （每一類代表了一種存儲器的結(jié)構(gòu)和互連策略）（每一類代表了一

2、種存儲器的結(jié)構(gòu)和互連策略） (1) (1) 集中式共享存儲器結(jié)構(gòu) 動畫動畫 這類機(jī)器有時被稱為這類機(jī)器有時被稱為 SMPSMP機(jī)器（機(jī)器（Symmetric shared-memory MultiProcessorSymmetric shared-memory MultiProcessor） UMAUMA機(jī)器（機(jī)器（Uniform Memory AccessUniform Memory Access）7.1 引 言集中共享存儲器計算機(jī)(2)(2) 分布式存儲器結(jié)構(gòu) 動畫動畫 每個結(jié)點(diǎn)包含：每個結(jié)點(diǎn)包含： q 處理器處理器q 存儲器存儲器q I IO O在許多情況下，分布式存儲器結(jié)構(gòu)優(yōu)于集中式共

3、享存儲器結(jié)構(gòu)7.1 引 言分布共享存儲器計算機(jī) 分布式存儲器結(jié)構(gòu)的優(yōu)點(diǎn) 主要缺點(diǎn)q 處理器之間的通信較為復(fù)雜，且各處理器之間的處理器之間的通信較為復(fù)雜，且各處理器之間的 訪問延遲較大。訪問延遲較大。q 需要高帶寬的互連。需要高帶寬的互連。 簇：超結(jié)點(diǎn)q 如果大多數(shù)的訪問是針對本結(jié)點(diǎn)的局部存儲器，如果大多數(shù)的訪問是針對本結(jié)點(diǎn)的局部存儲器， 則可降低對存儲器和互連網(wǎng)絡(luò)的帶寬要求；則可降低對存儲器和互連網(wǎng)絡(luò)的帶寬要求；q 局部存儲器的訪問延遲低。局部存儲器的訪問延遲低。7.1 引 言7.1.2 通信模型和存儲器的結(jié)構(gòu)模型1. 地址空間的組織方案（兩種）（兩種） (1) 物理上分離的多個存儲器作為一個

4、邏輯上共享的 存儲空間進(jìn)行編址。這類機(jī)器的結(jié)構(gòu)被稱為這類機(jī)器的結(jié)構(gòu)被稱為q 分布式共享存儲器結(jié)構(gòu)分布式共享存儲器結(jié)構(gòu) （DSMDSM: Distributed Shared-Memory): Distributed Shared-Memory)q 可縮放共享存儲器結(jié)構(gòu)可縮放共享存儲器結(jié)構(gòu) （SSMSSM: Scalable Shared-Memory): Scalable Shared-Memory)q NUMA NUMA機(jī)器機(jī)器 （NUMANUMA: Non-Uniform Memory Access): Non-Uniform Memory Access)7.1 引 言 (2) 整個地址空

5、間由多個獨(dú)立的地址空間構(gòu)成，它 們在邏輯上也是獨(dú)立的，遠(yuǎn)程的處理器不能對 其直接尋址。每一個處理器每一個處理器- -存儲器模塊實(shí)際上是一個單獨(dú)存儲器模塊實(shí)際上是一個單獨(dú)的計算機(jī)，這種機(jī)器也稱為的計算機(jī)，這種機(jī)器也稱為多計算機(jī)。多計算機(jī)。7.1 引 言q 共享地址空間的機(jī)器 利用利用LoadLoad和和StoreStore指令中的地址隱含地進(jìn)行指令中的地址隱含地進(jìn)行 數(shù)據(jù)通訊。數(shù)據(jù)通訊。q 多個地址空間的機(jī)器 通過處理器間顯式地傳遞消息完成。通過處理器間顯式地傳遞消息完成。 ( (消息傳遞機(jī)器消息傳遞機(jī)器) ) 2. 兩種通信模型7.1 引 言 消息傳遞機(jī)器根據(jù)簡單的網(wǎng)絡(luò)協(xié)議，通過傳遞消息 來請

6、求某些服務(wù)或傳輸數(shù)據(jù)，從而完成通信。 例如：例如：一個處理器要對遠(yuǎn)程存儲器上的數(shù)據(jù)進(jìn)行訪問一個處理器要對遠(yuǎn)程存儲器上的數(shù)據(jù)進(jìn)行訪問 或操作：或操作： (1) (1) 發(fā)送消息，請求傳遞數(shù)據(jù)或?qū)?shù)據(jù)進(jìn)行操作；發(fā)送消息，請求傳遞數(shù)據(jù)或?qū)?shù)據(jù)進(jìn)行操作； 遠(yuǎn)程進(jìn)程調(diào)用遠(yuǎn)程進(jìn)程調(diào)用( (RPCRPC， Remote Process Call)Remote Process Call) (2) (2) 目的處理器接收到消息以后，執(zhí)行相應(yīng)的操目的處理器接收到消息以后，執(zhí)行相應(yīng)的操 作或代替遠(yuǎn)程處理器進(jìn)行訪問，并發(fā)送一個作或代替遠(yuǎn)程處理器進(jìn)行訪問，并發(fā)送一個 應(yīng)答消息將結(jié)果返回。應(yīng)答消息將結(jié)果返回。7.1 引

7、言 同步消息傳遞 請求處理器發(fā)送一個請求后一直要等到應(yīng)答請求處理器發(fā)送一個請求后一直要等到應(yīng)答 結(jié)果才繼續(xù)運(yùn)行。結(jié)果才繼續(xù)運(yùn)行。 異步消息傳遞 發(fā)送方不先經(jīng)請求就直接把數(shù)據(jù)送往數(shù)據(jù)接發(fā)送方不先經(jīng)請求就直接把數(shù)據(jù)送往數(shù)據(jù)接 受方。受方。3.通信機(jī)制的性能指標(biāo)（3個）(1) 通信帶寬 理想狀態(tài)下的通信帶寬受限于處理器、存儲理想狀態(tài)下的通信帶寬受限于處理器、存儲 器和互連網(wǎng)絡(luò)的帶寬。器和互連網(wǎng)絡(luò)的帶寬。 7.1 引 言(2) 通信延遲 理想狀態(tài)下通信延遲應(yīng)盡可能地小。 通信延遲發(fā)送開銷 + 跨越時間 + 傳輸延遲 + 接收開銷(3) 通訊延遲的隱藏 如何才能較好地將通信和計算或多次通信之 間重疊起來

8、，以實(shí)現(xiàn)通訊延遲的隱藏。 通常的原則：只要可能就隱藏延遲。 通信延遲隱藏是一種提高性能的有效途徑，但 它對操作系統(tǒng)和編程者來講增加了額外的負(fù)擔(dān)。7.1 引 言4. 不同通信機(jī)制的優(yōu)點(diǎn) A. 共享存儲器通信的主要優(yōu)點(diǎn) (1) 與常用的集中式多處理機(jī)使用的通信機(jī)制兼容。 (2) 易于編程 與傳統(tǒng)的編程模式一致 (3) 當(dāng)通信數(shù)據(jù)較小時，通信開銷較低，帶寬利用 較好。 (4) 通過硬件控制的Cache減少了遠(yuǎn)程通信的頻度， 減少了通信延遲以及對共享數(shù)據(jù)的訪問沖突。 7.1 引 言B. 消息傳遞通信機(jī)制的主要優(yōu)點(diǎn) (1) 硬件較簡單。 (2) 通信是顯式的，從而引起編程者和編譯程序的 注意，著重處理開

9、銷大的通信。q 在共享存儲器上支持消息傳遞相對簡單在共享存儲器上支持消息傳遞相對簡單q 在消息傳遞的硬件上支持共享存儲器就困難得多。在消息傳遞的硬件上支持共享存儲器就困難得多。 所有對共享存儲器的訪問均要求操作系統(tǒng)提供地所有對共享存儲器的訪問均要求操作系統(tǒng)提供地 址轉(zhuǎn)換和存儲保護(hù)功能，即將存儲器訪問轉(zhuǎn)換為消址轉(zhuǎn)換和存儲保護(hù)功能，即將存儲器訪問轉(zhuǎn)換為消 息的發(fā)送和接收。息的發(fā)送和接收。7.1 引 言7.1.3 并行處理面臨的挑戰(zhàn) 并行處理面臨著兩個重要的挑戰(zhàn)并行處理面臨著兩個重要的挑戰(zhàn)： 。 q 程序中有限的并行性程序中有限的并行性q 相對較高的通信開銷相對較高的通信開銷理論加速比可加速部分比例

10、可加速部分比例）（11系統(tǒng)加速比系統(tǒng)加速比 = =7.1 引 言 例例7.17.1 如果想用如果想用100100個處理器達(dá)到個處理器達(dá)到8080的加速比，的加速比，求原計算程序中串行部分所占比例。求原計算程序中串行部分所占比例。 解解 動畫演示動畫演示2. 第二個挑戰(zhàn)：多處理機(jī)中遠(yuǎn)程訪問的延遲較大 在現(xiàn)有的機(jī)器中，處理器之間的數(shù)據(jù)通信在現(xiàn)有的機(jī)器中，處理器之間的數(shù)據(jù)通信 大約需要大約需要50501000010000個時鐘周期。個時鐘周期。 1. 第一個挑戰(zhàn)：有限的并行性 使機(jī)器要達(dá)到好的加速比十分困難7.1 引 言機(jī)機(jī) 器器通信機(jī)制通信機(jī)制互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)處理機(jī)數(shù)量處理機(jī)數(shù)量典型遠(yuǎn)程存儲典型遠(yuǎn)

11、程存儲器訪問時間器訪問時間SPARC Center共享存儲器共享存儲器總線總線 20 1sSGI Challenge共享存儲器共享存儲器總線總線 36 1sCray T3D共享存儲器共享存儲器3維環(huán)網(wǎng)維環(huán)網(wǎng) 322048 1sConvex Exemplar共享存儲器共享存儲器交叉開關(guān)環(huán)交叉開關(guān)環(huán) 864 2sKSR-1共享存儲器共享存儲器多層次環(huán)多層次環(huán) 32256 2-6sCM-5消息傳遞消息傳遞胖樹胖樹 321024 10sIntel Paragon消息傳遞消息傳遞2維網(wǎng)格維網(wǎng)格 322048 10-30sIBM SP-2消息傳遞消息傳遞多級開關(guān)多級開關(guān) 2512 30-100s遠(yuǎn)程訪問一

12、個字的延遲時間遠(yuǎn)程訪問一個字的延遲時間 例例 一臺一臺3232個處理器的計算機(jī)，對遠(yuǎn)程存儲個處理器的計算機(jī)，對遠(yuǎn)程存儲器訪問時間為器訪問時間為20002000nsns。除了通信以外，假設(shè)計算中的。除了通信以外，假設(shè)計算中的訪問均命中局部存儲器。當(dāng)發(fā)出一個遠(yuǎn)程請求時，本訪問均命中局部存儲器。當(dāng)發(fā)出一個遠(yuǎn)程請求時，本處理器掛起。處理器時鐘時間為處理器掛起。處理器時鐘時間為1010nsns，如果指令基本，如果指令基本的的CPICPI為為1.01.0( (設(shè)所有訪存均命中設(shè)所有訪存均命中Cache)Cache)，求在沒有遠(yuǎn)程，求在沒有遠(yuǎn)程訪問的狀態(tài)下與有訪問的狀態(tài)下與有0.5%0.5%的指令需要遠(yuǎn)程訪

13、問的狀態(tài)下，的指令需要遠(yuǎn)程訪問的狀態(tài)下，前者比后者快多少前者比后者快多少? ? 解解 有有0.5%0.5%遠(yuǎn)程訪問的機(jī)器的實(shí)際遠(yuǎn)程訪問的機(jī)器的實(shí)際CPICPI為為 CPICPI基本基本CPICPI遠(yuǎn)程訪問率遠(yuǎn)程訪問率遠(yuǎn)程訪問開銷遠(yuǎn)程訪問開銷 1.01.00.5%0.5%遠(yuǎn)程訪問開銷遠(yuǎn)程訪問開銷 7.1 引 言遠(yuǎn)程訪問開銷遠(yuǎn)程訪問時間遠(yuǎn)程訪問開銷遠(yuǎn)程訪問時間/ /時鐘時間時鐘時間 2000ns/10ns2000ns/10ns200200個時鐘個時鐘 CPICPI1.01.00.5%0.5%2002002.02.0 它為只有局部訪問的機(jī)器的它為只有局部訪問的機(jī)器的2.02.01.01.02 2倍，倍， 因此在沒有遠(yuǎn)程訪問的狀態(tài)下的機(jī)器速度是有因此在沒有遠(yuǎn)程訪問的狀態(tài)下的機(jī)器速度是有0.5%0.5%遠(yuǎn)程訪問