第九章 并行處理技術

本章講述的重點內容就是陣列處理機和多處理機，對陣列機的基本結構、主要特點、以及陣列機的互連網絡和并行存儲器的無沖突訪問等內容要加強理解。本章應掌握的概念有：陣列處理機、網絡拓撲結構、單級立方體網絡、多級立方體網等。

一、并行處理技術（識記）：

并行性主要是指同時性或并發性，并行處理是指對一種相對于串行處理的處理方式，它著重開發計算過程中存在的并發事件。

并行性通常劃分為作業級、任務級、例行程序或子程序級、循環和迭代級以及語句和指令級。作業級的層次高，并行處理粒度粗。粗粒度開并行性開發主要采用MIMD方式，而細粒度并行性開發則主要采用SIMD方式。

開發計算機并行性的方法主要有：資源重復、時間重疊和資源共享三種方法。

二、SIMD并行計算機（陣列處理機）

陣列機也稱并行處理機。它將大量重復設置的處理單元按一定方式互連成陣列，在單一控制部件CU（Contrul Unit）控制下對各自所分配的不同數據并行執行同一指令規定的操作，是操作并行的SIMD計算機。它采用資源重復的措施開發并行性。是以SIMD（單指令流多數據流）方式工作的。

1、陣列機的基本結構（識記）

陣列機通常由一個控制器CU、N個處理器單元PE（Processing Element）、M個存儲模塊以及一個互連網絡部件（IN）組成。根據其中存儲器模塊的分布方式，陣列機可分為兩種基本結構：分布式存儲器的陣列機和共享存儲器的陣列機（理解二者不同之處）。

陣列機的主要特點：

它采用資源重復的方法引入空間因素，這與利用時間重疊的流水線處理機是不一樣的。它是利用并行性中的同時性而不是并發性，所有的處理單元必須同時進行相同操作（資源重復同時性）（我們想象一下亞運會的開幕式大型團體操表演，每個人就是一個PE，他們聽從一個總指揮的指令，同時進行自己的操作，很快地就能"計算"出一個結果（隊形）來。）

它是以某類算法為背景的專用計算機，基本上是專用于向量處理的計算機（某類算法專用機）。

陣列機的研究必須與并行算法研究密切結合，以使它的求解算法適應性更強一些，應用面更廣一些（并行算法合研究）。

陳列機實質上是由專門對付數據組運算的處理單元陣列組成的處理機（M個PE）、專門從事處理單元陣列的控制及標量處理機（控制器CU）和專門從事系統輸入輸出操作及操作系統管理的處理機三部分構成的一個異構型多處理機系統（三個部分成異構）。

2、陣列機的并行算法（領會）

陣列機的算法是與結構緊密聯系在一起的，陣列機上常用的算法有矩陣計算、圖象處理等，我們對教材中舉的兩種算法要領會，特別是累加和遞歸操作，不難理解。它就是使各個處理器同時進行加的操作，但并不是全部處理器都參加運算，在處理時，根據累加計算的需要，由控制器CU借助屏蔽的方式將一部分PE設置成不活動的狀態。這種累加操作的速度提高倍數是N/log2N倍。

3.典型的SIMD計算機

對圖9.6要加以領會，對于ILLIAC-IV的互連方式，若給你N個PE，請你畫出各個PE 的連接，行不行？這種陣列中，任意兩個單元之間的最短距離不超過根號N減去1步。這種計算機就是前面說的分布式存儲器了陣列處理機。

另一種典型結構BSP結構。它的主要特點是將資源重復和時間重復結合起來開發并行性。這種結構就是集中式共享存儲器的陣列處理機。

4.SIMD計算機的互連網絡（簡單應用）

在陣列機中，各個處理單元和存儲模塊之間都要經過網絡交換信息。衡量互連網絡性能好壞的主要因素是它的連接度、延時性、帶寬、可靠性和成本。好象我們現在用的互聯網，沒有一項性能指標令人滿意呀。

設計互連網時應考慮的四個特征是：

通信工作方式：有同步、異步及同/異步組合等三種。陣列機都采用同步工作方式，也就是各種命令的廣播和并行操作都由統一的時鐘加以同步控制。

控制策略：集中和分散兩種。SIMD陣列機一般采用集中控制。

交換方式：線路交換和分組交換（又稱包交換）以及線路/包交換組合三種。SIMD一般采用線路交換