并行计算课件

並行處理與體系結構第一章並行電腦模型

1計算技術的現狀

2多處理機和多電腦

3多向量機和SIMD電腦

4並行電腦的抽象模型

5可擴展的範圍和設計

1計算技術的現狀一、並行技術的出現二、現代並行電腦的組成涉及6個問題：1.計算問題

現實生活中對問題要求快速而精確地求解推動了電腦的廣泛使用。科學技術中的數值計算問題人工智慧(AI)問題2.演算法和數據結構並行計算問題中的運算和通信，需要各種專門的演算法和數據結構。符號處理：存在的問題

：3.硬體資源處理機、記憶體和週邊設備組成了電腦系統的硬體核心週邊設備可以直接或通過局域網和廣域網與主機相連4.操作系統管理用戶程式執行過程中的資源分配和再分配。映射是一種演算法結構與硬體結構相匹配的雙向過程。並行操作系統的映射演算法和數據結構到機器結構的映射包括處理機調度、記憶體映象、處理器間的通信等。這些問題通常都與系統結構有關。5.系統軟體支持

存在的問題：不能以通用和可移植方式進行並行程式設計開發並行編程環境：一種與系統結構無關的語言、編譯器和軟體工具。兩個方向：對於開發並行語言，我們將著眼點放在語言執行的效率、對不同機器的可移植性、與現有的順序語言的相容性、並行性的表達和編程的簡便性等上面。可以設計一種新的語言，逐步擴展現有的順序語言。新語言有用顯式高級結構描述並行性的優點，但是新語言往往與現有語言不相容，而需要新的編譯器或者通過新的步驟才能利用現有的編譯器。大部分系統選用的是語言擴展方式。6.編譯器支持

改進編譯器有三種途徑：預處理程式;預編譯器;並行化編譯器。預處理程式採用順序編譯器和目標電腦的低層程式庫實現高級並行結構。預編譯器需要程式流分析、相關性檢查和有限的優化來檢測並行性。聯接過程的效果取決於預處理程式、預編譯器、並行化編譯器、加載程式和操作系統支持的功效。由於程式行為的不可預測，現有的編譯器在檢測所有類型的並行性時都不是完全自動或完全智能進行的。有效的方法：將編譯器命令插入源代碼，幫編譯器做出較好的結果。這樣，用戶可與編譯器進行交互重構程式，這已被證明對提高並行電腦性能是十分有用的。7.並行程式的設計環境

隱式並行性伊利諾依大學的DavidKuck和Rice大學的KenKennedy以及他們的合作者都已採用這種隱式並行性方法。顯式並行性加州理工學院的CharlesSeitz和麻省理工學院的WilliamDaily在開發多電腦時採用了這種顯式方法。總結：要使一個環境對用戶更加友好，必須要有專用軟體工具。一些工具是傳統高級語言的並行擴展；一些則是集成環境其中包括提供不同級別的程式抽象、驗證、測試、查錯和調試等各種工具；性能預測和監控；輔助程式開發的可視化支持、性能測量以及計算結果的圖形顯示及動畫表示三、電腦系統結構向高性能發展歷程主要探討順序到並行的過程1.先行、並行性和流水線技術用先行技術預取指令可使I／E(指令讀取／解碼和執行)支持功能並行性的方法有兩種：一種是同時使用多個功能部件；另一種是在不同處理級分別實施流水線技術。流水線指令執行、流水線算術計算和記憶體存取操作。2.Flynn分類法MkhealFlynn(1972)根據指令和數據流概念提出了不同電腦系統結構的分類法。傳統的順序機被稱為SISD(單指令流單數據流)電腦。向量電腦--標量和向量硬體裝備，或以SIMD(單指令流多數據流)機的形式出現。並行電腦則屬MIMD(多指令流多數據流)機MISD(多指令流單數據流)機在執行不同的指令流時，同一數據流通過處理機線性陣列。這種系統結構也就是所謂流水線執行特定演算法的脈動陣列(Systolicarrays)。由卡內基—梅隆大學的美籍華人學者H．T．Kung於1978年提出的。這一結構是隨著VLSI技術的發展和各種大運算量的信號/圖象處理及科學計算的運算要求而建立起來的。例1：用脈動陣列(Systolicarray)結構計算矩陣乘脈動陣列的特點：處理單元簡單流水演算法專業例2：數據流電腦數據流的計算模型--試圖使並行計算的基本方面在機器層顯式化，而不利用有可能限制程式並行性的人為約束。它的想法是程式由一個基本數據依賴圖來表示；一個指令可能在獲得了它的運算元後的任意時刻被執行，不是顯式控制線性程式列的固定組合。3.並行／向量電腦

真正的並行電腦是那些以MIMD模式執行程式的電腦。並行電腦有兩大類，即共用存儲型多處理機和消息傳遞型多電腦。多處理機和多電腦之間的主要差別就在於記憶體共用和處理機間通信機制的不同。多處理機系統中的處理機通過公用記憶體的共用變數實現互相通信。多電腦系統的每個電腦結點有一個與其它結點不共用的本地記憶體。處理機之間的通信通過結點間的消息傳遞來實現。顯式向量電腦指令是隨向量處理機的問世而出現的。一臺向量處理機可以裝備有用硬體或固件併發控制的多條向量流水線。4.開發層次

LionelNi的最新分類法(1990)，並行電腦的分層開發可表示於下圖四、性能的系統屬性1

.時鐘頻率和CPI

主頻當前數字電腦的CPU(或簡稱處理機)是由一個恒定週期(τ，以ns表示)的時鐘驅動的。週期的倒數是時鐘頻率(ｆ＝1/

τ）（以MHz表示）。程式的規模是由其指令數(Ic)，也就是程式串要執行的機器指令數來決定的。執行不同的機器指令所需要的時鐘週期數也是不一樣的。一條指令的週期數(CPl)就成為衡量執行每條指令所需時間的重要參數。2.性能因數執行程式所需的CPU時間：設Ic為已知程式的指令條數。執行程式所需的CPU時間(T，以秒/程式表示)可用三個主要因素的乘積來計算：

T＝Ic

×CPI×τ可將上式重寫成如下形式：

T＝Ic

×(p+m×k)×τ

一種指令類型的CPI可分為完成指令所需的處理機週期數和記憶體週期數兩部分。完整的指令執行過程可能包含一至四次記憶體訪問(一次用於取指令，兩次用於取運算元，一次用於存儲結果)，這與指令的類型有關。式中的細化：p為指令解碼和執行所需的處理機週期數;m為所需的記憶體訪問次數;k為存儲週期與處理機週期之比;Ic為指令條數，為處理機週期。3.系統屬性電腦系統屬性可以由五元組表示：(Ic，p，m，k，τ),五個量可以稱為性能因數。與四種系統屬性有關：指令系統結構、編譯技術、CPU實現和控制技術、高速緩存與記憶體層次結構。4.Mips速率5.吞吐率系統的吞吐率:系統在單位時間內能執行多少個程式，這稱為系統的吞吐率(單位為程式數／秒)Ws

。在多道程序系統中，系統吞吐率常低於CPU吞吐率Wp。Wp可用下式表示：

或：Wp=(MIPS)×106／Ic

Wp的單位是程式數／秒。CPU吞吐率是根據MIPS速率和程式的平均長度(Ic)來衡量機器每秒鐘能執行多少個程式的尺度。Ws<Wp，用多道程序或分時操作在CPU上交叉執行多個程式時，I／O、編譯器和操作系統產生的額外系統開銷所造成的。總結：並行的產生並行背景下的計算問題串行向並行的演化並行的性能與系統的關係並行處理與體系結構第一章並行電腦模型

1計算技術的現狀

2多處理機和多電腦

3多向量機和SIMD電腦

4並行電腦的抽象模型

5可擴展的範圍和設計

2多處理機和多電腦一、共用存儲型多處理機1.UMA模型UMA

--UniformMemoryAccess

結構和特點：緊耦合系統(tightlycoupledsystem)多處理機由於高度資源共用系統的互連採用匯流排、交叉開關、或多級網路形式對稱(symmetric)多處理機當所有處理機都能同樣訪問所有週邊設備時。例Fortran程式可在單處理機上順序執行，分析CPU的運行時間，假設條件：所有數組A(I)，B(I)，C(I)都有N個元素；分析：求和Fortran程式L1:Do10I＝1，NL2:A(I)＝B(I)+C(I)L3:10ContinueL4:SUM＝0L5:Do20J＝1，NL6:SUM＝SUM+A(J)L7:20Continue假定取指令和加載數據的開銷可以忽略不計；所有數組已經裝人主記憶體，並且短程序段已經裝入高速緩衝記憶體。忽略匯流排爭用或記憶體存取衝突問題。再假設：

執行代碼行L2，L4和L6，每行要用一個機器週期。執行程式控制語句L1，L3，L5和L7所需的時間可以忽略。假定經過共用記憶體的處理機之間的每次通信操作需要k個週期。結論：CPU用2N個週期串行程序並行化在M—處理機系統上執行程式將迴圈操作劃分成M段，每段有L＝N／M個元素。假設經過共用記憶體的處理機之間的每次通信操作需要：k個週期。

Doall表示所有M段在M臺處理機上並行執行Doallk＝1，MDo10I＝L(k-1)+1，kL。

A(I)＝B(I)+C(I)10ContinueSUM(k)＝0Do20J＝1，LSUM(k)=SUM(k)+A(L(k-1)+J)20ContinueENDall分析：迴圈1是L個週期；迴圈2是L個週期總時間：2L+h(k+1)=2N/M+(k+1)log2M2.NUAM模型3.COMA模型概念：只使用高速緩存的多處理機實現的機器：瑞典電腦科學研究所的數據擴散機(DDM，Hagersten等，1990)KendallSquareReserch公司的KSR—1機器(Burkhart等，1992)。特點：COMA模型是NUMA機的一種特例，將NUMA中分布主記憶體換成了高速緩存；全部高速緩衝記憶體組成了全局地址空間；遠程高速緩存訪問則借助於分佈高速緩存目錄進行，分級目錄往往可用來尋找高速緩存塊的副本，這與所用的互連網絡有關；數據的初始位置並不重要，因為它最終將會遷移到要用到它的地方。模型的演變：例如，高速緩存一致性非均勻存儲存取(CC—NUMA)模型。可以用分佈共用記憶體和高速緩存目錄來描述。CC—NUMA模型的實例斯坦福大學的Dash系統(Lenosh等，1990)和麻省理工學院的Alewife系統(Agarwal等，1990)；這些將在後面討論。4.典型的多處理機二、分佈存儲型多電腦系統1.概念由多個電腦結點，通過消息傳遞網路互相連接而成，每個結點是一臺由處理機、本地記憶體和有時接有磁片或I／0週邊設備組成的自治的電腦。2.特點：消息傳遞網路提供結點之間的點到點靜態連接傳統的多電腦已被稱為近地存儲訪問(NORMA)機所有本地記憶體是私用的，而且只有本地處理機才能訪問；私用記憶體逐漸在分佈共用記憶體的多電腦中將被逐步取消。3.多電腦的換代現代多電腦用硬體尋徑器來傳送資訊；電腦結點與尋徑器相連，邊界上的尋徑器與I／O和週邊設備連接；任何兩結點間的消息傳遞會涉及一連串的尋徑器和通道。在異構多電腦系統中，可以有多種類型的結點，結點間的通信是通過可相容的數據表示和消息傳遞協議來實現的。消息傳遞型多電腦的發展換代

第一代(1983—1987)是基於處理機板技術，採用了超立方體結構和軟體控制的消息交換方法。加州理工學院的Cosmic和InteliPSC／1是這一代研製的代表。第二代(1988—1992)是用網格連接的系統結構、硬體消息尋徑和中粒度分佈計算的軟體環境實現的；IntelParagon和ParsysSuperNodel000可作為代表性產品。現在面臨的第三代(1993—)預期是細粒度電腦麻省理工學院的J-Machine和加州工學院的Mosaic，VLSI片上實現處理機和通訊工具。

示例：IBMPOWER4體系結構特點PowerPC64位體系結構單晶片雙處理器，MCM八處理器集成多處理器互連接口集成I/O控制器集成L3Cache控制器集成存儲控制器IBMPOWER4(MCM結構)IBMPOWER4(32CPU)4.典型多電腦多電腦的可編程性取決於:高效編譯器實用高效的分佈式操作系統實用總結：本節區分了多處理機和多電腦的主要差別和分類。

3多向量機和SIMD電腦一、向量超級電腦1.早期的超級電腦可分為：流水線向量機；SIMD電腦兩類。執行過程：當譯出的指令為向量操作；它將被送至向量控制器，控制器將監督主記憶體與向量功能流水線之間的向量數據流，向量數據流由控制器協調控制；向量處理機則裝有若干條向量功能流水線。2.寄存器—寄存器的系統結構如1976年推出的Cray1。向量寄存器用來保存向量運算元、中間和最終的向量結果;向量功能流水線從向量寄存器檢索運算元，並將結果放入寄存器。

3.記憶體—記憶體結構這種結構比較早，與寄存器—寄存器結構的區別就在於採用向量流水部件代替了向量寄存器。例如:二、SIMD超級電腦1.SIMD的操作模型可用五元組表示M＝<N，C，I，M，R>N為機器的處理單元(PE)數。例如，illiacIV有64個PE，而連接機(ConnectionMachine)CM—2採用65536個PE。C為由控制部件(CU)直接執行的指令集；包括標量和程式流控制指令。I為由CU廣播至所有PE進行並行執行的指令集；它包括算術運算、邏輯運算、數據尋徑、遮罩以及其他由每個活動的PE對它的數據所執行的局部操作。M為遮罩方案集其中每種遮罩將PE集劃分為允許操作和禁止操作兩種子集。R是數據尋徑功能集說明互連網絡中PE間通信所需要的各種設置模式。示例：描述具體的SIMD機器MasParMP—1電腦的操作特性--五元組特性：MP—1是一種SIMD機器，其PE數N＝1024至16384。PE數目與機器配置有關。CU執行標量指令，將解碼後的向量指令播送到PE陣列，並控制PE間的通信。每個PE都是基於寄存器的加載／存儲RISC處理機，能執行不同數據量的整數運算和標準浮點運算。各PE從CU接受指令。遮罩方案設在每個PE中，並由CU連續監控，它能在運行時動態地使每個PE處於置位或複位狀態。例如：MP—1有一個X—Net網格網路和一個全局多級交叉開關尋徑器，以實現CU—PE之間、X—Net的8個近鄰之間和全局尋徑器的通信。2.SIMD的實施模型（1）分佈式記憶體模型記憶體分佈的SIMD特點：SIMD電腦開發的是PE之間的空間並行性。記憶體分佈的SIMD電腦由同一陣列控制部件控制的PE陣列組成。程式和數據通過主機裝入控制記憶體。指令是送到控制部件進行解碼。標量操作或控制操作，則將直接由與控制部件相連的標量處理機執行。向量操作，則將它廣播到所有PE並行地執行。劃分後的數據集合通過向量數據匯流排廣播到所有PE的本地記憶體。PE通過數據尋徑網路互連。數據尋徑網路執行PE間的通信，如移數、置換和其他尋徑操作。控制部件通過執行程式來控制數據尋徑網路。PE的同步由控制部件的硬體實現。所有PE在同一個週期執行同一條指令。可以用遮罩邏輯來決定任何一個PE在給定的指令週期執行或不執行指令。（2）

共用記憶體模型是一種PE使用共用記憶體的SIMD電腦。PE和記憶體之間的通信網絡是一個對準網路，它也受控制部件控制。

95

2多處理機和多電腦一、共用存儲型多處理機1.UMA模型UMA

--UniformMemoryAccess

結構和特點：9697緊耦合系統(tightlycoupledsystem)多處理機由於高度資源共用系統的互連採用匯流排、交叉開關、或多級網路形式對稱(symmetric)多處理機當所有處理機都能同樣訪問所有週邊設備時。98例Fortran程式可在單處理機上順序執行，分析CPU的運行時間，假設條件：所有數組A(I)，B(I)，C(I)都有N個元素；分析：求和Fortran程式99L1:Do10I＝1，NL2:A(I)＝B(I)+C(I)L3:10ContinueL4:SUM＝0L5:Do20J＝1，NL6:SUM＝SUM+A(J)L7:20Continue假定取指令和加載數據的開銷可以忽略不計；所有數組已經裝人主記憶體，並且短程序段已經裝入高速緩衝記憶體。忽略匯流排爭用或記憶體存取衝突問題。100再假設：

執行代碼行L2，L4和L6，每行要用一個機器週期。執行程式控制語句L1，L3，L5和L7所需的時間可以忽略。假定經過共用記憶體的處理機之間的每次通信操作需要k個週期。結論：CPU用2N個週期101串行程序並行化在M—處理機系統上執行程式將迴圈操作劃分成M段，每段有L＝N／M個元素。假設經過共用記憶體的處理機之間的每次通信操作需要：k個週期。

102Doall表示所有M段在M臺處理機上並行執行Doallk＝1，MDo10I＝L(k-1)+1，kL。

A(I)＝B(I)+C(I)10ContinueSUM(k)＝0Do20J＝1，LSUM(k)=SUM(k)+A(L(k-1)+J)20ContinueENDall103分析：迴圈1是L個週期；迴圈2是L個週期總時間：2L+h(k+1)=2N/M+(k+1)log2M1042.NUAM模型1053.COMA模型概念：只使用高速緩存的多處理機106實現的機器：瑞典電腦科學研究所的數據擴散機(DDM，Hagersten等，1990)KendallSquareReserch公司的KSR—1機器(Burkhart等，1992)。107特點：COMA模型是NUMA機的一種特例，將NUMA中分布主記憶體換成了高速緩存；全部高速緩衝記憶體組成了全局地址空間；遠程高速緩存訪問則借助於分佈高速緩存目錄進行，分級目錄往往可用來尋找高速緩存塊的副本，這與所用的互連網絡有關；數據的初始位置並不重要，因為它最終將會遷移到要用到它的地方。108模型的演變：例如，高速緩存一致性非均勻存儲存取(CC—NUMA)模型。可以用分佈共用記憶體和高速緩存目錄來描述。CC—NUMA模型的實例斯坦福大學的Dash系統(Lenosh等，1990)和麻省理工學院的Alewife系統(Agarwal等，1990)；這些將在後面討論。1094.典型的多處理機110二、分佈存儲型多電腦系統1.概念由多個電腦結點，通過消息傳遞網路互相連接而成，每個結點是一臺由處理機、本地記憶體和有時接有磁片或I／0週邊設備組成的自治的電腦。1111122.特點：消息傳遞網路提供結點之間的點到點靜態連接傳統的多電腦已被稱為近地存儲訪問(NORMA)機所有本地記憶體是私用的，而且只有本地處理機才能訪問；私用記憶體逐漸在分佈共用記憶體的多電腦中將被逐步取消。1133.多電腦的換代現代多電腦用硬體尋徑器來傳送資訊；電腦結點與尋徑器相連，邊界上的尋徑器與I／O和週邊設備連接；任何兩結點間的消息傳遞會涉及一連串的尋徑器和通道。在異構多電腦系統中，可以有多種類型的結點，結點間的通信是通過可相容的數據表示和消息傳遞協議來實現的。114消息傳遞型多電腦的發展換代

第一代(1983—1987)是基於處理機板技術，採用了超立方體結構和軟體控制的消息交換方法。加州理工學院的Cosmic和InteliPSC／1是這一代研製的代表。第二代(1988—1992)是用網格連接的系統結構、硬體消息尋徑和中粒度分佈計算的軟體環境實現的；IntelParagon和ParsysSuperNodel000可作為代表性產品。115現在面臨的第三代(1993—)預期是細粒度電腦麻省理工學院的J-Machine和加州工學院的Mosaic，VLSI片上實現處理機和通訊工具。116

示例：IBMPOWER4體系結構特點PowerPC64位體系結構單晶片雙處理器，MCM八處理器集成多處理器互連接口集成I/O控制器集成L3Cache控制器集成存儲控制器117118IBMPOWER4(MCM結構)119IBMPOWER4(32CPU)1204.典型多電腦多電腦的可編程性取決於:高效編譯器實用高效的分佈式操作系統實用121122總結：本節區分了多處理機和多電腦的主要差別和分類。123

3多向量機和SIMD電腦一、向量超級電腦1.早期的超級電腦可分為：流水線向量機；SIMD電腦兩類。124125執行過程：當譯出的指令為向量操作；它將被送至向量控制器，控制器將監督主記憶體與向量功能流水線之間的向量數據流，向量數據流由控制器協調控制；向量處理機則裝有若干條向量功能流水線。1262.寄存器—寄存器的系統結構如1976年推出的Cray1。127128向量寄存器用來保存向量運算元、中間和最終的向量結果;向量功能流水線從向量寄存器檢索運算元，並將結果放入寄存器。129

3.記憶體—記憶體結構這種結構比較早，與寄存器—寄存器結構的區別就在於採用向量流水部件代替了向量寄存器。例如:130131132二、SIMD超級電腦1331.SIMD的操作模型可用五元組表示M＝<N，C，I，M，R>N為機器的處理單元(PE)數。例如，illiacIV有64個PE，而連接機(ConnectionMachine)CM—2採用65536個PE。C為由控制部件(CU)直接執行的指令集；包括標量和程式流控制指令。134I為由CU廣播至所有PE進行並行執行的指令集；它包括算術運算、邏輯運算、數據尋徑、遮罩以及其他由每個活動的PE對它的數據所執行的局部操作。M為遮罩方案集其中每種遮罩將PE集劃分為允許操作和禁止操作兩種子集。R是數據尋徑功能集說明互連網絡中PE間通信所需要的各種設置模式。135示例：描述具體的SIMD機器MasParMP—1電腦的操作特性--五元組特性：MP—1是一種SIMD機器，其PE數N＝1024至16384。PE數目與機器配置有關。CU執行標量指令，將解碼後的向量指令播送到PE陣列，並控制PE間的通信。136每個PE都是基於寄存器的加載／存儲RISC處理機，能執行不同數據量的整數運算和標準浮點運算。各PE從CU接受指令。遮罩方案設在每個PE中，並由CU連續監控，它能在運行時動態地使每個PE處於置位或複位狀態。例如：MP—1有一個X—Net網格網路和一個全局多級交叉開關尋徑器，以實現CU—PE之間、X—Net的8個近鄰之間和全局尋徑器的通信。1372.SIMD的實施模型（1）分佈式記憶體模型138記憶體分佈的SIMD特點：SIMD電腦開發的是PE之間的空間並行性。記憶體分佈的SIMD電腦由同一陣列控制部件控制的PE陣列組成。程式和數據通過主機裝入控制記憶體。指令是送到控制部件進行解碼。標量操作或控制操作，則將直接由與控制部件相連的標量處理機執行。向量操作，則將它廣播到所有PE並行地執行。139劃分後的數據集合通過向量數據匯流排廣播到所有PE的本地記憶體。PE通過數據尋徑網路互連。數據尋徑網路執行PE間的通信，如移數、置換和其他尋徑操作。控制部件通過執行程式來控制數據尋徑網路。PE的同步由控制部件的硬體實現。所有PE在同一個週期執行同一條指令。可以用遮罩邏輯來決定任何一個PE在給定的指令週期執行或不執行指令。140（2）

共用記憶體模型是一種PE使用共用記憶體的SIMD電腦。PE和記憶體之間的通信網絡是一個對準網路，它也受控制部件控制。

4並行電腦的抽象模型並行電腦的理論模型是從物理模型抽象的；為開發並行演算法提供了一種方便的框架；用這些模型可求得並行電腦的理論性能界限；可在晶片製作前估算晶片區的VLSI複雜性和執行時間。一、時間與空間複雜性電腦求解一個規模為s的問題的演算法複雜性取決於：執行時間存儲空間時間複雜性：時間複雜性g(s)為O(f(s))，可讀作“數量級為f(s)”，如存在正的常量c和s0，則對所有s>s0的非負值就有g(s)≤cf(s)。空間複雜性為問題規模s的函數。漸近空間複雜性(asymptoticspacecom—plexity)主要與大問題的數據存儲有關，而程式(代碼)存儲的需求和輸入數據的存儲不考慮在內。串行演算法的時間複雜性簡稱為串行複雜性;並行演算法的時間複雜性就稱為並行複雜性;並行複雜性應比串行複雜性低，至少是相近。只考慮確定性演算法。NP完全性：P類(即多項式類)：具有多項式複雜性演算法的問題集，如果存在一多項式p(s)，對任何問題規模s的時間複雜性為O(p(s))，則某演算法即具有多項式複雜性。NP類(即不確定性多項式類)：能以多項式時間，用不確定性演算法求解的問題集。P

NP確定性演算法是不確定演算法的特殊情況。P類問題是計算易解的，而NP-P類問題是難解的。現在不知道是否P＝NP或P≠NP。難解的NP類問題又稱為具有指數時間複雜性的問題。例題：多項式複雜性和指數複雜性演算法：將幾個數排序的多項式時間複雜性分別為O(nlogn)，屬於P類對兩個n×n矩陣相乘演算法的多項式時間複雜性分別為O(n3)，屬於P類。旅行推銷員問題複雜性為O(n22n)和背包問題的複雜性為O(2n/2)指數複雜性問題是屬NP類的：到目前為止還未發現這類問題的確定性多項式演算法。P、NP和NPC（NP完全問題）二、並行隨機存取機模型(ParallelRandom—AccessMachine，PRAM)目的：可用來開發並行演算法和分析可擴展性及複雜性。MIMD細粒度嚴格同步零開銷共用變數在PRAM上的一個並行程式由n個進程組成，其中第i個進程留駐在第i個處理器上，且由一串指令所組成。在每個基本時間步(稱為週期)，每個處理器執行一條指令。這些指令包括數據傳送、算/邏、控制流以及I/O指令，在典型的順序電腦中均有這些指令。1.同構性規模為1的PRAM退化為傳統的RAM。這種機器為SISD。當處理器多於1個時，一個PRAM將訪問多個數據流，且通常可執行多個指令流。因此PRAM是一個MIMD機器。MIMD的特例:如果在每一週期，所有處理器必須執行相同指令，即只有一個指令流時，則PRAM就成為單指令(流)、多數據(流)(SIMD)機器。(SPMD)計算：單程序、多數據，所有進程執行同一程式，而由進程指標加以參數化。SIMD和SPMD間的差別是，在SPMD計算中，同一週期可以執行不同指令。2.同步性進程同步是嚴格的。PRAM是在指令級同步的。3.交互機制這一屬性描述了並行進程間如何相互影響行為的特性。在PRAM模型中，進程間通過共用變數(或共用記憶體)進行交互。4.地址空間理論PRAM模型的一個重要特徵是所有進程對所有存儲單元均有相等的訪問時間。這種機器為均勻記憶體訪問(UMA)。在多電腦中，每個處理機有它自己的分離地址空間。這些機器被稱為具有多地址空間。多電腦的處理機間通信不是通過共用變數，而是借助消息傳遞。5.記憶體模型各種方案的主要區別在於如何協調CW的衝突。四種PRAM模型方案都與記憶體讀寫如何處理有關。(1)EREW-PRAM模型——這種模型禁止一臺以上處理機同時讀、寫同一存儲單元(Snir，1982；Karp和Ramachandran，1988)。這是限制最大的PRAM模型。(2)CREW-PRAM模型——用互斥使寫衝突避免。可以並行讀同一存儲單元。

(3)ERCW-PRAM模型——允許互斥讀或並行寫同一存儲單元。(4)CRCW-PRAM模型——允許在同一時刻並行讀或者並行寫。寫衝突可用下述四種策略之一分解：共用——所有同時進行的寫操作將相同數據存入熱點存儲單元。任選——將任何一個要寫的數保存起來，而其他的忽略不計。最小值——將處理機要寫的下標值最小的數保存起來。優先——對要寫的數用求和或求最大值等聯想函數加以組合。

6.原子操作原子操作的定義：一個原子操作是指有如下特性的一種操作。不可分有限更嚴格的原子操作定義：需要滿足以下的4個性質。稱這樣的原子操作為一個事務操作。

原子性一致性隔離性持續性7.例題例題1：在一臺處理機數為n3／logn的PRAM上，用O(logn)時間完成兩個”nxn”矩陣的乘法(ViktorPrasanna，1992)設A和B為輸入矩陣，假定最初可用的PE數為n3個，後來降為n3／logn個。

假設記憶體由三維陣列組成，將A、B存入其中兩個平面。假設了PE的三維地址指標。PE(i，j，k)，0≤k≤n-1可用來計算輸出矩陣的第(i，j)項，0≤i，j≤n-1，n是2的冪。

第一步，對應於每個輸出的n乘積項用n個PE在O(1)時間內進行計算。第二步，這些乘積項用O(logn)時間相加產生一個輸出。所用的PE總數為n3，結果存在C(i，j，0)中(0≤i，j≤n-1)。假定這裏的PRAM採用的是CREW策略。Step1：1．ReadA(i，k)2．ReadB(k，j)3．ComputeA(i，k)×B(k,j)4．StoreinC(I,j,k)

Step2：

1．L←n2．RepeatL←L／2If(k<1)thenbegin

ReadA(i，k)ReadA(i，k)ComputeC(i,j,k)+C(i,j,k,k+l)StoreinC(i,j,k)EndUntil(l=1)上述是每個PE(i，j，k)要執行的程式。所有n3個PE對n3乘法進行並行運算。但對完成(n3-n2)加法最多只有n3／2個PE處於工作狀態。為了將PE數降為n3／logn，可採用nXnXn／logn的PE陣列。每個PE負責計算logn個乘積項並將它們求和。第一步很容易改寫產生n／logn個部分和，每一個部分和由logn次乘法和(logn-1)次加法完成。我們有數組C(i，j，k)，0≤i，j≤n-1，0≤k≤n／logn-1，它們可在log(n／logn)時間內完成求和，所以將第一步和第二步所花的時間相加，我們就得到總執行時間為2logn-1+log(n／logn)，在n比較大時近似為O(logn)。例題2：PRAM步中的計算複雜性

假設有三個PRAM演算法A，B和C，當在一個有n個處理器的PRAM電腦上執行時，各自的時間複雜性為A--7n，B--(nlogn)／4C--nloglogn。根據大O標誌：演算法A最快：(O(n))，C次之：O(nloglogn)，B為最慢：O(nlogn)。而實際上，當機器的處理器數小於、等於1024時，有logn<log1024=10以及loglogn≤loglog1024<4。如果，處理器數小於1024時：演算法B最快，其次是C，而A則是最慢的。與物理模型的差異

實際上，這種並行電腦是不存在的。共用記憶體SIMD機是與PRAM模型最接近的結構。更確切地說，共用存儲的同步MIMD模式運行。四種PRAM方案中，EREW和CRCW是應用最普遍的模型。每個CRCW演算法可用一個EREW演算法來模擬。CRCW演算法比一個等效的EREW要快，經證明，最好的n—處理機EREW演算法要比任一個n-處理機CRCW演算法慢O(logn)倍。對研究結構規則的並行性來說，用PRAM比用實際機器模型要好得多。PRAM能指出實際並行電腦性能的上限。三、非同步PRAM模型—APRAM是一個非同步的PRAM模型，簡記為APRAM1.模型特點：由p個處理器組成；每個處理器都有其本地記憶體、局部時鐘和局部程式；處理器間的通信經過共用全局記憶體；無全局時鐘各處理器非同步地獨立執行各自的指令；處理器任何時間依賴關係需明確地在各處理器的程式中加入同步(路)障(SynchronizationBarrier)；一條指令可在非確定但有限的時間內完成。2、APRAM模型中的指令類型有四類指令：①全局讀將全局存儲單元中的內容讀入局存單元中；②局部操作對局存中的數執行操作，其結果存入局存中；③全局寫將局存單元中的內容寫入全局存儲單元中；④同步同步是計算中的一個邏輯點，在該點各處理器均需等待別的處理器到達後，才能執行其局部程式。3.APRAM模型中完成的計算

計算是由一系列用同步障分開的全局相所組成。在各全局相內，每個處理器非同步地運行其局部程式；每個局部程式中的最後一條指令是一條同步障指令；各處理器均可非同步地讀取和寫入全局記憶體，在同一相內不允許兩個處理器訪問同一單元。不同的處理器訪問存儲單元總是由一同步障所分開，所以指令完成時間上的差異並不影響整個計算4.APRAM模型中的時間計算使用APRAM模型計算演算法的時間複雜度時，假定局部操作取單位時間；全局讀／寫時間為d它定量化了通信延遲，代表讀/寫全局記憶體的平均時間，d隨機器中的處理器增加而增加；同步障的時間為B它是處理器數P的非降函數B=B(P)。在APRAM中假定上述參數服從如下關係：2≤d≤B≤P同時：B(P)∈O(dlogP)或B(P)∈O(dlogP/logd)。令tph為全局相內各處理器指令執行時間中最長者，則整個程式運行時間T為各相的時間之和加上B乘以同步障次數，即:T=∑tph+B×同步障次數四.BSP模型BSP-BulkSynchronizationParallel1.BSP模型的提出：哈佛大學的LeslieValiant提出：塊同步並行(BSP)，用以克服PRAM模型的缺點，但保留其簡單性。一個BSP電腦由n個結點(處理器和記憶體對)所組成。2.特點：一個BSP程式有n個進程，每個駐留在一個結點上。基本時間單位是週期(或時間步)。程式按嚴格的超步序列執行。特點：同步路障迫使進程等待BSP電腦是MIMD系統BSP模型是超步級的松同步在一個超步中，不同進程以不同速率非同步執行。BSP模型交互機制是共用變數或是消息傳遞。3.h關係的定義:一個h關係是任何通信操作的抽象，在其中，每個結點最多發出h個字到各結點，並且每個結點最多接收h個字。在一個BSP電腦中，實現任何h關係的時間不會超過gh個週期。g是由機器平臺決定的一個常數。

4.一個超步執行時間的確定計算時間w處理器中完成計算操作所需的最大週期數。同步開銷為L。通信開銷為gh週期g是實現h關係的比例係數，常數。結論：執行一個超步的時間為w+gh+L5.例題：在一個有n個處理器的EREWPRAM電腦上，對兩個N維向量A和B求內積s，可指派每個處理器完成2N／n個加法和乘法（2N／n+logn）；改用BSP機器模型實現一個並行執行上述內積求解。在一個有8個處理器的BSP電腦上，用4個超步完成問題求解：超步１：每個處理器在w=2N／8週期內計算，求出局部和。通信1次：處理器0，2，4，6將其局部和→處理器1，3，5，7。路障同步。超步２：計算１、３、５、７各自完成一次加法；通訊1次：處理器１，５中間結果送處理器３和７。路障同步超步３：計算：處理器３和處理器７，各完成一次加；通訊：處理器３→處理器７，完成一次通訊路障同步。超步4計算：處理器7完成一次加法(w＝１）產生最後和。不再需要任何通信或同步。總執行時間：2N／8+3g+3Ｌ+3個週期總之：點積在一個有n個處理器的BSP電腦上，執行時間為：2N／n+logｎ(g+L+1)個週期。與PRAM電腦的2N／n+logn時間相比:多了兩項glogn和Llogn

關於BSP模型的實際優點和評論：比起PRAM模型來，BSP模型更為現實除了用於進程管理的並行性開銷外，它考慮了所有其他開銷。五.VLSI複雜性模型基本概念VLSI複雜性模型

背景：以ClarkThompson(1980)的研究工作為基礎的二維VLSI晶片的AT2模型。AT2模型：

設A是用VLSI電路晶片完成給定運算的晶片面積，T為執行時間，又設s為運算問題的規模。Thompson在其博士論文中曾指出：對某些運算存在一個下界f(s)，有AT2≥O(

f(s))1、晶片面積A的存儲界限許多計算在需要處理大型數據集時常受到記憶體的限制。計算對存儲量的需求常常決定了晶片面積A的下限。2、AT體積的I/O界限可以用乘積AT來表示I／O的下限。3、等分通信界限A1/2Ｔ

等分面積A1/2Ｔ，限定通信的下限。4、例題：矩陣相乘演算法的VLSI晶片的實現(VictorPrasanna，1992)

要求：在一個每行和每列處理單元(PE)都有廣播匯流排的網格系統上做n×n矩陣乘法C＝A×B如何計算晶片面積A和計算時間T？分析：二維網格結構如下圖所示。PE間的通信通過廣播匯流排實現。每個PE佔據一單位面積：總晶片面積為O(n2)。廣播匯流排需要O(n2)導線面積。nXn矩陣相乘可在此網格晶片上完成的時間為T＝O(n)。說明：PE表示成PE(i，j)，0≤i，j≤n-1。記憶體分佈在所有的PE上，每個PE只能訪問自己的本地記憶體。下麵的並行演算法，可完成C(i，j)＝∑n-1k=0A(i，k)XB(k，j)，其中0≤i，j≤n-1的點積運算，並產生全部輸出元素。Doall10for0≤i，j≤n-110PE(i，j)setsC(i,j)to0／Initializaton／Do50for0≤k≤n-1Doall20for0≤i≤n-120PE(i，k)broadcastA(i，k)alongisrowbusDoall30for0≤j≤n-130PE(k，j)broadcastB(k，j)alongitscolumnbus／PE(i，j)nowhasA(i，k)andB(k，j)，0≤i，j≤n/Doall40for0≤i，j≤n-1

40PE(i，j)computes

C(i，j)←C(i，j)+A(i，k)XB(k，j)50Continue210

5可擴展的範圍和設計一、可擴展性範圍二、可擴展設計原理211一、可擴展性範圍說明：系統伸縮：增加或減少系統資源。這裏假定並行處理電腦的體系中的結點均為單一處理器結點可擴展性範圍包括：資源可擴展性應用可擴展性技術可擴展性

2121.資源可擴展性

資源可擴展性是指通過增加處理器數、更多的存儲部件(高速緩存，存，磁片)以及增加軟體等方法，使系統具有更高性能或功能。涉及三方面：規模可伸縮性資源擴展軟體可擴展性213（1）規模可伸縮性：規模可伸縮性與處理器數相關聯。擴展一個電腦系統---增加機器規模（處理器數）。不同並行電腦規模可擴展能力不同。限制並行系統可擴展性的兩個主要因素是：程式設計及通信。214示例：在1997年時：一個對稱多處理機(SMP)系統最多能擴展到大約64個處理器；一個IBMSP2並行機能擴展到最多具有512個處理器。

215當前的並行電腦規模的擴展：加入更多處理器；增加互連網絡、介面以及通信軟體在內的子系統。有效地利用更大並行性，即如何為擴大的系統進行編程。216（2）資源擴展增加處理器數不是唯一方式。保持處理器數不變；通過增加更多存儲容量、更大的晶片外高速緩存以及更大容量磁片等方法來擴展系統。217例題：IBMSP2中的記憶體需求當Maui高性能計算中心(MHPCC)決定升級它的具有400個結點的SP2系統時，它選擇了增加記憶體和磁片容量方法，而不是增加更多結點數方法。下表概述了所擴展的存儲容量。218219要求：系統必須設計成能允許擴展這麼多的容量。實際系統總有一個最大記憶體容量的上限。例如：IBMSP2中的每個結點最多可容納2GB記憶體；CrayT3D為64MB。220（3）軟體可擴展性包括：操作系統的一個新版本，它具有更多功能性，如多線程，從而可支持更多的用戶進程，更大的地址空間以及更高效的內核功能等。具有更有效優化的編譯器。更有效的數學和工程庫。更有效和易於使用的應用軟體。對用戶更友好的編程環境。2212、應用可擴展性

相同程式在一個可擴展系統上運行時，其性能隨規模擴大成比例地改進。兩個度量：机器规模可扩展性。問題規模的可擴展性。（1）機器規模可擴展性隨著附加處理器的增多，系統性能會有多大改進。222例如，假定一個有n個處理器的系統，作數據庫伺服器用它擁有美國人口資料庫，通常有100位美國科學家查詢，其性能為每秒1000個事務處理(TPS)。現在如果我們將處理器數加倍成2n，能期望速度有多少改進?期望是多少？所增加的資源中，處理器最為常見；也可能是記憶體容量和I／O容量。223（2）問題規模可擴展性是指系統在處理更大數據量和工作負載的更大求解問題時其性能如何。例如：仍以上述的資料庫伺服器為例，如果該伺服器上裝有中國人口的資料庫，則此伺服器的服務品質將會如何?注意到此資料庫的大小已增至原來的5倍。如果用戶數增至200(100個美國和100中國科學家聯合參與研究)，將會發生什麼情況?224在研究應用可擴展性時，有以下3點值得注意：許多實際的並行應用問題對於機器和問題規模已有內在限制應將“應用／機器”一起視為一個系統它也依賴於資源規模。2253、技術可擴展性

是指該系統能適應技術的改變。它可進一步分為3類：代可擴展性，空間可擴展性，異構可擴展性。226（1）

代(時間)可擴展性一個系統擴展可以通過使用：下一代的硬體部件；更快的處理器更快記憶體新版本的操作系統；更強功能的編譯器。227電腦系統中發展最快的部件是處理器；進展最慢的部分是程式設計語言(Fortran77仍被廣泛使用)；單電腦每兩年可以將處理器升級一次並以慢得多的速度更新其他部件。並行電腦中這種更新不活躍。228例題：IBM個人電腦的代可擴展性

最具有代可擴展的電腦是IBMPC機。PC系統(從處理器到母板、I／O卡和軟體)是設計成代可擴展的。

現有系統中的二進位代碼和應用程式(DOS、Windows、資料庫、電子錶格及字處理軟體等)不用作任何修改，就可在升級的系統中運行得更快。229（2）空間可擴展性這一用語是由GordenBell發明的，用來表示一個系統可從一個盒子、一間房間或一幢大樓中的多處理器擴展到多幢大樓和地理範圍(遠距離範圍)中的多處理器的能力。SMP和MMP只具有有限的空間可擴展性因特網則具有最好的空間可擴展性230（3）異構可擴展性一個系統擴展不同設計者和廠商所提供的硬體和軟體部分的能力。系統應使用具有標準、開放系統結構和介面的部件。231例題1：可擴展並行電腦的軟體可移植性

IBM並行操作環境(POE)在任何規模的RS6000系統上具有可擴展性。232POE特點：支持一個並行程式無需任何修改就能在由RS6000結點機構成的任何網路中運行結點可以是一個低端PowerPC工作站，可以是一個高端SP2寬結點。這些結點能由任何普通互聯網路，從慢速以太網到SP2的高性能開關(HPS)，加以連接。結點只見的距離不限。233例題2：並行虛擬機(PVM)，它也是異構可擴展的：它允許一個並行程式運行在來自不同廠商的結點機所構成的網路上。234二、可擴展設計原理包括：獨立原理平衡設計原理可擴展性設計原理時延隱藏原理(第5章介紹）

2351.獨立原理（1）定義：應努力使系統中的各個組成部分（硬、軟體）相互獨立。如果無法達到完全獨立，則應盡力使相關程度減至最小並使相關性儘量清晰。236（2）採用獨立原理的優點：使獨立擴展成為可能；使異構可擴展性成為可能；要求部件不受制於一個特別的體系結構或系統。

237（3）獨立系統的特點：有一個開放的體系結構，有一個與系統其他部分銜接的標準介面；是市售產品，若不具有版權則更好；有多家供應商，在公開市場大批量供應；相對成熟，已為許多人使用相當長時間，且已完成必要的排錯。

238（4）獨立原理涉及的範圍：演算法應獨立於體系結構。應用應獨立於平臺。程式設計語言應獨立於機器。語言應模組化且具有獨立性。結點應獨立於網路，而網路介面應獨立於網路拓撲。239例題1，開發Internet和IBMSP2中所體現的獨立精神Internet的成功是表現獨立原理優點的完美例子。Internet獨立於主機、互連硬體和應用軟體。由不同供應商提供的，從PC機到超級電腦的不同類型主機相互連接起來。互連硬體可以是以太網、FDDI等。用戶能用不同軟體流覽Web萬維網。240例題2：IBMSP2設計結合了獨立原理設計的結點體系結構允許使用不同的通信體系結構(例如以太網或HPS)。通信協議獨立於通信硬體：如以太網或HPS，都允許使用標準IP協議或IBM專用用戶空間協議。241例題3：MPI及超立方體電腦消息傳遞介面(MPl)是使用少量獨立(正交)語言特徵的成功範例。MPI基於4個相互正交的主要概念：數據類型通信操作通信子虛擬拓撲4者的任何組合均是有效的。242為較早期的超立方體電腦而開發的許多並行演算法顯式地使用超立方體的互連拓撲，但在網路連接系統中，它們並不適用。現在的MPP使用獨立於互連拓撲的通信演算法。IBMSP系統中的集合通信庫便是一個很好的例子。243（5

）實現獨立原理的兩種通用技術：將體系結構和實現分開使用標準組件244體系結構和實現的分開體系結構是系統組件的公共行為或是功能性精確模型；實現是對模型的具體實施；用戶和設計者均可使用體系結構模型。一個體系結構可有許多不同實現，它們會有不同性能，但實現相同功能。245開放體系結構：體系結構的擁有者允許用戶或第3方瞭解體系結構；用戶可自己製造與體系結構相容的組件，甚至修改或重新加以設計；IBMPC機證實了這的確是一個技術上有影響的、商業上可行的。246使用標準組件

有兩種標準類型：工業標準(也稱為事實標準)，它通常為某公司所宣導，然後被最終用戶廣泛使用並為工業界的大多數所接受。由國家或國際標準機構所設立的標準，如國際標準組織(ISO)，美國國家標準機構(ANSl)以及IEEE標準委員會。247（6）在使用獨立原理時應注意：並行電腦中通常有某種關鍵組件和技術是先進的，但往往還不是標準。不可能靠簡單地單純擴展一個或少數幾個組件建成一個有效的系統。必須在所有獨立的子系統設計之間達到平衡。2482.平衡設計原理應努力最小化任何性能瓶頸。應避免不平衡系統的設計，在這種系統中，一個慢速的部件將降低整個系統性能，即使其他部件都是快速的也無濟於事。應避免單點失效，即一個部件失效將使整個系統崩潰。249（1）Amdahl定律:假定一個應用程式可分為兩類計算結構：X部分和Y部分。兩部分各自所占的總執行時間分別為：X％和Y％：250如果對X％作了某種改進後能以原來n倍速度運行，則加速比S定義如下：251此方程被稱為Amdahl定律，含義：應優化較大部分X，加速普通部分。最好加速比的上限值為1／Y。慢速部分Y稱為瓶頸，應使Y盡可能小。252Amdahl法則：處理速度應與記憶體容量和I／O速度相平衡。實現：粗略地估計每秒一百萬指令(MIPS)的計算速度，應與1MB記憶體容量和1Mb／s的I／O速率相平衡。Amdahl法則在近來的系統中逐漸適用253例題：PetaFLOPS科研專案來自PetaFLOPS科研專案的近期預測表明，在科學／工程模擬求解很寬的問題範圍內，對記憶體需求(以GB計)和速度要求(以Gflop／s計)有如下關係：記憶體----速度3/4這樣30TB容量的記憶體對一個Pflop／s機器是適合的。這裏的：1Pflop／s=1,000,000Gflop／s。254例I／O和檢查點問題為了解I／O速度需求，應考慮檢查點問題：該系統需要週期地轉存記憶體內容到磁片，萬一系統崩潰時，用戶能從最近檢查點重新開始他們的工作，而不必重頭開始。255假設要求轉存在90秒內完成，那麼對1MB記憶體來講，我們需要的磁片帶寬為1／90（Mb／s）=0．01Mb／s，不接近Amdahl法則。對於更大系統，則檢查點時間就會更長。假設轉存時間為900秒，那麼對於有1GB記憶體的機器，需要的磁片帶寬為1000／900MB／s=1．1MB／s。對於100GB記憶體，對磁片I/O需求就將增至大於100MB／s。256（2）50％法則並行程式性能取決於：負載不平衡、並行化開銷、通信啟動開銷以及每位元組通信開銷。50％法則是，4個開銷因素的每一個使性能衰減都不大於50％的話，那麼就認為此並行系統是平衡的。使用這一規則，就能估計對種種開銷因素的期望界限值。257下表列出了在不同顆粒度和速度條件下，對通信啟動開銷t0的期望值。包括：啟動開銷大的機器；啟動開銷快的機器。258259當消息大小α·ω或顆粒度ω很大時，帶寬r∞=1／tc變為最重要因素。其中:α是通訊與計算的比下表列出了在不同的速度P1和α（通訊與計算的比）的一些情況下，所期望的帶寬r∞值。260261例題:PDE求解方法中的柵格點陣二維(2D)問題中的許多數值並行偏微分方程(PDE)求解方法數據域是一個有N×N個數據點的2D柵格。每個數據點需要X個位元組的記憶體，那麼總的記憶體需求為N2X位元組。該演算法完成許多(例如10000)時間步。每一步中，一個柵格點需要完成Y-flop262計算並訪問它的4個鄰點。當用單處理器執行時所需時間為：263用n個處理器的MPP處理數據域可分解成n個方塊區域，每個區域是一個(N／n1/2)x(N／n1/2)子域共有N2／n柵格點。264在每個時間步，每個處理器的計算工作負載是YN2/n。每個處理器需要從4個鄰點的每一點中獲取XN／n1/2位元組。這樣在一個有n個處理器的機器上，所需的執行時間大約為：265它的加速比因數為：266對於4種並行電腦，它們的加速比曲線如圖所示：267第1個系統的處理器速度為：50Mflop／s，它們用t0=550Bs以及r∞=1MB／s的慢速通信網互連。此網路速度與以太網的點對點通信相近。當問題規模N=1024時，系統A的加速比很差(在圖中的下方用正方塊曲線表示)，128個處理器的加速比小於10。268當問題規模增至8倍為8K時(圖中用菱形曲線表示)，加速比有很大改進。此時顆粒度W增大了，通信-計算比α減小了。269第2個系統(上圖中用三角曲線表示)的處理器速度為：100Mflop／s（比第一個系統快一倍)，它們用同樣的慢速網互連。由於這是不平衡設計，在問題規模N=8192時，加速比下跌。

270第3個系統在圖中的頂部，用圓圈曲線表示；比系統B更為平衡，它的100Mflop／s處理器用類似於IBMSP2的快速網互連，t0=46μs，r∞=35MB／s。它的平衡設計使得它在3臺機器中具有最好的性能。2713、可擴展性設計在設計一個可擴展的系統時，應該從一開始就將可擴展性作為主要目標，而不是設計完成後再來考慮這一問題。必須為系統將來可能擴展以提供更高性能或縮小以使價格降低或是有更大的成本有效性作好準備。可擴展性設計的兩種流行方法：過度設計；向後相容性。272（1）過度設計使用過度設計技術是指系統在設計時不單純地只是為了滿足目前系統的最低需要。設計必須包括一些附加特性，以期在未來的擴展系統中性能得到改進。273例1：現代處理器設計中的地址空間

在設計處理器時要考慮的最重要的問題之一是它的地址空間大小，即處理器能直接訪問的位元組單元數。引用GordonBell的說法:在體系結構設計的錯誤中，唯一在以後不易改正的錯誤是採用小的地址空間。274現代的處理器支持64位地址空間，或2６４=11．8x1019B。這一巨大的地址空間，對於僅支持32位(4GB)

Unix來講可能未被充分利用。地址空間的過度設計為操作系統擴展為64位Unix時的方便過渡創造了條件。275例題2：在最初的IBMPC中使用的處理器—Intel8086／8088微處理器中，它的地址空間被限制為20位或1MB。DOS對內核和用戶軟體限制使用640KB地址空間。這個限制給編譯程序的編寫人員以及應用軟體開發者帶來許多煩惱。

276因為DOS程式(包括Windows)不能超過640KB限制，軟體設計者不得不創造一些複雜技術(例如高位記憶體、擴充記憶體和擴展記憶體)以使後幾代的處理器(Intel286、386、486、Pentium以及PentiumPro)能使用更大的地址空間。277例題3IBMRS6000SMP伺服器中的過度設計

考慮到代的可擴展性，IBMRS6000SMP作了過度設計。第一代的SMP基於PowerPC601處理器。系統的其他部分，從記憶體、I/O、電源、風扇直到時鐘電路，都設計成可容納後兩代的處理器PowerPC604以及620。278每個處理器的開關口的帶寬為600MB／S，大於PC601的需要。這些過度設計的特性使得在擴展為未來一代SMP系統時非常容易；只要簡單地升級處理器就可實現。279（2）向後相容性在設計硬體或軟體部分時，必須兼顧縮減系統的需求。280例題1：新處理器應能執行老處理器的二進位代碼。為在n個結點上運行而設計的並行程式，應能在單結點(n=1)上運行，此時可能只要求縮減的輸入數據集。281超級電腦程式應能在工作站上運行。此外，輸入數據集必須適應工作站的有限主存容量。操作系統的新版本應保留所有原來的功能，除了那些過時的不再使用，對此必須用文檔清楚地加以說明。282例題2：處理器中數據匯流排寬度的向後相容性

現代處理器的CPU，匯流排有一條64位數據匯流排。某些處理器支持向後相容性，它們允許64位處理器用在含有較小數據匯流排寬度(32、16或8位)的母板上。283這只需對該處理器的少數控制引腳進行設置就可做到這一點。假定處理器需要兩個匯流排週期完成記憶體的讀操作(一個週期送地址，另一個週期從記憶體讀出64位數據)。則當在一個8位母板上進行讀操作時，處理器的設置將自動地在9個匯流排週期內從記憶體讀出64位數據。284例題3：IBMSP系統中的並行操作環境IBM並行操作環境(POE)最初是為IBM可擴展並行電腦(SPl和SP2)設計的。環境中，用戶的應用程式在多個SP結點上執行。POE支持的向後相容性如下：POE完全可在一個結點上執行，因此它允許多個用戶任務在一個結點上運行。該結點不必非是一個SP結點，它可以是任何RS6000工作站。POE是在IBMUnix(AIX)上實現的，因此已有的Unix程式可在POE中運行。285說明：

向後相容性並不表示一個舊系統的所有特性都應保留。應該剔除陳舊的特性。在應用過度設計技術時，應考慮成本問題且不應對未來期待過多，雖然有時過度設計確實能減少總的開發和生產成本。286

5可擴展的範圍和設計一、可擴展性範圍二、可擴展設計原理287一、可擴展性範圍說明：系統伸縮：增加或減少系統資源。這裏假定並行處理電腦的體系中的結點均為單一處理器結點可擴展性範圍包括：資源可擴展性應用可擴展性技術可擴展性

2881.資源可擴展性

資源可擴展性是指通過增加處理器數、更多的存儲部件(高速緩存，存，磁片)以及增加軟體等方法，使系統具有更高性能或功能。涉及三方面：規模可伸縮性資源擴展軟體可擴展性289（1）規模可伸縮性：規模可伸縮性與處理器數相關聯。擴展一個電腦系統---增加機器規模（處理器數）。不同並行電腦規模可擴展能力不同。限制並行系統可擴展性的兩個主要因素是：程式設計及通信。290示例：在1997年時：一個對稱多處理機(SMP)系統最多能擴展到大約64個處理器；一個IBMSP2並行機能擴展到最多具有512個處理器。

291當前的並行電腦規模的擴展：加入更多處理器；增加互連網絡、介面以及通信軟體在內的子系統。有效地利用更大並行性，即如何為擴大的系統進行編程。292（2）資源擴展增加處理器數不是唯一方式。保持處理器數不變；通過增加更多存儲容量、更大的晶片外高速緩存以及更大容量磁片等方法來擴展系統。293例題：IBMSP2中的記憶體需求當Maui高性能計算中心(MHPCC)決定升級它的具有400個結點的SP2系統時，它選擇了增加記憶體和磁片容量方法，而不是增加更多結點數方法。下表概述了所擴展的存儲容量。294295要求：系統必須設計成能允許擴展這麼多的容量。實際系統總有一個最大記憶體容量的上限。例如：IBMSP2中的每個結點最多可容納2GB記憶體；CrayT3