高等计算机系统结构课件

高等電腦的核心技術——並行處理 1.1什麼是並行處理

1.1.1並行處理定義 1.1.2並行性級別 1.2為什麼要開發並行處理技術 1.3並行處理電腦結構沿革 1.4其他並行處理電腦技術1.1什麼是並行處理

1.1.1並行處理定義

並行處理用是指同時對多個任務或多條指令、或同時對多個數據項進行處理。 完成此項處理的電腦系統稱為並行處理電腦系統。

同時性（simultaneity）——兩個或多個事件在同一時刻發生。

併發性（concurrency）——兩個或多個事件在同一時間間隔內發生。

流水特性（pipelining）——在一個重疊的時間內所發生的流水事件。

1.1.2並行性級別

粒度（granularity）：衡量一個軟體進程的計算量的度量。最簡單的是指此程式段中的指令數。分細、中、粗三種。 按粒度的不同，並行性級別可以分為指令級、迴圈級、過程級、副程式級和作業級等不同的層次。它們對應的計算粒度可以為細粒度、中粒度和粗粒度。如下： 1.指令級並行

典型細粒度，一般少於20條指令。借助優化編譯器自動檢測並行性，將源代碼變成運行時系統能識別的並行形式。 2.迴圈級並行

典型迴圈含少於500條指令，由於有些迴圈操作在連續迭代中並不相關，易於向量化，是在並行機或向量機上運行的最優程式結構。遞歸迴圈的並行化比較困難。向量處理由優化編譯器在迴圈級開發，仍屬於細粒度計算。 3.過程級並行

中粒度並行，指令少於2000條，分析過程間的並行性比細粒度要困難。有時需要重新設計程式，並要編譯器的支持。SPMD、多任務處理屬於這一層。 4.副程式級並行

（粗）中粒度並行，幾千條指令，常在messagepassing多電腦上以SPMD或MPMD方式執行。並行性主要由演算法設計人員與程式員開發。 5.作業級並行

粗粒度並行，數萬條指令，常由加載程式和操作系統處理這類並行性，靠演算法有效性來保證。一般說來： 細粒度：用並行化或向量化編譯器來開發，共用變數通信支持。 中粒度：靠程式員和編譯器一起開發，共用變數通信。 粗粒度：取決於操作系統和演算法的效率，消息傳遞通信。 例子：共用存儲型多處理機上執行：

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

假設：L2，L4，L6每行要用一個機器週期。 L1，L3，L5，L7所需時間可以忽略。 所有數組已經裝入主存，程式已裝入Cache中（取指令和加載數據可以忽略不計）。 忽略匯流排爭用或記憶體訪問衝突。 上面的程式實際上把數組B(I)和C(I)相加，最後得到一個總和。

共用存儲多處理機結構如下圖：P1P2……Pm系統互連I/OSM1……SMm處理機共用記憶體 在單機系統中，2N個週期可以完成上述的操作：

I迴圈中執行N次獨立迭代需要N個週期；

J迴圈中執行N次遞歸迭代也需要N個週期。 在共用存儲型的多處理機系統上： 假設有M臺處理機，可以將迴圈分成M段，每段有L=N/M個元素。 代碼如下所示：

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迴圈可以在L個週期中完成； 分段的J迴圈在L個週期中產生M個部分和。 所以產生所有的M個部分和共需要2L個週期（還需要將這些部分和合併）。 假設經過共用記憶體的處理機之間的每次通信操作需要k個週期。 設N=32，M=8，則經過2L（即8個週期）後在8臺處理機上各有一個部分和，還需要8個數相加。 為了合併部分和，可以設計一個l層的二進位加法樹，其中l=log2M，加法樹用l(k+1)個週期從樹葉到樹根順序合併M個部分和，如下：

二進位加法樹： 所以，多處理機系統需要 才能得到最終的結果。 假定數組中有N=220個元素，順序執行需要2N=221個機器週期，假設機器間通信的開銷平均值為k=200個週期，則在M=256臺處理機的並行執行需要：第一章高等電腦的核心技術——並行處理 1.1什麼是並行處理

1.2為什麼要開發並行處理技術 1.3並行處理電腦結構沿革 1.4其他並行處理電腦技術1.2為什麼要開發並行處理技術

對單用戶，可以提高加速比（SpeedupOriented)； 對多用戶，可以提高吞吐率（ThroughputOriented).

對不同的需求我們可以做需求分析如下： 1.天氣預報 1990年10次颱風登陸，福建、浙江兩省損失79億元，死亡950餘人。 天氣預報模式為非線性偏微分方程，預報颱風暴雨過程，計算量為1014—1016次浮點運算，需要10GFlops—100GFlops的巨型機。

用途：局部災害性天氣預報。 2.石油工業

地震勘探資料處理 油藏數值模擬 測井資料處理 地震勘探由數據採集、數據處理和資料解釋三階段組成。 目前採用的三維地震勘探比較精確的反映地下情況，但數據量大，處理週期長。

100平方公里的三維勘探面積，道距25米，60次覆蓋，6秒長記錄，2毫秒採樣，一共採集2.881010個數據，約為116GB。 疊加後數據為4.8108個數據。用二維疊前深度偏移方法精確的產生地下深度圖像，需要進行251012FLOP，採用100MFLOPs機器計算250天，1GFLOPs機計算25天，10GFLOPs機器35分。考慮到機器持續速度常常是峰值速度的10-30%，所以需要100GFlops的機器。CrayT932/32約為60GFLOPs。 3.航空航太 研究三維翼型對飛機性能的影響。數值模擬用時間相關法解Navier-Stoker方程，網格分點為1204050，需記憶體160MB，6億電腦上解12小時，如果在數分鐘內完成設計，則需要千億次電腦。 4.重大挑戰性課題需求（圖3.5）

計算空氣動力學：千億次/秒（1011）

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

AI： 萬億次/秒（1012） 5.核武器 核爆炸數值模擬，推斷出不同結構與不同條件下核裝置的能量釋放效應。 壓力： 幾百萬大氣壓 溫度： 幾千萬攝氏度 能量在

秒級內釋放出來。 設計一個核武器型號，從模型規律、調整各種參數到優選，需計算成百上千次核子試驗。

LosAlamos實驗室要求計算一個模型的上限為8-10小時。 千萬次機上算橢球程式的計算模型需要40-60CPU小時。 二維計算，每方向上網格點數取100，二維計算是一維的200倍，三維是一維的33000倍。若每維設1000網格點，則三維計算是一維的幾十萬倍之多。此時對主記憶體容量要數十、數百億字單元（64位）。 另外還有I/O能力的要求，可視化圖形輸出。 6.解決方案 只有開發並行處理技術才能滿足要求：

3Tperformance：

TeraflopsofComputingPower TerabyteofMainMemory Terabyte/sofI/Obandwidth第一章高等電腦的核心技術——並行處理

1.1什麼是並行處理 1.2為什麼要開發並行處理技術 1.3並行處理電腦結構沿革

1.3.1向量機與多向量機 1.3.2SIMD電腦 1.3.3Shared-MemoryMultiprocessors 1.3.4Distributed-MemoryMultiprocessors

1.3.5四類實用的並行系統 1.4其他並行處理電腦技術1.3並行處理電腦結構沿革

1.3.1向量機與多向量機 向量機的結構如下圖：ScalarFunctionalpipelinesScalarControlunitscalarprocessorscalarinstructionMainMemory(Programanddata)MassStorageHostComputerI/O(user)VectorControlunitvectorregistersvectorprocessorcontrolVectorFunctionalpipelinesVectorFunctionalpipelines……vectorinstruction程式和數據從Host進入主機指令先在Scalarcontrolunit解碼，如是標量或控制操作指令，則在標量功能流水部件種執行。如果是向量指令，則進入向量控制部件。register-to-register：

Crayseries FujitsuVP2000seriesmemory-to-memory：

Cyber205向量化。多向量機發展過程：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個處理器，而C90有16個處理單元（PE），處理速度16GFlops。

ConvexC3800family：

8個處理器，4GB主記憶體，

Rerkperformance為2GFlops。

1.3.2SIMD電腦

SIMD電腦的結構如下圖：ControlUnitProc0Mem0Proc1Mem1……ProcN-1MemN-1PE0PE1PEN-1InterConnectionNetworkMasParMP-1： 可有1024，4096，…，16384個處理器。在16KPEs，32位整數運算，16KB局部記憶體模組的配置下，可達26000MIPS，單精確度浮點運算1.5GFlops，雙精度浮點運算650MFlops。CM-2：

65536個處理單元，1Mbit/PE。 峰值速率為28GFlops，持續速率5.6GFlops。SIMD電腦發展過程圖如下：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： 物理記憶體被所有處理機均勻共用，所有處理機對所有存儲字具有相同的存取時間。P0I/OP1SM1……PnSMnInterConnectionNetwork(Bus、Crossbar、MultistageNetwork)……處理器共用記憶體NUMA(NonUniform-memory-access)model：訪問時間隨存儲字的位置不同而變化。P1……PnLMnInter-ConnectionNetwork……LM1P2LM2……COMA(Cache-onlymemoryarchitecture)： 只用高速緩存的多處理機 遠程高速緩存訪問則借助於分佈高速緩存目錄進行。PDInterConnectionNetwork……distributedcachedirectoriesCPDCPDCKendallSquareResearch’sKSR-1Shared-MemoryMultiprocessors發展過程如下：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處理器，每個節點16-128MB主記憶體，採用2D-Mesh互連，浮點運算5-300GFlops，或2.8-160Gips。

nCube2SModel80： 有4096-8192個PE，主記憶體16384-262144MB，浮點運算163800-34000MFlops，整數運算61000-123000MIPS。 CosmicCube(1981)nCube-2/6400(1990)Mosaic(1992)Intelparagon(1992)MIT/Jmachine(1992)inteliPSC’s(1983)Distributed-Memorymultiprocessors發展進程：

1.3.5四類實用的並行系統

1.向量機與多向量機 硬、軟體技術相對成熟、應用廣泛、市場佔有率高。很難達到3Tperformance來解決GrandChallenge

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

2.對稱式多處理機SMP

SMP：SymmetricMultiProcessors SharedMemorymultiProcessors SmallsizeMultiProcessors

處理機之間無主從之分，對外有相同的訪問權，都有執行操作系統核心和I/O服務程式的能力。 共用記憶體、統一地址空間，系統編程比較容易。

CPU可多至16臺左右，做伺服器用，市場前景好。典型的SMP有：

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

2-18CPU，5.4GFlops

*64位MIPSchip，每週期指令發射數為4

*8路交錯主存、帶寬為1.2GB/s

*I/O帶寬320MB/s（每個控制器），配置4個可達1.2GB/s

3.MPP系統（分佈存儲）

多於100個PE，消息傳遞，分佈存儲； 可擴展，峰值可達3Tperformance； 貴，市場有限； 持續速度是峰值速度的3-10%； 可解決某些GrandChallenge問題，是國家綜合實力的象徵。

4.機群系統

NOW：NetworkOfWorkstations

COW：ClusterOfWorkstations特點：

投資風險小，軟體財富繼承性好；可構成異構系統，資源利用率高； 通信開銷大。一種典型的機群系統結構如下：CPUMemoryI/OCPUMemoryI/O……CPUMemoryI/OI/OI/OI/OMemoryMemory……MemoryCPUCPUCPUNetwork第一章高等電腦的核心技術——並行處理

1.1什麼是並行處理 1.2為什麼要開發並行處理技術

1.3並行處理電腦結構沿革

1.4其他並行處理電腦技術1.4其他並行處理電腦技術 1.數據流技術

dataflow以數據驅動機制代替控制流機制 當功能部件輸入端的運算元可用時就啟動執行；可開發程式中所有的並行性，但費用昂貴，實際性能與功能部件數量、記憶體帶寬以及掛起和可用部件相匹配的程度有關。 如：MIT的MonSoos，*T

ETL的Sigma1，EM5 2.多線程 每臺處理機有多個控制線程，同時運行多個現場，是實現時延隱藏的一種有效機制。 比如:

Tera，Alewife

成本高。 3.邏輯推理與規約結構

邏輯推理： 日本第五代機，面向邏輯語言、執行速度慢，軟體與程式設計環境欠豐富。

規約結構：

Alice，PGR，面向函數語言，執行速度慢，軟體與環境欠豐富。 4.關鍵技術 並行演算法（數值演算法與非數值演算法） 並行計算模型 互連與通信 並行存儲技術 同步與時延隱藏技術 並行I/O

劃分、調度與負載平衡 優化編譯 並行調試 工具與環境 5.美國的主要行動

（1）組織基於NSF的國家科學計算聯盟 （NationalComputationalScienceAlliance） 建立國家科技網（Grid）：97.11開始，五年計劃，總經費3.4億美元。

目標：使美國在全國範圍內的元電腦（網上的電腦可作為一個整體看待）達到實用水準。 為在桌面上解決計算科學與工程時提供一個有力的解題環境。 解決基於元計算環境的並行、分佈、協作和immersive等問題。

UIUC、SanDiago組織實施。

（2）DOE支持的ASIC計畫 （AcceleratedStrategicComputingInitiative） 保證在21世紀美國在核研究和核儲備繼續處於領先地位。 以LosAlamos，Sandia和LawrenceLivermore

三個國家實驗室為核心，組成遍及美國不同地區的“拆牆合作”。 為建立VirtualLaboratory奠定基礎。 研製出超級電腦系統：萬億次量級的電腦，2的50次冪（約千萬億）容量的資料庫系統。 提供高效、好用的計算環境。

能實現基於網路的、分佈式協同工作環境。 能提供高效的、點對點的計算設施。 在CORBA的環境下有效的把計算平臺和有關應用進行系統集成。 負載平衡。 可裁剪性。 6.ModelsofParallelComputers(1960s-1980s)DataMIMDSIMDInstructionImplicationMultipleDataStreamsMultipleDataStreamsSingleInstructionStreamsMultipleInstructionStreamsSingleProgram;Lotsofdatatohavelotsofparallelism;Programmingissimplersincecommunicationisalwayssynchronized;CommunicationsseperatefromcomputationsinceinstructionsdistinctMaybemanyProgramsLotsofprogramstohavelotsofparallelismH/Wconstructionissimplerusingoff-the-shelfuniprocessorscommunicationmergedwithcomputationImplicationIllivaIV、CM-2、MasParCrayX-MP、Sequent、nCube2.1加速比性能模型

2.1.1一般概念

1.處理機—時間積

處理機數目與處理時間的乘積用以度量這些處理機運行時的資源利用率。 若一程式在

P臺處理機上運行的時間為Tp，則此P臺處理機在Tp時間間隔內完成的工作最大數量為Tp*P。 可將處理機實際工作曲線對時間的積分看成是這些處理機完成的有效工作量。

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

並行度（DOP）是在一定時間間隔內執行一個程式所用的處理機的數目。3.並行性分佈圖

執行一個給定的程式時DOP對時間的分佈圖。

DOP與對應時間的間隔之積即為處理機要完成的工作或工作負載。下圖所示為一個並行性分佈圖。DOPt1tt2並行性分佈圖2.1.2加速比1.絕對加速比

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

定義一（與具體機器有關）將最好的串行演算法在一臺上的運行時間與並行演算法在N臺運行的時間相比。

定義二（與具體機器無關）將最好的串行演算法在最快的順序機上的執行時間與並行演算法在並行機上的運行時間相比。2.相對加速比

同一並行演算法在單節點上運行時間與在多個相同節點構成的處理機系統上的運行時間之比。 這種定義側重於描述演算法和並行電腦本身的可擴展性。線性加速比：中間開銷小，通信少，弱耦合計算超線性加速比：當應用需要大記憶體時可能出現病態加速比：加速比遞減，可能是計算量太小2.1.3三種加速比性能模型

1.固定負載加速比性能模型—Amdahl定律 在許多即時應用領域，計算負載的大小常固定。在並行機中，此負載可分佈至多臺並行執行，獲得的加速比稱為fixed-loadspeedup。

一個問題的負載可表示如下：W=Ws+Wp

其中，Ws代表問題中不可並行化的串行部分負載，

Wp表示可並行化的部分負載。 則n個節點情況下，加速比可以表示如下：設串行因數α為串行部分所占的比例。即代入即得Amdahl’law：不管採用多少處理機，可望達到的最好加速比：效率En可以表示為：處理機數目n越大，效率En越低。Amdahl定律告訴我們：系統中某一部件由於採用某種更快的執行方式後整個系統性能的提高與這種執行方式的使用頻率或占總執行時間的比例有關。加速比的兩個決定因素：1.電腦執行某個任務的總時間中可被改進部分的時間所占的百分比，即

可被改進部分佔用時間/改進前真個任務的執行時間， 記為Fe，它總小於1。2.改進部分採用改進措施後比沒有採用改進措施前性能提高的倍數，即

改進前改進部分執行時間/改進後改進部分執行時間， 記為Se。例1： 假設將某系統的某一部件的處理速度加快到10倍，但該部件的原處理時間僅為整個運行時間的40%，則整個系統的性能提高了多少？

解：Fe=0.4，Se=10，例2： 採用哪種實現技術來求浮點數平方根FPSQR的操作對系統的性能影響較大。假設FPSQR操作占整個測試程式執行時間的20%。一種實現方法是採用FPSQR硬體，使FPSQR操作的速度加快到10倍。另一種方法是使所有浮點數據指令的速度加快，使FP指令的速度加快到2倍，還假設FP指令占整個執行時間的50%。請比較這兩種設計方案。

解：Fe_FPSQR=0.2，Se_FPSQR=10，

Fe_FP=0.5，Se_FP=2，Amdahl’law又稱為固定規模加速比模型，問題規模不隨處理機變化而變化。固定問題規模，看用並行技術能達到的最短時間是多少。在固定規模加速比模型下，負載和執行時間隨系統中處理機數目n變化的情況如下圖：WsWpWsWpWsWpWsWpWorkloadN1234ExecutionTimeNTsTp1TsTp2TsTp3TsTp4固定負載執行時間隨N增加而減少固定負載加速比模型下的負載和執行時間情況當處理器數目n=1024，加速比Sn隨α變化的情況如下：得出曲線如下圖：91Snα102448312410可以比較不同的α對加速比帶來的不同影響：α=0Snnα=0.01α=0.1α=0.9α=0時得到理想加速比，當α值增加時，加速比性能急劇下降。結論：加速比曲線隨α的上升急劇下降，原因是存在順序部分Ws，無法用增加系統的處理機數目來解決。這一性質在過去二十年間給人們造成了對並行處理非常悲觀的印象。影響：兩種意見：

1.勸阻製造商生產大規模並行電腦。

2.研究並行編譯器，以降低α的值，從而提高系統的性能。規定負載加速比模型的可能應用範圍：

對時間要求嚴格的應用問題。

2.固定時間加速比性能模型—Gustafsun定律 有許多應用領域強調精度而不時運行時間。1988年，Gustafsun提出了固定時間加速比模型。當機器的規模擴大時，解題的規模也隨著擴大，從而得到更加精確的解，而使運行時間保持不變。 比如：有限元方法做結構分析，流體動力學做天氣預報解PDE(偏微分方程組）就需要提高精度。 粗格要求的計算量較少，而細格的計算量多，得到的精確度也較高。天氣預報模擬求解四維PDE，如果使每個實際方向（X，Y，Z）的格點距離減少10倍，並以同一幅度增加時間步，那麼可以說格點增加了104倍，因而工作負載也至少增大了10000倍。模型提出的背景： 固定負載模型由缺陷：因為Amdahl’law中，α取決於問題及並行編譯器的效率，無法描述系統固有的特性。加速比的公式：

其中，Wp’=nWp和Ws+Wp=Ws’+Wp’/n作為固定時間的條件。Ws’+Wp’/n表示在擴大負載後在增加處理機台數的情況下的平均負載（執行時間），它應當和負載沒有擴大情況下的平均負載（執行時間）Ws+Wp相等。即有Ws+Wp=Ws’+Wp’/n。同時，負載得串行部分並沒有改變，即有Ws=Ws’。在固定時間加速比模型下，負載和執行時間隨系統中處理機數目n變化的情況如下圖：WsWpWsWpWsWpWsWpWorkloadN1234ExecutionTimeNTsTp1TsTp2TsTp3TsTp4並行負載不斷增加執行時間固定固定時間加速比模型下的負載和執行時間情況

增大問題規模的辦法使所有處理機保持忙碌狀態，在問題擴大到與可用的計算能力匹配時，程式中的順序部分就不再是瓶頸了。 當處理器數目n=1024，加速比Sn隨α變化的情況如下：Sn’α102410141004993983

3.受限於記憶體的加速比模型

1993年，由Sun和Ni提出。 大型科學計算和工程設計需要較大的存儲空間，許多應用問題是記憶體受限，而不是CPU受限或者I/O受限。 比如：在分佈存儲系統中常遇到，總存儲容量隨節點數線性增加，許多節點集合起來解一個大題。 基本思想：要在存儲空間有限條件下解盡可能大的問題，這同樣需要擴展工作負載，才能提供加高的加速比、較高的精度和較好的資源利用率。加速比可以表示如下：其中：

在單個處理機上順序執行的工作負載與問題的規模或系統的規模無關，即：而G(n)反映的是存儲容量增加n倍時並行工作負載增加的倍數。討論：

1. G(n)=

1，即為固定負載的情況；

2. G(n)=n，即記憶體增加n倍，負載也增加n倍，為固定時間的情形；

3. G(n)>n，計算負載的增加情況比記憶體增加快，會有較高的加速比。比較三種加速比，對於相同的處理機數量，有：在受限於記憶體的加速比模型下，負載和執行時間隨系統中處理機數目n變化的情況如下圖：WsWpWsWpWsWpWsWpWorkloadN1234ExecutionTimeNTsTp1TsTp2TsTp3TsTp4規模擴展的工作負載執行時間稍有增加受限於記憶體的加速比模型下的負載和執行時間情況例：

n維矩陣乘法：A*B=C，其中A、B、C都是n*n的方陣。為得到C的每一個元素需要進行n次乘法、n次加法，所以總的計算量為：（n+n)*n2=2n3。需要的存儲量為3n2（兩個源矩陣，一個結果矩陣）。如果n臺電腦組成多電腦系統，則存儲容量擴大n倍，那麼矩陣的維數（原來為n)也可以增加了，設為N倍，那麼加速比為多少？

解：存儲容量變為：nM=n*3n2=3n3，而N維需要的存儲量為3N2，計算量變為2N3，則有：

4.並行計算的應用模型隨機器規模的增大，工作負載增長的模式如下圖：工作負載（問題規模）nθ（指數）γ（線性）β（亞線性）α（常數）上圖中：

採用受限於記憶體的加速比模型中給出的公式，

θ曲線對應的G(n)=n1.5

γ曲線對應的G(n)=n

β曲線對應的G(n)=0.5n

α曲線對應的G(n)=1

則有加速比公式:

給定一個程式，假設Ws/Wp=0.4，那麼效率為：相應的處理器數目—效率曲線如下圖：效率nθ（指數）γ（線性）β（亞線性）α（常數）結論：

1.如果工作負載（問題規模）保持不變，那麼效率E隨機器規模的增大而迅速下降，其原因是開銷h比機器規模增加得快，為了使效率保持在一定的水準上，我們可以按比例增大機器規模和問題規模。

2.如果工作負載按指數增長模式，效率要保持恒定或保持良好的加速比，必須使問題規模猛增才行，這樣就會超過記憶體或I/O限制，而問題規模只允許在電腦記憶體可用的限度以內增長。並行電腦的應用模型如下圖：通信界限

記憶體界限受限於記憶體模型工作負載（問題規模）機器規模固定負載模型固定時間模型第二章加速比性能模型與可擴展性分析 2.1加速比性能分析

2.2可擴展性分析

2.2.1可擴展性

2.2.2可擴展性分析2.2可擴展性分析

2.2.1可擴展性

1.可擴展性與可編程性增加可擴展性增加可編程性分佈存儲的消息傳遞型多電腦共用存儲型多處理機理想並行電腦 2.可擴展性指標 機器規模（n） 時鐘頻率（f） 問題規模（s）

CPU時間（T）

I/O需求（d） 存儲容量（m） 通信開銷（h） 電腦價格（c） 程式設計開銷（p） 3.可擴展性的直觀定義

對任意數量（n）的處理機和任意規模（s）的問題，若所有演算法的系統效率E=1，則系統是可擴展的。 4.規模可擴展性

系統性能隨處理機數量線性增長，包括：

處理速度和效率 存儲速度和容量 互連帶寬和時延

I/O速度和容量 軟體開銷規模可擴展性與空間局部性、時間局部性以及部件瓶頸都有關系。例子：

CrayY-MP：16臺處理機範圍可伸縮

CM-2： 8K-64K臺處理機範圍可伸縮

CM-5： 1024-16K臺處理機範圍可伸縮

KSR-1： 8-1088臺處理機範圍可伸縮 5.換代（時間）可擴展性

對系統各部分更換成新技術後，性能隨之易擴展，要求演算法、S/W均能相容運行。 6.問題可擴展性

問題規模擴大時，系統仍能很好的運行，或說問題規模擴展到很大時，系統能在給定粒度下高效運行。

2.2.2可擴展性

1.恒等效率概念（Isoefficiency）

恒等效率定義為一個並行演算法在並行電腦上實現時，為保持效率E固定所需的工作負載與機器規模n的相對關係。 設:

W=W（s）為工作負載，

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

問題的關鍵在於W（s）與h（s，n）之間的相對增長速度。機器規模一定，開銷h的增長比工作負載W要慢。因而，對一定規模的機器來說，效率會隨問題規模增大而提高。所以，假若工作負載W隨機器規模適當增加，那麼就有希望保持效率不變。

對於已知的演算法來說，為了保持恒定的效率，工作負載W可能需要對n以多項式或指數規律增長。不同的演算法可能需要不同的工作負載增長速率以便在n增加時保持效率不致下降。 一般並行演算法的恒定效率函數是n的多項式函數，即它們為O（nk），k1。n的冪越小，並行系統的可擴展性越大（系統包括演算法和結構的組合）。

2.恒等效率函數並行程式執行時間Tp=(T1+T0)/p， 其中，T1為總工作負載串行執行時間，T0為多節點總通信延時，p為節點數。那麼，加速比為：

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

。

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

W(s)=O（s3），

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

。

解：比較兩個式子，選出較大的：例3：

W(s)=O（s3），

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

。

解：第二個式子顯然成立，故例4：在n臺處理機網格和超立方體電腦上分別計算1維s點的FFT，其工作負載W(s)=O（slogs），已知：

超立方體電腦上：h1（s，n）=O（nlogn+slogn），

網格電腦上：h2（s，n）=O（nlogn+sn0.5），

問哪一種擴展性好？

解：對超立方體電腦，對網格電腦，3.1互連網絡的作用定義：由開關元件按一定拓撲結構和控制方式構成的網路以實現電腦系統內部多個處理機或多個功能部件間的相互連接。操作方式： 同步通信（SynchronousCommunication)

非同步通信(AsynchronousCommunication)控制策略：

集中控制(Centralizedcontrol)

分佈控制(Distributedcontrol)交換方式： 電路交換(Circuitswitching)

分組交換(Packetswitching)

Wormhole交換(Wormholeswitching)網路拓撲結構：

靜態網路(Staticnetwork)

動態網路(Dynamicnetwork)第三章互連與通信

3.1互連網絡的作用

3.2靜態網路

3.2.1靜態網路的特點與指標

3.2.2典型的靜態網路

3.3動態網路

3.4通信問題3.2靜態網路

3.2.1靜態網路的特點與指標

1.靜態網路的特點

靜態網路由點—點直接相連而成，這種連結方式在程式執行過程中不會改變。

如果用圖來表示，結點代表開關，邊代表通信鏈路，則

(1)

結點間的鏈路無源，不能重構

(2)

開關元件與處理機相連

(3)

不直接相連結點間的通信需通過中間結點中轉。 2.靜態網路的指標

結點度：與結點相連接的邊（鏈路或通道）數，表示節點所需要的I/O端口數，模組化要求結點度保持恒定。根據通道到結點的方向，結點度可以進一步表示為：

結點度=入度+出度 其中入度是進入結點的通道數，出度是從結點出來的通道數。

距離：與兩個結點之間相連的最少邊數。

網路直徑：網路中任意兩個結點間距離的最大值。

網路規模：網路中結點數，表示該網路功能連結部件的多少。

等分寬度：某一網路被切成相等的兩半時，沿切口的最小邊數稱為該網路的等分寬度。

結點間的線長：兩個結點間的線的長度。

對稱性：從任何結點看，拓撲結構都一樣，這種網路實現和編程都很容易。 結點是否同構。 通道是否有緩衝。

3.2.2典型的靜態網路

1.線性陣列

對N個結點的線性陣列，有N-1條鏈路，直徑為N-1（任意兩點之間距離的最大值），度為2，不對稱，等分寬度為1。

N很大時，通信效率很低。

線性陣列與匯流排的區別：

線性陣列：允許不同的源結點和目的結點對併發使用系統的不同部分。

匯流排：通過切換與其相連的許多結點來實現時分特性，同一時刻只有一對結點在傳送數據。

2.環對N個結點的環，考慮相鄰結點數據傳送方向：

雙向環：鏈路數為N，直徑N/2，度為2，對稱，等分寬度為2。比如KSR-1（1990）。

單向環：鏈路數為N，直徑N-1，度為2，對稱，等分寬度為2。 3.帶弦環對上圖中12個結點的帶弦雙向環，

結點度為3：鏈路數為18，直徑4（比如紅色結點），度為3，不對稱，等分寬度為2。

結點度為4：鏈路數為24，直徑3（比如紅色結點），度為4，對稱，等分寬度為8。度為3的帶弦環度為4的帶弦環 4.鏈接 鏈接是帶弦環的一種特殊情形。鏈接中的每個結點和其他結點之間都有單一的直接鏈路。如下圖中8個結點的鏈接：

有28條鏈路，直徑為1，度為7，對稱，等分寬度為16。 5.樹形

4層的二叉樹

一棵K層完全二叉樹應有N=2K-1個結點，對大結點度為3，直徑為2（K-1）（即右邊任意一個葉子結點到左邊任意一個葉子結點）。不對稱，等分度為1。 由於結點度為常數，所以樹是一種可擴展的系統結構。

樹形的擴展：

帶環樹二叉胖樹

這兩種結構都可以緩解根結點的瓶頸問題。 6.星形

星形實際上是一種二層樹（如右圖）。有N個結點的星形網路，有N-1條鏈路，直徑為2，最大結點度為N-1，非對稱，等分寬度為1。 7.網

有N個結點的rr網（其中 )，有2N-2r條鏈路，直徑為2（r-1)，結點度為4，非對稱，等分寬度為r。

網的變形：

a.Illiac網

有N個結點的rr網（其中 )，有2N條鏈路，直徑為r-1，結點度為4。

b.環形網（2D—Torus）

有N個結點的rr網（其中 )，有2N條鏈路，直徑為2r/2，結點度為4，對稱。

c.搏動式陣列（SystolicArray）

8.超立方體0-立方體1-立方體2-立方體3-立方體4-立方體

一個n-立方體由N=2n個結點構成，它們分佈在n維上，每維有兩個結點。直徑為n，結點度為n，對稱。由於結點度隨維數線性增加，所以超立方體不是一種可擴展結構。

例子：

Intel的iPSC/1、iPSC/2、nCUBE 9.帶環立方體

一個帶環n-立方體由N=2n個結點環構成，每個結點環是一個有n個結點的環，所以結點總數為n2n個。直徑通常為2n，結點度為3，對稱。帶環3-立方體 10.k元n-立方體網路4元3-立方體（隱藏的結點與連接沒有畫出)

在一個k元n-立方體網路中，結點的數目N=kn，即：

其中，k稱為基數（radix），n稱為維數（dimension）。

k元n-立方體的結點可以用基數為k的n位地址A=a0a1a2...

an來表示，其中ai代表第i維結點的位置。

傳統的環網等價於4元2-立方體。第三章互連與通信

3.1互連網絡的作用

3.2靜態網路

3.3動態網路

3.3.1互連函數

3.3.2多級互聯網路

3.4通信問題3.3動態網路

特點： 網路的開關元件有源，鏈路可通過設置這些開關的狀態來重構。 只有在網路邊界上的開關元件才能與處理機相連。

3.3.1互連函數

排列：N個數的每一種有確定次序的放置方法叫做一個N排列。

置換：把一個N排列變成另一個N排列的變換叫做N階置換。 在有N個輸入端和N個輸出端的網路中，輸入端和輸出端的連接關係可以用置換來表示（輸入端與輸出端一一對應）。

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

Xk

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

a.均勻洗牌（Shuffle-Exchange)

是洗牌函數與Cube0函數的組合。01234567：Cube0：洗牌b.第k個子洗牌即最低k位迴圈左移一位。c.第k個超洗牌即最高k-1位迴圈左移一位。0000010100111001011101110000010100111001011101114.逆洗牌函數012345670000010100111001011101110000010100111001011101115.蝶式012345676.PM2I函數（加減2i）

共有2n個互連函數，對N個結點的網路為例1：

N=8（8個結點），則n=log28=3，所以：i=0，1，2；j=0，1，…，7。

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

2: (04）（15）（26）（37）0123456701234567例2：89101112131415上面的網路可以用四個PM2I函數表示。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多級互連網絡

1.多級網路的三要素

（1）開關單元：a個輸入a個輸出的開關單元記做aa的開關單元，其中，a是2的整數倍。常見的有2

2、44、88等。

根據開關單元功能的多少，2

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

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

級控制：每級只有一個控制信號 單元控制：每個開關一個控制信號 部分級控制：幾個開關合用一個控制信號

2.Ω網0123456701234567第0級第1級第2級 Ω網的特點：

開關單元：22四功能開關

ISC：洗牌變換+恒等變換

控制方式：採用單元控制方式。當目的地址編碼從高位開始的第i位（從0開始）為0時，第i級的22開關的輸入端與上輸出端連接，否則輸入端與下輸出端連接。 例子：

UIUC的Cedar IBM的RP3 NYU的Ultracomputer0123456701234567第0級第1級第2級

無阻塞的實現置換

π1=（07642）（13）（5）0123456701234567第0級第1級第2級

置換π2=（06473）（15）（2）

在開關F、G、H、I和J上發生阻塞FGHJI Ω網的特點(2)：

並不是所有的置換在Ω網中一次通過便可以實現。

Ω網是阻塞網路：出現衝突時，可以採用幾次通過的方法來解決衝突。0123456701234567第0級第1級第2級

Ω網的廣播功能：

001

8個輸出端01第1級44開關構成的Ω網：多路洗牌

如16輸入4路洗牌：網路級數為log416=2

234567891011121314150123456789101112131415第0級 Ω網的特點(3)：

當採用kk開關元件時，則可以定義k路洗牌函數來構造更大的級數為logkn的Ω網路。

3.蝶式網路（Butterflyswitchnetwork）

蝶式網路的開關不允許廣播功能，它實際上是Omega網的一個子集。 兩級6464的蝶式網路如下圖所示：它採用16個88交叉開關構成，兩級間採用8路洗牌連接。8888880...7888888第1級第0級8...1556...63.........078155663........................兩級6464的蝶式網路

4.其他連接方式

匯流排 交叉開關第三章互連與通信 3.1互連網絡的作用

3.2靜態網路

3.3動態網路

3.4通信問題

3.4.1基本術語與性能指標

3.4.2尋徑演算法

3.4.3虛擬通道與死鎖

3.4.4包衝突的解決

3.4.5維序尋徑

3.4.6通信模式3.4通信問題

3.4.1基本術語與性能指標

1.消息、包和片

消息（Message）：是在多電腦系統的處理接點之間傳遞包含數據和同步消息的資訊包。它是一種邏輯單位，可由任意數量的包構成。

包（Packet）：包的長度隨協議不同而不同，它是資訊傳送的最小單位，64-512位。 片（Flit）：片的長度固定，一般為8位。 它們的相互關係如下圖：包……消息包片據片頭片尾片……順序號數bbbbbbbb 2.互連網絡

互連網絡用來在多電腦系統的處理結點之間傳遞消息。互連網絡的描述：

拓撲（Topology） 尋徑演算法（Routing） 流控制（FlowControl） 互連網絡性能的兩個重要指標： 傳輸時延（TransmissionLatency） 吞吐量（Throughput） 3.傳輸時延與吞吐量

一個消息的傳輸時延：從它在源結點進行發送初始化到它在目的結點完整的被接收所耗費的時間。

一個網路的傳輸時延：在一定條件下發送消息的平均時延。 網路的吞吐量：單位時間內網路所能傳輸的消息數目或長度。 4.傳輸時延的公式

其中，Ts稱為建立時延，Tn稱為網路時延，Tb稱為阻塞時延。 它們具體定義如下：

建立時延Ts：一個消息在源結點和目的結點上裝配和分解、從記憶體拷貝到通信緩衝區以及正確性驗證等所耗費的時間。它和機器本身的硬體、軟體技術有關。

其中：

Tss稱為源結點時延：從發送進程開始消息發送初始化到消息的頭部進入網路所經歷的時間。

Tsd稱為目的結點時延：從消息的尾部到達目的結點到消息完全被接收進程接收所經歷的時間。

網路時延Tn：消息頭部從源結點進入網路到消息的尾部到達目的結點的時間間隔。

其中：

TpD稱為結點時延：其中Tp是消息在它所經過的路徑上的每個中間結點上的平均時延，D為中間結點或源結點與目的結點之間的距離。

L/B稱為線路時延：其中L為消息長度，B為結點之間的通道帶寬。

阻塞時延Tb：消息傳遞過程中其他所有可能的時延（主要原因是資源衝突）。 5.網路的拓撲結構

第一代並行電腦：HyperCube

第二代並行電腦：n—Mesh 6.網路的尋徑演算法

決定發送一個消息到其目的地所經過的路徑。 可以分為：

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

確定性演算法：路徑的選擇只依賴於它所發送的消息的源結點和目的結點。

可適應演算法：消息從結點A到結點B可以由幾條不同的路徑。 7.網路的流控制

當一個消息在網路中沿著某條路徑傳送時，互連網絡如何來為它分配通道和緩沖器。

3.4.2尋徑演算法 我們介紹四種尋徑方式： 存儲轉發（Store-and-Forward） 虛擬直通（Virtualcutthrough） 線路交換（CircuitSwitching）

Wormhole交換（WormholeSwitching) 1.存儲轉發

當一個消息到達中間結點A時，A把整個消息放入其通信緩衝器中，然後在尋徑演算法的控制下選擇下一個相鄰結點B，當從A到B的通道空閒並且B的通信緩衝器可用時，把消息從A發向B。缺點：

每個結點必須對整個消息進行緩衝，緩衝器較大。 網路時延與發送消息所經歷的結點數成正比 2.虛擬直通

中間結點沒有必要等到整個消息全部被緩衝後再作出路由選擇，只要消息的目的資訊域可用後，就可以作出路由選擇。

其中，Lh為消息頭部開始到其目的資訊域的長度，顯然有L>>Lh，所以D的影響比較小。 而當通向下一結點的通道忙或結點的緩衝器非空閒時，必須把整個消息緩衝起來，這時和存儲轉發一樣。 3.線路開關

在傳遞一個消息之前，就為它建立一條從源結點到目的結點的物理通道。在傳遞的全部過程中，線路的每一段都被佔用，當消息的尾部經過網路後，整條物理鏈路才被廢棄。

其中，Lc是為消息建立物理通路所傳遞的控制資訊的長度。當L>>Lh時，D的影響較小。

缺點：

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

Dally於1986年提出。 首先把一個消息分成許多片，消息的頭片包含了這個消息的所有尋徑資訊。尾片是一個其最後包含了消息結束符的片。中間的片均為數據片。 片是最小資訊單位。每個結點上只需要緩衝一個片就能滿足要求。 用一個頭片直接開闢一條從輸入鏈路到輸出鏈路的路徑的方法來進行操作。每個消息中的片以流水的方式在網路中向前“蠕動”。每個片相當於Worm的一個節，“蠕動”以節為單位順序的向前爬行。

當消息的頭片到達一個結點A的尋徑器後，尋徑器根據頭片的尋徑資訊立即做出路由選擇：

（1）如果所選擇的通道空閒而且所選擇的結點B的通信緩衝器可用，那麼這個頭片就不必等待，直接通過結點A傳向下一個結點B；隨後的其他片跟著相應的向前“蠕動”一步。當消息的尾片向前“蠕動”一步後，它剛才所佔用的結點就被放棄了。

（2）如果所選擇的通道非空閒或者所選擇的結點的通信緩衝器非可用，那麼這個頭片就必須在此結點的通信緩衝器中等待，直到上述兩者都可用為止；其他片也在原來的結點上等待。此時，被阻塞的消息不從網路中移去，片不放棄它所佔有的結點和通道。這是Wormhole技術和其他流控制技術都不同的地方。優點：

（1）每個結點的緩衝器的需求量小，易於用VLSI實現。

（2）較低的網路傳輸延遲。所有的片以流水方式向前傳送，時間並形性。而在存儲轉發中，消息是整個的從一個結點“跳”向另一個結點，通道的使用時串行的。所以它的傳輸延遲基本上正比於消息在網路中傳輸的距離。Wormhole與線路開關的網路傳輸延遲正比於消息包的長度，傳輸距離對它的影響很小（消息包較長時的情況）。

（3）通道共用性好、利用率高。對通道的預約和釋放是結合在一起的一個完整的過程：佔有一段新的通道後將立即放棄用過的一段舊通道。

（4）易於實現Multicast和Broadcast。允許尋徑器複製消息包的片並把它們從多個輸出通道輸出。

Wormhole方式中，同一個包中所有的片象不可分離的同伴一樣以流水方式順序的傳送。包可看作是一列火車，由火車頭（頭片）和被牽引的車廂（數據片）組成。5.幾種尋徑技術的時空圖S時間I1I2D

L/B

D

存儲轉發（Store-and-forward）尋徑技術S時間I1I2D電路開關尋徑技術S時間I1I2D

L/B

D

Wormhole尋徑技術包頭數據

3.4.3死鎖和虛擬通道

1.虛擬通道

特點：

是兩個結點間的邏輯鏈。 由源結點的片緩衝區、結點間的物理通道和接收結點的緩衝區組成。 物理通道由所有虛擬通道分時共用。比如在下例中，四條虛擬通道以片傳遞為基礎分時的共用一條物理通道。物理通道源結點中的片緩衝區目的結點中的片緩衝區四條虛擬通道以片傳遞為基礎分時共用一條物理通道2.死鎖的產生

緩衝區產生死鎖：DDDDDD包緩衝區DDDDDD包緩衝區DDDDDD包緩衝區DDDDDD包緩衝區結點A結點D結點B結點C

採用存儲轉發，四個包佔用了四個結點的四個緩衝區，將導致迴圈等待。通信產生死鎖：結點A結點D結點B結點C尋徑器A尋徑器B尋徑器C尋徑器D消息4消息1消息3消息2m4m3m1m2片緩衝區

採用Wormhole，四個結點之間出現通道死鎖，4個消息的四個片同時佔用了4個通道。2.死鎖的避免C1

結點表示通道，帶方向的箭頭表示通道之間的依賴關係。ABC3DCC2C4通道死鎖C4C1C3C2包含迴圈的通道相關圖C1

利用虛擬通道將通道相關圖中的環路變成螺旋線來比避免死鎖。ABC3DCC4增加兩條虛擬通道V3,V4C4C1C3C2利用