計算機組成與系統結構并行計算機體系結構第13章

第13早

并行計算機體系結構

洋幸￡要向客

市不算機系統結構概述

⑥并行計算機系統的設計問題

.并行計算機系統的互連網絡

-并行計算機系統的性能問題

-并行計算機系統的軟件問題

⑥S1MD計算機簡介

?M1MD多處理機簡介

卷M1MD多計算機簡介

2

計算機京彩幡構的發(fā)展歷程

硬件技術和系統結構軟件和應用

電子管和繼電器。單CPU,以程

第一代機器語言或匯編語言。單用戶。

序計數器PC和累加器順序完成定

(1945?1954)用CPU程序控制I/O。

點運算

晶體管和磁芯存儲器。用印制電

第二代有編譯程序支持的高級語言，子

路互連。變址寄存器，浮點運算；

(1955?1964)程序庫，批處理監(jiān)控程序。

多路存儲器，I/O處理機。

中小規(guī)模集成電路。多層印制電

第三代多道程序設計，分時操作系統，

路。微程序設計，流水線，高速

(1965?1974)多用戶應用。

緩存，先行處理機。

大規(guī)模集成電路。半導體存儲器。用于并行處理的多處理機操作系

第四代

多處理機，多計算機，向量超級統、專用語言和編譯器；并行處

(1975?1990)

計算機。理或分布計算的軟件工具和環(huán)境。

超大規(guī)模集成電路。高密度高速

第五代大規(guī)模并行處理，Java語言，分

度處理器和存儲器芯片，可擴展

（1991?現在）布式操作系統，萬維網，網格。

體系結構，因特網。

3

計算機余就錯構的或展方向

⑥第一個是改變馮?諾依曼機器的串行執(zhí)行模式

■超標量計算機（執(zhí)行多條指令）

■多處理機系統（共享集中或分布式存儲器）

-大規(guī)模并行處理機MPP系統

■PC或工作站組成的機群系統

4

計算機京彩幡構的發(fā)展方向

⑥第二個是改變馮?諾依曼機器的控制驅動方式

■數據驅動方式：操作數到位即可運算，無序執(zhí)行,數據流計算機是一種數

據驅動式系統結構的計算機，只要指令所需的操作數準備好就可以立即

啟動執(zhí)行，一條指令的運算結果又流向下一條指令，作為下一條指令的

操作數來驅動該條指令的啟動執(zhí)行。程序中各條指令的執(zhí)行順序僅由指

令間的數據依賴關系決定。

■需求驅動方式：驅動方式與數據流相反，無序執(zhí)行.需求驅動方式是一個

操作僅在要用到其輸出結果時才開始啟動，如果這個操作的操作數沒有

準備好、那么它就去啟動能夠得到它的相應輸入操作數的其他操作，這

樣的需求鏈一直延伸下去，直到遇到常數或者外部已經輸入的數據為止,

然后再反方向的執(zhí)行運算。歸約機就屬于需求驅動式系統結構的使用函

數式程序設計語言的計算機。

■模式匹配驅動方式：非數值型應用，主要對象為符號.在模式匹配驅動方

式中，計算的進行是由謂詞模式匹配來驅動的，而謂詞是代表客體之間

關系的一種字符串模式，主要用來求解非數值的符號演算。面向智能的

Lisp機、Prolog機和神經網絡等就屬于這種模式匹配驅動式系統結構的

計壹機。

⑥第一個發(fā)展方向已經取得了重大進展，取得了一系列的成果。而第二

個發(fā)展方向，大多數還屬于探索、研究階段，還需要進行大量的工作。

5

計算機余就錯構的臺類方法

⑥過去曾普遍將計算機系統分為巨、大、中、小、

微型機五類。

-劃分原則、這種方法是按照規(guī)模、性能、速度以至價

格的一種大致劃分。

■存在問題,,只能對同時期的計算機大致分類，劃分的

標準是隨時間而變化，每5年左右降低一個等級；另

外，這種劃分方法不能反映機器的系統結構特征。

■設計方法:

?最局性能特殊用途

?最佳性能價格比一般商用計算機

?最低價格家用計算機等

6

7

吉林大學遠程教育學院

計算機原理及系統結構

第五十三講

主講教師：趙宏偉學時：64

第13早

并行計算機體系結構

計算機余就錯構的臺類方法

合工966年，MichaelJ.FIynn提出按指令流和數據流的多倍

性對計算機系統結構進行分類。

■指令流是指機器執(zhí)行的指令序列:

■數據流是由指令流調用的數據序列,包括輸入數據和中間結果；

■―是指在系統最受限制的部件上,同時處于同一執(zhí)行階段的

指令或數據的最大數目。

指令流數據流名稱舉例

1個1個SISD傳統的馮?諾依曼計算機

1個多個SIMD向量計算機，陣列處理機

多個1個MISD目前還沒有

多個多個MIMD多處理機，多計算機

10

S1SD體系輅相

④處理器串行執(zhí)行指令；或者處理器內采用指令流水線，

以時間重疊技術實現了一定程度上的指令并行執(zhí)行；甚

至于處理器是超標量處理器，內有幾條指令流水線實現

了更大程度上的指令并行執(zhí)行。但它們都是以單一的指

令流從存儲器取指令，以單一的數據流從存儲器取操作

數和將結果寫回存儲器。

IS

SISD

11

S1MD體奈輅構

④有單一的控制部件，但是有多個處理部件。計算機以一

個控制單元從存儲器取單一的指令流，一條指令同時作

用到各個處理單元，控制各個處理單元對來自不同數據

流的數據組進行操作。這種體系結構的典型代表是陣列

處理機，一些學者認為將向量處理機也劃入此類。

SIMD12

M1SD體奈輅構

④多個處理單元，各配有相應的控制單元。各個處理單元

接收不同的指令，多條指令同時在一份數據上進行操作。

這種計算機體系結構是一種比較奇怪的組合，這已經被

證明是不可能至少是不實際的，目前為止還不存在這種

類型的計算機。

DS

MISD13

M1MD體奈輅構

④同時有多個處理單元，并且每個處理單元都配有相應的

控制單元。各個處理單元可以接收不同的指令并對不同

的數據流進行操作。大多數現代的并行計算機都屬于這

一類，多處理機系統和多計算機系統都是MIMD型的計

算機。

MIMD

14

計算機余就錯構的臺類方法

爹Flynn分類法的局限

■分類的對象主要是控制驅動方式下的串行處理和并行處理計算機。

對于非控制驅動方式的計算機，就不適合采用Flynn分類法；

■把兩個不同等級的功能并列對待，通常，數據流受指令流控制從

而造成MISD不存在；

■分類太粗，對流水線處理機的劃分不明確，標量流水線為SISD,

向量流水線為SIMD。

④其他的分類方法

■美籍華人馮澤云教授在1972年提出了按最大并行度來定量描述各

種計算機系統的馮氏分類法。

■WolfganHandler在馮氏分類法的基礎上，于1977年根據并行度和

流水線提出了另外一種分類法。

-1978年由D.J.Kuck提出按控制流和執(zhí)行流分類。

15

開行計算機系您或展的原因

前需求永遠是并行計算機系統發(fā)展的動力。

■隨著計算機速度的提高，人們對計算機性能的要求也

越來越高。例如科學計算、工程和工業(yè)設計等都需要

高性能計算。

■芯片的速度不可能無限地提高，并行計算機可以處理

越來越復雜的問題。芯片的速度要受到光速的制約，

但芯片的集成度還有發(fā)展的空間。

令大量商品化的處理器的出現為設計并行計算機系

統提供了可能。

＞并行計算機系統獲得快速發(fā)展和處理機間通信技

術的發(fā)展密不可分。

16

P333

開行計算機系您的合美

共享內存消息傳遞

17

P333圖13.4并行計算機的分類

開行奸算機系挑的臺美

⑥MIMD體系結構

■多處理機系統——基于共享存儲器

?系統中只有唯一的地址空間，所有的處理器共享該地址空間。

?唯一的地址空間并不意味著在物理上只有一個存儲器。共享地

址空間可以通過一個物理上共享的存儲器來實現，也可以通過

分布式存儲器并在硬件和軟件的支持下實現。

■多計算機系統——基于消息傳遞

?每個處理器有自己的存儲器，該存儲器只能被該處理器訪問而

不能被其它處理器直接訪問，這種存儲器稱為局部存儲器或私

有存儲器。

?當處理器A需要向處理器B傳送數據時，A把數據以消息的形式

發(fā)送給B。

18

開行俄、可擴展俄前可編程植

e----------

⑥并行性(Parallelism)的基本概念

■并行性是指在同一時刻或同一時間間隔內完成兩種或

兩種以上的工作。

■并行性還可以進一步分為同時性和并發(fā)性，前者指同

一時刻發(fā)生的并行性，后者指同一時間間隔內發(fā)生的

并行性。

⑥并行的粒度問題

-粗、中、細三種不同的并行粒度，共享內存的多處理

機系統用于細粒度和中粒度并行計算，而消息傳遞型

多計算機系統用于中粒度和粗粒度并行計算。

19

P335

不行轆、可#展轆和可編程轆

合硬件資源的可擴展性(Scalability)

■是指通過增加處理器數目、投入更多的存儲器部件(高速緩存、

主存、磁盤等)，從而使系統具有更高的性能或功能。

■由于多處理機和多計算機主要是以資源重復手段實現并行處理的,

因此它們是可擴展系統。而且，松散耦合的多計算機系統的可擴

展性要好于緊密耦合的多處理機系統。

⑥并行計算機系統可編程性(Programmability)

■涉及到操作系統、編譯器、語言支持等多個方面的問題。到目前

為止，可以說對并行計算機系統編程仍然是非常困難和費力的事

情，這主要是因為人們原來所熟悉的順序編程不適合并行程序的

設計特征。

■從體系結構的角度來看，多處理機有統一編址的全局共享存儲器,

其可編程性要好于多計算機系統。

20

洋幸￡要的客

彳算機系統結構概述

合并行計算機系統的設計問題

?并行計算機系統的互連網絡

-并行計算機系統的性能問題

-并行計算機系統的軟件問題

⑥SIMD計算機簡介

爹MIMD多處理機簡介

爹MIMD多計算機簡介

21

量之網絡輟述

⑥并行計算機的通信體系結構是系統的核心

■兩個層次：底層的互連網絡；上層的語言、軟件工具

包、編譯器、操作系統等提供的通信支持。

⑥互連網絡是并行計算機系統內部的互連網絡

■定義：由開關元件按一定拓撲結構和控制方式構成的

網絡以實現計算機系統內部多個處理機或多個功能部

件間的相互連接。

■與計算機網絡在工作原理、概念以及術語上有許多相

同或相似之處；并且某些并行計算機系統中的互連網

絡就是高速以太網和ATM網絡。

⑥互連網絡一般由以下五個部分組成

■CPU、內存模塊、接口、鏈路和交換結點

22

接口、林路和變換修克

e------------

今接口：是從CPU和內存取得信息并向另外的CPU和內存

發(fā)送信息的設備。典型設備如網絡接口卡。

④鏈路：是傳送數據位的物理信道。鏈路可以是電纜、雙絞

線或者光纖；可以是串行的也可以是并行的，每種鏈路都

有其最大帶寬；鏈路可以是單工的（單方向傳送）、半雙

工的（某個時刻只能傳送一個方向的數據）和全雙工的

（同時兩個方向傳送）；鏈路使用的時鐘機制可以是同步

或是異步的。

合交換結點：是互連網絡的信息交換和控制站點，它是具有

多個輸入端口和多個輸出端口的設備。能夠進行數據緩沖

存儲和路徑選擇。

23

P336

世計和臺新量$1網絡的幾小/要冏您

⑥互連網絡的拓撲結構

■互連網絡的拓撲結構描述了鏈路和交換結點是如何組

織安排的。拓撲結構可以用圖來表示，鏈路用邊表示,

交換結點用結點表示。

⑥互連網絡的尋徑方式

■交換結點所做的工作就是接收到達輸入端口的分組然

后把分組發(fā)送到正確的輸出端口，具有多種不同的工

作方式。

⑥互連網絡的尋徑算法

■尋徑算法：決定一個分組從源結點到達目的結點的過

程中經過的結點序列的算法。

24

呈接網絡的合奏

合靜態(tài)網絡

■靜態(tài)網絡(StaticNetworks)是指結點間有著固

定連接通路且在程序執(zhí)行期間，這種連接保持

不變的網絡。

④動態(tài)網絡

■動態(tài)網絡(DynamicNetworks)由開關單元構成,

可按應用程序的要求動態(tài)地改變連接狀態(tài)。如

總線、交叉開關，多級交換網絡等。

25

星接網絡的參照

④結點度:與結點相連接的邊數,表示節(jié)點所需要的端口

數，根據鏈路到結點的方向，結點度可以進一步表示為:

結點度=入度+出度，其中入度是進入結點的鏈路數,

出度是從結點出來的鏈路數。

⑥鏤絡的長度：鏈路中包含的邊數

今距離:與兩個結點之間相連的最少邊數。

網絡直徑:網絡中任意兩個結點間距離的最大值。

?網絡規(guī)模:網絡中結點數,表示該網絡功能連結部件的

多少。

?等分寬度:某一網絡被切成相等的兩半時,沿切口的最

小邊數稱為該網絡的等分寬度。

⑥對稱性:從任何結點看，拓撲結構都一樣，這種網絡實

現和編程都很容易。

26

P337

希態(tài)量逵網絡

⑥線性陣列

■對N個結點的線性陣列，有N-1條鏈路，直徑為

N-1（任意兩點之間距離的最大值）度為2不對

稱，等分寬度為1。N很大時，通信效率很低。

O----O----O----O----O----O----O

27

希態(tài)量逵網絡

⑥環(huán)形

■對N個結點的環(huán)，考慮相

鄰結點數據傳送方向：

＞雙向環(huán)：鏈路數為N,直

徑小/2」，度為2,對稱,

等分寬度為2。

＞單向環(huán)：鏈路數為N,直

徑N-1,度為2,對稱，等

分寬度為2。

28

度

環(huán)

為

⑥帶弦環(huán)3

的

■對圖中12個結點的帶弦?guī)?/p>

雙向環(huán)弦

＞結點度為3：鏈路數為

18,直徑4（比如紅色

結點），度為3,不對

度

稱，等分寬度為2。環(huán)

為

＞結點度為4：鏈路數為4

24,直徑3（比如紅色的

結點），度為4,對稱,帶

等分寬度為8。弦

29

吉林大學遠程教育學院

計算機原理及系統結構

第五十四講

主講教師：趙宏偉學時：64

希態(tài)量逵網絡

⑥全鏈接

■全鏈接是帶弦環(huán)的一

種特殊情形。鏈接中

的每個結點和其他結

點之間都有單一的直

接鏈路。

■如下圖中8個結點的全

鏈接：有28條鏈路，

直徑為1,度為7,對

稱，等分寬度為16。

31

帶態(tài)量逵網絡

樹形

■一棵K層完全二叉樹應有N=2入1個結點，最大結點

度為3,直徑為2(K-1)(即右邊任意一個葉子結點

到左邊任意一個葉子結點)。不對稱，等分寬度為1。

32

樹形的#展

⑥這兩種結構都可以緩解根結點的瓶頸問題

33

希態(tài)量逵網絡

⑥星形

■星形實際上是一種二層樹（如右圖）。有N個結點的

星形網絡，有N-1條鏈路，直徑為2,最大結點度為

N-1,非對稱，等分寬度為1。

希態(tài)量逵網絡

⑥網格形

iJoIJ[

J、LJ}(J、LJLJ

■有N個結點的rxr

、/\1、f

y\J<JV

網，有2N-2r條)_cr

\r、/

鏈路，直徑為J;jC)<J、J<■

L

2g),結點度r\____rS___c、r>(、r

uQ)I

為4,非對稱，CXJ

JJ、)\L7JXiLJJ(

等分寬度為。

rS__rS__c3(\<\/

)\J\J、J<

S__rS__c>___rSr、r、/

J\J、J\)<

■其中1r

S_r

r￡「丫丫丫丫丫1

35

⑥二維環(huán)網形

■有N個結點的rxr網,

有2N條鏈路，直徑

為2上/2」，結點度

為4,對稱。

■其中r=y/~N~

36

⑥超立方體

■一個n-立方體由N二2。個結點構成，它們分布在n維上,

每維有兩個結點。直徑為n,結點度為n,對稱。

Jf

0-------J_____0——當

3-立方體

4-立方體

37

⑥帶環(huán)立方體

■一個帶環(huán)n-立方體由

N=2n個結點環(huán)構成,

每個結點環(huán)是一個有

n個結點的環(huán)，所以

結點總數為n2n個，

結點度為3,對稱。

帶環(huán)3-立方體

38

靜態(tài)或透網絡特喉一覽表

網絡名稱網絡規(guī)模結點度網絡直徑對分寬度對稱性鏈路數

線性陣列Mb結點2N-11非N-1

環(huán)形雙個結點2囪2」（雙向）2是N

全鏈接Nt結點N?11(N/2)2是N(N-1)I2

2(rio^-i)

二叉樹泌潘疝1g1非N-1

星形正結點N-12[”/2」非N-1

網格形J斤xj萬個結點42(而-1)國非2(N~y[N)

2?/2」

二維環(huán)網而xJW個結點4I4N是IN

超立方體N=2"個結點NnN/2是nNH

2k-1+[k/2\

立方環(huán)N二h2上個結點3N7（比）遽.37v72

39

P338

劭態(tài)量逵網絡

⑥網絡特點

■動態(tài)網絡中的連接不固定，在程序執(zhí)行過程中

可根據需要改變。

■網絡的開關元件有源，鏈路可通過設置這些開

關的狀態(tài)來重構。

■只有在網絡邊界上的開關元件才能與處理機相

連。

■動態(tài)網絡主要有總線、交叉開關、多級交換網

絡

40

劭態(tài)量逵網絡

⑥總線(Bus)

■總線實際上是連接處理器、存儲器和I/O等外圍設備的

一組導線和插座。

■它在某一時刻只能用于一對源和目的之間傳輸數據。

■當有多對源和目的請求使用總線時，要進行總線仲裁。

當CPU數目較多時對總線爭用嚴重(<=32個)O

⑥線性陣列與總線的區(qū)別

■線性陣列：允許不同的源結點和目的結點對并發(fā)使用

系統的不同部分。

-總線：通過切換與其相連的許多結點來實現時分特性,

同一時刻只有一對結點在傳送數據。

41

系統總線（在底板上）

IF:專用邏輯接口C:專用控制器P:處理器M:局部存儲器CA:高速緩存IOP:I/O處理第

劭態(tài)量逵網絡

⑥交叉開關(CrossbarSwitcher)

■交叉開關是一種高帶寬網絡，它可以在輸入端

和輸出端之間建立動態(tài)連接

■在每個輸入端和輸出端的交叉點上都有交叉點

開關。該開關可以根據需要置為“開”或“關”

狀態(tài)，從而使不同的輸入端和輸出端導通。

■交叉開關的硬件復雜性為汴數量級，造價昂貴。

但是其帶寬和尋徑性能在這三種動態(tài)網絡中最

好。如果網絡規(guī)模小，它是一種理想的選擇

(<=64個)o

43

委表開關

內存

CPU

圖13.218X8的交叉開關44

劭態(tài)量逵網絡

⑥多級交換網絡

■開關單元：a個輸入a個輸出的開關單元記作axa的開關

單元，其中，a是2的整數倍。常見的有2x2、4x4、

8x8等。

■根據開關單元功能的多少，2義2又可以分為兩功能和

四功能開關。

45

劭態(tài)量盤網絡

⑥多級交換網絡

■級間互連模式

?均勻洗牌、蝶式、多路洗牌、縱橫開關及立方體連結等

■控制方式

?級控制：每級只有一個控制信號

?單元控制：每個開關一個控制信號

?部分級控制：幾個開關合用一個控制信號

-多級交換網絡是總線和交叉開關的折衷。它的主要優(yōu)

點在于采用模塊結構，可擴展性好（＞64）

46

。多公會換網絡

第0級第1級第2級

0

1

2

3

4

5

6

7

47

吉林大學遠程教育學院

計算機原理及系統結構

第五十五講

主講教師：趙宏偉學時：64

量透網絡的尋桎方式

4多種不同的設計方案

■電路交換：預約資源（端口和緩沖區(qū)），預先建立固

定交換結點鏈路，分組能夠全速發(fā)送。

■存儲轉發(fā)分組交換：不預約資源，各個交換結點緩存

整個分組。需要有緩存策略：

?輸入緩存、輸出緩存、公共緩沖區(qū)

■虛擬直通尋徑：當分組第一個單元不能移動時，分組

的其余單元可以繼續(xù)向第一個單元所在的結點傳送。

-蟲蝕尋徑：當第一個單元不能移動時，通知源結點，

源結點就停止傳送，因此分組就像一條蟲子一樣停留

在兩個或者更多個交換結點中。

49

P339

量透網絡的尋桎方式

四

個

分組的后部＜交

換

結

點

的

方

型

互

連

網

絡

分組的中部S

分組的前部

50

王逡網絡的壽役方式

(a)(b)

存儲轉發(fā)分組交換

51

量透網絡的尋桎算法

?⑥加京徑和分布式尋徑

■在源尋徑中，源結點預先決定穿過互連網絡的完整的

路徑，使用路徑中每個結點的端口號的列表來表示。

■在分布式尋徑算法中，每個交換結點自己決定把到達

的分組發(fā)送到哪個輸出端口。一般來說在各個交換結

點都設立一個路徑表，而分組的頭部含有一個尋徑字

段說明分組的目的地址和選擇路徑的依據。

⑥靜態(tài)尋徑算法和自適應尋徑算法

■算法對所有到相同目的結點的分組都做出相同的決策,

那么這樣的尋徑算法就稱為靜態(tài)的。

■算法在做路徑選擇時考慮了當前情況，該算法就是自

適應的。

52

P341

洋幸￡要的客

彳算機系統結構概述

合并行計算機系統的設計問題

?并行計算機系統的互連網絡

-并行計算機系統的性能問題

-并行計算機系統的軟件問題

⑥SIMD計算機簡介

爹MIMD多處理機簡介

爹MIMD多計算機簡介

53

開行計算機系您的雌健冏題

卜硬件性能指標

■重要的性能指標是CPU和輸入/輸出的速度以及互連網

絡的性能。

■互連網絡的性能有兩個重要的指標：延時(Latency)

和帶寬(Bandwidth)。

?延遲時間是指從CPU發(fā)送分組至接收到響應的時間間隔。

?對分帶寬、聚集帶寬和平均帶寬(按照CPU能力計算)。

⑥軟件性能指標

■最關鍵的性能指標是加速比(speedup)：一個程序在

有n個處理器的計算機上運行和在只有一個處理器的計

算機上運行相比快多少倍。

54

P342

開行計算機余統的喉健問題

60

N-bodyproblem

50

40Linearspeedup

30

9p-

s

e

dAwari

s

20

-0tSkylin?matrixinversion

102030M60

NumberofCPUs

圖13.10實際程序獲得的加速比總是低于線性加速比

55

P342

開行計算機系您的雌健冏題

④理想的加速比不可能達到的部分原因是幾乎所有的程序都

有串行部分。

■假定一個程序在單處理器計算機上運行需要T秒，其中一部分是串

行代碼，所占比例記為f,那么剩余的(1-f)就是可以并行的。

■后一部分代碼運行在n個CPU上而且沒有任何其它開銷，那么在最

理想的情況下，執(zhí)行時間可以從(1-f)T減少到(1-f)T/n。

■串行部分加并行部分的整個執(zhí)行時間就是仃+(1-f)T/no

■加速比就是原來程序的執(zhí)行時間除以新的程序的執(zhí)行時間：

Tn

Speedup-----------------------------------------------二------------------------------

fT+(l-f)TInl+

56

洋幸：要向客

⑥并行計算機系統結構概述

⑥并行計算機系統的設計問題

■并行計算機系統的互連網絡

■并行計算機系統的性能問題

■并行計算機系統的軟件問題

⑥S1MD計算機簡介

?M1MD多處理機簡介

合MIMD多計算機簡介

57

開行計算機皴件的B種強針方汰

e------------

⑥第一種方法是為普通的串行語言增加特殊的函數庫。這種方法的問

題在于只是在很少的庫函數中實現了并行性，而大量的程序代碼仍

然是串行的。

⑥第二種方法是為編程語言增加包括通信和控制原語的庫函數。程序

員仍然使用傳統的編程語言編程，但是程序員需要使用這些原語來

創(chuàng)建和管理并行性。

⑥第三種方法是為現有的編程語言增加一些特殊的結構，比如可以很

容易地創(chuàng)建新的并行進程的能力，并行執(zhí)行循環(huán)的能力和同時對一

個向量的所有元素執(zhí)行算術運算的能力。

⑥第四種方法是發(fā)明一種全新的用于并行處理的語言。使用新語言的

一人顯而易見的優(yōu)勢是這樣的語言肯定很適合于并行處理，但是缺

點也同樣明顯，程序員必須學習一種新語言。

58

P344

洋幸：要向客

⑥并行計算機系統結構概述

⑥并行計算機系統的設計問題

■并行計算機系統的互連網絡

■并行計算機系統的性能問題

■并行計算機系統的軟件問題

⑥SIMD計算機簡介

?M1MD多處理機簡介

合MIMD多計算機簡介

59

S1MD計算機

⑥單指令流多數據流計算機用于解決使用向量和陣

列這樣比較規(guī)整的數據結構的復雜科學計算和工

程計算問題。

⑥只有一個控制單元，每次只能執(zhí)行一條指令，但

是這一條指令可以同時對多個數據進行操作。

⑥SIMD計算機可以分為陣列處理機和向量處理機

兩大類。

60

陣列處理機

------------

今設計陣列處理機基本思想

■用一個單一的控制單元提供信號驅動多個處理單元同時運行，如

下圖所示。每個處理器單元都由CPU或者是功能增強的ALU和本地

內存組成。由于所有的處理單元都是由一個控制單元驅動的，因

此它們的執(zhí)行是同步的。

⑥各種陣列處理機的不同之處

-處理單元的結構：處理單元的結構可能很簡單，也可能很復雜。

■處理單元如何連接：從原理上來說前面列出的拓撲結構都是可行

的，網格是比較常用的結構。

■處理單元自治能力：每個處理單元都可以選擇執(zhí)行或不執(zhí)行某條

指令。

④沒有那個公司的產品在市場上取得較大的成功，從并行計

算機系統體系結構來看，陣列處理機沒有好的發(fā)展前景。

61

P345

ILLIACIV型陣列處理機

控制器

M)A播指令

三三三=EJ

三三三三EJ

三三三三EdJutd

三三EJJt=8X8處理器/存儲器組

處理器——u

存儲器三

tdJt=J

圖13.14ILLIACIV型陣列處理機

62

向量處理機

卷向量處理機在商業(yè)上取得了很大成功。CrayResearch公

司設計的系列計算機，從CrayT到后來的C90和T90,在

科學計算領域占據了數十年的統治地位。

④從數學的概念上講，標量是指單個量，而向量是指一組標

量。例如，有一個數組A=(a1,a2?己3，…，aQ,其

中括號內的每一個元素aj就是一個標量。而A稱為向量，

它由一組標量組成。

合向量處理方式：引入向量數據表示，需要向量指令處理。

標量處理:向量處理:

for（i=0；i<N；i++）A=B+C

A[i]=B[i]+C[i]

63

向量處理機

e------------

爹向量處理方法

-例子：D=AX(B+C)其中A、B、C、

D都是長度為N的向量。

■橫向處理方法：逐個求向量D中N個

分量。輸入向量

-縱向處理方法：先求B+C各個分量

得向量K,然后計算口=人＞＜|＜。

■縱橫處理方法：分組處理，組內采

用縱向處理，組間采用橫向處理。

今最簡單的向量處理結構

合向量處理和流水線結合

④對語言結構和編譯程序提出

新的要求圖13.15用于向量處理的SIMD體系結構

64

P346

洋幸￡要的客

彳算機系統結構概述

合并行計算機系統的設計問題

?并行計算機系統的互連網絡

-并行計算機系統的性能問題

-并行計算機系統的軟件問題

⑥SIMD計算機簡介

爹MIMD多處理機簡介

爹MIMD多計算機簡介

65

易事飽存的多處理機

并且所有的CPU共享同一個映射到共享物理內存上的

虛擬地址空間。多處理機系統有時也被稱為共享內存系統(Shared

MemorySystem)。

⑥從軟件的角度來說，多處理機系統很容易擴展。任何一個處理器都可

以通過執(zhí)行LOAD/STORE指令訪問內存。兩個處理器之間可以通過

很簡單的方式進行通信，只要一個處理器把數據寫入內存而另一個處

理器從內存中把數據讀出就可以了。

⑥多處理機系統也有磁盤、網絡適配器和其它的輸入/輸出設備。如果

在一個系統中，每個CPU都能平等地訪問所有的內存模塊和輸入/輸

出設備，而且在操作系統看來這些CPU是可以互換的，那么這種系統

就是對禰多處理機系統SMP(SymmetricMultiProcessor)。

⑥多處理機系統中只有一個操作系統，操作系統負責管理一系列的表。

這種單一系統映像是多處理機系統區(qū)別于多計算機系統的主要特點。

66

P348

共事由存的多處理機

CPU

(a)16個CPU共享一個公共內存的多處理機系統(b)一個圖像分成16塊，每塊都由不同的CPU分析

圖13.17多處理機設計方案

67

UMA,處理機奈加

e----------

⑥UMA系統特點

?物理存儲器被所有處理器均勻共享

■所有處理器訪問任何存儲字需相同的時間

■每臺處理器可帶私有高速緩存或私有內存

⑥基于總線的UMA多處理機系統

總線總線總線

(a)不使用Cache(b)使用Cache(c)使用Cache和私有內存

圖13.18基于總線結構的多處理機系統

68

P349

NUMA,處理機奈統

國而|謔系統特點

■所有的CPU都看到一個單一的地址空間

■使用LOAD和STORE指令訪問遠程內存

■訪問遠程內存比訪問本地內存慢

■NUMA系統中的處理器可使用高速緩存

爹NONUMA與CC-NUMA

■不使用Cache的NUMA系統被稱為NC-NUMA多

處理機系統，也就是說這種系統中不隱藏遠程

內存的訪問時間。如果使用了Cache,那么系

統就被稱為CC-NUMA多處理機系統。

69

P356

NUMA多處理機奈統

e------------

爹NONUMA多處理機系統

CPU內存CPU內存CPU內存CPU內存

MMU

系統總線

圖13.26基于兩級總線的NUMA計算機

爹CONUMA多處理機系統

結點0結點1結點255

CPU內存CPU內存CPU內存

基于目錄的多處理機系統

70

P356

Cache一致轆問您與Cache一致他快衩

⑥Cache一致性問題產生原因

■現代并行計算機中，處理器往往帶有Cache。一個內存

數據在整個系統內可能有多份拷貝。這就引發(fā)了Cache

一致性問題。

⑥Cache一致性協議

■由Cache、CPU和內存共同實現的防止多個Cache中出

現相同數據的不同版本的規(guī)則集合就組成了Cache一致

性協議。

⑥Cache一致性協議通常可以分為兩類

■監(jiān)聽總線的協議

■基于目錄的協議

71

Cache一致轆問您與Cache一致他快衩

合監(jiān)聽總線的協議

■在監(jiān)聽總線協議中，所有的處理器都監(jiān)聽總線，當某個處理器修

改了私有Cache中的數據后，它在總線上廣播無效信息或更新后

的數據，以使其它副本無效或得到更新。

■監(jiān)聽總線協議適用于互連網絡可以實現廣播功能的并行系統。