并行處理技術(shù)

1、并行處理技術(shù)摘要：并行處理計(jì)算機(jī)是計(jì)算機(jī)設(shè)計(jì)的未來。當(dāng)代面臨著的重大科學(xué)技術(shù)問題要依賴于計(jì)算技術(shù)協(xié)助解決，一方面要作 大型計(jì)算以得到更精確的解，另一方面要作計(jì)算機(jī)模擬，以便進(jìn)一步了解所探討 問題的結(jié)構(gòu)與運(yùn)動(dòng)規(guī)律。這兩個(gè)方面都離不開并行處理技術(shù)。雖然許多人都認(rèn)識(shí) 到并行處理技術(shù)的重要性，但并行處理技術(shù)的發(fā)展道路并不平坦。從70年代到 90年代中期，中間幾起幾落，究其原因，就是并行計(jì)算技術(shù)仍然遇到若干困難， 使其無法推廣應(yīng)用。這其中既有軟件方面的（并行程序設(shè)計(jì)）問題，也有硬件方 面（并行處理機(jī)）的原因。本文主要從并行程序設(shè)計(jì)和并行處理機(jī)兩方面對(duì)并行 處理技術(shù)進(jìn)行了簡要的介紹。關(guān)鍵詞：并行處理技術(shù)、

2、并行處理機(jī)、并行程序引言人類對(duì)計(jì)算能力的需求是永無止境的，而在各種類型的計(jì)算系統(tǒng)中，超級(jí)計(jì) 算機(jī)的性能最高。90年代以來，超級(jí)計(jì)算機(jī)在工業(yè)、商業(yè)和設(shè)計(jì)等民用領(lǐng)域的 重要性越來越明顯了。因此，超級(jí)計(jì)算機(jī)的發(fā)展，不僅會(huì)深刻地改變產(chǎn)品和材料 的設(shè)計(jì)方法，改變研究和實(shí)驗(yàn)的方式，而且將逐步影響人們的生活方式。超級(jí)計(jì) 算機(jī)已經(jīng)成為體現(xiàn)一個(gè)國家經(jīng)濟(jì)和國防力量的重要標(biāo)志。20多年來，超級(jí)計(jì)算機(jī)的工作頻率只提高了將近10倍，而峰值速度卻提高了 1 萬倍。這說明，主要的性能改善來自結(jié)構(gòu)的進(jìn)步，尤其是來自各種形式的并行處 理技術(shù)。但是，超級(jí)計(jì)算機(jī)的用戶們關(guān)心的并不是系統(tǒng)在理論上的最高速度，而 是實(shí)際解題所需要的時(shí)間

3、和程序設(shè)計(jì)及移植的工作量。并行處理是提高計(jì)算機(jī)系統(tǒng)性能的重要途徑。目前幾乎所有的高性能計(jì)算機(jī) 系統(tǒng)，都或多或少地采用了并行處理技術(shù)。本文將就并行處理技術(shù)做簡要的介紹。何為并行并行性主要是指同時(shí)性或并發(fā)性，并行處理是指對(duì)一種相對(duì)于串行處理的處 理方式，它著重開發(fā)計(jì)算過程中存在的并發(fā)事件。并行性通常劃分為作業(yè)級(jí)、任務(wù)級(jí)、例行程序或子程序級(jí)、循環(huán)和迭代級(jí)以 及語句和指令級(jí)。作業(yè)級(jí)的層次高，并行處理粒度粗。粗粒度開并行性開發(fā)主要 采用MIMD方式，而細(xì)粒度并行性開發(fā)則主要采用SIMD方式。開發(fā)計(jì)算機(jī)并行性的方法主要有：資源重復(fù)、時(shí)間重疊和資源共享三種方法。并行程序設(shè)計(jì)在并行處理技術(shù)中，并行程序是最為核

4、心的領(lǐng)域之一。沒有好的并行程序的 支持，并行處理機(jī)就不可能很好的工作，所謂超級(jí)計(jì)算也就更加無從談起了。并行程序設(shè)計(jì)方法不同于順序程序設(shè)計(jì)方法，主要在于對(duì)問題采取何種看 法：順序程序設(shè)計(jì)方法把事物的變化發(fā)展看成是單線程的，任何兩種事物之間必 然存在因果關(guān)系，從而把一系列統(tǒng)一事物看成是不可分割的整體。后來的結(jié)構(gòu)程 序設(shè)計(jì)特別是對(duì)象式程序設(shè)計(jì)把一個(gè)復(fù)雜的事物分解成多個(gè)簡單的事物，或者把 一個(gè)系統(tǒng)看成是由多個(gè)相互聯(lián)系的實(shí)體構(gòu)成的。應(yīng)該說，這里在對(duì)事物的認(rèn)識(shí)上 取得了突破性的進(jìn)展，但也是從事物的靜態(tài)結(jié)構(gòu)上來看的，并未從行為上來分解。 從行為上來看，它們?nèi)匀槐徽J(rèn)為或者是一致的，或者是先后相繼的，相互之間不

5、 存在有并發(fā)干擾現(xiàn)象，更不存在可同時(shí)發(fā)生的相互作用的行為。并行程序設(shè)計(jì)方法的一個(gè)最基本的觀點(diǎn)，就是把一個(gè)事物的行為看成是多個(gè) 事物互相作用的結(jié)果。這是一個(gè)觀念上的根本轉(zhuǎn)變，根據(jù)這個(gè)觀點(diǎn)，并行程序設(shè) 計(jì)方法的核心內(nèi)容就是并行劃分與算法映射。其理論基礎(chǔ)是并行計(jì)算模型。并行 計(jì)算模型決定了并行語義，并行語義決定了可并行執(zhí)行的準(zhǔn)則，從而決定了并行 劃分的原則。要研究并行程序設(shè)計(jì)，首先就要討論并行算法的結(jié)構(gòu)，這涉及到對(duì)并行算法 的理解、并行程序設(shè)計(jì)方法、并行算法與并行系統(tǒng)結(jié)構(gòu)匹配等問題。所謂并行算法結(jié)構(gòu)，就是構(gòu)成并行算法的基本組成部分與屬性及其互相之間 的關(guān)系。一般來講，一個(gè)并行算法結(jié)構(gòu)由以下幾部分組成

6、：（1）劃分模式，即并行劃分類型與并行模塊;（2）合作模式，即合作方式與計(jì)算圖；（3）映射（分配）格局；通信模式；運(yùn)行模式。一個(gè)并行算法的結(jié)構(gòu)既是該算法的骨架，也是該算法的精髓，這些方面確定 了，這個(gè)算法也就基本上確定了。理解或者說一個(gè)算法，都可以從這幾個(gè)方面來 考慮。算法結(jié)構(gòu)應(yīng)當(dāng)與機(jī)器結(jié)構(gòu)相匹配，這是提高應(yīng)用程序?qū)嶋H執(zhí)行性能的一條重 要途徑。因此，從算法結(jié)構(gòu)應(yīng)與機(jī)器系統(tǒng)結(jié)構(gòu)相匹配的觀點(diǎn)出發(fā)，對(duì)算法結(jié)構(gòu)作 一個(gè)分類，具有重要的實(shí)際意義。根據(jù)算法結(jié)構(gòu)的組成部分，我們按以下優(yōu)先級(jí) 進(jìn)行分類：運(yùn)行模式一通信模式一并行劃分類型與合作模式。分類情況如下：同步操作公共變量型消息傳遞型向量型水平數(shù)據(jù)劃分+分

7、工式水線型垂直劃分+接力式脈動(dòng)型水平垂直劃分+接力式異步操作公共變量型消息傳遞型數(shù)據(jù)流型垂直水平劃分+合力式對(duì)話型垂直水平劃分+對(duì)話式過程型(歸約型，對(duì)象型)垂直水平劃分+請求式會(huì)議型垂直水平劃分+會(huì)議式SPMD型水平劃分+分工式MPMD型混合劃分+合力式以上這些算法結(jié)構(gòu)類型，大多數(shù)都有一種特定的系統(tǒng)與之對(duì)應(yīng)。算法結(jié)構(gòu)的 分類，對(duì)于設(shè)計(jì)一個(gè)滿足與系統(tǒng)結(jié)構(gòu)相匹配的算法也是很有意義的。并行處理機(jī)好的并行程序也要在好的并行處理機(jī)上運(yùn)行，才能發(fā)揮出最大的能量。并行 機(jī)按系統(tǒng)結(jié)構(gòu)劃分可分為以下五類：向量流水巨型機(jī)、SIMD陣列機(jī)、共享主存 多處理機(jī)、分布存儲(chǔ)多計(jì)算機(jī)和聯(lián)網(wǎng)計(jì)算機(jī)。本章將著重介紹SIMD陣

8、列機(jī)何多處理機(jī)的相關(guān)知識(shí)。（一）SIMD并行計(jì)算機(jī)（陣列處理機(jī)）陣列機(jī)也稱并行處理機(jī)。它將大量重復(fù)設(shè)置的處理單元按一定方式互連成陣 列，在單一控制部件CU（Contrul Unit）控制下對(duì)各自所分配的不同數(shù)據(jù)并行執(zhí) 行同一指令規(guī)定的操作，是操作并行的SIMD計(jì)算機(jī)。它采用資源重復(fù)的措施開 發(fā)并行性。是以SIMD（單指令流多數(shù)據(jù)流）方式工作的。1、陣列機(jī)的基本結(jié)構(gòu)陣列機(jī)通常由一個(gè)控制器CU、N個(gè)處理器單元PE（Processing Element）、M 個(gè)存儲(chǔ)模塊以及一個(gè)互連網(wǎng)絡(luò)部件（IN）組成。根據(jù)其中存儲(chǔ)器模塊的分布方式， 陣列機(jī)可分為兩種基本結(jié)構(gòu)：分布式存儲(chǔ)器的陣列機(jī)和共享存儲(chǔ)器的陣列機(jī)

9、。 陣列機(jī)的主要特點(diǎn)：它采用資源重復(fù)的方法引入空間因素，這與利用時(shí)間重疊的流水線處理機(jī)是 不一樣的。它是利用并行性中的同時(shí)性而不是并發(fā)性，所有的處理單元必須同時(shí) 進(jìn)行相同操作（資源重復(fù)同時(shí)性）（我們想象一下亞運(yùn)會(huì)的開幕式大型團(tuán)體操表 演，每個(gè)人就是一個(gè)PE，他們聽從一個(gè)總指揮的指令，同時(shí)進(jìn)行自己的操作， 很快地就能“計(jì)算”出一個(gè)結(jié)果（隊(duì)形）來。它是以某類算法為背景的專用計(jì)算機(jī)，基本上是專用于向量處理的計(jì)算機(jī) （某類算法專用機(jī)）。陣列機(jī)的研究必須與并行算法研究密切結(jié)合，以使它的求解算法適應(yīng)性更強(qiáng) 一些，應(yīng)用面更廣一些（并行算法合研究）。陳列機(jī)實(shí)質(zhì)上是由專門對(duì)付數(shù)據(jù)組運(yùn)算的處理單元陣列組成的處理機(jī)

10、（M個(gè) PE）、專門從事處理單元陣列的控制及標(biāo)量處理機(jī)（控制器CU）和專門從事系統(tǒng)輸 入輸出操作及操作系統(tǒng)管理的處理機(jī)三部分構(gòu)成的一個(gè)異構(gòu)型多處理機(jī)系統(tǒng)（三 個(gè)部分成異構(gòu)）。3、陣列機(jī)的并行算法陣列機(jī)的算法是與結(jié)構(gòu)緊密聯(lián)系在一起的，陣列機(jī)上常用的算法有矩陣計(jì) 算、圖形處理等，我們對(duì)教材中舉的兩種算法要領(lǐng)會(huì)，特別是累加和遞歸操作， 不難理解。它就是使各個(gè)處理器同時(shí)進(jìn)行加的操作，但并不是全部處理器都參加 運(yùn)算，在處理時(shí)，根據(jù)累加計(jì)算的需要，由控制器CU借助屏蔽的方式將一部分 PE設(shè)置成不活動(dòng)的狀態(tài)。這種累加操作的速度提高倍數(shù)是N/log2N倍。（二）多處理機(jī)多處理機(jī)具有兩臺(tái)以上的處理機(jī)，在操作系統(tǒng)

11、控制下通過共享的主存或輸入 輸出子系統(tǒng)或高速通訊網(wǎng)絡(luò)進(jìn)行通訊。多處理機(jī)屬M(fèi)IMD系統(tǒng)。多處理機(jī)與SIMD相比有較大不同，表現(xiàn)在：結(jié)構(gòu)靈活性：MIMD機(jī)結(jié)構(gòu)上具有更大靈活性和更強(qiáng)的通用性；程序并行性：前者是作業(yè)級(jí)并行，后者則是操作級(jí)并行；并行任務(wù)派生：前者需要由專用語句顯式指明是否派生并行任務(wù)，而后者 則不需要專門指令；進(jìn)程同步：MIMD機(jī)中各進(jìn)程的同步需要采取特殊措施來保證，而SIMD機(jī) 則由于受同一控制器控制，自然是同步的；資源分配和調(diào)度：MIMD機(jī)任務(wù)調(diào)度要采用軟件手段，而SIMD機(jī)中，只需 用屏蔽來控制實(shí)際參加并行操作的處理單元數(shù)目。；多處理機(jī)在系統(tǒng)結(jié)構(gòu)上分為兩類：緊耦合和松耦合系統(tǒng)。緊

12、耦合是通過共享 主存實(shí)現(xiàn)處理機(jī)間的互相通信，處理機(jī)間的相互聯(lián)系比較緊密。按所用處理機(jī)類 型是否相同及對(duì)稱，又可分為同構(gòu)或異構(gòu)及對(duì)稱或非對(duì)稱的形式。常見組合是同 構(gòu)對(duì)稱式和異構(gòu)非對(duì)稱式多機(jī)系統(tǒng)。松耦合是通過消息傳遞方式來實(shí)現(xiàn)處理機(jī)間 的相互通信，而每個(gè)處理機(jī)是由一個(gè)獨(dú)立性較強(qiáng)的計(jì)算機(jī)模塊組成。為了解決多系統(tǒng)中的cache 一致性問題，可采用的方法有（1）件方法（2）采用總線監(jiān)聽機(jī)制（3）目錄表法多處理機(jī)系統(tǒng)中，機(jī)間互連主要采用以下幾種方式。（1）總線方式（2）縱橫交叉開關(guān)互連方式（3）多端口存儲(chǔ)器互連方式（4）多級(jí)網(wǎng)絡(luò)互連方式（5）蟲孔互連和尋徑技術(shù)多處理機(jī)中并行性的開發(fā)第一步是要對(duì)程序中存在的

13、并行性進(jìn)行分析，主要 分析其中的數(shù)據(jù)相關(guān)、數(shù)據(jù)反相關(guān)及數(shù)據(jù)輸入相關(guān)，其次是用伯恩斯坦準(zhǔn)則來分 析哪些部分是可以并行執(zhí)行的。并行的程序設(shè)計(jì)語言常用FORK-JOIN原語及塊結(jié)構(gòu)語言Cobegin-Coend語言 來表示程序中可并行執(zhí)行部分及相互之間的同步關(guān)系。多處理機(jī)操作系統(tǒng)除了完成通常單機(jī)操作系統(tǒng)的資源分配和管理、存儲(chǔ)管理 和保護(hù)、死鎖防止、異常里程終止或例外處理等功能外，還必須具有以下特點(diǎn)和 功能：（1）支持多個(gè)任務(wù)的并行執(zhí)行（2）支持處理機(jī)同步和通信管理（3）提供系統(tǒng)結(jié)構(gòu)重構(gòu)運(yùn)動(dòng)系統(tǒng)降級(jí)使用（4）自動(dòng)支持硬件并行性和程序并行性的開發(fā)多處理機(jī)操作系統(tǒng)主要分成三類結(jié)構(gòu)：主從結(jié)構(gòu)、獨(dú)立監(jiān)控結(jié)構(gòu)和浮動(dòng)監(jiān)控 結(jié)構(gòu)。其中主從結(jié)構(gòu)適用于系統(tǒng)負(fù)載固定以及主機(jī)功能較強(qiáng)、從機(jī)功能較弱的非 對(duì)稱多處理機(jī)系統(tǒng)；獨(dú)立監(jiān)控結(jié)構(gòu)適用于松耦合多處理機(jī)系統(tǒng)；第三種結(jié)構(gòu)則適 用于對(duì)稱緊耦全多處理機(jī)系統(tǒng)。衡量多處理機(jī)