第2講-并行計算機系統(tǒng)及其結(jié)構(gòu)模型

1計算機學(xué)院計算機科學(xué)與技術(shù)系主講：陳蕾博士/副教授E-mail:chenlei@第二講并行計算機系統(tǒng)及其結(jié)構(gòu)模型2并行計算的研究內(nèi)容IssuesinParallelComputing

并行計算的研究內(nèi)容廣泛，包括并行計算機系統(tǒng)結(jié)構(gòu)、并行算法設(shè)計、并行編程環(huán)境等，具體表現(xiàn)在下面幾個方面：（1）并行計算機的設(shè)計

DesignofParallelComputers包括并行計算機的結(jié)構(gòu)設(shè)計、互聯(lián)拓撲、網(wǎng)絡(luò)通信等。設(shè)計并行計算機重要的一點要考慮處理機數(shù)目的按比例增長（即可擴展性）及支持快速通信及處理機間的數(shù)據(jù)共享等。3(2)有效算法的設(shè)計

DesignofEfficientAlgorithms如果沒有有效的并行算法，并行計算機無法使用，而并行算法的設(shè)計完全不同于串行算法的設(shè)計，不同的并行計算機的算法設(shè)計不同，只有將不同的并行計算機與不同的實際問題相結(jié)合，才能設(shè)計出有效的并行算法。主要研究內(nèi)容包括并行計算模型、并行算法的一般設(shè)計方法、基本設(shè)計技術(shù)和一般設(shè)計過程，并討論一些數(shù)值并行算法與非數(shù)值并行算法的設(shè)計。4(3)評價并行算法的方法

MethodsforEvaluatingParallelAlgorithms

對于給定的并行計算機及運行在上面的并行算法，需要評價運行性能。性能分析需解決的問題：如何利用基于并行計算機及其相適應(yīng)的并行算法去快速地解決問題，及如何有效地利用各個處理器。研究內(nèi)容包括結(jié)合機器與算法，提出相應(yīng)的性能評測指標，為設(shè)計高效的并行算法提供依據(jù)。5(4)并行計算機語言

ParallelComputingLanguage

與傳統(tǒng)的機器語言不同，并行計算機語言依賴于并行計算機，并行計算機語言必須簡潔，編程容易，可以有效地實現(xiàn)，目前的語言有：PVM（ParallelVirtualMachine）、MPI(MessagePassingInterface)、HPF(HighPerformanceFortran)等，而且新的編程語言與編程模式正在不斷地出現(xiàn)。6(5)并行編程環(huán)境與工具

ParallelProgrammingEnvironmentsandTools為了使編程容易，必須開發(fā)綜合的編程環(huán)境與工具，且能達到兩個目的：并行計算機的底層結(jié)構(gòu)對用戶透明；為用戶提供設(shè)計與開發(fā)程序所需要的調(diào)試器與模擬器等工具7(6)并行程序的可移植性

PortableParallelPrograms可移植性為并行程序設(shè)計的主要問題，要求在一臺并行機上開發(fā)的程序不加修改或進行少量修改即可在另一臺計算機上運行。這一點為目前受到了廣泛關(guān)注的重要課題。8(7)并行計算機的自動編程

AutomaticProgrammingofParallelComputers

可否設(shè)計一個并行化編譯器，使用戶的串行程序通過并行化編譯器編譯，直接可在并行機上運行。到目前為此，這種編譯器還不存在，而僅有一些半自動并行化編譯器。9并行計算機分類

對并行計算機的分類有多種方法，其中最著名的是1966年由M.J.Flynn提出的分類法，稱為Flynn分類法。Flynn分類法是從計算機的運行機制進行分類的。首先作如下定義：

指令流（instructionstream）：機器執(zhí)行的指令序列；

數(shù)據(jù)流（datastream）：由指令流調(diào)用的數(shù)據(jù)序列，包括輸入數(shù)據(jù)和中間結(jié)果。

10Flynn根據(jù)指令流和數(shù)據(jù)流的不同組織方式，把計算機系統(tǒng)的結(jié)構(gòu)分為以下四類：

（1）單指令流單數(shù)據(jù)流（SingleInstructionstreamSingleDatastream,SISD）；

（2）單指令流多數(shù)據(jù)流（SingleInstructionstreamMultipleDatastream,SIMD）；

（3）多指令流單數(shù)據(jù)流（MultipleInstructionstreamSingleDatastream,MISD）；

（4）多指令流多數(shù)據(jù)流（MultipleInstructionstreamMultipleDatastream,MIMD）。SISD就是普通的順序處理的串行機。SIMD和MIMD是典型的并行計算機。MISD在實際中代表何種計算機，也存在不同的看法，甚至有學(xué)者認為根本不存在MISD。

11單指令流多數(shù)據(jù)流機SIMD

在一臺SIMD計算機中，有一個控制部件（又稱為控制單元，controlunit）和許多處理單元（processingunit）。大量的處理單元通常構(gòu)成陣列，因此SIMD計算機有時也稱為陣列處理機。所有的處理單元在控制部件的統(tǒng)一控制下工作?？刂撇考蛩械奶幚韱卧獜V播同一條指令，所有的處理單元同時執(zhí)行這條指令，但是每個處理單元操作的數(shù)據(jù)不同?？刂撇考梢杂羞x擇地屏蔽掉一些處理單元，被屏蔽掉的處理單元不執(zhí)行控制部件廣播的指令。12SIMD計算機其結(jié)構(gòu)如下圖所示，其中PE表示處理單元，P表示處理器，M表示存儲器。

SIMD中通常包含大量處理單元PE，而控制部件只有一個?？刂撇考V播一條指令，所有的處理單元同時執(zhí)行這條指令，但不同的處理單元操作的數(shù)據(jù)可能不同。

13典型的SIMD計算機-MasParMP-1可有1024，4096，…，16384個處理器。在16k個處理器，32位整數(shù)運算，16kB局部存儲器模塊的配置下，1.5GFlops.單指令流多數(shù)據(jù)流機SIMD

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

多指令流多數(shù)據(jù)流機MIMD多指令流多數(shù)據(jù)流機MIMD一般可以分為5類：

1、并行向量處理機PVP（ParallelVectorProcessor）

2、對稱多處理機SMP（SymmetricMultiprocessor）

3、大規(guī)模并行處理機MPP（MassivelyParallelProcessor）

4、工作站機群COW（ClusterOfWorkstations，也稱為NetworkOfWorkstations，NOW）

5、分布式共享存儲多處理機DSM（DistributedSharedMemory）。

16并行向量處理機PVP在并行向量處理機中有少量專門定制的向量處理器。每個向量處理器有很高的處理能力。并行向量處理機通過向量處理和多個向量處理器并行處理兩條途徑來提高處理能力。CrayC-90、CrayT-90、NECSX-4和我國的銀河1號都是PVP。PVP通常使用定制的高帶寬網(wǎng)絡(luò)將向量處理器連向共享存儲器模塊。存儲器可以以很高的速度向處理器提供數(shù)據(jù)。例如，在CrayT-90中，共享存儲器能以14GB/s的速率將數(shù)據(jù)提供給一個處理器。這種機器通常不使用高速緩存，而是使用大量的向量寄存器和指令緩沖器。17并行向量處理機其系統(tǒng)結(jié)構(gòu)如下圖所示。圖中VP表示向量處理器，SM表示共享存儲器。

18對稱多處理機SMP對稱多處理機的最大特點是其中的各處理器完全平等，無主從之分。所有的處理器都可以訪問任何存儲單元和I/O設(shè)備。存儲器一般使用共享存儲器，只有一個地址空間。因為使用共享存儲器，通信可用共享變量（讀寫同一內(nèi)存單元）來實現(xiàn)。這使得編程很容易。對稱多處理機（SymmetricMultiprocessor,SMP）結(jié)構(gòu)在現(xiàn)今的并行服務(wù)器中普遍采用。它是應(yīng)用得最廣泛的并行計算機，例如曙光1號、HP9000/T600、IBMRS6000/R40、SGIPowerChallengeXL、SUNUltraEnterprise6000等。采用商用微處理器，通常有片上和外置Cache，基于總線或交叉開關(guān)連接，集中式共享存儲

19SMP的結(jié)構(gòu)如下圖所示。P/C表示處理器和高速緩存，SM表示共享存儲器。20對稱多處理機SMP優(yōu)點對稱性單地址空間，易編程，動態(tài)負載平衡，無需顯式數(shù)據(jù)分配高速緩存及其一致性，硬件維持一致性低通信延遲問題所有的處理器都可以訪問存儲器和I/O設(shè)備，使得存儲器和I/O設(shè)備的負載很大，容易成為系統(tǒng)的瓶頸，這限制了系統(tǒng)中處理器的數(shù)量。可用性：總線、存儲器、操作系統(tǒng)中有一個失效就會導(dǎo)致整個系統(tǒng)的崩潰，系統(tǒng)不夠可靠和穩(wěn)定。不可擴放性：總線和交叉開關(guān)一旦做成就難以擴展。21

大規(guī)模并行處理機（MPP）大規(guī)模并行處理機（MassivelyParallelProcessor,MPP）是指由幾百或幾千臺處理機組成的大規(guī)模并行計算機系統(tǒng)。Intel和美國Sandia國家實驗室1997年6月研制成功的MPP系統(tǒng)ASCIOptionRed有9216個處理器。MPP系統(tǒng)中處理器數(shù)目巨大，整個系統(tǒng)規(guī)模龐大，許多硬件設(shè)備是專門設(shè)計制造的，開發(fā)起來比較困難，通常被視為國家綜合實力的象征。同時，MPP能夠提供其它并行計算機不能達到的計算能力。達到3T性能目標和解決重大挑戰(zhàn)性課題都寄希望于MPP。大規(guī)模并行處理機一般指規(guī)模非常大的并行計算機系統(tǒng)，含有成千上萬個處理器。它一般采用分布式存儲器，存儲器一般為處理器私有，各處理器之間用消息傳遞的方式通信。大規(guī)模并行處理機的互連網(wǎng)絡(luò)一般是專門設(shè)計定制的。典型的MPP有IntelParagon、IBMSP2以及OptionRed、曙光1000等。

22處理節(jié)點采用商用微處理器專門設(shè)計制造的高速互連網(wǎng)絡(luò)每個節(jié)點內(nèi)有一個或多個處理器、高速緩存、一個本地存儲器和本地互連網(wǎng)絡(luò)，有的MPP系統(tǒng)節(jié)點內(nèi)還有磁盤存儲器在物理上是分布的，而且都是私有的程序由多個進程組成，每個都有其私有空間，進程間采用消息傳遞相互作用

大規(guī)模并行處理機（MPP）23典型MPP系統(tǒng)特性比較MPP模型Intel/SandiaASCIOptionRedIBMSP2SGI/CrayOrigin2000一個大型樣機的配置9072個處理器，1.8Tflop/s(NSL)400個處理器，100Gflop/s(MHPCC)128個處理器，51Gflop/s(NCSA)問世日期1996年12月1994年9月1996年10月處理器類型200MHz,200Mflop/sPentiumPro67MHz，267Mflop/sPOWER2200MHz，400Mflop/sMIPSR10000節(jié)點體系結(jié)構(gòu)和數(shù)據(jù)存儲器2個處理器，32到256MB主存，共享磁盤1個處理器，64MB到2GB本地主存，1GB到14.5GB本地磁盤2個處理器，64MB到256MB分布共享主存和共享磁盤互連網(wǎng)絡(luò)和主存模型分離兩維網(wǎng)孔，NORMA多級網(wǎng)絡(luò)，NORMA胖超立方體網(wǎng)絡(luò)，CC-NUMA節(jié)點操作系統(tǒng)輕量級內(nèi)核（LWK）完全AIX（IBMUNIX）微內(nèi)核CellularIRIX自然編程機制基于PUMAPortals的MPIMPI和PVMPowerC，PowerFortran其他編程模型Nx，PVM，HPFHPF，LindaMPI，PVM24MPP所用的高性能CPU特性比較屬性PentiumProPowerPC602Alpha21164AUltraSPARCIIMIPSR10000工藝BiCMOSCMOSCMOSCMOSCMOS晶體管數(shù)5.5M/15.5M7M9.6M5.4M6.8M時鐘頻率150MHz133MHz417MHz200MHz200MHz電壓2.9V3.3V2.2V2.5V3.3V功率20W30W20W28W30W字長32位64位64位64位64位I/O高速緩存8KB/8KB32KB/32KB8KB/8KB16KB/16KB32KB/32KB2級高速緩存256KB(多芯片模塊)1~128MB(片外)96KB(片上)16MB(片外)16MB(片外)執(zhí)行單元5個單元6個單元4個單元9個單元5個單元超標量3路(Way)4路4路4路4路流水線深度14級4~8級7~9級9級5~7級SPECint92366225>500350300SPECfp92283300>750550600SPECint958.09225>11N/A7.4SPECfp956.70300>17N/A15其它特性CISC/RISC混合短流水線長L1高速緩存最高時鐘頻率最大片上2級高速緩存多媒體和圖形指令MP機群總線可支持4個CPU25MPP的結(jié)構(gòu)如下圖所示。其中MB表示存儲器總線，P/C表示處理器和高速緩存，NIC表示網(wǎng)絡(luò)接口電路，LM表示本地存儲器。NIC是用來將計算機與網(wǎng)絡(luò)（例如局域網(wǎng)）連接起來的接口電路。它的功能有：將消息格式化、路由選擇、流和錯誤控制等。26分布式共享存儲器多處理機DSM分布式共享存儲器多處理機的主要特點是它的存儲器在物理上是分布在各個結(jié)點中的，但是通過硬件和軟件為用戶提供一個單一地址的編程空間，即形成一個虛擬的共享存儲器。DSM相對于MPP的優(yōu)越性是編程較容易。它通過高速緩存目錄支持分布高速緩存的一致性。DSM與SMP的區(qū)別在于各結(jié)點內(nèi)有存儲器，與MPP的區(qū)別在于存儲器在邏輯上是共享的。典型的DSM有StanfordDASH、SGI/CrayOrigin2000。27DSM的結(jié)構(gòu)如下圖所示，其中DIR表示高速緩存目錄，其它符號同前。

28工作站機群（COW）1994年,NASA兩位工程師構(gòu)建了第一個機群系統(tǒng):Beowulf16臺100MHz486微機10Mb/s以太網(wǎng)絡(luò)74Mflops1997年,UCBerkeleyNOW-2100臺SUN工作站Myrinet10Gflops首次進入Top500最新的Top500中，機群占81%29典型的機群系統(tǒng)結(jié)構(gòu)30工作站機群COW分布式存儲，MIMD，工作站+商用互連網(wǎng)絡(luò)，每個節(jié)點是一個完整的計算機，有自己的磁盤和操作系統(tǒng)，而MPP中只有微內(nèi)核優(yōu)點：投資風(fēng)險小系統(tǒng)結(jié)構(gòu)靈活性能/價格比高能充分利用分散的計算資源可擴放性好問題通信性能并行編程環(huán)境例子：BerkeleyNOW，AlphaFarm,FXCOWP/CMMIOMIOMP/CNICNICDDLAN31工作站機群

工作站機群是一種新興的并行系統(tǒng)。COW是由高檔商品微機（包括工作站）用高速商品互連網(wǎng)絡(luò)（有的商用機群也使用定制的網(wǎng)絡(luò)）連接而成。COW的每個結(jié)點都是一臺完整的計算機（可能沒有鼠標、顯示器等外設(shè)）。COW的每個結(jié)點上都有完整的操作系統(tǒng)，而MPP的每個結(jié)點上通常只有操作系統(tǒng)的微核。COW的每個結(jié)點內(nèi)有本地磁盤，而MPP的結(jié)點內(nèi)沒有。COW各結(jié)點的網(wǎng)絡(luò)接口是連接到I/O總線上的（松耦合），而MPP各結(jié)點的網(wǎng)絡(luò)接口是連接到存儲總線上的（緊耦合）。32COW的結(jié)構(gòu)如下圖所示，其中LD表示本地磁盤，B