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

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

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

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

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

MethodsforEvaluatingParallelAlgorithms

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

ParallelComputingLanguage

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

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

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

AutomaticProgrammingofParallelComputers

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

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

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

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

10Flynn根據(jù)指令流和數(shù)據(jù)流的不同組織方式，把計算機(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就是普通的順序處理的串行機(jī)。SIMD和MIMD是典型的并行計算機(jī)。MISD在實際中代表何種計算機(jī)，也存在不同的看法，甚至有學(xué)者認(rèn)為根本不存在MISD。

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

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

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

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

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

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

1、并行向量處理機(jī)PVP（ParallelVectorProcessor）

2、對稱多處理機(jī)SMP（SymmetricMultiprocessor）

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

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

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

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

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

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

大規(guī)模并行處理機(jī)（MPP）大規(guī)模并行處理機(jī)（MassivelyParallelProcessor,MPP）是指由幾百或幾千臺處理機(jī)組成的大規(guī)模并行計算機(jī)系統(tǒng)。Intel和美國Sandia國家實驗室1997年6月研制成功的MPP系統(tǒng)ASCIOptionRed有9216個處理器。MPP系統(tǒng)中處理器數(shù)目巨大，整個系統(tǒng)規(guī)模龐大，許多硬件設(shè)備是專門設(shè)計制造的，開發(fā)起來比較困難，通常被視為國家綜合實力的象征。同時，MPP能夠提供其它并行計算機(jī)不能達(dá)到的計算能力。達(dá)到3T性能目標(biāo)和解決重大挑戰(zhàn)性課題都寄希望于MPP。大規(guī)模并行處理機(jī)一般指規(guī)模非常大的并行計算機(jī)系統(tǒng)，含有成千上萬個處理器。它一般采用分布式存儲器，存儲器一般為處理器私有，各處理器之間用消息傳遞的方式通信。大規(guī)模并行處理機(jī)的互連網(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)還有磁盤存儲器在物理上是分布的，而且都是私有的程序由多個進(jìn)程組成，每個都有其私有空間，進(jìn)程間采用消息傳遞相互作用

大規(guī)模并行處理機(jī)（MPP）23典型MPP系統(tǒng)特性比較MPP模型Intel/SandiaASCIOptionRedIBMSP2SGI/CrayOrigin2000一個大型樣機(jī)的配置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自然編程機(jī)制基于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個單元超標(biāo)量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機(jī)群總線可支持4個CPU25MPP的結(jié)構(gòu)如下圖所示。其中MB表示存儲器總線，P/C表示處理器和高速緩存，NIC表示網(wǎng)絡(luò)接口電路，LM表示本地存儲器。NIC是用來將計算機(jī)與網(wǎng)絡(luò)（例如局域網(wǎng)）連接起來的接口電路。它的功能有：將消息格式化、路由選擇、流和錯誤控制等。26分布式共享存儲器多處理機(jī)DSM分布式共享存儲器多處理機(jī)的主要特點是它的存儲器在物理上是分布在各個結(jié)點中的，但是通過硬件和軟件為用戶提供一個單一地址的編程空間，即形成一個虛擬的共享存儲器。DSM相對于MPP的優(yōu)越性是編程較容易。它通過高速緩存目錄支持分布高速緩存的一致性。DSM與SMP的區(qū)別在于各結(jié)點內(nèi)有存儲器，與MPP的區(qū)別在于存儲器在邏輯上是共享的。典型的DSM有StanfordDASH、SGI/CrayOrigin2000。27DSM的結(jié)構(gòu)如下圖所示，其中DIR表示高速緩存目錄，其它符號同前。

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

工作站機(jī)群是一種新興的并行系統(tǒng)。COW是由高檔商品微機(jī)（包括工作站）用高速商品互連網(wǎng)絡(luò)（有的商用機(jī)群也使用定制的網(wǎng)絡(luò)）連接而成。COW的每個結(jié)點都是一臺完整的計算機(jī)（可能沒有鼠標(biāo)、顯示器等外設(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