計算機組成與系統(tǒng)結(jié)構(gòu)并行計算機體系結(jié)構(gòu)第13章

第13早

并行計算機體系結(jié)構(gòu)

洋幸￡要向客

市不算機系統(tǒng)結(jié)構(gòu)概述

⑥并行計算機系統(tǒng)的設(shè)計問題

.并行計算機系統(tǒng)的互連網(wǎng)絡(luò)

-并行計算機系統(tǒng)的性能問題

-并行計算機系統(tǒng)的軟件問題

⑥S1MD計算機簡介

?M1MD多處理機簡介

卷M1MD多計算機簡介

2

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

硬件技術(shù)和系統(tǒng)結(jié)構(gòu)軟件和應(yīng)用

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

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

序計數(shù)器PC和累加器順序完成定

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

點運算

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

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

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

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

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

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

第三代多道程序設(shè)計，分時操作系統(tǒng)，

路。微程序設(shè)計，流水線，高速

(1965?1974)多用戶應(yīng)用。

緩存，先行處理機。

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

第四代

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

(1975?1990)

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

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

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

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

（1991?現(xiàn)在）布式操作系統(tǒng)，萬維網(wǎng)，網(wǎng)格。

體系結(jié)構(gòu)，因特網(wǎng)。

3

計算機余就錯構(gòu)的或展方向

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

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

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

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

■PC或工作站組成的機群系統(tǒng)

4

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

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

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

據(jù)驅(qū)動式系統(tǒng)結(jié)構(gòu)的計算機，只要指令所需的操作數(shù)準備好就可以立即

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

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

令間的數(shù)據(jù)依賴關(guān)系決定。

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

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

準備好、那么它就去啟動能夠得到它的相應(yīng)輸入操作數(shù)的其他操作，這

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

然后再反方向的執(zhí)行運算。歸約機就屬于需求驅(qū)動式系統(tǒng)結(jié)構(gòu)的使用函

數(shù)式程序設(shè)計語言的計算機。

■模式匹配驅(qū)動方式：非數(shù)值型應(yīng)用，主要對象為符號.在模式匹配驅(qū)動方

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

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

Lisp機、Prolog機和神經(jīng)網(wǎng)絡(luò)等就屬于這種模式匹配驅(qū)動式系統(tǒng)結(jié)構(gòu)的

計壹機。

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

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

5

計算機余就錯構(gòu)的臺類方法

⑥過去曾普遍將計算機系統(tǒng)分為巨、大、中、小、

微型機五類。

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

格的一種大致劃分。

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

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

外，這種劃分方法不能反映機器的系統(tǒng)結(jié)構(gòu)特征。

■設(shè)計方法:

?最局性能特殊用途

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

?最低價格家用計算機等

6

7

吉林大學(xué)遠程教育學(xué)院

計算機原理及系統(tǒng)結(jié)構(gòu)

第五十三講

主講教師：趙宏偉學(xué)時：64

第13早

并行計算機體系結(jié)構(gòu)

計算機余就錯構(gòu)的臺類方法

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

性對計算機系統(tǒng)結(jié)構(gòu)進行分類。

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

■數(shù)據(jù)流是由指令流調(diào)用的數(shù)據(jù)序列,包括輸入數(shù)據(jù)和中間結(jié)果；

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

指令或數(shù)據(jù)的最大數(shù)目。

指令流數(shù)據(jù)流名稱舉例

1個1個SISD傳統(tǒng)的馮?諾依曼計算機

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

多個1個MISD目前還沒有

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

10

S1SD體系輅相

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

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

至于處理器是超標(biāo)量處理器，內(nèi)有幾條指令流水線實現(xiàn)

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

令流從存儲器取指令，以單一的數(shù)據(jù)流從存儲器取操作

數(shù)和將結(jié)果寫回存儲器。

IS

SISD

11

S1MD體奈輅構(gòu)

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

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

用到各個處理單元，控制各個處理單元對來自不同數(shù)據(jù)

流的數(shù)據(jù)組進行操作。這種體系結(jié)構(gòu)的典型代表是陣列

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

SIMD12

M1SD體奈輅構(gòu)

④多個處理單元，各配有相應(yīng)的控制單元。各個處理單元

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

這種計算機體系結(jié)構(gòu)是一種比較奇怪的組合，這已經(jīng)被

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

類型的計算機。

DS

MISD13

M1MD體奈輅構(gòu)

④同時有多個處理單元，并且每個處理單元都配有相應(yīng)的

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

的數(shù)據(jù)流進行操作。大多數(shù)現(xiàn)代的并行計算機都屬于這

一類，多處理機系統(tǒng)和多計算機系統(tǒng)都是MIMD型的計

算機。

MIMD

14

計算機余就錯構(gòu)的臺類方法

爹Flynn分類法的局限

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

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

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

而造成MISD不存在；

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

向量流水線為SIMD。

④其他的分類方法

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

種計算機系統(tǒng)的馮氏分類法。

■WolfganHandler在馮氏分類法的基礎(chǔ)上，于1977年根據(jù)并行度和

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

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

15

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

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

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

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

高性能計算。

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

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

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

令大量商品化的處理器的出現(xiàn)為設(shè)計并行計算機系

統(tǒng)提供了可能。

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

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

16

P333

開行計算機系您的合美

共享內(nèi)存消息傳遞

17

P333圖13.4并行計算機的分類

開行奸算機系挑的臺美

⑥MIMD體系結(jié)構(gòu)

■多處理機系統(tǒng)——基于共享存儲器

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

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

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

分布式存儲器并在硬件和軟件的支持下實現(xiàn)。

■多計算機系統(tǒng)——基于消息傳遞

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

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

有存儲器。

?當(dāng)處理器A需要向處理器B傳送數(shù)據(jù)時，A把數(shù)據(jù)以消息的形式

發(fā)送給B。

18

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

e----------

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

■并行性是指在同一時刻或同一時間間隔內(nèi)完成兩種或

兩種以上的工作。

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

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

并行性。

⑥并行的粒度問題

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

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

多計算機系統(tǒng)用于中粒度和粗粒度并行計算。

19

P335

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

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

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

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

■由于多處理機和多計算機主要是以資源重復(fù)手段實現(xiàn)并行處理的,

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

展性要好于緊密耦合的多處理機系統(tǒng)。

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

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

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

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

設(shè)計特征。

■從體系結(jié)構(gòu)的角度來看，多處理機有統(tǒng)一編址的全局共享存儲器,

其可編程性要好于多計算機系統(tǒng)。

20

洋幸￡要的客

彳算機系統(tǒng)結(jié)構(gòu)概述

合并行計算機系統(tǒng)的設(shè)計問題

?并行計算機系統(tǒng)的互連網(wǎng)絡(luò)

-并行計算機系統(tǒng)的性能問題

-并行計算機系統(tǒng)的軟件問題

⑥SIMD計算機簡介

爹MIMD多處理機簡介

爹MIMD多計算機簡介

21

量之網(wǎng)絡(luò)輟述

⑥并行計算機的通信體系結(jié)構(gòu)是系統(tǒng)的核心

■兩個層次：底層的互連網(wǎng)絡(luò)；上層的語言、軟件工具

包、編譯器、操作系統(tǒng)等提供的通信支持。

⑥互連網(wǎng)絡(luò)是并行計算機系統(tǒng)內(nèi)部的互連網(wǎng)絡(luò)

■定義：由開關(guān)元件按一定拓撲結(jié)構(gòu)和控制方式構(gòu)成的

網(wǎng)絡(luò)以實現(xiàn)計算機系統(tǒng)內(nèi)部多個處理機或多個功能部

件間的相互連接。

■與計算機網(wǎng)絡(luò)在工作原理、概念以及術(shù)語上有許多相

同或相似之處；并且某些并行計算機系統(tǒng)中的互連網(wǎng)

絡(luò)就是高速以太網(wǎng)和ATM網(wǎng)絡(luò)。

⑥互連網(wǎng)絡(luò)一般由以下五個部分組成

■CPU、內(nèi)存模塊、接口、鏈路和交換結(jié)點

22

接口、林路和變換修克

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

今接口：是從CPU和內(nèi)存取得信息并向另外的CPU和內(nèi)存

發(fā)送信息的設(shè)備。典型設(shè)備如網(wǎng)絡(luò)接口卡。

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

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

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

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

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

或是異步的。

合交換結(jié)點：是互連網(wǎng)絡(luò)的信息交換和控制站點，它是具有

多個輸入端口和多個輸出端口的設(shè)備。能夠進行數(shù)據(jù)緩沖

存儲和路徑選擇。

23

P336

世計和臺新量$1網(wǎng)絡(luò)的幾小/要冏您

⑥互連網(wǎng)絡(luò)的拓撲結(jié)構(gòu)

■互連網(wǎng)絡(luò)的拓撲結(jié)構(gòu)描述了鏈路和交換結(jié)點是如何組

織安排的。拓撲結(jié)構(gòu)可以用圖來表示，鏈路用邊表示,

交換結(jié)點用結(jié)點表示。

⑥互連網(wǎng)絡(luò)的尋徑方式

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

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

作方式。

⑥互連網(wǎng)絡(luò)的尋徑算法

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

程中經(jīng)過的結(jié)點序列的算法。

24

呈接網(wǎng)絡(luò)的合奏

合靜態(tài)網(wǎng)絡(luò)

■靜態(tài)網(wǎng)絡(luò)(StaticNetworks)是指結(jié)點間有著固

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

不變的網(wǎng)絡(luò)。

④動態(tài)網(wǎng)絡(luò)

■動態(tài)網(wǎng)絡(luò)(DynamicNetworks)由開關(guān)單元構(gòu)成,

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

總線、交叉開關(guān)，多級交換網(wǎng)絡(luò)等。

25

星接網(wǎng)絡(luò)的參照

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

數(shù)，根據(jù)鏈路到結(jié)點的方向，結(jié)點度可以進一步表示為:

結(jié)點度=入度+出度，其中入度是進入結(jié)點的鏈路數(shù),

出度是從結(jié)點出來的鏈路數(shù)。

⑥鏤絡(luò)的長度：鏈路中包含的邊數(shù)

今距離:與兩個結(jié)點之間相連的最少邊數(shù)。

網(wǎng)絡(luò)直徑:網(wǎng)絡(luò)中任意兩個結(jié)點間距離的最大值。

?網(wǎng)絡(luò)規(guī)模:網(wǎng)絡(luò)中結(jié)點數(shù),表示該網(wǎng)絡(luò)功能連結(jié)部件的

多少。

?等分寬度:某一網(wǎng)絡(luò)被切成相等的兩半時,沿切口的最

小邊數(shù)稱為該網(wǎng)絡(luò)的等分寬度。

⑥對稱性:從任何結(jié)點看，拓撲結(jié)構(gòu)都一樣，這種網(wǎng)絡(luò)實

現(xiàn)和編程都很容易。

26

P337

希態(tài)量逵網(wǎng)絡(luò)

⑥線性陣列

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

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

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

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

27

希態(tài)量逵網(wǎng)絡(luò)

⑥環(huán)形

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

鄰結(jié)點數(shù)據(jù)傳送方向：

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

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

等分寬度為2。

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

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

分寬度為2。

28

度

環(huán)

為

⑥帶弦環(huán)3

的

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

雙向環(huán)弦

＞結(jié)點度為3：鏈路數(shù)為

18,直徑4（比如紅色

結(jié)點），度為3,不對

度

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

為

＞結(jié)點度為4：鏈路數(shù)為4

24,直徑3（比如紅色的

結(jié)點），度為4,對稱,帶

等分寬度為8。弦

29

吉林大學(xué)遠程教育學(xué)院

計算機原理及系統(tǒng)結(jié)構(gòu)

第五十四講

主講教師：趙宏偉學(xué)時：64

希態(tài)量逵網(wǎng)絡(luò)

⑥全鏈接

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

種特殊情形。鏈接中

的每個結(jié)點和其他結(jié)

點之間都有單一的直

接鏈路。

■如下圖中8個結(jié)點的全

鏈接：有28條鏈路，

直徑為1,度為7,對

稱，等分寬度為16。

31

帶態(tài)量逵網(wǎng)絡(luò)

樹形

■一棵K層完全二叉樹應(yīng)有N=2入1個結(jié)點，最大結(jié)點

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

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

32

樹形的#展

⑥這兩種結(jié)構(gòu)都可以緩解根結(jié)點的瓶頸問題

33

希態(tài)量逵網(wǎng)絡(luò)

⑥星形

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

星形網(wǎng)絡(luò)，有N-1條鏈路，直徑為2,最大結(jié)點度為

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

希態(tài)量逵網(wǎng)絡(luò)

⑥網(wǎng)格形

iJoIJ[

J、LJ}(J、LJLJ

■有N個結(jié)點的rxr

、/\1、f

y\J<JV

網(wǎng)，有2N-2r條)_cr

\r、/

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

L

2g),結(jié)點度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)網(wǎng)形

■有N個結(jié)點的rxr網(wǎng),

有2N條鏈路，直徑

為2上/2」，結(jié)點度

為4,對稱。

■其中r=y/~N~

36

⑥超立方體

■一個n-立方體由N二2。個結(jié)點構(gòu)成，它們分布在n維上,

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

Jf

0-------J_____0——當(dāng)

3-立方體

4-立方體

37

⑥帶環(huán)立方體

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

N=2n個結(jié)點環(huán)構(gòu)成,

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

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

結(jié)點總數(shù)為n2n個，

結(jié)點度為3,對稱。

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

38

靜態(tài)或透網(wǎng)絡(luò)特喉一覽表

網(wǎng)絡(luò)名稱網(wǎng)絡(luò)規(guī)模結(jié)點度網(wǎng)絡(luò)直徑對分寬度對稱性鏈路數(shù)

線性陣列Mb結(jié)點2N-11非N-1

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

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

2(rio^-i)

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

星形正結(jié)點N-12[”/2」非N-1

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

2?/2」

二維環(huán)網(wǎng)而xJW個結(jié)點4I4N是IN

超立方體N=2"個結(jié)點NnN/2是nNH

2k-1+[k/2\

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

39

P338

劭態(tài)量逵網(wǎng)絡(luò)

⑥網(wǎng)絡(luò)特點

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

可根據(jù)需要改變。

■網(wǎng)絡(luò)的開關(guān)元件有源，鏈路可通過設(shè)置這些開

關(guān)的狀態(tài)來重構(gòu)。

■只有在網(wǎng)絡(luò)邊界上的開關(guān)元件才能與處理機相

連。

■動態(tài)網(wǎng)絡(luò)主要有總線、交叉開關(guān)、多級交換網(wǎng)

絡(luò)

40

劭態(tài)量逵網(wǎng)絡(luò)

⑥總線(Bus)

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

一組導(dǎo)線和插座。

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

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

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

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

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

系統(tǒng)的不同部分。

-總線：通過切換與其相連的許多結(jié)點來實現(xiàn)時分特性,

同一時刻只有一對結(jié)點在傳送數(shù)據(jù)。

41

系統(tǒng)總線（在底板上）

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

劭態(tài)量逵網(wǎng)絡(luò)

⑥交叉開關(guān)(CrossbarSwitcher)

■交叉開關(guān)是一種高帶寬網(wǎng)絡(luò)，它可以在輸入端

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

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

開關(guān)。該開關(guān)可以根據(jù)需要置為“開”或“關(guān)”

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

■交叉開關(guān)的硬件復(fù)雜性為汴數(shù)量級，造價昂貴。

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

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

(<=64個)o

43

委表開關(guān)

內(nèi)存

CPU

圖13.218X8的交叉開關(guān)44

劭態(tài)量逵網(wǎng)絡(luò)

⑥多級交換網(wǎng)絡(luò)

■開關(guān)單元：a個輸入a個輸出的開關(guān)單元記作axa的開關(guān)

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

8x8等。

■根據(jù)開關(guān)單元功能的多少，2義2又可以分為兩功能和

四功能開關(guān)。

45

劭態(tài)量盤網(wǎng)絡(luò)

⑥多級交換網(wǎng)絡(luò)

■級間互連模式

?均勻洗牌、蝶式、多路洗牌、縱橫開關(guān)及立方體連結(jié)等

■控制方式

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

?單元控制：每個開關(guān)一個控制信號

?部分級控制：幾個開關(guān)合用一個控制信號

-多級交換網(wǎng)絡(luò)是總線和交叉開關(guān)的折衷。它的主要優(yōu)

點在于采用模塊結(jié)構(gòu)，可擴展性好（＞64）

46

。多公會換網(wǎng)絡(luò)

第0級第1級第2級

0

1

2

3

4

5

6

7

47

吉林大學(xué)遠程教育學(xué)院

計算機原理及系統(tǒng)結(jié)構(gòu)

第五十五講

主講教師：趙宏偉學(xué)時：64

量透網(wǎng)絡(luò)的尋桎方式

4多種不同的設(shè)計方案

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

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

■存儲轉(zhuǎn)發(fā)分組交換：不預(yù)約資源，各個交換結(jié)點緩存

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

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

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

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

-蟲蝕尋徑：當(dāng)?shù)谝粋€單元不能移動時，通知源結(jié)點，

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

在兩個或者更多個交換結(jié)點中。

49

P339

量透網(wǎng)絡(luò)的尋桎方式

四

個

分組的后部＜交

換

結(jié)

點

的

方

型

互

連

網(wǎng)

絡(luò)

分組的中部S

分組的前部

50

王逡網(wǎng)絡(luò)的壽役方式

(a)(b)

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

51

量透網(wǎng)絡(luò)的尋桎算法

?⑥加京徑和分布式尋徑

■在源尋徑中，源結(jié)點預(yù)先決定穿過互連網(wǎng)絡(luò)的完整的

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

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

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

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

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

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

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

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

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

適應(yīng)的。

52

P341

洋幸￡要的客

彳算機系統(tǒng)結(jié)構(gòu)概述

合并行計算機系統(tǒng)的設(shè)計問題

?并行計算機系統(tǒng)的互連網(wǎng)絡(luò)

-并行計算機系統(tǒng)的性能問題

-并行計算機系統(tǒng)的軟件問題

⑥SIMD計算機簡介

爹MIMD多處理機簡介

爹MIMD多計算機簡介

53

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

卜硬件性能指標(biāo)

■重要的性能指標(biāo)是CPU和輸入/輸出的速度以及互連網(wǎng)

絡(luò)的性能。

■互連網(wǎng)絡(luò)的性能有兩個重要的指標(biāo)：延時(Latency)

和帶寬(Bandwidth)。

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

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

⑥軟件性能指標(biāo)

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

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

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

54

P342

開行計算機余統(tǒng)的喉健問題

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

洋幸：要向客

⑥并行計算機系統(tǒng)結(jié)構(gòu)概述

⑥并行計算機系統(tǒng)的設(shè)計問題

■并行計算機系統(tǒng)的互連網(wǎng)絡(luò)

■并行計算機系統(tǒng)的性能問題

■并行計算機系統(tǒng)的軟件問題

⑥S1MD計算機簡介

?M1MD多處理機簡介

合MIMD多計算機簡介

57

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

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

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

題在于只是在很少的庫函數(shù)中實現(xiàn)了并行性，而大量的程序代碼仍

然是串行的。

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

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

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

⑥第三種方法是為現(xiàn)有的編程語言增加一些特殊的結(jié)構(gòu)，比如可以很

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

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

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

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

點也同樣明顯，程序員必須學(xué)習(xí)一種新語言。

58

P344

洋幸：要向客

⑥并行計算機系統(tǒng)結(jié)構(gòu)概述

⑥并行計算機系統(tǒng)的設(shè)計問題

■并行計算機系統(tǒng)的互連網(wǎng)絡(luò)

■并行計算機系統(tǒng)的性能問題

■并行計算機系統(tǒng)的軟件問題

⑥SIMD計算機簡介

?M1MD多處理機簡介

合MIMD多計算機簡介

59

S1MD計算機

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

列這樣比較規(guī)整的數(shù)據(jù)結(jié)構(gòu)的復(fù)雜科學(xué)計算和工

程計算問題。

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

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

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

兩大類。

60

陣列處理機

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

今設(shè)計陣列處理機基本思想

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

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

內(nèi)存組成。由于所有的處理單元都是由一個控制單元驅(qū)動的，因

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

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

-處理單元的結(jié)構(gòu)：處理單元的結(jié)構(gòu)可能很簡單，也可能很復(fù)雜。

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

的，網(wǎng)格是比較常用的結(jié)構(gòu)。

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

指令。

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

算機系統(tǒng)體系結(jié)構(gòu)來看，陣列處理機沒有好的發(fā)展前景。

61

P345

ILLIACIV型陣列處理機

控制器

M)A播指令

三三三=EJ

三三三三EJ

三三三三EdJutd

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

處理器——u

存儲器三

tdJt=J

圖13.14ILLIACIV型陣列處理機

62

向量處理機

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

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

科學(xué)計算領(lǐng)域占據(jù)了數(shù)十年的統(tǒng)治地位。

④從數(shù)學(xué)的概念上講，標(biāo)量是指單個量，而向量是指一組標(biāo)

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

中括號內(nèi)的每一個元素aj就是一個標(biāo)量。而A稱為向量，

它由一組標(biāo)量組成。

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

標(biāo)量處理:向量處理:

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,然后計算口=人＞＜|＜。

■縱橫處理方法：分組處理，組內(nèi)采

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

今最簡單的向量處理結(jié)構(gòu)

合向量處理和流水線結(jié)合

④對語言結(jié)構(gòu)和編譯程序提出

新的要求圖13.15用于向量處理的SIMD體系結(jié)構(gòu)

64

P346

洋幸￡要的客

彳算機系統(tǒng)結(jié)構(gòu)概述

合并行計算機系統(tǒng)的設(shè)計問題

?并行計算機系統(tǒng)的互連網(wǎng)絡(luò)

-并行計算機系統(tǒng)的性能問題

-并行計算機系統(tǒng)的軟件問題

⑥SIMD計算機簡介

爹MIMD多處理機簡介

爹MIMD多計算機簡介

65

易事飽存的多處理機

并且所有的CPU共享同一個映射到共享物理內(nèi)存上的

虛擬地址空間。多處理機系統(tǒng)有時也被稱為共享內(nèi)存系統(tǒng)(Shared

MemorySystem)。

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

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

很簡單的方式進行通信，只要一個處理器把數(shù)據(jù)寫入內(nèi)存而另一個處

理器從內(nèi)存中把數(shù)據(jù)讀出就可以了。

⑥多處理機系統(tǒng)也有磁盤、網(wǎng)絡(luò)適配器和其它的輸入/輸出設(shè)備。如果

在一個系統(tǒng)中，每個CPU都能平等地訪問所有的內(nèi)存模塊和輸入/輸

出設(shè)備，而且在操作系統(tǒng)看來這些CPU是可以互換的，那么這種系統(tǒng)

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

⑥多處理機系統(tǒng)中只有一個操作系統(tǒng)，操作系統(tǒng)負責(zé)管理一系列的表。

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

66

P348

共事由存的多處理機

CPU

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

圖13.17多處理機設(shè)計方案

67

UMA,處理機奈加

e----------

⑥UMA系統(tǒng)特點

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

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

■每臺處理器可帶私有高速緩存或私有內(nèi)存

⑥基于總線的UMA多處理機系統(tǒng)

總線總線總線

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

圖13.18基于總線結(jié)構(gòu)的多處理機系統(tǒng)

68

P349

NUMA,處理機奈統(tǒng)

國而|謔系統(tǒng)特點

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

■使用LOAD和STORE指令訪問遠程內(nèi)存

■訪問遠程內(nèi)存比訪問本地內(nèi)存慢

■NUMA系統(tǒng)中的處理器可使用高速緩存

爹NONUMA與CC-NUMA

■不使用Cache的NUMA系統(tǒng)被稱為NC-NUMA多

處理機系統(tǒng)，也就是說這種系統(tǒng)中不隱藏遠程

內(nèi)存的訪問時間。如果使用了Cache,那么系

統(tǒng)就被稱為CC-NUMA多處理機系統(tǒng)。

69

P356

NUMA多處理機奈統(tǒng)

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

爹NONUMA多處理機系統(tǒng)

CPU內(nèi)存CPU內(nèi)存CPU內(nèi)存CPU內(nèi)存

MMU

系統(tǒng)總線

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

爹CONUMA多處理機系統(tǒng)

結(jié)點0結(jié)點1結(jié)點255

CPU內(nèi)存CPU內(nèi)存CPU內(nèi)存

基于目錄的多處理機系統(tǒng)

70

P356

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

⑥Cache一致性問題產(chǎn)生原因

■現(xiàn)代并行計算機中，處理器往往帶有Cache。一個內(nèi)存

數(shù)據(jù)在整個系統(tǒng)內(nèi)可能有多份拷貝。這就引發(fā)了Cache

一致性問題。

⑥Cache一致性協(xié)議

■由Cache、CPU和內(nèi)存共同實現(xiàn)的防止多個Cache中出

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

性協(xié)議。

⑥Cache一致性協(xié)議通?？梢苑譃閮深?/p>

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

■基于目錄的協(xié)議

71

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

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

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

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

的數(shù)據(jù)，以使其它副本無效或得到更新。

■監(jiān)聽總線協(xié)議適用于互連網(wǎng)絡(luò)可以實現(xiàn)廣播功能的并行系統(tǒng)。