Ch1 高等計(jì)算機(jī)的核心技術(shù)-并行處理

高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)研究生課程高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程介紹參考書(shū)目：1．PattersonD.A.，Hennesy

J.L.，Computer

Architecture：AQuantitativeApproach，Morgan

KanfmannPublishers，1995。2．ComputerOrganization &Design：The

Hardware／SoftwareInterface。第一章高等計(jì)算機(jī)的核心技術(shù)——并行處理第二章加速比性能模型與可擴(kuò)展性分析第三章互連與通信第四章劃分與調(diào)度第五章并行存儲(chǔ)器系統(tǒng)第六章CacheCoherence第七章MemoryConsistency第八章指令級(jí)并行處理第一章高等計(jì)算機(jī)的核心技術(shù)——并行處理1.1什么是并行處理

1.1.1并行處理定義 1.1.2并行性級(jí)別1.2為什么要開(kāi)發(fā)并行處理技術(shù)1.3并行處理計(jì)算機(jī)結(jié)構(gòu)沿革1.4其它并行處理計(jì)算機(jī)技術(shù)1.1什么是并行處理1.1.1并行處理定義并行處理是指同時(shí)對(duì)多個(gè)任務(wù)或多條指令、或同時(shí)對(duì)多個(gè)數(shù)據(jù)項(xiàng)進(jìn)行處理。 完成此項(xiàng)處理的計(jì)算機(jī)系統(tǒng)稱為并行處理計(jì)算機(jī)系統(tǒng)。弗林分類法按照指令流和數(shù)據(jù)流多倍性的特點(diǎn)，計(jì)算機(jī)可以劃分為以下四類：1、SISD：?jiǎn)沃噶盍鲉螖?shù)據(jù)流計(jì)算機(jī)2、SIMD：?jiǎn)沃噶盍鞫鄶?shù)據(jù)流計(jì)算機(jī)3、MISD：多指令流單數(shù)據(jù)流計(jì)算機(jī)4、MIMD：多指令流多數(shù)據(jù)流計(jì)算機(jī)SISD：傳統(tǒng)的單CPU順序機(jī)SIMD：空間并行，多PE，向量處理MISD：流水線＋脈動(dòng)陣列，專用MIMD：真正的并行處理機(jī)，包括共享存儲(chǔ)器型和消息傳遞型。MMPUCUDSISIS1、SISD：?jiǎn)沃噶盍鲉螖?shù)據(jù)流計(jì)算機(jī)

SISD典型單處理機(jī)，包括：?jiǎn)喂δ懿考幚頇C(jī)：IBM1401，VAX-11

多功能部件處理機(jī)：IBM360/91，370/168，CDC6600

流水線處理機(jī)：標(biāo)量流水線處理機(jī)MM1PU2CU….ISISPUnPU1MM2MMnDS2DSnDS12、SIMD：?jiǎn)沃噶盍鞫鄶?shù)據(jù)流計(jì)算機(jī)

SIMD并行處理機(jī)、陣列處理機(jī)、向量處理機(jī)、相聯(lián)處理機(jī)、超標(biāo)量處理機(jī)、超流水線處理機(jī)、…多個(gè)PU按一定方式互連，在同一個(gè)CU控制下，多各自的數(shù)據(jù)完成同一條指令規(guī)定的操作；從CU看，指令順序（串行）執(zhí)行，從PU看，數(shù)據(jù)并行執(zhí)行。3、MISD：多指令流單多數(shù)據(jù)流計(jì)算機(jī)MMCU1PU1CUnPUnCU2PU2……IO脈動(dòng)式陣列（systolicarray）PU2CU1….IS3IS1PUnPU1MM1DS1CU2CUn….IS2MM2DS2MM2DS2IS1IS2IS3包括：緊密偶合：IBM3081、IBM3084松散偶合：D-825、Cmmp、CRAP-23、MIMD：多指令流單多數(shù)據(jù)流計(jì)算機(jī)

同時(shí)性（simultaneity）——兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生，資源重復(fù)。

并發(fā)性（concurrency）——兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生，分時(shí)共用。

流水特性（pipelining）——在一個(gè)重疊的時(shí)間內(nèi)所發(fā)生的流水事件，時(shí)間重疊。

1.1.2并行性級(jí)別

粒度（granularity）：衡量一個(gè)軟件進(jìn)程的計(jì)算量的度量。最簡(jiǎn)單的是指此程序段中的指令數(shù)。分細(xì)、中、粗三種。 按粒度的不同，并行性級(jí)別可以分為指令級(jí)、循環(huán)級(jí)、過(guò)程級(jí)、子程序級(jí)和作業(yè)級(jí)等不同的層次。它們對(duì)應(yīng)的計(jì)算粒度可以為細(xì)粒度、中粒度和粗粒度。如下：1.指令級(jí)并行典型細(xì)粒度，一般少于20條指令。借助優(yōu)化編譯器自動(dòng)檢測(cè)并行性，將源代碼變成運(yùn)行時(shí)系統(tǒng)能識(shí)別的并行形式。2.循環(huán)級(jí)并行

典型循環(huán)含少于500條指令，由于有些循環(huán)操作在連續(xù)迭代中并不相關(guān)，易于向量化，是在并行機(jī)或向量機(jī)上運(yùn)行的最優(yōu)程序結(jié)構(gòu)。遞歸循環(huán)的并行化比較困難。向量處理由優(yōu)化編譯器在循環(huán)級(jí)開(kāi)發(fā)，仍屬于細(xì)粒度計(jì)算。3.過(guò)程級(jí)并行

中粒度并行，指令少于2000條，分析過(guò)程間的并行性比細(xì)粒度要困難。有時(shí)需要重新設(shè)計(jì)程序，并要編譯器的支持。SIMD、多任務(wù)處理屬于這一層。4.子程序級(jí)并行（粗）中粒度并行，幾千條指令，常在messagepassing多計(jì)算機(jī)上以SIMD或MIMD方式執(zhí)行。并行性主要由算法設(shè)計(jì)人員與程序員開(kāi)發(fā)。5.作業(yè)級(jí)并行粗粒度并行，數(shù)萬(wàn)條指令，常由加載程序和操作系統(tǒng)處理這類并行性，靠算法有效性來(lái)保證。一般說(shuō)來(lái)： 細(xì)粒度：用并行化或向量化編譯器來(lái)開(kāi)發(fā)，共享變量通信支持。 中粒度：靠程序員和編譯器一起開(kāi)發(fā)，共享變量通信。 粗粒度：取決于操作系統(tǒng)和算法的效率，消息傳遞通信。例子：在共享存儲(chǔ)器型多處理機(jī)上執(zhí)行：

L1: DO 10 I=1,N L2: A(I)=B(I)+C(I) L3: 10 Continue L4: SUM=0 L5: DO 20 J=1,N L6: SUM=SUM+A(J) L7: 20 Continue假設(shè)：L2，L4，L6每行要用一個(gè)機(jī)器周期。L1，L3，L5，L7所需時(shí)間可以忽略。 所有數(shù)組已經(jīng)裝入主存，程序已裝入Cache中（取指令和加載數(shù)據(jù)可以忽略不計(jì)）。 忽略總線爭(zhēng)用或存儲(chǔ)器訪問(wèn)沖突。 上面的程序?qū)嶋H上把數(shù)組B(I)和C(I)相加，最后得到一個(gè)總和。

共享存儲(chǔ)多處理機(jī)結(jié)構(gòu)如下圖：P1P2……Pm系統(tǒng)互連I/OSM1……SMm處理機(jī)共享存儲(chǔ)器 在單機(jī)系統(tǒng)中，2N個(gè)周期可以完成上述的操作：

I循環(huán)中執(zhí)行N次獨(dú)立迭代需要N個(gè)周期；

J循環(huán)中執(zhí)行N次遞歸迭代也需要N個(gè)周期。 在共享存儲(chǔ)型的多處理機(jī)系統(tǒng)上： 假設(shè)有M臺(tái)處理機(jī)，可以將循環(huán)分成M段，每段有L=N/M個(gè)元素。 代碼如下所示：

Doall k=1,M Do10I=L(k-1)+1,kL A(I)=B(I)+C(I) 10 Continue

SUM(k)=0 Do20J=1,L

SUM(k)=SUM(k)+A(L(k-1)+J) 20 Continue

Endall 分段的I循環(huán)可以在L個(gè)周期中完成； 分段的J循環(huán)在L個(gè)周期中產(chǎn)生M個(gè)部分和。 所以產(chǎn)生所有的M個(gè)部分和共需要2L個(gè)周期（還需要將這些部分和合并）。 假設(shè)經(jīng)過(guò)共享存儲(chǔ)器的處理機(jī)之間的每次通信操作需要k個(gè)周期。 設(shè)N=32，M=8，則經(jīng)過(guò)2L（即8個(gè)周期）后在8臺(tái)處理機(jī)上各有一個(gè)部分和，還需要8個(gè)數(shù)相加。 為了合并部分和，可以設(shè)計(jì)一個(gè)l層的二進(jìn)制加法樹(shù)，其中l(wèi)=log2M，加法樹(shù)用l(k+1)個(gè)周期從樹(shù)葉到樹(shù)根順序合并M個(gè)部分和，如下：

二進(jìn)制加法樹(shù)： 所以，多處理機(jī)系統(tǒng)需要 才能得到最終的結(jié)果。 假定數(shù)組中有N=220個(gè)元素，順序執(zhí)行需要2N=221個(gè)機(jī)器周期，假設(shè)機(jī)器間通信的開(kāi)銷平均值為k=200個(gè)周期，則在M=256臺(tái)處理機(jī)的并行執(zhí)行需要：第一章高等計(jì)算機(jī)的核心技術(shù)——并行處理 1.1什么是并行處理

1.2為什么要開(kāi)發(fā)并行處理技術(shù) 1.3并行處理計(jì)算機(jī)結(jié)構(gòu)沿革 1.4其它并行處理計(jì)算機(jī)技術(shù)1.2為什么要開(kāi)發(fā)并行處理技術(shù)

對(duì)單用戶，可以提高加速比（SpeedupOriented)；

對(duì)多用戶，可以提高吞吐率（ThroughputOriented).

對(duì)不同的需求我們可以做需求分析如下： 1.天氣預(yù)報(bào) 天氣預(yù)報(bào)模式為非線性偏微分方程，預(yù)報(bào)臺(tái)風(fēng)暴雨過(guò)程，計(jì)算量為1014—1016次浮點(diǎn)運(yùn)算，需要10GFlops—100GFlops的巨型機(jī)。 用途：局部災(zāi)害性天氣預(yù)報(bào)。2.石油工業(yè)

地震勘探資料處理 油藏?cái)?shù)值模擬 測(cè)井資料處理 地震勘探由數(shù)據(jù)采集、數(shù)據(jù)處理和資料解釋三階段組成。 目前采用的三維地震勘探比較精確的反映地下情況，但數(shù)據(jù)量大，處理周期長(zhǎng)。

100平方公里的三維勘探面積，道距25米，60次覆蓋，6秒長(zhǎng)記錄，2毫秒采樣，一共采集2.881010個(gè)數(shù)據(jù)，約為116GB。 疊加后數(shù)據(jù)為4.8108個(gè)數(shù)據(jù)。用二維疊前深度偏移方法精確的產(chǎn)生地下深度圖像，需要進(jìn)行251012FLOP，采用100MFLOPs機(jī)器計(jì)算250天，1GFLOPs機(jī)計(jì)算25天，10GFLOPs機(jī)器35分?？紤]到機(jī)器持續(xù)速度常常是峰值速度的10-30%，所以需要100GFlops的機(jī)器。CrayT932/32約為60GFLOPs。3.航空航天 研究三維翼型對(duì)飛機(jī)性能的影響。數(shù)值模擬用時(shí)間相關(guān)法解Navier-Stoker方程，網(wǎng)格分點(diǎn)為1204050，需內(nèi)存160MB，6億計(jì)算機(jī)上解12小時(shí)，如果在數(shù)分鐘內(nèi)完成設(shè)計(jì)，則需要千億次計(jì)算機(jī)。4.重大挑戰(zhàn)性課題需求（圖3.5）

計(jì)算空氣動(dòng)力學(xué)：千億次/秒（1011）

圖像處理： 百億次/秒（1010）

AI： 萬(wàn)億次/秒（1012）5.核武器 核爆炸數(shù)值模擬，推斷出不同結(jié)構(gòu)與不同條件下核裝置的能量釋放效應(yīng)。 壓力： 幾百萬(wàn)大氣壓 溫度： 幾千萬(wàn)攝氏度 能量在秒級(jí)內(nèi)釋放出來(lái)。設(shè)計(jì)一個(gè)核武器型號(hào)，從模型規(guī)律、調(diào)整各種參數(shù)到優(yōu)選，需計(jì)算成百上千次核試驗(yàn)。LosAlamos實(shí)驗(yàn)室要求計(jì)算一個(gè)模型的上限為8-10小時(shí)。 千萬(wàn)次機(jī)上算橢球程序的計(jì)算模型需要40-60CPU小時(shí)。 二維計(jì)算，每方向上網(wǎng)格點(diǎn)數(shù)取100，二維計(jì)算是一維的200倍，三維是一維的33000倍。若每維設(shè)1000網(wǎng)格點(diǎn)，則三維計(jì)算是一維的幾十萬(wàn)倍之多。此時(shí)對(duì)主存儲(chǔ)器容量要數(shù)十、數(shù)百億字單元（64位）。 另外還有I/O能力的要求，可視化圖形輸出。 6.解決方案只有開(kāi)發(fā)并行處理技術(shù)才能滿足要求：

3Tperformance：

TeraflopsofComputingPower TerabyteofMainMemory Terabyte/sofI/Obandwidth第一章高等計(jì)算機(jī)的核心技術(shù)——并行處理1.1什么是并行處理1.2為什么要開(kāi)發(fā)并行處理技術(shù)1.3并行處理計(jì)算機(jī)結(jié)構(gòu)沿革

1.3.1向量機(jī)與多向量機(jī) 1.3.2SIMD計(jì)算機(jī) 1.3.3Shared-MemoryMultiprocessors 1.3.4Distributed-MemoryMultiprocessors

1.3.5四類實(shí)用的并行系統(tǒng)1.4其它并行處理計(jì)算機(jī)技術(shù)1.3并行處理計(jì)算機(jī)結(jié)構(gòu)沿革1.3.1向量機(jī)與多向量機(jī)向量機(jī)的結(jié)構(gòu)如下圖：ScalarFunctionalpipelinesScalarControlunitscalarprocessorscalarinstructionMainMemory(Programanddata)MassStorageHostComputerI/O(user)VectorControlunitvectorregistersvectorprocessorcontrolVectorFunctionalpipelinesVectorFunctionalpipelines……vectorinstruction程序和數(shù)據(jù)從Host進(jìn)入主機(jī)指令先在Scalarcontrolunit譯碼，如是標(biāo)量或控制操作指令，則在標(biāo)量功能流水部件種執(zhí)行。如果是向量指令，則進(jìn)入向量控制部件。register-to-register：

Crayseries FujitsuVP2000seriesmemory-to-memory：

Cyber205多向量機(jī)發(fā)展過(guò)程：CDC7600(CDC,1970)CDCCyber205(Levine,1982)Memory-MemoryCray1(Russell,1978)register-registerETA10(ETA,Inc,1989)CrayY-MPCrayResearch1989FujitsuNECHitachiModelsCrayMPPCrayResearch1993其中：

CrayY-MP,C90：

Y-MP有2，4，8個(gè)處理器，而C90有16個(gè)處理單元（PE），處理速度16GFlops。

ConvexC3800family：8個(gè)處理器，4GB主存儲(chǔ)器，

Peakperformance為2GFlops。1.3.2SIMD計(jì)算機(jī)SIMD計(jì)算機(jī)的結(jié)構(gòu)如下圖：ControlUnitProc0Mem0Proc1Mem1……ProcN-1MemN-1PE0PE1PEN-1InterConnectionNetworkMasParMP-1：可有1024，4096，…，16384個(gè)處理器。在16KPEs，32位整數(shù)運(yùn)算，16KB局部存儲(chǔ)器模塊的配置下，可達(dá)26000MIPS，單精度浮點(diǎn)運(yùn)算1.5GFlops，雙精度浮點(diǎn)運(yùn)算650MFlops。CM-2：

65536個(gè)處理單元，1Mbit/PE。 峰值速率為28GFlops，持續(xù)速率5.6GFlops。SIMD計(jì)算機(jī)發(fā)展過(guò)程圖如下：IlliacIV(1968)GoodYearMPP(1980)BSP(1982)MasParMP1(1990)IBMGF/11(1985)DAP610(AMT，Inc.1987)CM2(1990)CM5(1991)1.3.3MIMD－Shared-MemoryMultiprocessorsUMA(Uniform-memory-access)model：

物理存儲(chǔ)器被所有處理機(jī)均勻共享，所有處理機(jī)對(duì)所有存儲(chǔ)字具有相同的存取時(shí)間。P0I/OP1SM1……PnSMnInterConnectionNetwork(Bus、Crossbar、MultistageNetwork)……處理器共享存儲(chǔ)器NUMA(NonUniform-memory-access)model：訪問(wèn)時(shí)間隨存儲(chǔ)字的位置不同而變化。P1……PnLMnInter-ConnectionNetwork……LM1P2LM2……COMA(Cache-onlymemoryarchitecture)：只用高速緩存的多處理機(jī) 遠(yuǎn)程高速緩存訪問(wèn)則借助于分布高速緩存目錄進(jìn)行。PDInterConnectionNetwork……distributedcachedirectoriesCPDCPDCKendallSquareResearch’sKSR-1Shared-MemoryMultiprocessors發(fā)展過(guò)程如下：Cmmp(cmu,1972)IllinoisCedar(1987)UltraComputerNYU(1983)FujitsuVPP500(1992)IBMRP3(1985)BBNButterfly(1989)stanford/Dash(1992)KSR-1(1990)1.3.4MIMD－Distributed-MemoryMultiprocessorsP……Message-passinginterconnectionnetwork(Mesh,ring,torus,hypercube,cube,cycle)MPMPMP……PPMMMMP……MPMP……MP例子：

IntelParagonXP/s：

采用50MHz的i860處理器，每個(gè)節(jié)點(diǎn)16-128MB主存儲(chǔ)器，采用2D-Mesh互連，浮點(diǎn)運(yùn)算5-300GFlops，或2.8-160Gips。

nCube2SModel80：

有4096-8192個(gè)PE，主存儲(chǔ)器16384-262144MB，浮點(diǎn)運(yùn)算163800-34000MFlops，整數(shù)運(yùn)算61000-123000MIPS。 CosmicCube(1981)nCube-2/6400(1990)Mosaic(1992)Intelparagon(1992)MIT/Jmachine(1992)intel

iPSC’s(1983)Distributed-Memorymultiprocessors發(fā)展進(jìn)程：1.3.5四類實(shí)用的并行系統(tǒng)1.向量機(jī)與多向量機(jī)硬、軟件技術(shù)相對(duì)成熟、應(yīng)用廣泛、市場(chǎng)占有率高。很難達(dá)到3Tperformance來(lái)解決GrandChallenge

問(wèn)題。 下面圖表說(shuō)明了這一類機(jī)器的發(fā)展過(guò)程。GFlops100100.11976197919821985198819911994YearCray1/10.16GFCrayX-MP/20.24GFCray2/41.9GFCrayY-MP/82.6GFCrayJ916/163.2GFCrayC916/1616GFCrayT932/3260GF2.對(duì)稱式多處理機(jī)SMP

SMP：Symmetric

MultiProcessors SharedMemorymultiProcessors SmallsizeMultiProcessors

處理機(jī)之間無(wú)主從之分，對(duì)外有相同的訪問(wèn)權(quán)，都有執(zhí)行操作系統(tǒng)核心和I/O服務(wù)程序的能力。 共享存儲(chǔ)器、統(tǒng)一地址空間，系統(tǒng)編程比較容易。

CPU可多至16臺(tái)左右，做服務(wù)器用，市場(chǎng)前景好。典型的SMP有：

SunSPARCserver1000 SunSPARCcenter2000 SGIPowerChallengeSGIPowerChallengeL：2-6CPU，1.8GFlopsSGIPowerChallengeXL：

2-18CPU，5.4GFlops

*64位MIPSchip，每周期指令發(fā)射數(shù)為4

*8路交錯(cuò)主存、帶寬為1.2GB/s

*I/O帶寬320MB/s（每個(gè)控制器），配置4個(gè)可達(dá)1.2GB/s3.MPP系統(tǒng)（分布存儲(chǔ)）多于100個(gè)PE，消息傳遞，分布存儲(chǔ)； 可擴(kuò)展，峰值可達(dá)3Tperformance；

貴，市場(chǎng)有限； 持續(xù)速度是峰值速度的3-10%； 可解決某些GrandChallenge問(wèn)題，是國(guó)家綜合實(shí)力的象征。 4.機(jī)群系統(tǒng)

NOW：NetworkOfWorkstations

COW：ClusterOfWorkstations特點(diǎn)： 投資風(fēng)險(xiǎn)小，軟件財(cái)富繼承性好；可構(gòu)成異構(gòu)系統(tǒng)，資源利用率高； 通信開(kāi)銷大。 一種典型的機(jī)群系統(tǒng)結(jié)構(gòu)如下：CPUMemoryI/OCPUMemoryI/O……CPUMemoryI/OI/OI/OI/OMemoryMemory……MemoryCPUCPUCPUNetwork第一章高等計(jì)算機(jī)的核心技術(shù)——并行處理

1.1什么是并行處理 1.2為什么要開(kāi)發(fā)并行處理技術(shù)

1.3并行處理計(jì)算機(jī)結(jié)構(gòu)沿革

1.4其它并行處理計(jì)算機(jī)技術(shù)1.4其它并行處理計(jì)算機(jī)技術(shù)1.數(shù)據(jù)流技術(shù) dataflow以數(shù)據(jù)驅(qū)動(dòng)機(jī)制代替控制流機(jī)制 當(dāng)功能部件輸入端的操作數(shù)可用時(shí)就啟動(dòng)執(zhí)行；可開(kāi)發(fā)程序中所有的并行性，但費(fèi)用昂貴，實(shí)際性能與功能部件數(shù)量、存儲(chǔ)器帶寬以及掛起和可用部件相匹配的程度有關(guān)。 如：MIT的MonSoos，*T

ETL的Sigma1，EM52.多線程 每臺(tái)處理機(jī)有多個(gè)控制線程，同時(shí)運(yùn)行多個(gè)現(xiàn)場(chǎng)，是實(shí)現(xiàn)時(shí)延隱藏的一種有效機(jī)制。 比如:

Tera，Alewife

成本高。3.邏輯推理與規(guī)約結(jié)構(gòu) 邏輯推理： 日本第五代機(jī)，面向邏輯語(yǔ)言、執(zhí)行速度慢，軟件與程序設(shè)計(jì)環(huán)境欠豐富。

規(guī)約結(jié)構(gòu)：

Alice，PGR，面向函數(shù)語(yǔ)言，執(zhí)行速度慢，軟件與環(huán)境欠豐富。4.關(guān)鍵技術(shù) 并行算法（數(shù)值算法與非數(shù)值算法） 并行計(jì)算模型 互連與通信 并行存儲(chǔ)技術(shù) 同步與時(shí)延隱藏技術(shù) 并行I/O

劃分、調(diào)度與負(fù)載平衡 優(yōu)化編譯 并行調(diào)試 工具與環(huán)境5.美國(guó)的主要行動(dòng)（1）組織基于NSF的國(guó)家科學(xué)計(jì)算聯(lián)盟 （NationalComputationalScienceAlliance）

建立國(guó)家科技網(wǎng)（Grid）：97.11開(kāi)始，五年計(jì)劃，總經(jīng)費(fèi)3.4億美元。

目標(biāo)：使美國(guó)在全國(guó)范圍內(nèi)的元計(jì)算機(jī)（網(wǎng)上的計(jì)算機(jī)可作為一個(gè)整體看待）達(dá)到實(shí)用水平。 為在桌面上解決計(jì)算科學(xué)與工程時(shí)提供一個(gè)有力的解題環(huán)境。 解決基于元計(jì)算環(huán)境的并行、分布、協(xié)作和immersive等問(wèn)題。

UIUC、San

Diago組織實(shí)施。（2）DOE（能源部）支持的ASIC計(jì)劃 （AcceleratedStrategicComputingInitiative）

保證在21世紀(jì)美國(guó)在核研究和核儲(chǔ)備繼續(xù)處于領(lǐng)先地位。 以LosAlamos，