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

高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第一章高等計(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為什么要開發(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í)性（simultaneity）——兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生。

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

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

1.1.2并行性級(jí)別

粒度（granularity）：衡量一個(gè)軟件進(jìn)程的計(jì)算量的度量。最簡(jiǎn)單的是指此程序段中的指令數(shù)。分細(xì)、中、粗三種。

按粒度的不同，并行性級(jí)別可以分為指令級(jí)、循環(huán)級(jí)、過程級(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í)開發(fā)，仍屬于細(xì)粒度計(jì)算。 3.過程級(jí)并行

中粒度并行，指令少于2000條，分析過程間的并行性比細(xì)粒度要困難。有時(shí)需要重新設(shè)計(jì)程序，并要編譯器的支持。SPMD、多任務(wù)處理屬于這一層。

4.子程序級(jí)并行 （粗）中粒度并行，幾千條指令，常在messagepassing多計(jì)算機(jī)上以SPMD或MPMD方式執(zhí)行。并行性主要由算法設(shè)計(jì)人員與程序員開發(fā)。

5.作業(yè)級(jí)并行

粗粒度并行，數(shù)萬(wàn)條指令，常由加載程序和操作系統(tǒng)處理這類并行性，靠算法有效性來(lái)保證。一般說(shuō)來(lái)： 細(xì)粒度：用并行化或向量化編譯器來(lái)開發(fā)，共享變量通信支持。 中粒度：靠程序員和編譯器一起開發(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ǔ)器訪問沖突。上面的程序?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)過共享存儲(chǔ)器的處理機(jī)之間的每次通信操作需要k個(gè)周期。

設(shè)N=32，M=8，則經(jīng)過2L（即8個(gè)周期）后在8臺(tái)處理機(jī)上各有一個(gè)部分和，還需要8個(gè)數(shù)相加。 為了合并部分和，可以設(shè)計(jì)一個(gè)l層的二進(jìn)制加法樹，其中l(wèi)=log2M，加法樹用l(k+1)個(gè)周期從樹葉到樹根順序合并M個(gè)部分和，如下：

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

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

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

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

對(duì)不同的需求我們可以做需求分析如下： 1.天氣預(yù)報(bào) 1990年10次臺(tái)風(fēng)登陸，福建、浙江兩省損失79億元，死亡950余人。 天氣預(yù)報(bào)模式為非線性偏微分方程，預(yù)報(bào)臺(tái)風(fēng)暴雨過程，計(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.解決方案 只有開發(fā)并行處理技術(shù)才能滿足要求：

3Tperformance：

TeraflopsofComputingPower TerabyteofMainMemory Terabyte/sofI/Obandwidth第一章高等計(jì)算機(jī)的核心技術(shù)——并行處理

1.1什么是并行處理 1.2為什么要開發(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ā)展過程：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ǔ)器，

Rerkperformance為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ā)展過程圖如下：IlliacIV(1968)GoodYearMPP(1980)BSP(1982)MasParMP1(1990)IBMGF/11(1985)DAP610(AMT，Inc.1987)CM2(1990)CM5(1991)

1.3.3Shared-MemoryMultiprocessors

UMA(Uniform-memory-access)model：

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

1.3.4Distributed-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)inteliPSC’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

問題。 下面圖表說(shuō)明了這一類機(jī)器的發(fā)展過程。GFlops100100.11976197919821985198819911994YearCray1/10.16GFCrayX-MP/20.24GFCray2/41.9GFCrayY-MP/82.6GFCrayJ916/163.2GFCrayC916/1616GFCrayT932/3260GF

2.對(duì)稱式多處理機(jī)SMP

SMP：SymmetricMultiProcessors SharedMemorymultiProcessors SmallsizeMultiProcessors

處理機(jī)之間無(wú)主從之分，對(duì)外有相同的訪問權(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/s

3.MPP系統(tǒng)（分布存儲(chǔ)）

多于100個(gè)PE，消息傳遞，分布存儲(chǔ)； 可擴(kuò)展，峰值可達(dá)3Tperformance；

貴，市場(chǎng)有限； 持續(xù)速度是峰值速度的3-10%； 可解決某些GrandChallenge問題，是國(guó)家綜合實(shí)力的象征。

4.機(jī)群系統(tǒng)

NOW：NetworkOfWorkstations

COW：ClusterOfWorkstations特點(diǎn)：

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

1.1什么是并行處理 1.2為什么要開發(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í)行；可開發(fā)程序中所有的并行性，但費(fèi)用昂貴，實(shí)際性能與功能部件數(shù)量、存儲(chǔ)器帶寬以及掛起和可用部件相匹配的程度有關(guān)。 如：MIT的MonSoos，*T

ETL的Sigma1，EM5 2.多線程 每臺(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開始，五年計(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等問題。

UIUC、SanDiago組織實(shí)施。

（2）DOE支持的ASIC計(jì)劃 （AcceleratedStrategicComputingInitiative）

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

三個(gè)國(guó)家實(shí)驗(yàn)室為核心，組成遍及美國(guó)不同地區(qū)的“拆墻合作”。 為建立VirtualLaboratory奠定基礎(chǔ)。 研制出超級(jí)計(jì)算機(jī)系統(tǒng)：萬(wàn)億次量級(jí)的計(jì)算機(jī)，2的50次冪（約千萬(wàn)億）容量的數(shù)據(jù)庫(kù)系統(tǒng)。 提供高效、好用的計(jì)算環(huán)境。

能實(shí)現(xiàn)基于網(wǎng)絡(luò)的、分布式協(xié)同工作環(huán)境。 能提供高效的、點(diǎn)對(duì)點(diǎn)的計(jì)算設(shè)施。 在CORBA的環(huán)境下有效的把計(jì)算平臺(tái)和有關(guān)應(yīng)用進(jìn)行系統(tǒng)集成。 負(fù)載平衡。 可裁剪性。 6.ModelsofParallelComputers(1960s-1980s)DataMIMDSIMDInstructionImplicationMultipleDataStreamsMultipleDataStreamsSingleInstructionStreamsMultipleInstructionStreamsSingleProgram;Lotsofdatatohavelotsofparallelism;Programmingissimplersincecommunicationisalwayssynchronized;CommunicationsseperatefromcomputationsinceinstructionsdistinctMaybemanyProgramsLotsofprogramstohavelotsofparallelismH/Wconstructionissimplerusingoff-the-shelfuniprocessorscommunicationmergedwithcomputationImplicationIllivaIV、CM-2、MasParCrayX-MP、Sequent、nCube 7.一些縮寫

SPMD——SingleProgramMultipleDataStream

MPMD——MultipleProgramMultiple DataStream

SIMD——SingleInstructionMultiple Data

MIMD——MultipleInstructionMultiple Data

網(wǎng)格是通過網(wǎng)絡(luò)提供綜合計(jì)算機(jī)資源和服務(wù)的基礎(chǔ)設(shè)施

公用網(wǎng)絡(luò)，計(jì)算機(jī)，存儲(chǔ)。應(yīng)用服務(wù)的支柱提供不間斷的，無(wú)限的處理能力。Mainframe70sDistributedComputing21stCenturyInternetLate90sPC80sClient/Server90s什么是網(wǎng)格？

IanFoster關(guān)于網(wǎng)格的三個(gè)判斷標(biāo)準(zhǔn)“WhatisGrid,aGuideforthePerplexed”GridToday,July17,2002,

網(wǎng)格的判斷標(biāo)準(zhǔn)資源的協(xié)調(diào)而不僅僅是集中控制。使用標(biāo)準(zhǔn)的，開放式的，通用的協(xié)議和接口。提供安全可靠、高質(zhì)量的服務(wù)?；ヂ?lián)網(wǎng)服務(wù)提供方服務(wù)網(wǎng)格VirtualizationofservicesDynamicserviceprovisioningSelf-healingofservicesIntegratablewithEnterpriseapplications企業(yè)間及合作伙伴合作網(wǎng)格DOE,UKGrid&DoD協(xié)同共享公用的數(shù)據(jù)中心動(dòng)態(tài)的提供資源企業(yè)內(nèi)部網(wǎng)格及其三個(gè)階段time共享程度企業(yè)網(wǎng)格Toshiba,TI,GMCluster-to-clustersharingmanagementReliablefiletransfer&stagingUseraccountmapping,Firewalls,Kerboros1996200020042008網(wǎng)格應(yīng)用的挑戰(zhàn)計(jì)算機(jī)制造業(yè)機(jī)械制造業(yè)

Projectfairshareflexiblelease適度的規(guī)模本地管理

ClearcasesupNFSloadbalanceWANfilesync

OptimaluseWANlicsharingBorrow/ReclaimServicedomains生命科學(xué)可靠文件傳輸

PDM集成

自動(dòng)的工具最佳的應(yīng)用

DatasourcesyncDatasetlifecycleDataCacheDataPipeline

WorkflowmgmtCapacityworkloadLargenumberofjobs

政府與教育

Efficientxferdatareplication

NUMACo-allocAdvanceRsv金融

WorkflowbusinessunitsilosDeadline

Messagingdatacaching計(jì)算機(jī)數(shù)據(jù)軟件

第二章加速比性能模型與可擴(kuò)展性分析 2.1加速比性能分析

2.1.1一般概念 2.1.2加速比 2.1.3三種加速比性能模型 2.2可擴(kuò)展性分析2.1加速比性能模型

2.1.1一般概念 1.處理機(jī)—時(shí)間積

處理機(jī)數(shù)目與處理時(shí)間的乘積用以度量這些處理機(jī)運(yùn)行時(shí)的資源利用率。 若一程序在

P臺(tái)處理機(jī)上運(yùn)行的時(shí)間為Tp，則此P臺(tái)處理機(jī)在Tp時(shí)間間隔內(nèi)完成的工作最大數(shù)量為Tp*P。

可將處理機(jī)實(shí)際工作曲線對(duì)時(shí)間的積分看成是這些處理機(jī)完成的有效工作量。

效率為有效工作量與最大工作量之比。2.并行度（DegreeOfParallelism—DOP）

并行度（DOP）是在一定時(shí)間間隔內(nèi)執(zhí)行一個(gè)程序所用的處理機(jī)的數(shù)目。3.并行性分布圖

執(zhí)行一個(gè)給定的程序時(shí)DOP對(duì)時(shí)間的分布圖。

DOP與對(duì)應(yīng)時(shí)間的間隔之積即為處理機(jī)要完成的工作或工作負(fù)載。下圖所示為一個(gè)并行性分布圖。DOPt1tt2并行性分布圖2.1.2加速比1.絕對(duì)加速比

將最好的串行算法與并行算法相比較.

定義一（與具體機(jī)器有關(guān)）將最好的串行算法在一臺(tái)上的運(yùn)行時(shí)間與并行算法在N臺(tái)運(yùn)行的時(shí)間相比。

定義二（與具體機(jī)器無(wú)關(guān)）將最好的串行算法在最快的順序機(jī)上的執(zhí)行時(shí)間與并行算法在并行機(jī)上的運(yùn)行時(shí)間相比。2.相對(duì)加速比

同一并行算法在單節(jié)點(diǎn)上運(yùn)行時(shí)間與在多個(gè)相同節(jié)點(diǎn)構(gòu)成的處理機(jī)系統(tǒng)上的運(yùn)行時(shí)間之比。 這種定義側(cè)重于描述算法和并行計(jì)算機(jī)本身的可擴(kuò)展性。線性加速比：中間開銷小，通信少，弱耦合計(jì)算超線性加速比：當(dāng)應(yīng)用需要大內(nèi)存時(shí)可能出現(xiàn)病態(tài)加速比：加速比遞減，可能是計(jì)算量太小2.1.3三種加速比性能模型

1.固定負(fù)載加速比性能模型—Amdahl定律 在許多實(shí)時(shí)應(yīng)用領(lǐng)域，計(jì)算負(fù)載的大小常固定。在并行機(jī)中，此負(fù)載可分布至多臺(tái)并行執(zhí)行，獲得的加速比稱為fixed-loadspeedup。一個(gè)問題的負(fù)載可表示如下：W=Ws+Wp

其中，Ws代表問題中不可并行化的串行部分負(fù)載，Wp表示可并行化的部分負(fù)載。 則n個(gè)節(jié)點(diǎn)情況下，加速比可以表示如下：設(shè)串行因子α為串行部分所占的比例。即代入即得Amdahl’law：不管采用多少處理機(jī)，可望達(dá)到的最好加速比：效率En可以表示為：處理機(jī)數(shù)目n越大，效率En越低。Amdahl定律告訴我們：系統(tǒng)中某一部件由于采用某種更快的執(zhí)行方式后整個(gè)系統(tǒng)性能的提高與這種執(zhí)行方式的使用頻率或占總執(zhí)行時(shí)間的比例有關(guān)。加速比的兩個(gè)決定因素：1.計(jì)算機(jī)執(zhí)行某個(gè)任務(wù)的總時(shí)間中可被改進(jìn)部分的時(shí)間所占的百分比，即

可被改進(jìn)部分占用時(shí)間/改進(jìn)前整個(gè)任務(wù)的執(zhí)行時(shí)間， 記為Fe，它總小于1。2.改進(jìn)部分采用改進(jìn)措施后比沒有采用改進(jìn)措施前性能提高的倍數(shù)，即

改進(jìn)前改進(jìn)部分執(zhí)行時(shí)間/改進(jìn)后改進(jìn)部分執(zhí)行時(shí)間， 記為Se。例1： 假設(shè)將某系統(tǒng)的某一部件的處理速度加快到10倍，但該部件的原處理時(shí)間僅為整個(gè)運(yùn)行時(shí)間的40%，則整個(gè)系統(tǒng)的性能提高了多少？

解：Fe=0.4，Se=10，例2： 采用哪種實(shí)現(xiàn)技術(shù)來(lái)求浮點(diǎn)數(shù)平方根FPSQR的操作對(duì)系統(tǒng)的性能影響較大。假設(shè)FPSQR操作占整個(gè)測(cè)試程序執(zhí)行時(shí)間的20%。一種實(shí)現(xiàn)方法是采用FPSQR硬件，使FPSQR操作的速度加快到10倍。另一種方法是使所有浮點(diǎn)數(shù)據(jù)指令的速度加快，使FP指令的速度加快到2倍，還假設(shè)FP指令占整個(gè)執(zhí)行時(shí)間的50%。請(qǐng)比較這兩種設(shè)計(jì)方案。

解：Fe_FPSQR=0.2，Se_FPSQR=10， Fe_FP=0.5，Se_FP=2，Amdahl’law又稱為固定規(guī)模加速比模型，問題規(guī)模不隨處理機(jī)變化而變化。固定問題規(guī)模，看用并行技術(shù)能達(dá)到的最短時(shí)間是多少。在固定規(guī)模加速比模型下，負(fù)載和執(zhí)行時(shí)間隨系統(tǒng)中處理機(jī)數(shù)目n變化的情況如下圖：WsWpWsWpWsWpWsWpWorkloadN1234ExecutionTimeNTsTp1TsTp2TsTp3TsTp4固定負(fù)載執(zhí)行時(shí)間隨N增加而減少固定負(fù)載加速比模型下的負(fù)載和執(zhí)行時(shí)間情況當(dāng)處理器數(shù)目n=1024，加速比Sn隨α變化的情況如下：得出曲線如下圖：91Snα102448312410可以比較不同的α對(duì)加速比帶來(lái)的不同影響：α=0Snnα=0.01α=0.1α=0.9α=0時(shí)得到理想加速比，當(dāng)α值增加時(shí)，加速比性能急劇下降。結(jié)論：加速比曲線隨α的上升急劇下降，原因是存在順序部分Ws，無(wú)法用增加系統(tǒng)的處理機(jī)數(shù)目來(lái)解決。這一性質(zhì)在過去二十年間給人們?cè)斐闪藢?duì)并行處理非常悲觀的印象。影響：兩種意見： 1.勸阻制造商生產(chǎn)大規(guī)模并行計(jì)算機(jī)。 2.研究并行編譯器，以降低α的值，從而提高系統(tǒng)的性能。規(guī)定負(fù)載加速比模型的可能應(yīng)用范圍：

對(duì)時(shí)間要求嚴(yán)格的應(yīng)用問題。

2.固定時(shí)間加速比性能模型—Gustafsun定律 有許多應(yīng)用領(lǐng)域強(qiáng)調(diào)精度而不時(shí)運(yùn)行時(shí)間。1988年，Gustafsun提出了固定時(shí)間加速比模型。當(dāng)機(jī)器的規(guī)模擴(kuò)大時(shí)，解題的規(guī)模也隨著擴(kuò)大，從而得到更加精確的解，而使運(yùn)行時(shí)間保持不變。 比如：有限元方法做結(jié)構(gòu)分析，流體動(dòng)力學(xué)做天氣預(yù)報(bào)解PDE(偏微分方程組)就需要提高精度。 粗格要求的計(jì)算量較少，而細(xì)格的計(jì)算量多，得到的精確度也較高。天氣預(yù)報(bào)模擬求解四維PDE，如果使每個(gè)實(shí)際方向（X，Y，Z）的格點(diǎn)距離減少10倍，并以同一幅度增加時(shí)間步，那么可以說(shuō)格點(diǎn)增加了104倍，因而工作負(fù)載也至少增大了10000倍。模型提出的背景： 固定負(fù)載模型有缺陷：因?yàn)锳mdahl’law中，α取決于問題及并行編譯器的效率，無(wú)法描述系統(tǒng)固有的特性。加速比的公式： 其中，Wp’=nWp和Ws+Wp=Ws’+Wp’/n作為固定時(shí)間的條件。Ws’+Wp’/n表示在擴(kuò)大負(fù)載后在增加處理機(jī)臺(tái)數(shù)的情況下的平均負(fù)載（執(zhí)行時(shí)間），它應(yīng)當(dāng)和負(fù)載沒有擴(kuò)大情況下的平均負(fù)載（執(zhí)行時(shí)間）Ws+Wp相等。即有Ws+Wp=Ws’+Wp’/n。同時(shí)，負(fù)載的串行部分并沒有改變，即有Ws=Ws’。在固定時(shí)間加速比模型下，負(fù)載和執(zhí)行時(shí)間隨系統(tǒng)中處理機(jī)數(shù)目n變化的情況如下圖：WsWpWsWpWsWpWsWpWorkloadN1234ExecutionTimeNTsTp1TsTp2TsTp3TsTp4并行負(fù)載不斷增加執(zhí)行時(shí)間固定固定時(shí)間加速比模型下的負(fù)載和執(zhí)行時(shí)間情況 增大問題規(guī)模的辦法使所有處理機(jī)保持忙碌狀態(tài)，在問題擴(kuò)大到與可用的計(jì)算能力匹配時(shí)，程序中的順序部分就不再是瓶頸了。 當(dāng)處理器數(shù)目n=1024，加速比Sn隨α變化的情況如下：Sn’α102410141004993983

3.受限于存儲(chǔ)器的加速比模型

1993年，由Sun和Ni提出。 大型科學(xué)計(jì)算和工程設(shè)計(jì)需要較大的存儲(chǔ)空間，許多應(yīng)用問題是存儲(chǔ)器受限，而不是CPU受限或者I/O受限。 比如：在分布存儲(chǔ)系統(tǒng)中常遇到，總存儲(chǔ)容量隨節(jié)點(diǎn)數(shù)線性增加，許多節(jié)點(diǎn)集合起來(lái)解一個(gè)大題。 基本思想：要在存儲(chǔ)空間有限條件下解盡可能大的問題，這同樣需要擴(kuò)展工作負(fù)載，才能提供較高的加速比、較高的精度和較好的資源利用率。加速比可以表示如下：其中：

在單個(gè)處理機(jī)上順序執(zhí)行的工作負(fù)載與問題的規(guī)模或系統(tǒng)的規(guī)模無(wú)關(guān)，即：而G(n)反映的是存儲(chǔ)容量增加n倍時(shí)并行工作負(fù)載增加的倍數(shù)。討論：

1. G(n)=

1，即為固定負(fù)載的情況； 2. G(n)=n，即存儲(chǔ)器增加n倍，負(fù)載也增加n倍，為固定時(shí)間的情形； 3. G(n)>n，計(jì)算負(fù)載的增加情況比存儲(chǔ)器增加快，會(huì)有較高的加速比。比較三種加速比，對(duì)于相同的處理機(jī)數(shù)量，有：在受限于存儲(chǔ)器的加速比模型下，負(fù)載和執(zhí)行時(shí)間隨系統(tǒng)中處理機(jī)數(shù)目n變化的情況如下圖：WsWpWsWpWsWpWsWpWorkloadN1234ExecutionTimeNTsTp1TsTp2TsTp3TsTp4規(guī)模擴(kuò)展的工作負(fù)載執(zhí)行時(shí)間稍有增加受限于存儲(chǔ)器的加速比模型下的負(fù)載和執(zhí)行時(shí)間情況例： n維矩陣乘法：A*B=C，其中A、B、C都是n*n的方陣。為得到C的每一個(gè)元素需要進(jìn)行n次乘法、n次加法，所以總的計(jì)算量為：（n+n)*n2=2n3。需要的存儲(chǔ)量為3n2（兩個(gè)源矩陣，一個(gè)結(jié)果矩陣）。如果n臺(tái)計(jì)算機(jī)組成多計(jì)算機(jī)系統(tǒng)，則存儲(chǔ)容量擴(kuò)大n倍，那么矩陣的維數(shù)（原來(lái)為n)也可以增加了，設(shè)為N倍，那么加速比為多少？

解：存儲(chǔ)容量變?yōu)椋簄M=n*3n2=3n3，而N維需要的存儲(chǔ)量為3N2，計(jì)算量變?yōu)?N3，則有：

4.并行計(jì)算的應(yīng)用模型隨機(jī)器規(guī)模的增大，工作負(fù)載增長(zhǎng)的模式如下圖：工作負(fù)載（問題規(guī)模）nθ（指數(shù)）γ（線性）β（亞線性）α（常數(shù)）上圖中：

采用受限于存儲(chǔ)器的加速比模型中給出的公式，

θ曲線對(duì)應(yīng)的G(n)=n1.5

γ曲線對(duì)應(yīng)的G(n)=n

β曲線對(duì)應(yīng)的G(n)=0.5n

α曲線對(duì)應(yīng)的G(n)=1

則有加速比公式:

給定一個(gè)程序，假設(shè)Ws/Wp=0.4，那么效率為：相應(yīng)的處理器數(shù)目—效率曲線如下圖：效率nθ（指數(shù)）γ（線性）β（亞線性）α（常數(shù)）結(jié)論： 1.如果工作負(fù)載（問題規(guī)模）保持不變，那么效率E隨機(jī)器規(guī)模的增大而迅速下降，其原因是開銷h比機(jī)器規(guī)模增加得快，為了使效率保持在一定的水平上，我們可以按比例增大機(jī)器規(guī)模和問題規(guī)模。

2.如果工作負(fù)載按指數(shù)增長(zhǎng)模式，效率要保持恒定或保持良好的加速比，必須使問題規(guī)模猛增才行，這樣就會(huì)超過存儲(chǔ)器或I/O限制，而問題規(guī)模只允許在計(jì)算機(jī)存儲(chǔ)器可用的限度以內(nèi)增長(zhǎng)。并行計(jì)算機(jī)的應(yīng)用模型如下圖：通信界限存儲(chǔ)器界限受限于存儲(chǔ)器模型工作負(fù)載（問題規(guī)模）機(jī)器規(guī)模固定負(fù)載模型固定時(shí)間模型第二章加速比性能模型與可擴(kuò)展性分析 2.1加速比性能分析

2.2可擴(kuò)展性分析 2.2.1可擴(kuò)展性

2.2.2可擴(kuò)展性分析2.2可擴(kuò)展性分析

2.2.1可擴(kuò)展性 1.可擴(kuò)展性與可編程性增加可擴(kuò)展性增加可編程性分布存儲(chǔ)的消息傳遞型多計(jì)算機(jī)共享存儲(chǔ)型多處理機(jī)理想并行計(jì)算機(jī) 2.可擴(kuò)展性指標(biāo) 機(jī)器規(guī)模（n） 時(shí)鐘頻率（f） 問題規(guī)模（s） CPU時(shí)間（T） I/O需求（d） 存儲(chǔ)容量（m） 通信開銷（h） 計(jì)算機(jī)價(jià)格（c） 程序設(shè)計(jì)開銷（p） 3.可擴(kuò)展性的直觀定義

對(duì)任意數(shù)量（n）的處理機(jī)和任意規(guī)模（s）的問題，若所有算法的系統(tǒng)效率E=1，則系統(tǒng)是可擴(kuò)展的。 4.規(guī)?？蓴U(kuò)展性

系統(tǒng)性能隨處理機(jī)數(shù)量線性增長(zhǎng)，包括：

處理速度和效率 存儲(chǔ)速度和容量 互連帶寬和時(shí)延 I/O速度和容量 軟件開銷規(guī)?？蓴U(kuò)展性與空間局部性、時(shí)間局部性以及部件瓶頸都有關(guān)系。例子：

CrayY-MP：16臺(tái)處理機(jī)范圍可伸縮

CM-2： 8K-64K臺(tái)處理機(jī)范圍可伸縮

CM-5： 1024-16K臺(tái)處理機(jī)范圍可伸縮

KSR-1： 8-1088臺(tái)處理機(jī)范圍可伸縮 5.換代（時(shí)間）可擴(kuò)展性

對(duì)系統(tǒng)各部分更換成新技術(shù)后，性能隨之易擴(kuò)展，要求算法、S/W均能兼容運(yùn)行。 6.問題可擴(kuò)展性

問題規(guī)模擴(kuò)大時(shí)，系統(tǒng)仍能很好的運(yùn)行，或說(shuō)問題規(guī)模擴(kuò)展到很大時(shí)，系統(tǒng)能在給定粒度下高效運(yùn)行。

2.2.2可擴(kuò)展性 1.恒等效率概念（Isoefficiency）

恒等效率定義為一個(gè)并行算法在并行計(jì)算機(jī)上實(shí)現(xiàn)時(shí)，為保持效率E固定所需的工作負(fù)載與機(jī)器規(guī)模n的相對(duì)關(guān)系。 設(shè):

W=W（s）為工作負(fù)載，

h=h（s，n）為通信開銷，它隨s、n增加而增大。其中，s為問題規(guī)模，n為機(jī)器規(guī)模。 則效率可以表示為：

問題的關(guān)鍵在于W（s）與h（s，n）之間的相對(duì)增長(zhǎng)速度。機(jī)器規(guī)模一定，開銷h的增長(zhǎng)比工作負(fù)載W要慢。因而，對(duì)一定規(guī)模的機(jī)器來(lái)說(shuō)，效率會(huì)隨問題規(guī)模增大而提高。所以，假若工作負(fù)載W隨機(jī)器規(guī)模適當(dāng)增加，那么就有希望保持效率不變。

對(duì)于已知的算法來(lái)說(shuō)，為了保持恒定的效率，工作負(fù)載W可能需要對(duì)n以多項(xiàng)式或指數(shù)規(guī)律增長(zhǎng)。不同的算法可能需要不同的工作負(fù)載增長(zhǎng)速率以便在n增加時(shí)保持效率不致下降。 一般并行算法的恒定效率函數(shù)是n的多項(xiàng)式函數(shù)，即它們?yōu)镺（nk），k1。n的冪越小，并行系統(tǒng)的可擴(kuò)展性越大（系統(tǒng)包括算法和結(jié)構(gòu)的組合）。

2.恒等效率函數(shù)并行程序執(zhí)行時(shí)間Tp=(T1+T0)/p， 其中，T1為總工作負(fù)載串行執(zhí)行時(shí)間，T0為多節(jié)點(diǎn)總通信延時(shí)，p為節(jié)點(diǎn)數(shù)。那么，加速比為：

而T1=Wtc，W為以操作次數(shù)計(jì)算的總工作負(fù)載，tc為每個(gè)操作的平均執(zhí)行時(shí)間。如前面所述，工作負(fù)載W與開銷h均可以表示成n與s的函數(shù)，所以，效率也可以表示如下：為了使E保持不變，工作負(fù)載W（s）應(yīng)該與開銷h(s,n)成比例增長(zhǎng)，由此可以得出以下條件：如果工作負(fù)載W(s)與fE(n)一樣快的增長(zhǎng)，那么已知算法結(jié)構(gòu)組合就能使效率保持恒定。這個(gè)結(jié)論和前面的結(jié)論是一致的。此時(shí)，W(s)與fE(n)是相同的，只要求出了W(s)的數(shù)量級(jí)，就可知道fE(n)了。為了得到恒等效率，只要使W(s)與h(s,n)同一個(gè)數(shù)量級(jí)就可以了。例1： 矩陣乘法的W(s)=O（s3）（其中s為維數(shù)），還設(shè)h（s，n）=O（nlogn+s2n0.5）。求fE(n)。

解：要滿足W與h同數(shù)量級(jí)的條件，需要在兩式中選出大的：例2：

W(s)=O（s3）， h（s，n）=O（nlogn+s2n1/3logn）。求fE(n)。

解：比較兩個(gè)式子，選出較大的：例3：

W(s)=O（s3）， h（s，n）=O（nlogn+s3）。求fE(n)。

解：第二個(gè)式子顯然成立，故例4：在n臺(tái)處理機(jī)網(wǎng)格和超立方體計(jì)算機(jī)上分別計(jì)算1維s點(diǎn)的FFT，其工作負(fù)載W(s)=O（slogs），已知：

超立方體計(jì)算機(jī)上：h1（s，n）=O（nlogn+slogn），

網(wǎng)格計(jì)算機(jī)上：h2（s，n）=O（nlogn+sn0.5），

問哪一種擴(kuò)展性好？

解：對(duì)超立方體計(jì)算機(jī)，對(duì)網(wǎng)格計(jì)算機(jī)， 為了得到恒等效率，對(duì)網(wǎng)格計(jì)算機(jī)，它的負(fù)載必須以指數(shù)增長(zhǎng)，而超立方體的負(fù)載的增長(zhǎng)不超過多項(xiàng)式增長(zhǎng)速度，

結(jié)論：超立方體具有更好的可擴(kuò)展性。 對(duì)于相同的效率E，設(shè)k=2，它們的機(jī)器規(guī)模-問題規(guī)模曲線可能如下圖所示：?jiǎn)栴}規(guī)模s機(jī)器規(guī)模n網(wǎng)格超立方體第三章互連與通信 3.1互連網(wǎng)絡(luò)的作用 3.2靜態(tài)網(wǎng)絡(luò) 3.3動(dòng)態(tài)網(wǎng)絡(luò) 3.4通信問題3.1互連網(wǎng)絡(luò)的作用定義：由開關(guān)元件按一定拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)以實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或多個(gè)功能部件間的相互連接。操作方式： 同步通信（SynchronousCommunication) 異步通信(AsynchronousCommunication)控制策略：

集中控制(Centralizedcontrol) 分布控制(Distributedcontrol)交換方式： 電路交換(Circuitswitching) 分組交換(Packetswitching)

Wormhole交換(Wormholeswitching)蟲洞交換，數(shù)據(jù)包被分成許多小的流量控制單位（flit），在網(wǎng)絡(luò)中以流水的方式傳送。

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：

靜態(tài)網(wǎng)絡(luò)(Staticnetwork) 動(dòng)態(tài)網(wǎng)絡(luò)(Dynamicnetwork)第三章互連與通信

3.1互連網(wǎng)絡(luò)的作用

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

3.2.1靜態(tài)網(wǎng)絡(luò)的特點(diǎn)與指標(biāo) 3.2.2典型的靜態(tài)網(wǎng)絡(luò) 3.3動(dòng)態(tài)網(wǎng)絡(luò) 3.4通信問題3.2靜態(tài)網(wǎng)絡(luò)

3.2.1靜態(tài)網(wǎng)絡(luò)的特點(diǎn)與指標(biāo)

1.靜態(tài)網(wǎng)絡(luò)的特點(diǎn)

靜態(tài)網(wǎng)絡(luò)由點(diǎn)—點(diǎn)直接相連而成，這種連結(jié)方式在程序執(zhí)行過程中不會(huì)改變。

如果用圖來(lái)表示，結(jié)點(diǎn)代表開關(guān)，邊代表通信鏈路，則

(1)結(jié)點(diǎn)間的鏈路無(wú)源，不能重構(gòu)

(2)開關(guān)元件與處理機(jī)相連

(3)不直接相連結(jié)點(diǎn)間的通信需通過中間結(jié)點(diǎn)中轉(zhuǎn)。 2.靜態(tài)網(wǎng)絡(luò)的指標(biāo)

結(jié)點(diǎn)度：與結(jié)點(diǎn)相連接的邊（鏈路或通道）數(shù)，表示節(jié)點(diǎn)所需要的I/O端口數(shù)，模塊化要求結(jié)點(diǎn)度保持恒定。根據(jù)通道到結(jié)點(diǎn)的方向，結(jié)點(diǎn)度可以進(jìn)一步表示為：

結(jié)點(diǎn)度=入度+出度 其中入度是進(jìn)入結(jié)點(diǎn)的通道數(shù)，出度是從結(jié)點(diǎn)出來(lái)的通道數(shù)。

距離：與兩個(gè)結(jié)點(diǎn)之間相連的最少邊數(shù)。

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

網(wǎng)絡(luò)規(guī)模：網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)，表示該網(wǎng)絡(luò)功能連結(jié)部件的多少。

等分寬度：某一網(wǎng)絡(luò)被切成相等的兩半時(shí)，沿切口的最小邊數(shù)稱為該網(wǎng)絡(luò)的等分寬度。

結(jié)點(diǎn)間的線長(zhǎng)：兩個(gè)結(jié)點(diǎn)間的線的長(zhǎng)度。

對(duì)稱性：從任何結(jié)點(diǎn)看，拓?fù)浣Y(jié)構(gòu)都一樣，這種網(wǎng)絡(luò)實(shí)現(xiàn)和編程都很容易。 結(jié)點(diǎn)是否同構(gòu)。 通道是否有緩沖。

3.2.2典型的靜態(tài)網(wǎng)絡(luò)

1.線性陣列 對(duì)N個(gè)結(jié)點(diǎn)的線性陣列，有N-1條鏈路，直徑為N-1（任意兩點(diǎn)之間距離的最大值），度為2，不對(duì)稱，等分寬度為1。 N很大時(shí)，通信效率很低。

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

線性陣列：允許不同的源結(jié)點(diǎn)和目的結(jié)點(diǎn)對(duì)并發(fā)使用系統(tǒng)的不同部分。

總線：通過切換與其相連的許多結(jié)點(diǎn)來(lái)實(shí)現(xiàn)時(shí)分特性，同一時(shí)刻只有一對(duì)結(jié)點(diǎn)在傳送數(shù)據(jù)。

2.環(huán)對(duì)N個(gè)結(jié)點(diǎn)的環(huán)，考慮相鄰結(jié)點(diǎn)數(shù)據(jù)傳送方向：

雙向環(huán)：鏈路數(shù)為N，直徑N/2，度為2，對(duì)稱，等分寬度為2。比如KSR-1（1990）。

單向環(huán)：鏈路數(shù)為N，直徑N-1，度為2，對(duì)稱，等分寬度為2。 3.帶弦環(huán)對(duì)上圖中12個(gè)結(jié)點(diǎn)的帶弦雙向環(huán)，

結(jié)點(diǎn)度為3：鏈路數(shù)為18，直徑4（比如紅色結(jié)點(diǎn)），度為3，不對(duì)稱，等分寬度為2。

結(jié)點(diǎn)度為4：鏈路數(shù)為24，直徑3（比如紅色結(jié)點(diǎn)），度為4，對(duì)稱，等分寬度為8。度為3的帶弦環(huán)度為4的帶弦環(huán) 4.全鏈接 全鏈接是帶弦環(huán)的一種特殊情形。全鏈接中的每個(gè)結(jié)點(diǎn)和其他結(jié)點(diǎn)之間都有單一的直接鏈路。如下圖中8個(gè)結(jié)點(diǎn)的全鏈接： 有28條鏈路，直徑為1，度為7，對(duì)稱，等分寬度為16。 5.樹形

4層的二叉樹 一棵K層完全二叉樹應(yīng)有N=2K-1個(gè)結(jié)點(diǎn)，大多數(shù)結(jié)點(diǎn)的結(jié)點(diǎn)度為3，直徑為2（K-1）（即右邊任意一個(gè)葉子結(jié)點(diǎn)到左邊任意一個(gè)葉子結(jié)點(diǎn)）。不對(duì)稱，等分度為1。 由于結(jié)點(diǎn)度為常數(shù)，所以樹是一種可擴(kuò)展的系統(tǒng)結(jié)構(gòu)。 樹形的擴(kuò)展：

帶環(huán)樹二叉胖樹 這兩種結(jié)構(gòu)都可以緩解根結(jié)點(diǎn)的瓶頸問題。 6.星形

星形實(shí)際上是一種二層樹（如右圖）。有N個(gè)結(jié)點(diǎn)的星形網(wǎng)絡(luò)，有N-1條鏈路，直徑為2，最大結(jié)點(diǎn)度為N-1，非對(duì)稱，等分寬度為1。 7.網(wǎng)格

有N個(gè)結(jié)點(diǎn)的rr網(wǎng)格（其中 )，有2N-2r條鏈路，直徑為2（r-1)，結(jié)點(diǎn)度為4，非對(duì)稱，等分寬度為r。 網(wǎng)格的變形：

a.Illiac網(wǎng)

有N個(gè)結(jié)點(diǎn)的rr網(wǎng)格（其中 )，有2N條鏈路，直徑為r-1，結(jié)點(diǎn)度為4。

b.環(huán)形網(wǎng)（2D—Torus）

有N個(gè)結(jié)點(diǎn)的rr網(wǎng)（其中 )，有2N條鏈路，直徑為2r/2，結(jié)點(diǎn)度為4，對(duì)稱。

c.搏動(dòng)式陣列（SystolicArray）

8.超立方體0-立方體1-立方體2-立方體3-立方體4-立方體 一個(gè)n-立方體由N=2n個(gè)結(jié)點(diǎn)構(gòu)成，它們分布在n維上，每維有兩個(gè)結(jié)點(diǎn)。直徑為n，結(jié)點(diǎn)度為n，對(duì)稱。由于結(jié)點(diǎn)度隨維數(shù)線性增加，所以超立方體不是一種可擴(kuò)展結(jié)構(gòu)。

例子：

Intel的iPSC/1、iPSC/2、nCUBE 9.帶環(huán)立方體 一個(gè)帶環(huán)n-立方體由N=2n個(gè)結(jié)點(diǎn)環(huán)構(gòu)成，每個(gè)結(jié)點(diǎn)環(huán)是一個(gè)有n個(gè)結(jié)點(diǎn)的環(huán)，所以結(jié)點(diǎn)總數(shù)為n2n個(gè)。直徑通常為2n，結(jié)點(diǎn)度為3，對(duì)稱。帶環(huán)3-立方體 10.k元n-立方體網(wǎng)絡(luò)4元3-立方體（隱藏的結(jié)點(diǎn)與連接沒有畫出) 在一個(gè)k元n-立方體網(wǎng)絡(luò)中，結(jié)點(diǎn)的數(shù)目N=kn，即： 其中，k稱為基數(shù)（radix），n稱為維數(shù)（dimension）。

k元n-立方體的結(jié)點(diǎn)可以用基數(shù)為k的n位地址A=a0a1a2...

an來(lái)表示，其中ai代表第i維結(jié)點(diǎn)的位置。 傳統(tǒng)的環(huán)網(wǎng)等價(jià)于4元2-立方體。第三章互連與通信

3.1互連網(wǎng)絡(luò)的作用 3.2靜態(tài)網(wǎng)絡(luò)

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

3.3.1互連函數(shù) 3.3.2多級(jí)互聯(lián)網(wǎng)絡(luò) 3.4通信問題3.3動(dòng)態(tài)網(wǎng)絡(luò) 特點(diǎn)： 網(wǎng)絡(luò)的開關(guān)元件有源，鏈路可通過設(shè)置這些開關(guān)的狀態(tài)來(lái)重構(gòu)。 只有在網(wǎng)絡(luò)邊界上的開關(guān)元件才能與處理機(jī)相連。

3.3.1互連函數(shù)

排列：N個(gè)數(shù)的每一種有確定次序的放置方法叫做一個(gè)N排列。

置換：把一個(gè)N排列變成另一個(gè)N排列的變換叫做N階置換。 在有N個(gè)輸入端和N個(gè)輸出端的網(wǎng)絡(luò)中，輸入端和輸出端的連接關(guān)系可以用置換來(lái)表示（輸入端與輸出端一一對(duì)應(yīng)）。

一些常見的置換方式可以用下面的函數(shù)表示：1.恒等函數(shù)其中，Xn-1Xn-2

Xk

X0是PE的地址（通常為二進(jìn)制）。n為3時(shí)的恒等函數(shù)的連接情形如下：0000010100111001011101110000010100111001011101112.方體函數(shù)（cube0，cube1，…，cuben-1)方體函數(shù)是由n個(gè)互連函數(shù)組成，其中0kn。比如，n為3時(shí)，3-立方體各結(jié)點(diǎn)地址如下：YZX010011110000111001100101000001010011100101110111000001010011100101110111Cube0:01234567000001010011100101110111000001010011100101110111Cube1:01234567000001010011100101110111000001010011100101110111Cube2:012345670000010100111001011101110000010100111001011101113.洗牌函數(shù)01234567洗牌函數(shù)的變形：

a.均勻洗牌（Shuffle-Exchange)

是洗牌函數(shù)與Cube0函數(shù)的組合。01234567：Cube0：洗牌b.第k個(gè)子洗牌即最低k位循環(huán)左移一位。c.第k個(gè)超洗牌即最高k-1位循環(huán)左移一位。0000010100111001011101110000010100111001011101114.逆洗牌函數(shù)012345670000010100111001011101110000010100111001011101115.蝶式012345676.PM2I函數(shù)（加減2i）

共有2n個(gè)互連函數(shù)，對(duì)N個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)為例1：

N=8（8個(gè)結(jié)點(diǎn)），則n=log28=3，所以：i=0，1，2；j=0，1，…，7。

6個(gè)PM2I函數(shù)如下：PM2+0: (01234567）01234567PM2-0: (76543210）01234567PM2+1: (0246）（1357）01234567PM2-1: (6420）（7531）01234567PM2

2: (04）（15）（26）（37）0123456701234567例2：89101112131415上面的網(wǎng)絡(luò)可以用四個(gè)PM2I函數(shù)表示。PM2+0: (012…15)PM2-0: (151413…0)

PM2

2: (04）（15）（26）（37） (48）（59）（610）（711） (812）（913）（1014）（1115） (120）（131）（142）（153）

3.3.2多級(jí)互連網(wǎng)絡(luò)

1.多級(jí)網(wǎng)絡(luò)的三要素

（1）開關(guān)單元：a個(gè)輸入a個(gè)輸出的開關(guān)單元記做aa的開關(guān)單元，其中，a是2的整數(shù)倍。常見的有2

2、44、88等。

根據(jù)開關(guān)單元功能的多少，2

2又可以分為兩功能和四功能開關(guān)。如下圖所示：0101直送0101交叉0101上播0101下播

（2）級(jí)間互連模式（InterStageConnection）： 均勻洗牌、蝶式、多路洗牌（比如四路洗牌即是把牌平均分成4份，然后4堆分別進(jìn)行均勻洗牌）、縱橫開關(guān)（CrossSwitch)及立方體連結(jié)等。 （3）控制方式

級(jí)控制：每級(jí)只有一個(gè)控制信號(hào) 單元控制：每個(gè)開關(guān)一個(gè)控制信號(hào) 部分級(jí)控制：幾個(gè)開關(guān)合用一個(gè)控制信號(hào)

2.Ω網(wǎng)0123456701234567第0級(jí)第1級(jí)第2級(jí) Ω網(wǎng)的特點(diǎn)：

開關(guān)單元：22四功能開關(guān)

ISC：洗牌變換+恒等變換

控制方式：采用單元控制方式。當(dāng)目的地址編碼從高位開始的第i位（從0開始）為0時(shí)，第i級(jí)的22開關(guān)的輸入端與上輸出端連接，否則輸入端與下輸出端連接。 例子： UIUC的Cedar IBM的RP3 NYU的Ultracomputer0123456701234567第0級(jí)第1級(jí)第2級(jí)

無(wú)阻塞的實(shí)現(xiàn)置換

π1=（07642）（13）（5）0123456701234567第0級(jí)第1級(jí)第2級(jí) 置換π2=（06473）（15）（2）

在開關(guān)F、G、H、I和J上發(fā)生阻塞FGHJI Ω網(wǎng)的特點(diǎn)(2)：

并不是所有的置換在Ω網(wǎng)中一次通過便可以實(shí)現(xiàn)。

Ω網(wǎng)是阻塞網(wǎng)絡(luò)：出現(xiàn)沖突時(shí)，可以采用幾次通過的方法來(lái)解決沖突。0123456701234567第0級(jí)第1級(jí)第2級(jí)

Ω網(wǎng)的廣播功能：

001

8個(gè)輸出端01第1級(jí)44開關(guān)構(gòu)成的Ω網(wǎng)：多路洗牌

如16輸入4路洗牌：網(wǎng)路級(jí)數(shù)為log416=2

234567891011121314150123456789101112131415第0級(jí) Ω網(wǎng)的特點(diǎn)(3)：

當(dāng)采用kk開關(guān)元件時(shí)，則可以定義k路洗牌函數(shù)來(lái)構(gòu)造更大的級(jí)數(shù)為logkn的Ω網(wǎng)絡(luò)。

3.蝶式網(wǎng)絡(luò)（Butterflyswitchnetwork）

蝶式網(wǎng)絡(luò)的開關(guān)不允許廣播功能，它實(shí)際上是Omega網(wǎng)的一個(gè)子集。 兩級(jí)6464的蝶式網(wǎng)絡(luò)如下圖所示：它采用16個(gè)88交叉開關(guān)構(gòu)成，兩級(jí)間采用8路洗牌連接。8888880...7888888第1級(jí)第0級(jí)8...1556...63.........078155663........................兩級(jí)6464的蝶式網(wǎng)絡(luò)

4.其他連接方式

總線 交叉開關(guān)第三章互連與通信 3.1互連網(wǎng)絡(luò)的作用 3.2靜態(tài)網(wǎng)絡(luò) 3.3動(dòng)態(tài)網(wǎng)絡(luò)

3.4通信問題

3.4.1基本術(shù)語(yǔ)與性能指標(biāo) 3.4.2尋徑算法 3.4.3虛擬通道與死鎖 3.4.4包沖突的解決 3.4.5維序?qū)? 3.4.6通信模式3.4通信問題

3.4.1基本術(shù)語(yǔ)與性能指標(biāo) 1.消息、包和片

消息（Message）：是在多計(jì)算機(jī)系統(tǒng)的處理結(jié)點(diǎn)之間傳遞包含數(shù)據(jù)和同步消息的信息包。它是一種邏輯單位，可由任意數(shù)量的包構(gòu)成。

包（Packet）：包的長(zhǎng)度隨協(xié)議不同而不同，它是信息傳送的最小單位，64-512位。 片（Flit）：片的長(zhǎng)度固定，一般為8位。 它們的相互關(guān)系如下圖：包……消息包片據(jù)片頭片尾片……順序號(hào)數(shù)bbbbbbbb 2.互連網(wǎng)絡(luò)

互連網(wǎng)絡(luò)用來(lái)在多計(jì)算機(jī)系統(tǒng)的處理結(jié)點(diǎn)之間傳遞消息。互連網(wǎng)絡(luò)的描述：

拓?fù)洌═opology） 尋徑算法（Routing） 流控制（FlowControl） 互連網(wǎng)絡(luò)性能的兩個(gè)重要指標(biāo)： 傳輸時(shí)延（TransmissionLatency） 吞吐量（Throughput） 3.傳輸時(shí)延與吞吐量

一個(gè)消息的傳輸時(shí)延：從它在源結(jié)點(diǎn)進(jìn)行發(fā)送初始化到它在目的結(jié)點(diǎn)完整的被接收所耗費(fèi)的時(shí)間。

一個(gè)網(wǎng)絡(luò)的傳輸時(shí)延：在一定條件下發(fā)送消息的平均時(shí)延。 網(wǎng)絡(luò)的吞吐量：?jiǎn)挝粫r(shí)間內(nèi)網(wǎng)絡(luò)所能傳輸?shù)南?shù)目或長(zhǎng)度。 4.傳輸時(shí)延的公式

其中，Ts稱為建立時(shí)延，Tn稱為網(wǎng)絡(luò)時(shí)延，Tb稱為阻塞時(shí)延。 它們具體定義如下：

建立時(shí)延Ts：一個(gè)消息在源結(jié)點(diǎn)和目的結(jié)點(diǎn)上裝配和分解、從存儲(chǔ)器拷貝到通信緩沖區(qū)以及正確性驗(yàn)證等所耗費(fèi)的時(shí)間。它和機(jī)器本身的硬件、軟件技術(shù)有關(guān)。

其中：

Tss稱為源結(jié)點(diǎn)時(shí)延：從發(fā)送進(jìn)程開始消息發(fā)送初始化到消息的頭部進(jìn)入網(wǎng)絡(luò)所經(jīng)歷的時(shí)間。

Tsd稱為目的結(jié)點(diǎn)時(shí)延：從消息的尾部到達(dá)目的結(jié)點(diǎn)到消息完全被接收進(jìn)程接收所經(jīng)歷的時(shí)間。

網(wǎng)絡(luò)時(shí)延Tn：消息頭部從源結(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)到消息的尾部到達(dá)目的結(jié)點(diǎn)的時(shí)間間隔。

其中：

TpD稱為結(jié)點(diǎn)時(shí)延：其中Tp是消息在它所經(jīng)過的路徑上的每個(gè)中間結(jié)點(diǎn)上的平均時(shí)延，D為中間結(jié)點(diǎn)或源結(jié)點(diǎn)與目的結(jié)點(diǎn)之間的距離。

L/B稱為線路時(shí)延：其中L為消息長(zhǎng)度，B為結(jié)點(diǎn)之間的通道帶寬。

阻塞時(shí)延Tb：消息傳遞過程中其他所有可能的時(shí)延（主要原因是資源沖突）。 5.網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

第一代并行計(jì)算機(jī)：HyperCube

第二代并行計(jì)算機(jī)：n—Mesh 6.網(wǎng)絡(luò)的尋徑算法

決定發(fā)送一個(gè)消息到其目的地所經(jīng)過的路徑。 可以分為：

最短路徑算法 非最短路徑算法 或者：

確定性算法：路徑的選擇只依賴于它所發(fā)送的消息的源結(jié)點(diǎn)和目的結(jié)點(diǎn)。

可適應(yīng)算法：消息從結(jié)點(diǎn)A到結(jié)點(diǎn)B可以由幾條不同的路徑。 7.網(wǎng)絡(luò)的流控制

當(dāng)一個(gè)消息在網(wǎng)絡(luò)中沿著某條路徑傳送時(shí)，互連網(wǎng)絡(luò)如何來(lái)為它分配通道和緩沖器。

3.4.2尋徑算法 我們介紹四種尋徑方式： 存儲(chǔ)轉(zhuǎn)發(fā)（Store-and-Forward） 虛擬直通（Virtualcutthrough） 線路交換（CircuitSwitching） Wormhole交換（WormholeSwitching) 1.存儲(chǔ)轉(zhuǎn)發(fā)

當(dāng)一個(gè)消息到達(dá)中間結(jié)點(diǎn)A時(shí)，A把整個(gè)消息放入其通信緩沖器中，然后在尋徑算法的控制下選擇下一個(gè)相鄰結(jié)點(diǎn)B，當(dāng)從A到B的通道空閑并且B的通信緩沖器可用時(shí)，把消息從A發(fā)向B。缺點(diǎn)：

每個(gè)結(jié)點(diǎn)必須對(duì)整個(gè)消息進(jìn)行緩沖，緩沖器較大。 網(wǎng)絡(luò)時(shí)延與發(fā)送消息所經(jīng)歷的結(jié)點(diǎn)數(shù)成正比 2.虛擬直通

中間結(jié)點(diǎn)沒有必要等到整個(gè)消息全部被緩沖后再作出路由選擇，只要消息的目的信息域可用后，就可以作出路由選擇。

其中，Lh為消息頭部開始到其目的信息域的長(zhǎng)度，顯然有L>>Lh，所以D的影響比較小。 而當(dāng)通向下一結(jié)點(diǎn)的通道忙或結(jié)點(diǎn)的緩沖器非空閑時(shí)，必須把整個(gè)消息緩沖起來(lái)，這時(shí)和存儲(chǔ)轉(zhuǎn)發(fā)一樣。 3.線路開關(guān)

在傳遞一個(gè)消息之前，就為它建立一條從源結(jié)點(diǎn)到目的結(jié)點(diǎn)的物理通道。在傳遞的全部過程中，線路的每一段都被占用，當(dāng)消息的尾部經(jīng)過網(wǎng)絡(luò)后，整條物理鏈路才被廢棄。

其中，Lc是為消息建立物理通路所傳遞的控制信息的長(zhǎng)度。當(dāng)L>>Lc時(shí)，D的影響較小。

缺點(diǎn)：

物理通道非共享 傳輸過程中物理通道一直被占用 4.Wormhole

Dally于1986年提出。 首先把一個(gè)消息分成許多片，消息的頭片包含了這個(gè)消息的所有尋徑信息。尾片是一個(gè)其最后包含了消息結(jié)束符的片。中間的片均為數(shù)據(jù)片。 片是最小信息單位。每個(gè)結(jié)點(diǎn)上只需要緩沖一個(gè)片就能滿足要求。 用一個(gè)頭片直接開辟一條從輸入鏈路到輸出鏈路的路徑的方法來(lái)進(jìn)行操作。每個(gè)消息中的片以流水的方式在網(wǎng)絡(luò)中向前“蠕動(dòng)”。每個(gè)片相當(dāng)于Worm的一個(gè)節(jié)，“蠕動(dòng)”以節(jié)為單位順序的向前爬行。 當(dāng)消息的頭片到達(dá)一個(gè)結(jié)點(diǎn)A的尋徑器后，尋徑器根據(jù)頭片的尋徑信息立即做出路由選擇：

（1）如果所選擇的通道空閑而且所選擇的結(jié)點(diǎn)B的通信緩沖器可用，那么這個(gè)頭片就不必等待，直接通過結(jié)點(diǎn)A傳向下一個(gè)結(jié)點(diǎn)B；隨后的其它片跟著相應(yīng)的向前“蠕動(dòng)