并行计算机模型课件.pptVIP

緊耦合系統(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和週邊設備連接；任何兩結點間的消息傳遞會涉及一連串的尋徑器和通道。在異構多電腦系統中，可以有多種類型的結點，結點間的通信是通過可相容的數據表示和消息傳遞協議來實現的。1.先行、並行性和流水線技術用先行技術預取指令可使I／E(指令讀取／解碼和執行)支持功能並行性的方法有兩種：一種是同時使用多個功能部件；另一種是在不同處理級分別實施流水線技術。流水線指令執行、流水線算術計算和記憶體存取操作。2.Flynn分類法MkhealFlynn(1972)根據指令和數據流概念提出了不同電腦系統結構的分類法。傳統的順序機被稱為SISD(單指令流單數據流)電腦。向量電腦--標量和向量硬體裝備，或以SIMD(單指令流多數據流)機的形式出現。並行電腦則屬MIMD(多指令流多數據流)機MISD(多指令流單數據流)機在執行不同的指令流時，同一數據流通過處理機線性陣列。這種系統結構也就是所謂流水線執行特定演算法的脈動陣列(Systolicarrays)。由卡內基—梅隆大學的美籍華人學者H．T．Kung於1978年提出的。這一結構是隨著VLSI技術的發展和各種大運算量的信號/圖象處