並行處理:特點,算法基本策略,並行性描述定義,並行軟體,硬體技術,並行計算機發展簡-九游会j9

只有部分應用程式在滿足以下條件的情況下可利用並行處理：具有充足的能充分利用的應用程式； 並行化目標應用程式或用戶需進行新的編碼來利用並行程式。

傳統上，專為“並行計算機”所設計，沿著這樣的思路，當前 linux 支持 smp 奔騰系統，在該系統中多處理機共享單個計算機中的單個和。每個運行 linux 的機器組都有可能通過網路互相連線形成並行處理群。第三種選擇是使用 linux 系統作為“”，提供專門的相關並行（attached parallel processor）。第四種新選擇是暫存器內 simd 並行，套用於多媒體擴展（mmx）。

並行處理所需要提供的典型有：

單處理機上的單個區；

多處理機（smp）中的單個區；

多區配置

一個處理機（mpp）中的各區 ；

多處理機（smp 群）中的各區；

邏輯資料庫區（在 aix 第1版的 db2 並行版 － db2 pe 中也稱之為多邏輯代碼或 mln）

並行計算機具有代表性的套用領域有：天氣預報建摸、vlsi電路的、大型、、犯罪控制和國防戰略研究等，而且它的套用範圍還在不斷地擴大。主要是以算法為核心，並行語言為描述，軟硬體作為實現工具的相互聯繫而又相互制約的一種結構技術。

在中所使用的算法主要遵循三種策略：

1．分而治之法：也就是把多個任務分解到多個處理器或多個計算機中，然後再按照一定的來進行求解。

2．重新排序法：分別採用或動態的指令詞度方式。

3．顯式/隱式結合：顯式指的是並行語言通過編譯形成並行程式，隱式指的是串列語言通過編譯形成並行程式，顯式/隱式結合的關鍵就在於並行編譯，而並行編譯涉及到語句、、進程以及各級程式的。

利用進行並行性描述的時候主要有三種方案：

1．語言擴展方案：也就是利用各種語言的來進行並行性功能的擴展。

2．編譯製導法：也稱為智慧型編譯，它是隱式並行策略的體現，主要是由並行進行程式表示、的分析、相關分析、最佳化分析和並行化劃分，由相關分析得到方法庫管理方案，由最佳化分析得到知識庫管理方案，由並行化劃分得到程式重構，從而形成並行程式。

3．新的語言結構法：這是顯式並行策略的體現。也就是建立一種全新的並行語言的體系，而這種並行語言通過編譯就能直接形成並行程式。

並行可分成並行系統軟體和並行兩大類，並行系統軟體主要指並行和並行，並行套用軟體主要指各種軟體工具和套用。在中所牽涉到的程式的主要是指程式的相關性和網路互連兩方面。

1．程式的相關性：程式的相關性主要分為數據相關、控制相關和資源相關三類。

數據相關說明的是語句之間的有序關係，主要有流相關、反相關、輸出相關、i/o相關和求知相關等，這種關係在程式運行前就可以通過分析程式確定下來。數據相關是一種偏序關係，程式中並不是每一對語句的成員都是相關聯的。可以通過分析程式的數據相關，把程式中一些不存在相關性的指令並行地執行，以提高程式運行的速度。

控制相關指的是語句執行次序在運行前不能確定的情況。它一般是由轉移指令引起的，只有在程式執行到一定的語句時才能判斷出語句的相關性。控制相關常使正在開發的中止，為了開發更多的並行性，必須用克服控制相關。

而資源相關則與系統進行的工作無關，而與並行事件利用整數部件、浮點部件、和存儲區等共享資源時發生的衝突有關。的主要是由程式的控制相關和數據相關性決定的。在開發時往往把程式劃分成許多的——顆粒。顆粒的規模也稱為粒度，它是衡量進程所含計算量的尺度，一般用細、中、粗來描述。劃分的粒度越細，各子系統間的通信時延也越低，就越高，但也越大。因此，我們在進行程式的時候應該選擇適當的粒度，並且把通訊時延儘可能放在中進行，還可以通過軟硬體適配和編譯最佳化的手段來提高程式的。

2．網路互連：將計算機子系統互連在一起或構造或多計算機時可使用靜態或動態的網路。靜態網路由點一點直接相連而成，這種連線方式在程式執行過程中不會改變，常用來實現的子系統之間或的多個計算結點之間的固定連線。是用開關通道實現的，它可動態地改變結構，使之與中的通信要求匹配。包括、和多級網路，常用於共享存儲型中。在網路上的訊息傳遞主要通過尋徑來實現。常見的尋徑方式有尋徑和等。在網路中以長度固定的包作為信息流的基本單位，每個結點有一個包，包從源結點經過一系列中間結點到達目的結點。網路的時延與源和目的之間的距離(段數)成正比。而在新型的中採用，把包進一步分成一些固定長度的片，與結點相連的硬體尋徑器中有片。訊息從源傳送到目的結點要經過一系列尋徑器。同一個包中所有的片以流水方式順序傳送，不同的包可交替地傳送，但不同包的片不能交叉，以免被送到錯誤的目的地。的時延幾乎與源和目的之間的距離無關。在尋徑中產生的問題可以由虛擬通道來解決。虛擬通道是兩個結點間的邏輯鏈，它由源結點的片、結點間的物理通道以及接收結點的片緩衝區組成。物理通道由所有的虛擬通道分時地共享。虛擬通道雖然可以避免死鎖，但可能會使每個請求可用的有效通道頻寬降低。因此，在確定虛擬通道數目時，需要對和通信時延折衷考慮。

硬體技術在硬體技術方面主要從、和流水線三個方面來實現並行。

1．：主要的處理機系列包括cisc、risc、、vl1w、、向量以及符號處理機。

傳統的屬於複雜計算(cisc)結構。大，可變，個數較少，基本上使用合一的指令與數據高速快取，較低，cpi較高，大多數利用rom 實現微碼控制cpu，而當今的精簡指令系統計算(risc)指令格式簡單，面向暫存器堆，採用重疊暫存器，具有多級cache，多種，強調編譯最佳化技術，時鐘頻率快，cpi低，大多數用硬連線控制cpu。

cisc或risc標量都可以採用或向量結構來改善性能。標量在每個周期內只發射一條指令並要求周期只完成從流水線來的一條指令。而在中，使用了多，每個周期要發射多條指令並產生多個結果。由於希望程式中有許多的指令級，因此更要依靠最佳化去開發並行性。

vl1w 結構是將水平微碼和處理這兩種普遍採用的概念結合起來產生的。典型的超長vl1w 字長度有數百位。在vllw 中，多個功能部件是並發工作的，所有的功能部件共享使用公用大型堆，由功能部件同時執行的各種操作是用vl1w 指令來同步的，每條指令可指定多個操作。vl1w 指令解碼比指令容易，但在開發不同數量的時總是需要不同的。vl1w 主要是開發標量操作之間的，它的成功與否很大程度取決於代碼壓縮的效率，其結構和任何傳統的通用完全不兼容。即使同一結構的不同實現也不大可能做到彼此二進制兼容。vl1w 的主要優點在於它的硬體結構和簡單，在科學套用領域可以發揮良好作用，但在一般套用場合可能並不很好用。

對執行向量指令，每條指令都包含一串重複的操作。它是專門設計用來完成向量運算的協，通常用於多流水線中。向量處理機可以利用循環級展開所得的，它可以附屬於任何標量處理機。專用的向量流水線可以在循環控制中消除某些開銷，它的效果與最佳化將順序代碼向量化的性能很有關係。從理論上說，向量機可以具有和同樣的性能，因此可以說向量機的與超標量機相同。

符號是為ai套用而研製的，已用於定理證明、、專家系統、、、科學以及機器智慧型等許多套用領域。在這些套用中，數據和知識、操作、算法特性、、i/0和通信以及專用的結構特性與數值計算是不一樣的，符號也稱為語言處理機、語言處理機或符號變換器。符號處理並不和數值數據打交道，它處理的是邏輯程式、、對象、劇本、黑板、、、框架以及等問題。這些操作需要專門的，通常不使用浮點操作。

2．：存儲設備按和從低到高可分為、高速快取、、設備和五個層次。較低層存儲設備與較高層的相比，存取速度較快、容量較小，每位元組成本較高、頻寬較寬、傳輸單位較小。

存放在中的信息滿足三個重要特性：包含性、一致性和局部性。所謂包含性，指的是一個信息字的複製品可以在比它高的所有層中找到，而如果在高層中丟失了一個信息，則在比它低的所有層中此信息也將丟失。cpu 和高速快取之間的信息傳送是按字進行的，高速快取和間用塊作為的基本單位，主存和之間又是以頁面為基本單位來傳送信息的，而在磁碟和之間的數據傳送則是按檔案級處理的。所謂一致性要求的是同一個信息項與後繼層次上的副本是一致的。也就是說，如果在高速快取中的一個字被修改過，那么在所有更高層上該字的副本也必須立即或最後加以修改。為了儘量減少的有效，通常把頻繁使用的信息放在較低層次。維護一致性一般有兩種策略，一種是寫直達策略，也就是如果，則立即在所有高層存儲器中進行同樣的修改；另一種是寫回策略，也就是在較低層中對信息進行修改後並不立即在高層存儲器中進行相應的修改，而是等到該信息將被替換或將從低層中消失時才在所有高層存儲器中進行同樣的修改。甚至可以將寫直達和寫回策略的優點結合起來，形成寫一次協定來維護的一致性。

的層次結構是在一種程式行為——訪問的局部性基礎上開發出來的。主要有時間局部性、空間局部性和順序局部性。時間局部性指的是最近的訪問項很可能在不久的將來再次被訪問。它往往會引起對最近使用區域的集中訪問。空間局部性表示一種趨勢，指的是一個進程訪問的各項其地址彼此很近。順序局部性指的是在典型程式中，除非是轉移指令，一般指令都是的。

在中一般使用共享。對共享的組織一般採用低位交叉、高位交叉、高低位交叉三種方法。低位交叉又稱並發存取，它是把相鄰的地址放在相鄰的模組中，在訪問時不容易產生衝突，較好，但可靠性容錯能力和擴展性均較差。高位交叉又稱允許同時存取，它是把相鄰地址分配到同一個模組中，可靠性、容錯能力和擴展性均較強，但訪問時易產生衝突，頻寬較窄，較差。高低位交叉存取又稱c—s存取，它是結合了高位交叉和低位交叉兩種方法的優點，既解決了衝突問題，又能有效地提高容錯能力和，最適合於結構。

3．流水線：主要有指令流水線技術和運算流水線技術兩種。

指令流水線技術主要目的是要提高計算機的運行效率和。它主要通過設定預取指令、設定多功能部件、進行內部數據定向、採取適當的指令調度策略來實現。指令調度的策略主要有靜態和動態兩種，靜態詞度是基於的，主要由完成，動態詞度是基於硬體的，主要是通過硬體技術進行。

運算流水線主要有單功能流水線和多功能流水線兩種。其中多功能流水線又可分為靜態流水線和。靜態只用來實現確定的功能，而可以在不同時間重新組合，實現不同的功能，它除流線連線外，還允許前饋和反饋連線，因此也稱為非線性流水線。這些前饋和反饋連線使得進入流水線的相繼事件的詞度變得很不簡單。由於這些連線，流水線不一定從最後一段輸出。根據不同的數據流動模式，人們可以用同一條流水線求得不同功能的值。

40 年代開始的現代計算機發展歷程可以分為兩個明顯的發展時代：串列計算時代、時代。每一個計算時代都從發展開始，接著是系統（特別是與）、，最後隨著問題求解環境的發展而達到頂峰。創建和使用並行計算機的主要原因是因為並行計算機是解決單處理器速度瓶頸的最好方法之一。

並行計算機是由一組處理單元組成的，這組處理單元通過相互之間的通信與協作，以更快的速度共同完成一項大規模的計算任務。因此，並行計算機的兩個最主要的組成部分是計算節點和節點間的通信與協作機制。的發展也主要體現在計算節點性能的提高以及節點間通信技術的改進兩方面。

60 年代初期，由於電晶體以及的出現，處理單元變得越來越小，存儲器也更加小巧和廉價。這些技術發展的結果導致了並行計算機的出現，這一時期的並行計算機多是規模不大的共享存儲，即所謂大型主機（mainframe）。ibm360 是這一時期的典型代表。

到了60 年代末期，同一個處理器開始設定多個功能相同的功能單元，也出現了。與單純提高相比，這些並行特性在處理器內部的套用大大提高了並行計算機系統的性能。和burroughs 公司此時開始實施illiaciv 計畫，研製一台64 個cpu 的simd ，它涉及到硬體技術、、i/o 設備、、直至應用程式在內的眾多研究課題。不過，當一台規模大大縮小了的16cpu 系統終於在1975 年面世時，整個計算機界已經發生了巨大變化。

首先是概念的革新，提出和快取的思想。ibm360/85 系統與360/91是屬於同一系列的兩個機型，360/91 的高於360/85，所選用的也較快，並且採用了動態調度的；但是，360/85 的整體性能卻高於360/91，唯一的原因就是前者採用了技術，而後者則沒有。

其次是開始代替。最初，半導體存儲器只是在某些機器被用作快取，而cdc7600 則率先全面採用這種體積更小、速度更快、可以直接定址的半導體存儲器，從此退出了歷史舞台。與此同時，積體電路也出現了，並迅速套用到了計算機中。元器件技術的這兩大革命性突破，使得illiaciv 的設計者們在底層硬體以及並行體系結構方面提出的種種改進都大為遜色。

1976 年cray-1 問世以後，從此牢牢地控制著整個高性能計算機市場15 年。cray-1 對所使用的邏輯電路進行了精心的設計，採用了我們如今稱為risc 的，還引入了向量，以完成向量運算。這一系列全新技術手段的使用，使cray-1 的達到了80mhz。

隨著機器的從4 位、8 位、16 位一直增加到32 位，其性能也隨之顯著提高。正是因為看到了的這種潛力，卡內基- 梅隆大學開始在當時流行的decpdp11 的基礎上研製成功一台由16 個pdp11/40 通過與16 個共享模組相連線而成的共享存儲c.mmp。

從80 年代開始，微處理器技術一直在高速前進。稍後又出現了非常適合於smp 方式的協定，而伯克利大學則對匯流排協定進行了擴展，提出了cache 一致性問題的處理方案。從此，c.mmp 開創出的共享存儲多處理器之路越走越寬；現在，這種體系結構已經基本上統治了伺服器和市場。

同一時期，基於訊息傳遞機制的並行計算機也開始不斷湧現。80 年代中期，加州理工成功地將64 個i8086/i8087 處理器通過超立方體互連結構連結起來。此後，便先後出現了intel ipsc 系列、inmos transputer 系列，intel paragon 以及ibm sp 的前身vulcan 等基於訊息傳遞機制的並行計算機。

80 年代末到90 年代初，共享方式的大規模並行計算機又獲得了新的發展。ibm將大量早期risc 微處理器通過蝶形連結起來。人們開始考慮如何才能在實現共享快取一致的同時，使系統具有一定的可擴展性（scalability）。90 年代初期，提出了dash 計畫，它通過維護一個保存有每一快取塊位置信息的目錄結構來實現分散式共享的快取一致性。後來，ieee 在此基礎上提出了快取一致性協定的標準。

90 年代以來，主要的幾種體系結構開始走向融合。屬於數據並行類型的cm-5 除大量採用商品化的微處理器以外，也允許的程式傳遞一些簡單的訊息；cray t3d是一台numa 結構的共享存儲型並行計算機，但是它也提供了全局同步機制、機制，並採取了一些減少訊息傳遞延遲的技術。

隨著商品化、網路設備的發展，以及mpi/pvm 等並行編程標準的發布，機群架構的並行計算機出現。ibm sp2 系列就是其中的典型代表。在這些系統中，各個節點採用的都是標準的商品化計算機，它們之間通過高速網路連線起來。

越來越多的並行計算機系統採用商品化的加上商品化的互連網路構造，這種分布存儲的並行計算機系統稱為機群。國內幾乎所有的高性能計算機廠商都生產這種具有極高性能價格比的高性能計算機，機就進入了一個新的時代，並行計算的套用達到了前所未有的廣度和深度。

並行計算機隨著微處理晶片的發展，已經進入了一個新時代。並行計算機的性能已經突破20pflops，正在向百億億次發展。我國並行計算機的研製已經走在世界前列。2003年由生產的深騰6800 在2003 年11 月世界top500 排名中位列第14 名，2004 年生產的曙光4000a 在2004 年6 月的世界top500 排名中位列第10 名，這是我國的高性能計算機在世界top500 中首次進入前十名，這標誌著我國在並行計算機系統的研製和生產中已經趕上了國際先進水平，為提高我國的科學研究水平奠定了物質基礎。2013年國際超級計算機大會最新發布的世界超級計算機500強排名中，國防科技大學研製的天河二號超級計算機系統，以峰值計算速度每秒5.49億億次、持續計算速度每秒3.39億億次雙精度浮點運算的優異性能位居榜首。

從top500 的前10 名來看，仍然是的最大擁有者。按照世界top500 的統計數據來分析，美國在計算能力上占有近全世界的一半，在top500 中的所有計算機中擁有的數量超過50%。