并行計(jì)算1結(jié)構(gòu)

1、1. 并行計(jì)算基礎(chǔ)1.1 并行計(jì)算定義并行計(jì)算并行計(jì)算是指同時(shí)對(duì)多個(gè)任務(wù)或多條指令、或?qū)Χ鄠€(gè)數(shù)據(jù)項(xiàng)進(jìn)行處理。完成此項(xiàng)處理的計(jì)算機(jī)系統(tǒng)稱(chēng)為并行計(jì)算機(jī)系統(tǒng)，它是將多個(gè)處理器（可以幾個(gè)、幾十個(gè)、幾千個(gè)、幾萬(wàn)個(gè)等）通過(guò)網(wǎng)絡(luò)連接以一定的方式有序地組織起來(lái)（一定的連接方式涉及網(wǎng)絡(luò)的互聯(lián)拓?fù)?、通信協(xié)議等，而有序的組織則涉及操作系統(tǒng)、中間件軟件等）。并行計(jì)算的主要目的：一是為了提供比傳統(tǒng)計(jì)算機(jī)快的計(jì)算速度；二是解決傳統(tǒng)計(jì)算機(jī)無(wú)法解決的問(wèn)題。1.2 并行計(jì)算的研究?jī)?nèi)容 (1)并行計(jì)算機(jī)的設(shè)計(jì)并行計(jì)算機(jī)的設(shè)計(jì)包括本并行計(jì)算機(jī)的結(jié)構(gòu)設(shè)計(jì)、互聯(lián)拓?fù)?、網(wǎng)絡(luò)通信等。設(shè)計(jì)并行計(jì)算機(jī)重要的一點(diǎn)要考慮處理機(jī)數(shù)目的按比例增長(zhǎng)（即

2、可擴(kuò)展性）及支持快速通信及處理機(jī)間的數(shù)據(jù)共享等。(2)有效算法的設(shè)計(jì)有效算法的設(shè)計(jì)如果沒(méi)有有效的并行算法，并行計(jì)算機(jī)無(wú)法使用，而并行算法的設(shè)計(jì)完全不同于串行算法的設(shè)計(jì)，不同的并行計(jì)算機(jī)的算法設(shè)計(jì)不同，只有將不同的并行計(jì)算機(jī) 與不同的實(shí)際問(wèn)題相結(jié)合，才能設(shè)計(jì)出有效的并行算法。 主要研究?jī)?nèi)容包括并行計(jì)算模型、并行算法的一般設(shè)計(jì)方法、基本設(shè)計(jì)技術(shù)和一般設(shè)計(jì)過(guò)程，并討論一些數(shù) 值并行算法與非數(shù)值并行算法的設(shè)計(jì)。1.2 并行計(jì)算的研究?jī)?nèi)容(3)評(píng)價(jià)并行算法的方法評(píng)價(jià)并行算法的方法對(duì)于給定的并行計(jì)算機(jī)及運(yùn)行在上面的并行算法，需要評(píng)價(jià)運(yùn)行性能。性能分析需解決的問(wèn)題：如何利用基于并行計(jì)算機(jī)及其相適應(yīng)的并行算法

3、去快速地解決問(wèn) 題，及如何有效地利用各個(gè)處理器。研究?jī)?nèi)容包括結(jié)合機(jī)器與算法，提出相應(yīng)的性能評(píng)測(cè)指標(biāo)，為設(shè)計(jì)高效的并行算法提供依據(jù)。(4)并行計(jì)算機(jī)語(yǔ)言并行計(jì)算機(jī)語(yǔ)言與傳統(tǒng)的機(jī)器語(yǔ)言不同，并行計(jì)算機(jī)語(yǔ)言依賴于并行計(jì)算機(jī)，并行計(jì)算機(jī)語(yǔ)言必須簡(jiǎn)潔，編程容易，可以有效地實(shí)現(xiàn)，目前的語(yǔ)言有：PVM、MPI、HPF等，而且新的編程語(yǔ)言于編程模式正在不斷地出現(xiàn)。 1.2 并行計(jì)算的研究?jī)?nèi)容(5)并行編程環(huán)境與工具并行編程環(huán)境與工具為了使編程容易，必須開(kāi)發(fā)綜合的編程環(huán)境與工具，且能達(dá)到兩個(gè)目的：并行計(jì)算機(jī)的底層機(jī)構(gòu)對(duì)用戶透明；為用戶提供設(shè)計(jì)與開(kāi)發(fā)程序所需要的調(diào)試器與模擬器等工具(6)并行程序的可移植性并行程序

4、的可移植性可移植性為并行程序設(shè)計(jì)的主要問(wèn)題，要求在一臺(tái)并行機(jī)上開(kāi)發(fā)的程序不加修改或進(jìn)行少量修改即可在另一臺(tái)計(jì)算機(jī)上運(yùn)行。這一點(diǎn)為目前受到了廣泛關(guān)注的重要課題。(7) 并行計(jì)算機(jī)的自動(dòng)編程并行計(jì)算機(jī)的自動(dòng)編程可否設(shè)計(jì)一個(gè)并行化編譯器，使用戶的串行程序通過(guò)并行化編譯器編譯，直接可在并行機(jī)上運(yùn)行。到目前為此，這種編譯器還不存在，而僅有一些半自動(dòng)并行化編譯器。1.3 并行計(jì)算的應(yīng)用分類(lèi) 計(jì)算密集型（計(jì)算密集型（Compute-Intensive）大型科學(xué)工程計(jì)算與數(shù)值模擬（氣象預(yù)報(bào)、地球物理勘探等）數(shù)據(jù)密集型數(shù)據(jù)密集型 (Data-Intensive)大量數(shù)據(jù)資源的有效處理，包括數(shù)字圖書(shū)館、數(shù)據(jù)倉(cāng)庫(kù)、

5、數(shù)據(jù)挖掘、計(jì)算可視化。網(wǎng)絡(luò)密集型網(wǎng)絡(luò)密集型 (Network-Intensive)通過(guò)網(wǎng)絡(luò)進(jìn)行遠(yuǎn)距離信息交互，來(lái)完成用傳統(tǒng)方法不同的一些應(yīng)用問(wèn)題。如協(xié)同工作、遙控與遠(yuǎn)程醫(yī)療診斷等2. 并行計(jì)算平臺(tái)并行計(jì)算機(jī)的控制結(jié)構(gòu) Flynn分類(lèi)法 Flynn分類(lèi)法是從計(jì)算機(jī)的運(yùn)行機(jī)制進(jìn)行分類(lèi)的。 指令流（instruction stream）：機(jī)器執(zhí)行的指令序列 數(shù)據(jù)流（data stream）：由指令流調(diào)用的數(shù)據(jù)序列，包括輸入數(shù)據(jù)和中間結(jié)果 。 Flynn根據(jù)指令流和數(shù)據(jù)流的不同組織方式，把計(jì)算機(jī)系統(tǒng)的結(jié)構(gòu)分為以下四類(lèi)： （1）單指令流單數(shù)據(jù)流（Single Instruction stream Sin

6、gle Data stream, SISD）；（2）單指令流多數(shù)據(jù)流（Single Instruction stream Multiple Data stream, SIMD）；（3）多指令流單數(shù)據(jù)流（Multiple Instruction stream Single Data stream, MISD）；（4）多指令流多數(shù)據(jù)流（Multiple Instruction stream Multiple Data stream, MISD）。 并行計(jì)算機(jī)的控制結(jié)構(gòu)SISD就是普通的順序處理的串行機(jī)。SIMD和MIMD是典型的并行計(jì)算機(jī)。MISD在實(shí)際中代表何種計(jì)算機(jī)，也存在不同的看法，甚至有學(xué)

7、者認(rèn)為根本不存在MISD。有的文獻(xiàn)把流水線結(jié)構(gòu)的計(jì)算機(jī)看成MISD結(jié)構(gòu)。在一臺(tái)SIMD計(jì)算機(jī)中，有一個(gè)控制部件（又稱(chēng)為控制單元，control unit）和許多處理單元（processing unit）。大量的處理單元通常構(gòu)成陣列，因此SIMD計(jì)算機(jī)有時(shí)也稱(chēng)為陣列處理機(jī)。所有的處理單元在控制部件的統(tǒng)一控制下工作?？刂撇考蛩械奶幚韱卧獜V播同一條指令，所有的處理單元同時(shí)執(zhí)行這條指令，但是每個(gè)處理單元操作的數(shù)據(jù)不同?？刂撇考梢杂羞x擇地屏蔽掉一些處理單元，被屏蔽掉的處理單元不執(zhí) 行控制部件廣播的指令。典型的SIMD計(jì)算機(jī)有Illiac IV, Goodyear MPP, DAP, CM-2, M

8、asPar MP-1和MasPar MP-2等。 并行計(jì)算機(jī)的控制結(jié)構(gòu)在MIMD計(jì)算機(jī)中沒(méi)有統(tǒng)一的控制部件沒(méi)有統(tǒng)一的控制部件，各處理器可以獨(dú)立地執(zhí)行不同的指令。實(shí)際上，在SIMD機(jī)中，各處理單元執(zhí)行的是同一個(gè)程序，而在 MIMD機(jī)上，各處理器可以獨(dú)立執(zhí)行不同的程序。在MIMD中，每個(gè)處理器都有控制部件，各處理器通過(guò)互連網(wǎng)絡(luò)進(jìn)行通信。MIMD結(jié)構(gòu)比SIMD結(jié)構(gòu)更加 靈活。SIMD計(jì)算機(jī)通常要求實(shí)際問(wèn)題包含大量的對(duì)不同數(shù)據(jù)的相同運(yùn)算（例如向量運(yùn)算和矩陣運(yùn)算）才能發(fā)揮其優(yōu)勢(shì)。而MIMD計(jì)算機(jī)則無(wú)此要求，它可以適 應(yīng)更多的并行算法，因此可以更加充分地開(kāi)掘?qū)嶋H問(wèn)題的并行性。SIMD所使用的CPU通常是專(zhuān)

9、門(mén)設(shè)計(jì)的，而MIMD可以使用通用CPU。后面將會(huì)介紹各種 MIMD計(jì)算機(jī)。并行計(jì)算機(jī)的控制結(jié)構(gòu)隨著并行計(jì)算技術(shù)的不斷發(fā)展，近來(lái)又出現(xiàn)了SPMD，MPMD等概念。SPMD是指單程序多數(shù)據(jù)（Single Program Multiple Data），MPMD是指多程序多數(shù)據(jù)（ Multiple Program Multiple Data ）。在SPMD機(jī)制中，各處理器有自己的控制部件。各處理器并行地執(zhí)行同一個(gè)程序，但所操作的數(shù)據(jù)不一定相同。與相比SIMD，在 SPMD模式下，各處理器只在需要時(shí)進(jìn)行同步，而不是同步地執(zhí)行每一條指令。在某一時(shí)刻，不同的處理器執(zhí)行的指令可能不相同。SPMD易于在機(jī)群系統(tǒng)

10、和 MPI（一種并行編程環(huán)境）的支持下得以實(shí)現(xiàn)，因此被廣泛使用。 地址空間 從地址空間的角度，可以將并行計(jì)算機(jī)分為兩類(lèi)：消息傳遞體系結(jié)構(gòu)和共享地址空間體系結(jié)構(gòu)。 消息傳遞體系結(jié)構(gòu)：在消息傳遞結(jié)構(gòu)的并行機(jī)中，通常每個(gè)處理器有自己的存儲(chǔ)器。該存儲(chǔ)器只能被該處理器訪問(wèn)而不能被其它處理器直接訪問(wèn)，因此這種存儲(chǔ)器通常稱(chēng)為局部存儲(chǔ)器局部存儲(chǔ)器或私有存儲(chǔ)器私有存儲(chǔ)器。當(dāng)處理器A需要向處理器B傳送數(shù)據(jù)時(shí)， 把被傳送的數(shù)據(jù)以消息的形式發(fā)送給B。典型的消息傳遞結(jié)構(gòu)的并行機(jī)有Cosmic Cube, Paragon XP/S, iPSC, CM-5和nCUBE 2。 地址空間共享地址空間體系結(jié)構(gòu)：在共享地址空間體系

11、結(jié)構(gòu)的并行機(jī)中，通過(guò)硬件支持，使得系統(tǒng)中只有唯一的一個(gè)地址空間系統(tǒng)中只有唯一的一個(gè)地址空間，所有的處理器共享該地址空間。共享地址空間并不意味著系統(tǒng)中必須存在一個(gè)在物理上共享的存儲(chǔ)器。共享地址空間可以通過(guò)一個(gè)物理上共享的存儲(chǔ)器來(lái)實(shí)現(xiàn)，也可以通過(guò)分布式存儲(chǔ)器來(lái)實(shí)現(xiàn)。在某些并行系統(tǒng)中，存儲(chǔ)器分布在各結(jié)點(diǎn)內(nèi)，通過(guò)硬件和軟件的方法維護(hù)一個(gè)單一的地址空間。當(dāng)處理器要訪問(wèn)不在本結(jié)點(diǎn)內(nèi)的內(nèi)存時(shí)，由系統(tǒng)硬件和軟件為它找到所需訪問(wèn)的內(nèi)存。采用消息傳遞結(jié)構(gòu)的MIMD計(jì)算機(jī)又稱(chēng)為多計(jì)算機(jī)（multicomputers），采用共享地址空間結(jié)構(gòu)的MIMD計(jì)算機(jī)又稱(chēng)為多處理器（multiprocessors）。但實(shí)際上，隨

12、著并行機(jī)結(jié)構(gòu)的發(fā)展，多處理機(jī)和多處理器的界限已不十分清晰，很難嚴(yán)格區(qū)分。 互連網(wǎng)絡(luò) 在并行計(jì)算的過(guò)程中，處理器要與局部存儲(chǔ)器、共享存儲(chǔ)器及其它處理器通信。因此互連網(wǎng)絡(luò)在并行計(jì)算機(jī)中擔(dān)當(dāng)著十分重要的角色。并行計(jì)算機(jī)中的互連網(wǎng)絡(luò)有兩個(gè)層次：結(jié)點(diǎn)內(nèi)的和結(jié)點(diǎn)間的。結(jié)點(diǎn)內(nèi)的互連網(wǎng)絡(luò)指CPU、局部?jī)?nèi)存、本地磁盤(pán)和結(jié)點(diǎn)內(nèi)的其它設(shè)備之間的互連網(wǎng)絡(luò)，例如處理器總線，存儲(chǔ)總線。結(jié)點(diǎn)間的互連 網(wǎng)絡(luò)指各結(jié)點(diǎn)之間的互連網(wǎng)絡(luò)，例如以太網(wǎng)和各種定制的網(wǎng)絡(luò)。結(jié)點(diǎn)間的互連網(wǎng)絡(luò)可以有各種拓?fù)浣Y(jié)構(gòu)，按照程序執(zhí)行過(guò)程中鏈路是否可變可分為動(dòng)態(tài)網(wǎng)絡(luò)和靜態(tài)網(wǎng)絡(luò)?；ミB網(wǎng)絡(luò)的操作方式可分為同步通信和異步通信，控制策略可分為集中控制和分布控制。

13、互連網(wǎng)絡(luò)的交換方式有存儲(chǔ)轉(zhuǎn)發(fā)和切通尋徑。 并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)模型 從系統(tǒng)結(jié)構(gòu)的角度，并行計(jì)算機(jī)一般可以分為6類(lèi)： 單指令流多數(shù)據(jù)流計(jì)算機(jī)SIMD（Single Instruction stream Multiple Data stream）、 并行向量處理機(jī)PVP（Parallel Vector Processor）、 對(duì)稱(chēng)多處理機(jī)SMP（Symmetric Multiprocessor）、 大規(guī)模并行處理機(jī)MPP（Massively Parallel Processor ）、 分布式共享存儲(chǔ)多處理機(jī)DSM（Distributed Shared Memory）。 工作站機(jī)群COW（Cluste

14、r Of Workstations，也稱(chēng)為Network Of Workstations，NOW）這6種中，除了SIMD外，其余5種均屬于MIMD計(jì)算機(jī)。 SIMD計(jì)算機(jī)SIMD計(jì)算機(jī)：SIMD計(jì)算機(jī)前面已經(jīng)介紹過(guò)，其結(jié)構(gòu)如下圖所示，其中PE表示處理單元，P表示處理器，M表示存儲(chǔ)器。 SIMD中通常包含大量處理單元PE，而控制部件只有一個(gè)?？刂撇考V播一條指令，所有的處理單元同時(shí)執(zhí)行這條指令，但不同的處理單元操作的數(shù)據(jù)可能不同。典型的SIMD計(jì)算機(jī)有MasPar公司的MP-1系列，Thinking Machines公司的CM-2，Illiac IV，BSP等。MasPar MP-1最多可容納1

15、6384個(gè)處理器。當(dāng)配置16384個(gè)處理器時(shí)，32位的整數(shù)操作的峰值性能可達(dá)26000MIPS，單精度浮點(diǎn)運(yùn)算性能達(dá) 1.5GFlops，雙精度浮點(diǎn)運(yùn)算性能達(dá)650MFlops。CM-2有65536個(gè)處理單元，峰值速度達(dá)到28GFlops，持續(xù)速度達(dá)到 5.6GFlops。 SIMD計(jì)算機(jī)并行向量處理機(jī)并行向量處理機(jī)：在并行向量處理機(jī)中有少量專(zhuān)門(mén)定制的向量處理器專(zhuān)門(mén)定制的向量處理器。每個(gè)向量處理器有很高的處理能力。并行向量處理機(jī)通過(guò)向量處理和多個(gè)向量處理器并行處理兩條途徑來(lái)提高處理能力。PVP通常使用定制的高帶寬網(wǎng)絡(luò)將向量處理器連向共享存儲(chǔ)器模塊。存儲(chǔ)器可以以很高的速度向處理器提供數(shù)據(jù)。這種機(jī)

16、器通常不使用高速緩存，而是使用大量的向量寄存器和指令緩沖器。 Cray C-90、Cray T-90、NEC SX-4和我國(guó)的銀河1號(hào)都是PVP。 并行向量處理機(jī)圖中VP表示向量處理器，SM表示共享存儲(chǔ)器。對(duì)稱(chēng)多處理機(jī) 對(duì)稱(chēng)多處理機(jī)的最大特點(diǎn)是其中的各處理器完全平等，無(wú)主從之分。所有的處理器都可以訪問(wèn)任何存儲(chǔ)單元和I/O設(shè)備。存儲(chǔ)器一般使用使用共享存儲(chǔ)器共享存儲(chǔ)器，只有一個(gè)地址空間。因?yàn)槭褂霉蚕泶鎯?chǔ)器，通信可用共享變量（讀寫(xiě)同一內(nèi)存單元）來(lái)實(shí)現(xiàn)。這使得編程很容易。典型的對(duì)稱(chēng)多處理機(jī)有Sun SPARC server 10000，Sun SPARC center 2000，SGI Power C

17、hallenge以及我國(guó)的曙光1號(hào)。SMP廣泛地用于服務(wù)器領(lǐng)域。 對(duì)稱(chēng)多處理機(jī)P/C表示處理器和高速緩存，SM表示共享存儲(chǔ)器。大規(guī)模并行處理機(jī) 大規(guī)模并行處理機(jī)一般指規(guī)模非常大的并行計(jì)算機(jī)系統(tǒng)，含有成千上萬(wàn)個(gè)處理器。它一般采用分布的存儲(chǔ)器采用分布的存儲(chǔ)器，存儲(chǔ)器一般為處理器私有，各處理器之間用消息傳遞的方式通信。大規(guī)模并行處理機(jī)的互連網(wǎng)絡(luò)一般是專(zhuān)門(mén)設(shè)計(jì)定制的。典型的MPP有Intel Paragon、IBM SP2以及Option Red。MPP的結(jié)構(gòu)如下圖所示。網(wǎng)絡(luò)接口電路（Network Interface Circuitry，NIC）是用來(lái)將計(jì)算機(jī)與網(wǎng)絡(luò)（例如局域網(wǎng)）連接起來(lái)的接口電路。

18、典型的NIC包括一個(gè)嵌入式的處理器，一些輸入、輸出緩沖器，以及一些控制存儲(chǔ)器和控制邏輯，它的功能有：將消息格式化、路由選擇、流和錯(cuò)誤控制等。）大規(guī)模并行處理機(jī)MB表示存儲(chǔ)器總線，P/C表示處理器和高速緩存，NIC表示網(wǎng)絡(luò)接口電路，LM表示本地存儲(chǔ)器。分布式共享存儲(chǔ)器多處理機(jī) 分布式共享存儲(chǔ)器多處理機(jī)的主要特點(diǎn)是它的存儲(chǔ)器在物理上是分布在各個(gè)結(jié)點(diǎn)中的，但是通過(guò)硬件和軟件為用戶提供一個(gè)單一地址的編提供一個(gè)單一地址的編程空間程空間，即形成一個(gè)虛擬的共享存儲(chǔ)器。它通過(guò)高速緩存目錄支持分布高速緩存的一致性。DSM與SMP的區(qū)別在于各結(jié)點(diǎn)內(nèi)有存儲(chǔ)器，與MPP的區(qū)別在于存儲(chǔ)器在邏輯上是共享的。典型的DSM有

19、Stanford DASH、SGI/Cray Origin 2000。 分布式共享存儲(chǔ)器多處理機(jī)DIR表示高速緩存目錄工作站機(jī)群 工作站機(jī)群是一種新興的并行系統(tǒng)。COW是由高檔微機(jī)（包括工作站）用高速互連網(wǎng)絡(luò)（有的商用機(jī)群也使用定制的網(wǎng)絡(luò)）連接而成。因此COW的每個(gè)結(jié)點(diǎn)都是一臺(tái)完整的計(jì)算機(jī)（可能沒(méi)有鼠標(biāo)、顯示器等外設(shè)）。COW的每個(gè)結(jié)點(diǎn)上都有完整的操作系統(tǒng)，而MPP的每個(gè)結(jié)點(diǎn)上通常只有操作系統(tǒng)的微核。COW的每個(gè)結(jié)點(diǎn)內(nèi)有本地磁盤(pán)，而MPP的結(jié)點(diǎn)內(nèi)沒(méi)有。COW各結(jié)點(diǎn)的網(wǎng)絡(luò)接口是連接到I/O總線上的（松耦合），而MPP各結(jié)點(diǎn)的網(wǎng)絡(luò)接口是連接到存儲(chǔ)總線上的（緊耦合）。 工作站機(jī)群工作站機(jī)群LD表示本

20、地磁盤(pán)，B表示存儲(chǔ)總線與I/O總線的接口，IOB表示I/O總線。并行計(jì)算機(jī)訪存模型 本節(jié)將從訪問(wèn)存儲(chǔ)器的方式的角度來(lái)研究并行計(jì)算機(jī)。常用的并行計(jì)算機(jī)訪存模型有UMA，NUMA，COMA，CC-NUMA，NORMA五種。在分布式的并行機(jī)中，通常包含多個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)內(nèi)都有處理器和存儲(chǔ)器。本結(jié)點(diǎn)內(nèi)的處理器和存儲(chǔ)器通常稱(chēng)為本地的或局部的，而其它結(jié)點(diǎn)中的處理器和存儲(chǔ)器常稱(chēng)為遠(yuǎn)程的。 UMA訪存模型UMA（Uniform Memory Access）模型是均勻存儲(chǔ)訪問(wèn)模型的簡(jiǎn)稱(chēng)。其特點(diǎn)是： 物理存儲(chǔ)器被所有處理器均勻共享； 所有處理器訪問(wèn)任何存儲(chǔ)字需要相同的時(shí)間 ； 每臺(tái)處理器可帶私有高速緩存； 外圍設(shè)

21、備也可以一定形式共享。UMA訪存模型NUMA訪存模型NUMA(Nonuniform Memory Access)模型是非均勻存儲(chǔ)訪問(wèn)非均勻存儲(chǔ)訪問(wèn)模型的簡(jiǎn)稱(chēng)。特點(diǎn)是： 被共享的存儲(chǔ)器在物理上是分布在所有的處理器中的，其所有本地存儲(chǔ)器的集合就組成了全局地址空間； 處理器訪問(wèn)存儲(chǔ)器的時(shí)間是不一樣的；訪問(wèn)本地存儲(chǔ)器LM或群內(nèi)共享存儲(chǔ)器CSM較快，而訪問(wèn)外部的存儲(chǔ)器或全局共享存儲(chǔ)器GSM較慢(此即非均勻存儲(chǔ)訪問(wèn)名稱(chēng)的由來(lái))； 每臺(tái)處理器照例可帶私有高速緩存，外設(shè)也可以某種形式共享。 NUMA訪存模型在NUMA中，共享存儲(chǔ)器在物理上是分布的，所有的本地存儲(chǔ)器構(gòu)成了全局地址空間。NUMA與UMA的區(qū)別在于

22、處理器訪問(wèn)本地存儲(chǔ)器和群內(nèi)共享存儲(chǔ)器比訪問(wèn)遠(yuǎn)程存儲(chǔ)器或全局共享存儲(chǔ)器快（此即非均勻存儲(chǔ)訪問(wèn)名稱(chēng)的由來(lái)）。下圖中（a）表示共享本地存儲(chǔ)器的NUMA結(jié)構(gòu)，（b）為層次式機(jī)群NUMA結(jié)構(gòu)。 NUMA訪存模型LM表示本地存儲(chǔ)器，GSM表示全局共享存儲(chǔ)器，P表示處理器，CSM表示群內(nèi)共享存儲(chǔ)器，CIN表示機(jī)群互連網(wǎng)絡(luò)。NUMA訪存模型COMA訪存模型COMA(Cache-Only Memory Access)模型是全高速緩存存儲(chǔ)訪問(wèn)全高速緩存存儲(chǔ)訪問(wèn)的簡(jiǎn)稱(chēng)。其特點(diǎn)是： 各處理器節(jié)點(diǎn)中沒(méi)有存儲(chǔ)層次結(jié)構(gòu)，全部高速緩存組成了全局地址空間； 利用分布的高速緩存目錄D進(jìn)行遠(yuǎn)程高速緩存的訪問(wèn); COMA中的高速緩存

23、容量一般都大于2 級(jí)高速緩存容量； 使用COMA時(shí)，數(shù)據(jù)開(kāi)始時(shí)可任意分配，因?yàn)樵谶\(yùn)行時(shí)它最終會(huì)被遷移到要用到它們的地方。 COMA訪存模型COMA實(shí)際是NUMA的一種特例，將NUMA中的分布存儲(chǔ)器換成高速緩存就得到了COMA。在COMA中，每個(gè)結(jié)點(diǎn)上沒(méi)有存儲(chǔ)層次結(jié)構(gòu)，所有的高速緩存構(gòu)成了全局地址空間。訪問(wèn)遠(yuǎn)程高速緩存要借助分布的高速緩存目錄。COMA結(jié)構(gòu)如下圖所示。D表示高速緩存目錄，C表示高速緩存，P表示處理器。COMA訪存模型CC-NUMA訪存模型CC-NUMA（Coherent-Cache Nonuniform Memory Access）模型是高速緩存一致性非均勻存儲(chǔ)訪問(wèn)高速緩存一致性

24、非均勻存儲(chǔ)訪問(wèn)模型的簡(jiǎn)稱(chēng)。其特點(diǎn)是： 大多數(shù)CC-NUMA多處理機(jī)系統(tǒng)使用基于目錄的高速緩存一致性協(xié)議； 保留SMP結(jié)構(gòu)易于編程的優(yōu)點(diǎn)，也改善了常規(guī)SMP結(jié)構(gòu)的可擴(kuò)放性； CC-NUMA實(shí)際上是一個(gè)分布共享存儲(chǔ)的DSM多處理機(jī)系統(tǒng)； 它最顯著的優(yōu)點(diǎn)是程序員無(wú)需明確地在節(jié)點(diǎn)上分配數(shù)據(jù)，系統(tǒng)的硬件和軟件開(kāi)始時(shí)自動(dòng)在各節(jié)點(diǎn)分配數(shù)據(jù)，在運(yùn)行期間，高速緩存一致性硬件會(huì)自動(dòng)地將數(shù)據(jù)遷移至要用到它的地方。 CC-NUMA訪存模型CC-NUMA結(jié)構(gòu)的并行機(jī)實(shí)際上是將一些SMP機(jī)作為結(jié)點(diǎn)互連起來(lái)而構(gòu)成的并行機(jī)。這樣可以改善SMP機(jī)的可擴(kuò)展性。CC-NUMA注重開(kāi)拓?cái)?shù)據(jù)的局部性和增強(qiáng)系統(tǒng)的可擴(kuò)展性。在實(shí)際應(yīng)用中，

25、大多數(shù)的數(shù)據(jù)訪問(wèn)都可在本結(jié)點(diǎn)內(nèi)完成，網(wǎng)絡(luò)上傳輸?shù)闹饕歉咚倬彺鏌o(wú)效性信息而不是數(shù)據(jù)。CC-NUMA和COMA的共同特點(diǎn)是它們都對(duì)高速緩存一致性提供硬件支持，而在另一種訪存模型NCC-NUMA（Non-Cache Coherent Non-Uniform Memory Access）中，則沒(méi)有對(duì)高速緩存的一致性提供硬件支持。CC-NUMA訪存模型I/ONIC,DIR,RC系統(tǒng)互連網(wǎng)路MemP/CP/CI/ONIC,DIR,RCMemP/CP/C節(jié)點(diǎn)N節(jié)點(diǎn) 1總線或 交叉 開(kāi)關(guān)總線或 交叉 開(kāi)關(guān)訪存模型NORMA（No-Remote Memory Access）模型是非遠(yuǎn)程存儲(chǔ)訪問(wèn)模是非遠(yuǎn)程存儲(chǔ)訪

26、問(wèn)模型型的簡(jiǎn)稱(chēng)。在NORMA中，所有的存儲(chǔ)器都是處理器私有的，僅能由其處理器訪問(wèn)。各處理器之間通過(guò)消息傳遞方式通信。MPP多采用這種結(jié)構(gòu)。 NORMA的特點(diǎn)是： 所有存儲(chǔ)器是私有的； 絕大數(shù)NUMA都不支持遠(yuǎn)程存儲(chǔ)器的訪問(wèn)； 在DSM中，NORMA就消失了。 訪存模型消息傳遞互連網(wǎng)絡(luò)(網(wǎng)絡(luò)，環(huán)網(wǎng)，超立方，立方環(huán)等)PMPMMPMPMPMPMPPMPMPM.消息傳遞多計(jì)算機(jī)一般模型構(gòu)筑并行機(jī)系統(tǒng)的不同存儲(chǔ)結(jié)構(gòu)MIMDMIMD多計(jì)算機(jī)(多地址空間非共享存儲(chǔ)器)(IBM SP2,DEC TruClusterTandem Hymalaya,HP,Microsoft Wolfpack,etc)NORMA

27、NORMAUMAUMANUMANUMAClusterClusterMPPMPP(Intel TFLOPS)緊耦合PVPPVP(Cray T90)SMPSMP(Intel SHV,SunFire,DEC 8400,SGI PowerChallenge,IBMR60,etc.)COMACOMA(KSR-1,DDM)CC-NUMACC-NUMA(Stanford Dash,SGI Origin 2000,Sequent NUMA-Q,HP/Convex Exemplar)NCC-NUMANCC-NUMA(Cray T3E)DSMDSM(TreadMarks,Wind Tunnel,IVY,Shrim

28、p,etc.)（）松散耦合（）中央存儲(chǔ)器分布存儲(chǔ)器多處理機(jī)單地址共享（）空間存儲(chǔ)器并行機(jī)結(jié)構(gòu)模型和訪存模型的關(guān)系物理上分布的存儲(chǔ)器從編程的觀點(diǎn)來(lái)看可以是共享的也可以是非共享的；多處理機(jī)共享存儲(chǔ)結(jié)構(gòu)可同時(shí)支持共享存儲(chǔ)和消息傳遞編程模型；共享存儲(chǔ)的編程模型可同時(shí)執(zhí)行于共享存儲(chǔ)結(jié)構(gòu)和分布式存儲(chǔ)結(jié)構(gòu)的多計(jì)算機(jī)上。計(jì)算機(jī)存儲(chǔ)器組織層次存儲(chǔ)技術(shù)層次存儲(chǔ)技術(shù)存儲(chǔ)器相鄰層之間數(shù)據(jù)的傳輸： 處理器和高速緩存之間數(shù)據(jù)按字傳輸(4Bytes)； 高速緩存按行（Cache Line）存儲(chǔ)數(shù)據(jù)(16Bytes)； 高速緩存和主存之間數(shù)據(jù)按塊傳輸(32Bytes)； 主存和磁盤(pán)之間數(shù)據(jù)按頁(yè)傳輸(1KBytes)； 磁盤(pán)和

29、后援存儲(chǔ)之間的數(shù)據(jù)按段傳輸。高速緩存一致性 多處理機(jī)系統(tǒng)共享存儲(chǔ)器存在的問(wèn)題 訪存沖突與數(shù)據(jù)一致性 數(shù)據(jù)多個(gè)副本之間的相同性高速緩存一致性造成高速緩存不一致的原因 由共享可寫(xiě)數(shù)據(jù)所造成的不一致； 由進(jìn)程遷移造成的不一致； 由繞過(guò)高速緩存的I/O操作造成的不一致； 偽共享失效false sharing。例子（1）CPU寫(xiě)Cache，沒(méi)有立即寫(xiě)主存； （2）I/O處理機(jī)或I/O設(shè)備寫(xiě)主存。 高速緩存一致性高速緩存寫(xiě)策略 寫(xiě)通過(guò)（Write-Through）：如果修改了cache中的一個(gè)數(shù)據(jù)，則在主存中立即修改相應(yīng)變量的值； 寫(xiě)回（Write-back）：主存中變量值的修改，可以延遲到cache中正

30、在修改的數(shù)據(jù)被替換或從cache中消除后才進(jìn)行。高速緩存一致性總線監(jiān)聽(tīng)協(xié)議（Snoopy protocol） 如果連接在公共總線上的每個(gè)處理器都帶有私有高速緩存，那么，可使用寫(xiě)無(wú)效（write invalidate）和寫(xiě)更新（write update）兩種策略來(lái)保證高速緩存的一致性。 寫(xiě)無(wú)效：更新本地高速緩存中的數(shù)據(jù)時(shí)，強(qiáng)迫所有其他處理器的高速緩存中的該數(shù)據(jù)副本均無(wú)效。 寫(xiě)更新：把更新的數(shù)據(jù)塊廣播給含該數(shù)據(jù)塊的所有高速緩存。高速緩存一致性寫(xiě)更新和寫(xiě)無(wú)效策略性能差別的原因 對(duì)同一數(shù)據(jù)的多個(gè)寫(xiě)而中間無(wú)讀操作的情況，寫(xiě)更新協(xié)議需進(jìn)行多次寫(xiě)廣播操作，而在寫(xiě)無(wú)效協(xié)議下只需一次作廢操作。 對(duì)同一塊中多個(gè)字

31、進(jìn)行寫(xiě)，寫(xiě)更新協(xié)議對(duì)每個(gè)字的寫(xiě)均要進(jìn)行一次廣播，而在寫(xiě)無(wú)效協(xié)議下僅在對(duì)本塊第一次寫(xiě)時(shí)進(jìn)行作廢操作即可。寫(xiě)無(wú)效是針對(duì)Cache塊進(jìn)行操作，而寫(xiě)更新則是針對(duì)字(或字節(jié))進(jìn)行操作 從一個(gè)處理器寫(xiě)到另一個(gè)處理器讀之間的延遲通常在寫(xiě)更新模式中較低，因?yàn)樗鼘?xiě)數(shù)據(jù)時(shí)馬上更新了相應(yīng)的其它Cache中的內(nèi)容(假設(shè)讀的處理器Cache中有此數(shù)據(jù))。而在寫(xiě)無(wú)效協(xié)議中，需要讀一個(gè)新的拷貝。 高速緩存一致性基于目錄的協(xié)議（Directory Based Protocol） 采用多級(jí)互聯(lián)網(wǎng)絡(luò)實(shí)現(xiàn)的多處理機(jī)系統(tǒng)，使用一個(gè)目錄來(lái)記錄共享數(shù)據(jù)的所有高速緩存行的位置和狀態(tài)。3.并行計(jì)算機(jī)互連網(wǎng)絡(luò) 靜態(tài)網(wǎng)絡(luò)和動(dòng)態(tài)網(wǎng)絡(luò)的基本概念 網(wǎng)

32、絡(luò)可以用圖來(lái)表示。結(jié)點(diǎn)表示網(wǎng)絡(luò)中的各種部件，邊表示鏈路。互連網(wǎng)絡(luò)分為靜態(tài)網(wǎng)絡(luò)和動(dòng)態(tài)網(wǎng)絡(luò)兩大類(lèi)。靜態(tài)網(wǎng)絡(luò)靜態(tài)網(wǎng)絡(luò)（Static Networks） 靜態(tài)網(wǎng)絡(luò)是指結(jié)點(diǎn)間有著固定連接通路且在程序執(zhí)行期間，這種連接保持不變的網(wǎng)絡(luò)。典型的靜態(tài)網(wǎng)絡(luò)有一維線性陣列、二維網(wǎng)孔、樹(shù)連接、超立方網(wǎng)絡(luò)、立方環(huán)、洗牌交換網(wǎng)、蝶形網(wǎng)絡(luò)等動(dòng)態(tài)網(wǎng)絡(luò)動(dòng)態(tài)網(wǎng)絡(luò)（Dynamic Networks） 動(dòng)態(tài)網(wǎng)絡(luò)是用開(kāi)關(guān)單元構(gòu)成的，可按應(yīng)用程序的要求動(dòng)態(tài)地改變連接狀態(tài)的網(wǎng)絡(luò)。典型的動(dòng)態(tài)網(wǎng)絡(luò)包括總線、交叉開(kāi)關(guān)和多級(jí)互連網(wǎng)絡(luò)等。 互連函數(shù) 為了反映不同互連網(wǎng)絡(luò)的連接特性，每種互連網(wǎng)絡(luò)可以用一組互連函數(shù)來(lái)描述。用整數(shù)0、1、N-1 分別表示

33、互連網(wǎng)絡(luò)的N 個(gè)輸入端和N 個(gè)輸出端。記互連函數(shù)為f ，它表示輸入端 (0iN-1)與輸出端f(i) 相連。N個(gè)數(shù)的每一種有確定次序的放置方式稱(chēng)為一個(gè)N 排列。把一個(gè)N排列變成另一個(gè)N排列的變換稱(chēng)為N階置換?；ミB函數(shù)反映了網(wǎng)絡(luò)輸出端相對(duì)于輸入端的置換關(guān)系或排列關(guān)系。所以互連函數(shù)有時(shí)也稱(chēng)為置換函數(shù)或排列函數(shù)。表示互連函數(shù)時(shí)，輸入端和輸出端通常用二進(jìn)制的形式，寫(xiě)成 的形式。互連函數(shù)常用的互連函數(shù) 恒等置換 交換置換 方體置換 均勻洗牌置換 蝶式置換 位序顛倒置換 移數(shù)置換 加減 置換 例：恒等置換恒等置換恒等置換：輸入與輸出相同的函數(shù)稱(chēng)為恒等函數(shù)，其表達(dá)式為 其中等式左邊括號(hào)內(nèi)的 和等式右邊的 分

34、別是網(wǎng)絡(luò)輸入端和輸出端的二進(jìn)制地址編號(hào)。恒等置換完成的變換如下圖所示。 例：恒等置換例：交換置換交換置換交換置換：交換置換是把輸入端二進(jìn)制地址中最低位取反的置換，其表達(dá)式為 交換置換完成的變換如下圖所示 例：交換置換例：方體置換 方體置換是把輸入端二進(jìn)制地址中第k位取反的置換。方體置換實(shí)際上是一組函數(shù)，共有n個(gè)。它們的表達(dá)式為 0 k n-1 以N=8，n=3為例例：方體置換 例：方體置換例：方體置換例：均勻洗牌置換 均勻洗牌置換是把輸入端分成數(shù)目相等的兩半，前一半和后一半按原順序相間排列的置換。這種置換很像洗撲克牌時(shí)將整副牌分成相等的兩疊來(lái)洗，以達(dá)到一張隔一張的均勻狀況，由此而得名。其表達(dá)式

35、為即均勻洗牌置換是將輸入端地址的二進(jìn)制編號(hào)循環(huán)左移一位的置換。它完成的變換如下圖所示。 例：均勻洗牌置換例：蝶式置換 蝶式置換：將輸入端的二進(jìn)制地址的最高位和最低位互換位置 。其函數(shù)表達(dá)式為 例：蝶式置換 網(wǎng)絡(luò)的參數(shù) 通常用以下參數(shù)來(lái)描述和衡量一個(gè)靜態(tài)網(wǎng)絡(luò)。結(jié)點(diǎn)度：與結(jié)點(diǎn)相連接的邊數(shù)，表示結(jié)點(diǎn)所需要的I/O端口數(shù)。結(jié)點(diǎn)度保持恒定的網(wǎng)絡(luò)可擴(kuò)展性更好，因?yàn)樵谶@種網(wǎng)絡(luò)中每個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)接口規(guī)格統(tǒng)一。根據(jù)通道到結(jié)點(diǎn)的方向，結(jié)點(diǎn)度可以進(jìn)一步表示為結(jié)點(diǎn)度 入度 出度其中入度是進(jìn)入結(jié)點(diǎn)的通道數(shù)，出度是從結(jié)點(diǎn)出來(lái)的通道數(shù)。鏈路的長(zhǎng)度：鏈路中包含的邊數(shù)。距離：兩個(gè)結(jié)點(diǎn)之間最短的鏈路的長(zhǎng)度。 網(wǎng)絡(luò)的參數(shù)網(wǎng)絡(luò)直徑網(wǎng)絡(luò)

36、直徑（Network Diameter）：網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)之間的最長(zhǎng)距離。它表征了信息在網(wǎng)絡(luò)中傳輸時(shí)可能經(jīng)過(guò)的鏈路長(zhǎng)度的最大值，因此它是說(shuō)明網(wǎng)絡(luò)通信性能的一個(gè)指標(biāo)。從通信的觀點(diǎn)來(lái)看，網(wǎng)絡(luò)直徑應(yīng)當(dāng)盡可能地小。 網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)規(guī)模：網(wǎng)絡(luò)中的結(jié)點(diǎn)數(shù)，它表示該網(wǎng)絡(luò)所能連接部件的多少。等分寬度等分寬度（Bisection Width）：網(wǎng)絡(luò)被切成相等的兩半時(shí)，沿切口的最小邊數(shù)。對(duì)稱(chēng)性對(duì)稱(chēng)性：若從任何結(jié)點(diǎn)看，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)都一樣，則該網(wǎng)絡(luò)稱(chēng)為對(duì)稱(chēng)的。對(duì)稱(chēng)的網(wǎng)絡(luò)實(shí)現(xiàn)和編程都比較容易。 靜態(tài)互連網(wǎng)絡(luò)1一維線性陣列（1-D Linear Array）： 并行機(jī)中最簡(jiǎn)單、最基本的互連方式， 每個(gè)節(jié)點(diǎn)只與其左、右近

37、鄰相連，也叫二近鄰連接， N個(gè)節(jié)點(diǎn)用N-1條邊串接之，內(nèi)節(jié)點(diǎn)度為2，直徑為N-1，對(duì)剖寬度為1靜態(tài)互連網(wǎng)絡(luò)2 環(huán)：將一個(gè)線性陣列的兩端相連就構(gòu)成一個(gè)環(huán)。環(huán)可以是單向工作的，也可以是雙向工作的。雙向環(huán)因?yàn)橛袃蓷l通路，所以可靠性比單向環(huán)更高。環(huán)是對(duì)稱(chēng)的，結(jié)點(diǎn)度為常數(shù)2。單向環(huán)直徑為N-1 ，雙向環(huán)直徑為 N/2靜態(tài)互連網(wǎng)絡(luò)3帶弦環(huán)帶弦環(huán)：在環(huán)中不相鄰的結(jié)點(diǎn)之間加入鏈路，就得到了帶弦環(huán)。與環(huán)相比，帶弦環(huán)的結(jié)點(diǎn)度大。 結(jié)點(diǎn)度為3的帶弦環(huán)中，鏈路數(shù)為18，直徑為4（圖中紅色結(jié)點(diǎn)之間的距離），度為3，不對(duì)稱(chēng)，等分寬度為2。結(jié)點(diǎn)度為4的帶弦環(huán)中，鏈路數(shù)為24，直徑為3，度為4，對(duì)稱(chēng)，等分寬度為8。一般地，結(jié)

38、點(diǎn)度越高，直徑越短，鏈路數(shù)越多。 靜態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò)4鏈接鏈接：鏈接又稱(chēng)為全連接。它是帶弦環(huán)的一種特殊情形。鏈接中的每個(gè)結(jié)點(diǎn)和其它結(jié)點(diǎn)之間都有一條直接鏈路。下圖是8個(gè)結(jié)點(diǎn)的鏈接，有28條鏈路，直徑為1，度為 7，對(duì)稱(chēng)，等分寬度為16。鏈接的直徑最短，性能最好。但是它需要大量的鏈路，每個(gè)結(jié)點(diǎn)需要大量的網(wǎng)絡(luò)接口，這在實(shí)際中是很難實(shí)現(xiàn)的，成本也是很高的。 靜態(tài)互連網(wǎng)絡(luò)4靜態(tài)互連網(wǎng)絡(luò)5樹(shù)形和星形樹(shù)形和星形：一棵K層完全二叉樹(shù)有 個(gè)結(jié)點(diǎn)。最大結(jié)點(diǎn)度為3，直徑為 2(logN - 1) （即左邊任意一個(gè)葉子結(jié)點(diǎn)到右邊任意一個(gè)葉子結(jié)點(diǎn)），不對(duì)稱(chēng)，等分寬度為1。由于結(jié)點(diǎn)度為常數(shù)，所以樹(shù)是一種可擴(kuò)展的系統(tǒng)

39、結(jié)構(gòu)。 星形實(shí)際上是二層樹(shù)。星形如下圖（a）所示，它等價(jià)于（b）中的二層樹(shù)。由N個(gè)結(jié)點(diǎn)構(gòu)成的星形網(wǎng)絡(luò)中，包含N-1條鏈路，直徑為2。根結(jié)點(diǎn)的度為N-1，葉子結(jié)點(diǎn)的度為1，不對(duì)稱(chēng)。 靜態(tài)互連網(wǎng)絡(luò)5靜態(tài)互連網(wǎng)絡(luò)5靜態(tài)互連網(wǎng)絡(luò)5為了彌補(bǔ)其不足，樹(shù)形結(jié)構(gòu)有許多變形結(jié)構(gòu)，例如帶環(huán)樹(shù)帶環(huán)樹(shù)和胖樹(shù)胖樹(shù)。帶環(huán)樹(shù)是在樹(shù)結(jié)構(gòu)的基礎(chǔ)上，將同級(jí)的兄弟結(jié)點(diǎn)環(huán)狀連接起來(lái)。這種結(jié)構(gòu)對(duì)樹(shù)結(jié)構(gòu)的改進(jìn)之處在于減小了網(wǎng)絡(luò)直徑。 傳統(tǒng)二叉樹(shù)的另一個(gè)問(wèn)題是根部容易成為通信瓶頸。這是因?yàn)?，子結(jié)點(diǎn)之間若要通信，都必須通過(guò)父結(jié)點(diǎn)。這樣，越靠近根部的鏈路和結(jié)點(diǎn)通信量就越大。1985年Leiserson提出將計(jì)算機(jī)科學(xué)中所用的一般樹(shù)結(jié)構(gòu)修改為胖

40、樹(shù)形（fat tree）。二叉胖樹(shù)結(jié)構(gòu)如下圖所示： 靜態(tài)互連網(wǎng)絡(luò)5靜態(tài)互連網(wǎng)絡(luò)6網(wǎng)（網(wǎng)（Mesh）:網(wǎng)又稱(chēng)為網(wǎng)格。在一個(gè) 的二維網(wǎng)格中，有N個(gè)結(jié)點(diǎn)和2(N- ) 條鏈路。每個(gè)結(jié)點(diǎn)只與其上、下、左、右的近鄰結(jié)點(diǎn)相連（邊界結(jié)點(diǎn)除外）。二維網(wǎng)格中，結(jié)點(diǎn)度為4，直徑為 ，等分寬度為 。 NNN) 1( 2NN靜態(tài)互連網(wǎng)絡(luò)6一般地，在結(jié)點(diǎn)數(shù)為 的k維網(wǎng)中，內(nèi)部結(jié)點(diǎn)度為2k（每一維上有兩個(gè)鄰居），網(wǎng)絡(luò)直徑為k(n-1)。 網(wǎng)也有多種變形，比如illiac網(wǎng)和環(huán)繞網(wǎng)格。如果把一個(gè)網(wǎng)格在各維上都環(huán)繞連接起來(lái)，就構(gòu)成環(huán)繞網(wǎng)格。下圖是一種二維環(huán)繞網(wǎng)格（2D-Torus）。 一般說(shuō)來(lái)， 的環(huán)繞網(wǎng)格有2N條鏈路，直徑

41、為 ，結(jié)點(diǎn)度為4，對(duì)稱(chēng)。所有附加的回繞連接使直徑較純網(wǎng)減少一半。如果把一個(gè)二維網(wǎng)在一維上環(huán)繞連接，另一維上蛇形連接，就構(gòu)成Illiac網(wǎng)。一般說(shuō)來(lái)，一個(gè) 的Illiac網(wǎng)有2N條鏈路，直徑為 ，僅為純網(wǎng)的直徑的一半。結(jié)點(diǎn)度為4。 NN 2/2NNN 1N靜態(tài)互連網(wǎng)絡(luò)6靜態(tài)互連網(wǎng)絡(luò)7搏動(dòng)式陣列（Systolic Array）:搏動(dòng)式陣列是一類(lèi)為實(shí)現(xiàn)特定的算法而設(shè)計(jì)的多維流水線陣列結(jié)構(gòu)。下圖是完成矩陣-矩陣相乘而專(zhuān)門(mén)設(shè)計(jì)的搏動(dòng)式陣列，其內(nèi)部結(jié)點(diǎn)度為6。 靜態(tài)互連網(wǎng)絡(luò)7一般地，靜態(tài)搏動(dòng)式陣列可在多個(gè)方向上使數(shù)據(jù)流變成以流水線方式工作。商用Intel iWarp系統(tǒng)就是用搏動(dòng)式結(jié)構(gòu)設(shè)計(jì)的。自從1978

42、年Kung和Leiserson提出搏動(dòng)式陣列后，它已成為廣泛研究的領(lǐng)域。通過(guò)確定的互連和同步操作，搏動(dòng)式陣列可與算法的通信結(jié)構(gòu)相匹配。對(duì)信號(hào)/圖象處理等特殊應(yīng)用，搏動(dòng)式陣列可提供更好的性能/價(jià)格比。但是，其結(jié)構(gòu)的實(shí)用性有限，而且編制程序也很難。 靜態(tài)互連網(wǎng)絡(luò)8超立方體：一個(gè) n-立方體由 個(gè)結(jié)點(diǎn)組成，它們分布在n維上，每維有兩個(gè)結(jié)點(diǎn)。0-立方體、1-立方體、2-立方體、3-立方體如下圖所示。一般地，n-立方體可以通過(guò)兩個(gè)(n-1)-立方體互連得到。例如，4-立方體可以用兩個(gè)3-立方體互連得到。 靜態(tài)互連網(wǎng)絡(luò)8一個(gè)n-立方體的結(jié)點(diǎn)度為n，網(wǎng)絡(luò)直徑也是n，對(duì)分寬度為N/2，對(duì)稱(chēng)。在80年代并行系統(tǒng)

43、的研究開(kāi)發(fā)工作中，超立方體是一種極為普遍采用的結(jié)構(gòu)。 Intel iPSC/1、iPSC/2和nCUBE機(jī)等并行機(jī)都采用了超立方體結(jié)構(gòu)。許多并行算法也是針對(duì)超立方體結(jié)構(gòu)設(shè)計(jì)的。這種結(jié)構(gòu)的連接比較密集。它的一個(gè)特點(diǎn)是，許多其它結(jié)構(gòu)諸如二叉樹(shù)，網(wǎng)格和許多其它低維網(wǎng)絡(luò)都能嵌入到超立方體中去。因此超立方體結(jié)構(gòu)有很大的理論價(jià)值。但是超立方體結(jié)構(gòu)也有很大的缺陷。它的結(jié)點(diǎn)度隨維數(shù)線性增加，所以超立方體不是一種可擴(kuò)展的結(jié)構(gòu)。由于超立方體缺乏可擴(kuò)展性以及難于組成高維的超立方體，所以超立方體結(jié)構(gòu)正逐漸被淘汰。例如，CM-5選用了勝過(guò)CM-2超立方體的胖樹(shù)結(jié)構(gòu)。Intel Paragon選用了較其前身超立方體更好的

44、2維網(wǎng)格結(jié)構(gòu)。 靜態(tài)互連網(wǎng)絡(luò)9帶環(huán)立方體帶環(huán)立方體：這種結(jié)構(gòu)是從超立方體改進(jìn)而來(lái)的，主要是為了解決超立方體不可擴(kuò)展的問(wèn)題。將一個(gè)n-立方體的每個(gè)結(jié)點(diǎn)用n個(gè)結(jié)點(diǎn)組成的環(huán)代替，就構(gòu)成了帶環(huán)n-立方體。因此，一個(gè)n-立方體由 個(gè)結(jié)點(diǎn)環(huán)構(gòu)成，每個(gè)結(jié)點(diǎn)環(huán)是n個(gè)結(jié)點(diǎn)構(gòu)成的環(huán)。所以結(jié)點(diǎn)總數(shù)為 個(gè)，直徑為 2n-1+| n/2 | ，對(duì)稱(chēng)。特別地，帶環(huán)立方體的結(jié)點(diǎn)度為3，與超立方體的維數(shù)無(wú)關(guān)。 靜態(tài)互連網(wǎng)絡(luò)9靜態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò)小結(jié)靜態(tài)互連網(wǎng)絡(luò)小結(jié)：下表列出了各種靜態(tài)互連網(wǎng)絡(luò)的特性。大多數(shù)網(wǎng)絡(luò)的結(jié)點(diǎn)度都小于4，這是比較理想的。全連接網(wǎng)絡(luò)和星形網(wǎng)絡(luò)的結(jié)點(diǎn)度比較高。超立方體的結(jié)點(diǎn)度隨 著 值增大而增大，當(dāng)N值

45、很大時(shí)，其結(jié)點(diǎn)度也很高。網(wǎng)絡(luò)直徑的變化范圍很大。但是，隨著硬件尋徑技術(shù)的發(fā)展（例如蟲(chóng)蝕尋徑技術(shù)的出現(xiàn)），源結(jié)點(diǎn)和目的結(jié)點(diǎn)之間的距離已經(jīng)不是影響通信延遲的主要因素。在使用了類(lèi)似于流水線操作的技術(shù)后（例如蟲(chóng)蝕尋徑），任意兩結(jié)點(diǎn)間的通信延遲幾乎是相同的。鏈路數(shù)決定了實(shí)際使用的物理線路的數(shù)量，從而會(huì)影響網(wǎng)絡(luò)的價(jià)格。 網(wǎng)絡(luò)的價(jià)格隨結(jié)點(diǎn)度和鏈路數(shù)的增大而上升。等分寬度會(huì)影響網(wǎng)絡(luò)的帶寬。對(duì)稱(chēng)性會(huì)影響可擴(kuò)展性和尋徑效率。直徑可以體現(xiàn)出兩結(jié)點(diǎn)之間距離的上限，但是結(jié)點(diǎn)之 間的平均距離可能能夠更好地反映任意兩結(jié)點(diǎn)之間的距離。網(wǎng)絡(luò)名稱(chēng)網(wǎng)絡(luò)名稱(chēng)網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)規(guī)模節(jié)點(diǎn)度節(jié)點(diǎn)度網(wǎng)絡(luò)直徑網(wǎng)絡(luò)直徑對(duì)剖寬度對(duì)剖寬度對(duì)稱(chēng)對(duì)稱(chēng)鏈路數(shù)鏈

46、路數(shù)線性陣列線性陣列21非非環(huán)形環(huán)形2 （雙向）（雙向）2是是2-D網(wǎng)孔網(wǎng)孔 4非非Illiac網(wǎng)孔網(wǎng)孔 4非非2-D環(huán)繞環(huán)繞4是是二叉樹(shù)二叉樹(shù)31非非星形星形2非非超立方超立方 n n是是立方環(huán)立方環(huán)3是是NNNNNN NN NN nN2kkN21N1N2/N) 1(2N1N2/2N1log2N2/12kkNN2N22/N2/N)2/(kN1NN)(2NN N2N21N1N2/nN2/3N靜態(tài)互連網(wǎng)絡(luò)動(dòng)態(tài)互連網(wǎng)絡(luò) 動(dòng)態(tài)網(wǎng)絡(luò)中的連接不固定，在程序執(zhí)行過(guò)程中可以改變。動(dòng)態(tài)網(wǎng)絡(luò)中設(shè)置有電子開(kāi)關(guān)、路由器、集中器、分配器、仲裁器等部件?？梢韵蜻@些開(kāi)關(guān)發(fā)送控制信號(hào)來(lái)設(shè)置這些設(shè)備的狀態(tài)，從而改變網(wǎng)絡(luò)的連接

47、狀態(tài)。動(dòng)態(tài)網(wǎng)絡(luò)主要有總線、交叉開(kāi)關(guān)和多級(jí)互連網(wǎng)絡(luò)。 動(dòng)態(tài)互連網(wǎng)絡(luò)1總線總線：總線（Bus）實(shí)際上是連接處理器、存儲(chǔ)器和I/O等外圍設(shè)備的一組導(dǎo)線和插座?？偩€的一個(gè)特點(diǎn)是：它在某一時(shí)刻只能用于一對(duì)源和目的之間傳輸數(shù)據(jù)。當(dāng)有多對(duì)源和目的請(qǐng)求使用總線時(shí)，必須由總線仲裁邏輯進(jìn)行總線仲裁，即確定先為哪一對(duì)源和目的服務(wù)?？偩€與其它兩種動(dòng)態(tài)網(wǎng)絡(luò)相比，價(jià)格較低，帶寬較窄。目前已有很多總線標(biāo)準(zhǔn)，如PCI、VME、Multibus、Sbus、MicroChannel和IEEE Futurebus。在構(gòu)造并行系統(tǒng)時(shí)，常使用多處理器總線。下圖給出了的典型的多處理器總線結(jié)構(gòu)。 動(dòng)態(tài)互連網(wǎng)絡(luò)1動(dòng)態(tài)互連網(wǎng)絡(luò)1上圖中包括板級(jí)

48、總線、底板級(jí)總線和I/O總線。在印刷電路板上實(shí)現(xiàn)的總線稱(chēng)為局部總線局部總線或本地總線本地總線（Local Bus），存儲(chǔ)器板級(jí)上的總線稱(chēng)為存儲(chǔ)器總線存儲(chǔ)器總線，I/O板級(jí)和通信板級(jí)上的總線稱(chēng)為數(shù)據(jù)總線數(shù)據(jù)總線。局部總線布設(shè)在CPU、I/O和網(wǎng)絡(luò)接口板上，起到將局部設(shè)備相連的作用。系統(tǒng)總線系統(tǒng)總線是 在底板上實(shí)現(xiàn)的，它為所有插在底板上的插入板提供通信通路。各插入板中均設(shè)有專(zhuān)用邏輯接口（IF）和專(zhuān)用控制器（C），包括I/O控制器、存儲(chǔ)控制器和通 信控制器。I/O設(shè)備通過(guò)I/O總線與計(jì)算機(jī)系統(tǒng)相連。P表示處理器，M表示局部存儲(chǔ)器，CA表示高速緩存，IOP表示I/O處理器。 動(dòng)態(tài)互連網(wǎng)絡(luò)1設(shè)計(jì)多處理器

49、總線的重要問(wèn)題包括：總線仲裁，中斷處理，協(xié)議轉(zhuǎn)換，快速同步，Cache一致性等?？偩€與線性陣列是不同的。線性陣列允許不同的源和目的結(jié)點(diǎn)對(duì)并發(fā)使用系統(tǒng)的不同部分。總線在某一時(shí)刻只允許一對(duì)源和目的結(jié)點(diǎn)通信。總線是通過(guò)切換與其連接的許多結(jié)點(diǎn)來(lái)實(shí)現(xiàn)時(shí)分特性的。 動(dòng)態(tài)互連網(wǎng)絡(luò)2交叉開(kāi)關(guān)交叉開(kāi)關(guān)：交叉開(kāi)關(guān)（Crossbar Switcher）是一種高帶寬網(wǎng)絡(luò)，它可以在輸入端和輸出端之間建立動(dòng)態(tài)連接，其結(jié)構(gòu)如下圖所示。 在每個(gè)輸入端和輸出端的交叉點(diǎn)上都有交叉點(diǎn)開(kāi)關(guān)交叉點(diǎn)開(kāi)關(guān)。該開(kāi)關(guān)可以根據(jù)需要置為開(kāi)或關(guān)狀態(tài)，從而使不同的輸入端和輸出端導(dǎo)通。nn交叉開(kāi)關(guān)允許n對(duì)源和目的同時(shí)用互不重疊的通道進(jìn)行通信，也允許一個(gè)

50、輸入端向多個(gè)輸出端同時(shí)發(fā)送信息。在并行系統(tǒng)中，交叉開(kāi)關(guān)可以用來(lái)連接處理器和處理器，也可以用來(lái)連接處理器和存儲(chǔ)器。 動(dòng)態(tài)互連網(wǎng)絡(luò)2動(dòng)態(tài)互連網(wǎng)絡(luò)3多級(jí)互連網(wǎng)絡(luò)多級(jí)互連網(wǎng)絡(luò)：為了構(gòu)造大型網(wǎng)絡(luò)，可以把交叉開(kāi)關(guān)級(jí)聯(lián)起來(lái)，構(gòu)成多級(jí)互連網(wǎng)絡(luò)（Multistage Interconnection Network, MIN）。下圖是一種一般的多級(jí)互連網(wǎng)絡(luò)的構(gòu)造方式。每一級(jí)都用了多個(gè)ab開(kāi)關(guān)，相鄰的各級(jí)開(kāi)關(guān)之間是固定的級(jí)間連接（ISC）。通過(guò)設(shè)置交叉開(kāi)關(guān)的狀態(tài)就可以建立所需要的輸入和輸出之間的連接。 動(dòng)態(tài)互連網(wǎng)絡(luò)3動(dòng)態(tài)互連網(wǎng)絡(luò)3各種多級(jí)網(wǎng)絡(luò)的區(qū)別就在于所用的交叉開(kāi)關(guān)、控制方式和級(jí)間連接模式不同?？刂品绞娇刂品绞绞?/p>

51、指對(duì)各個(gè)交叉開(kāi)關(guān)進(jìn)行控制的方式，它有3種：級(jí)控制，單元控制和部分級(jí)控制。級(jí)控制級(jí)控制是指每一級(jí)的所有開(kāi)關(guān)用一個(gè)控制信號(hào)控制，從而同一級(jí)的所有開(kāi)關(guān)只能處于同一種狀態(tài)；單元控制單元控制是指每一個(gè)開(kāi)關(guān)都有獨(dú)立的控制信號(hào)來(lái)控制，從而所有的開(kāi)關(guān)可以處于不同的狀態(tài)；部分級(jí)控制部分級(jí)控制介于前兩種控制方式之間，它是指幾個(gè)開(kāi)關(guān)合用一個(gè)控制信號(hào)。常用的級(jí)間連接模式有均勻洗牌、蝶式、多路洗牌（比如四路洗牌就是把輸入端平均分為4份，然后對(duì)這4份分別進(jìn)行均勻洗牌）、縱橫交叉、立方體連接等。 動(dòng)態(tài)互連網(wǎng)絡(luò)3 網(wǎng)絡(luò)網(wǎng)絡(luò)（即Omega網(wǎng)絡(luò)）是一種著名的多級(jí)互連網(wǎng)絡(luò)。伊利諾依大學(xué)的Cedar多處理機(jī)、IBM的RP3和紐約大學(xué)

52、的Ultracomputer都使用了 網(wǎng)絡(luò)。 網(wǎng)絡(luò)級(jí)間連接采用均勻洗牌。下圖是使用22交叉開(kāi)關(guān)和均勻洗牌構(gòu)成的88 網(wǎng)絡(luò)。動(dòng)態(tài)互連網(wǎng)絡(luò)3動(dòng)態(tài)互連網(wǎng)絡(luò)3每個(gè)交叉開(kāi)關(guān)有直送、交叉、上播、下播四種連接方式，如下圖所示。通過(guò)切換各個(gè)交叉開(kāi)關(guān)的狀態(tài)就可以改變 的連接狀態(tài)，實(shí)現(xiàn)一對(duì)一的連接和廣播等多種功能。 動(dòng)態(tài)互聯(lián)網(wǎng)絡(luò)3一般地，用22交叉開(kāi)關(guān)構(gòu)造的n個(gè)輸入端的 網(wǎng)絡(luò)有 級(jí)，每一級(jí)有n/2個(gè)交叉開(kāi)關(guān),采用單元控制。如果將輸入端和輸出端從上到下依次用二進(jìn)制編號(hào)（最上的輸入端和輸出端編號(hào)為0），將各級(jí)從輸入級(jí)到輸出級(jí)依次編號(hào)為0到 -1，則可以通過(guò)檢查地址編號(hào)來(lái)尋徑：當(dāng)目的地址編號(hào)從高位開(kāi)始的第i位為0時(shí)，第

53、i級(jí)的22開(kāi)關(guān)的輸入端與上輸入端連接，否則與下輸出端連接。也可以使用其它規(guī)格的交叉開(kāi)關(guān)構(gòu)造 網(wǎng)絡(luò)，此時(shí)級(jí)間連接方式也要相應(yīng)地改變。下圖是使用44交叉開(kāi)關(guān)構(gòu)造的 網(wǎng)絡(luò)，級(jí)間連接方式為4路洗牌。4路洗牌相當(dāng)于把16個(gè)輸入端均勻分成4個(gè)子組，然后對(duì)這4個(gè)子組均勻洗牌。 動(dòng)態(tài)互聯(lián)網(wǎng)絡(luò)3動(dòng)態(tài)互聯(lián)網(wǎng)絡(luò)動(dòng)態(tài)互連網(wǎng)絡(luò)小結(jié)動(dòng)態(tài)互連網(wǎng)絡(luò)小結(jié)：總線容易產(chǎn)生故障。為了減小故障的影響，可以采用雙總線結(jié)構(gòu)。交叉開(kāi)關(guān)的硬件復(fù)雜性為n2數(shù)量級(jí)，造價(jià)昂貴。但是其帶寬和尋徑性能在這三種動(dòng)態(tài)網(wǎng)絡(luò)中最好。如果網(wǎng)絡(luò)規(guī)模小，它是一種理想的選擇。多級(jí)互連網(wǎng)絡(luò)是二者的折衷。它的主要優(yōu)點(diǎn)在于采用模塊結(jié)構(gòu)，可擴(kuò)展性好。 標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò)1Myrin

54、et Myrinet是Myricom公司研制的一種高帶寬低延遲的互連網(wǎng)絡(luò)。由于它使用了多項(xiàng)大規(guī)模并行處理機(jī)（MPP）中的技術(shù),使得它有很高的帶寬。它的物理鏈路的速度單向可以達(dá)到1.28Gb/s，雙向總帶寬可達(dá)到2.56Gb/s。雖然這只是最底層的物理鏈路的帶寬，但即使考慮到上層軟件的開(kāi)銷(xiāo)會(huì)對(duì)性能有一定的影響，其性能仍是很高的。Myrinet網(wǎng)絡(luò)包括一系列多端口交換開(kāi)關(guān)組成。每個(gè)交換開(kāi)關(guān)可與計(jì)算機(jī)或其它交換開(kāi)關(guān)相連。Myrinet可以構(gòu)成任意拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)。Myrinet的交換開(kāi)關(guān)內(nèi)部使用流水線機(jī)制，支持蟲(chóng)蝕尋徑。Myrinet網(wǎng)絡(luò)與計(jì)算機(jī)的接口是一個(gè)32位的用戶定制的VLSI處理器，稱(chēng)作LAN

55、ai芯片，帶有Myrinet接口、報(bào)文接口、DMA引擎和快速靜態(tài)RAM。RAM用來(lái)存儲(chǔ)Myrinet控制程序（MCP）并用作報(bào)文緩存。MCP在接口的處理器上運(yùn)行。這避免了操作系統(tǒng)的開(kāi)銷(xiāo)。目前Myrinet大量被用來(lái)構(gòu)造機(jī)群系統(tǒng)（COW）。Myrinet連接的LAN/Cluster交換開(kāi)關(guān)交換開(kāi)關(guān)交換開(kāi)關(guān)交換開(kāi)關(guān)桌面主機(jī)機(jī)箱內(nèi)多計(jì)算機(jī)機(jī)群多處理機(jī)機(jī)群網(wǎng)絡(luò)RAM和VME 單板磁盤(pán)Myrinet2000Product seriesMyrinet-2000Myri-10GFull-duplex data rate for the links, NIC ports, and switch ports2+

56、2Gigabits/s10+10Gigabits/sLink cablesLC-connectorized duplex multimode fiber to 200mSelected 10-Gigabit Ethernet cables, copper and fiberNICsSingle-port and dual-port PCI-XSingle-port PCI-Express, dual-protocol 10G Myrinet or 10G EthernetSwitchesBased on 16-port and 32-port crossbar switchesBased on

57、 16-port crossbar switchesSwitch networksUp to 256 host ports with a single Network in a Box component, and up to tens of thousands of hosts by combining these componentsUp to 128 host ports with a single Network in a Box component, and up to tens of thousands of hosts by combining these componentsI

58、nteroperabilityGigabit Ethernet10-Gigabit EthernetMyrinet software supportMyrinet Express (MX-2G) or GM-2Myrinet Express (MX-10G)MX or MPI latency2.6s3.2s2sMX unidirectional data rate247 MBytes/s (one-port NICs)495 MBytes/s (two-port NICs)1.2 GBytes/sTCP/IP (MX ethernet emulation) data rate1.98 Gbit

59、s/s (one-port NICs)3.95 Gbits/s (two-port NICs)9.6 Gbits/sInfiniBand 技術(shù)技術(shù) Infiniband是一個(gè)基于交換的串行I/O互連體系結(jié)構(gòu)，運(yùn)行速度為每方向2.5Gb/s或10Gb/s（每端口）。和共享總線結(jié)構(gòu)不同，InfiniBand是一個(gè)針數(shù)很少的串行結(jié)構(gòu)，可連接印刷電路板（PCB Printed circuit board）上的設(shè)備，并支持箱外帶寬。使用普通的雙絞銅線，InfiniBand支持的連接距離為17m；而如果使用光纜，其支持的距離則可達(dá)數(shù)公里甚至更遠(yuǎn)。InfiniBand支持QoS和RAS。InfiniBand

60、系統(tǒng)網(wǎng)絡(luò)受到各大工業(yè)公司的支持，其中包括了所有主要服務(wù)器廠商，如：戴爾，惠普，IBM，英特爾，微軟和Sun等公司。 InfiniBand 技術(shù)技術(shù) InfiniBand的特性包括： 分層的協(xié)議：物理、鏈路、網(wǎng)絡(luò)、傳輸和上層協(xié)議 基于包的通訊方式 三種鏈路速度 1X 2.5Gb/s 4線 4X 10Gb/s 16線 12X 30Gb/s 48線 支持PCB, 銅纜和光纖線纜連接 子網(wǎng)管理協(xié)議 支持遠(yuǎn)程DMA 支持組播和點(diǎn)播 可靠傳輸方式：消息隊(duì)列 通訊流控：鏈路級(jí)和端到端方式InfiniBand 技術(shù)技術(shù)InfiniBand的體系結(jié)構(gòu)被分為多層，每層完成各自獨(dú)立的操作。InfiniBand有物理