1、并行處理與體系結(jié)構(gòu),聯(lián)系方式：綜合樓605房間電話：,課程背景,并行處理技術(shù)已經(jīng)成為現(xiàn)代計算機科研與發(fā)展的關(guān)鍵技術(shù)；其推動力來自實際應(yīng)用對高性能、低價格和持續(xù)生產(chǎn)力日益增長的要求,計算機原理的概念計算機體系結(jié)構(gòu)的概念(Amdahl)；,并行主要研究：先行方式、流水方式、向量化；并發(fā)性、同時性；數(shù)據(jù)并行性、劃分；交叉、重疊、多重性、重復(fù)；時間共享、空間共享；多任務(wù)處理、多道程序、多線程方式和分布式計算?！?第一章

2、 并行計算機模型,?1 計算技術(shù)的現(xiàn)狀?2 多處理機和多計算機?3 多向量機和SIMD計算機?4 并行計算機的抽象模型?5 可擴展的范圍和設(shè)計,?1 計算技術(shù)的現(xiàn)狀,一、并行技術(shù)的出現(xiàn),,第六代：超標(biāo)量，超流水線，超長指令字？第七代：CMP（chip multiprocessor），Kunle Olukotun 博士，斯坦福大學(xué)計算機系教授，第一片CMP的設(shè)計者，推動了片上多處理器的研究熱潮。,二、現(xiàn)代并行計算機的組成,涉及

3、6個問題：1.計算問題 現(xiàn)實生活中對問題要求快速而精確地求解推動了計算機的廣泛使用?？茖W(xué)技術(shù)中的數(shù)值計算問題人工智能(AI)問題事務(wù)處理,2.算法和數(shù)據(jù)結(jié)構(gòu) 并行計算問題中的運算和通信，需要各種專門的算法和數(shù)據(jù)結(jié)構(gòu)。符號處理科學(xué)計算存在的問題?,3.硬件資源 處理機、存儲器和外圍設(shè)備組成了計算機系統(tǒng)的硬件核心外圍設(shè)備可以直接或通過局域網(wǎng)和廣域網(wǎng)與主機相連,4.操作系統(tǒng) 管理用戶程序執(zhí)行過程中的資源分配和再分

4、配。映射是一種算法結(jié)構(gòu)與硬件結(jié)構(gòu)相匹配的雙向過程。并行操作系統(tǒng)的映射算法和數(shù)據(jù)結(jié)構(gòu)到機器結(jié)構(gòu)的映射包括處理機調(diào)度、存儲器映象、處理器間的通信等。這些問題通常都與系統(tǒng)結(jié)構(gòu)有關(guān)。,5.系統(tǒng)軟件支持 存在的問題：不能以通用和可移植方式進(jìn)行并行程序設(shè)計開發(fā)并行編程環(huán)境：一種與系統(tǒng)結(jié)構(gòu)無關(guān)的語言、編譯器和軟件工具。,兩個方向：對于開發(fā)并行語言，將著眼點放在語言執(zhí)行的效率、對不同機器的可移植性、與現(xiàn)有的順序語言的兼容性、并行性的

5、表達(dá)和編程的簡便性等上面?？梢栽O(shè)計一種新的語言，逐步擴展現(xiàn)有的順序語言。新語言有用顯式高級結(jié)構(gòu)描述并行性的優(yōu)點，但是新語言往往與現(xiàn)有語言不兼容，而需要新的編譯器或者通過新的步驟才能利用現(xiàn)有的編譯器。大部分系統(tǒng)選用的是語言擴展方式。,6.編譯器支持 改進(jìn)編譯器有三種途徑：預(yù)處理程序;預(yù)編譯器;并行化編譯器。,預(yù)處理程序采用順序編譯器和目標(biāo)計算機的低層程序庫實現(xiàn)高級并行結(jié)構(gòu)。預(yù)編譯器需要程序流分析、相關(guān)性檢查和有限的優(yōu)化來檢測

6、并行性。聯(lián)接過程效果取決于預(yù)處理程序、預(yù)編譯器、并行化編譯器、加載程序和操作系統(tǒng)支持的功效。由于程序行為的不可預(yù)測，現(xiàn)有的編譯器在檢測所有類型的并行性時都不是完全自動或完全智能進(jìn)行的。存在一些有效的方法：將編譯器命令插入源代碼，幫編譯器做出較好的結(jié)果。這樣，用戶可與編譯器進(jìn)行交互重構(gòu)程序，這已被證明對提高并行計算機性能是十分有用的。,7.并行程序的設(shè)計環(huán)境 隱式并行性伊利諾依大學(xué)的David Kuck和Rice大學(xué)的KenK

7、ennedy以及他們的合作者都已采用這種隱式并行性方法。 顯式并行性 加州理工學(xué)院的CharlesSeitz和麻省理工學(xué)院的WilliamDaily在開發(fā)多計算機時采用了這種顯式方法。,總結(jié)：要使一個環(huán)境對用戶更加友好，必須要有專用軟件工具。一些工具是傳統(tǒng)高級語言的并行擴展；一些則是集成環(huán)境其中包括提供不同級別的程序抽象、驗證、測試、查錯和調(diào)試等各種工具；性能預(yù)測和監(jiān)控；輔助程序開發(fā)的可視化支持、性能測量以及計算結(jié)果的圖形

8、顯示及動畫表示,三、計算機系統(tǒng)結(jié)構(gòu)向高性能發(fā)展歷程,主要探討順序到并行的過程,1.先行、并行性和流水線技術(shù)用先行技術(shù)預(yù)取指令可使I／E(指令讀?。g碼和執(zhí)行)支持功能并行性的方法有兩種：一種是同時使用多個功能部件；另一種是在不同處理級分別實施流水線技術(shù)。 流水線指令執(zhí)行、流水線算術(shù)計算和存儲器存取操作。,2.Flynn分類法MkhealFlynn(1972)根據(jù)指令和數(shù)據(jù)流概念提出了不同計算機系統(tǒng)結(jié)構(gòu)的分類法。,傳統(tǒng)的順序

9、機被稱為SISD(單指令流單數(shù)據(jù)流)計算機。向量計算機--標(biāo)量和向量硬件裝備，或以SIMD(單指令流多數(shù)據(jù)流)機的形式出現(xiàn)。并行計算機則屬MIMD(多指令流多數(shù)據(jù)流)機,MISD(多指令流單數(shù)據(jù)流)機在執(zhí)行不同的指令流時，同一數(shù)據(jù)流通過處理機線性陣列。這種系統(tǒng)結(jié)構(gòu)也就是所謂流水線執(zhí)行特定算法的脈動陣列(Systolicarrays)。由卡內(nèi)基—梅隆大學(xué)的美籍華人學(xué)者H．T．Kung于1978年提出的。這一結(jié)構(gòu)是隨著VLSI技術(shù)

10、的發(fā)展和各種大運算量的信號/圖象處理及科學(xué)計算的運算要求而建立起來的。,脈動陣列的特點：處理單元簡單流水算法專業(yè),例：數(shù)據(jù)流計算機數(shù)據(jù)流的計算模型--試圖使并行計算的基本方面在機器層顯式化，而不利用有可能限制程序并行性的人為約束。它的想法是程序由一個基本數(shù)據(jù)依賴圖來表示；一個指令可能在獲得了它的操作數(shù)后的任意時刻被執(zhí)行，不是顯式控制線性程序列的固定組合。,3.并行／向量計算機 真正的并行計算機是那些以MIMD模式執(zhí)行程序的

11、計算機。并行計算機有兩大類，即共享存儲型多處理機和消息傳遞型多計算機。多處理機和多計算機之間的主要差別就在于存儲器共享和處理機間通信機制的不同。多處理機系統(tǒng)中的處理機通過公用存儲器的共享變量實現(xiàn)互相通信。多計算機系統(tǒng)的每個計算機結(jié)點有一個與其它結(jié)點不共享的本地存儲器。處理機之間的通信通過結(jié)點間的消息傳遞來實現(xiàn)。,顯式向量計算機指令是隨向量處理機的問世而出現(xiàn)的。一臺向量處理機可以裝備有用硬件或固件并發(fā)控制的多條向量流水線。,4.

12、開發(fā)層次 Lionel Ni的最新分類法(1990)，并行計算機的分層開發(fā)可表示于下圖,四、性能的系統(tǒng)屬性,1 .時鐘頻率和CPI 主頻當(dāng)前數(shù)字計算機的CPU(或簡稱處理機)是由一個恒定周期(τ，以ns表示)的時鐘驅(qū)動的。周期的倒數(shù)是時鐘頻率(ｆ＝1/ τ ）（以MHz表示）。,程序的規(guī)模是由其指令數(shù)(Ic)，也就是程序串要執(zhí)行的機器指令數(shù)來決定的。執(zhí)行不同的機器指令所需要的時鐘周期數(shù)也是不一樣的。一條指令的周期數(shù)(C

13、Pl)就成為衡量執(zhí)行每條指令所需時間的重要參數(shù)。,2.性能因子執(zhí)行程序所需的CPU時間：設(shè)Ic為已知程序的指令條數(shù)。執(zhí)行程序所需的CPU時間(T，以秒/程序表示)可用三個主要因素的乘積來計算： T＝ Ic × CPI × τ,可將上式重寫成如下形式： T＝ Ic × (p+m×k) × τ 一種指令類型的CPI可分為完成指令所需的處理機周期數(shù)和存儲器周期數(shù)兩部分。完整

14、的指令執(zhí)行過程可能包含一至四次存儲器訪問(一次用于取指令，兩次用于取操作數(shù)，一次用于存儲結(jié)果)，這與指令的類型有關(guān)。,式中的細(xì)化：p為指令譯碼和執(zhí)行所需的處理機周期數(shù);m為所需的存儲器訪問次數(shù);k為存儲周期與處理機周期之比;Ic為指令條數(shù)，為處理機周期。,3.系統(tǒng)屬性計算機系統(tǒng)屬性可以由五元組表示：(Ic，p，m，k，τ),五個量可以稱為性能因子。與四種系統(tǒng)屬性有關(guān)：指令系統(tǒng)結(jié)構(gòu)、編譯技術(shù)、CPU實現(xiàn)和控制技術(shù)、高速緩存

15、與存儲器層次結(jié)構(gòu)。,推廣---并行系統(tǒng)的性能屬性機器規(guī)模 n—處理機個數(shù)時鐘速率 f工作負(fù)載 W--程序中的計算操作數(shù)順序執(zhí)行時間 T1并行執(zhí)行時間 Tn速度 Pn=W/Tn加速比 Sn=T1/Tn效率 En=Sn/n 利用率 Un=Pn/n(Ppeak)啟動時間 t0 漸進(jìn)帶寬

16、 r∞,4.Mips速率(其中C是總的周期數(shù)),5.吞吐率系統(tǒng)的吞吐率:系統(tǒng)在單位時間內(nèi)能執(zhí)行多少個程序，這稱為系統(tǒng)的吞吐率(單位為程序數(shù)／秒) Ws 。,在多道程序系統(tǒng)中，系統(tǒng)吞吐率常低于CPU吞吐率Wp。Wp可用下式表示：,或： Wp=(MIPS)×106／Ic Wp的單位是程序數(shù)／秒。,CPU吞吐率是根據(jù)MIPS速率和程序的平均長度(Ic)來衡量機器每秒鐘能執(zhí)行多少個程序的尺度。Ws<Wp，