並行結構

並行性有兩種解釋，同時性：兩個或兩個以上的事件在同一時刻發生。併發性：兩個或兩個以上的事件在同一時間間隔發生。

從處理數據的角度看，並行性等級從低到高可分為四類。字串位串：同時只對一個字的一位進行處理。這是最基本的串行處理方式，不存在並行性。字串位並：同時對一個字的全部位進行處理，不同字之間是串行的。這裏已開始出現並行性。字並位串：同時對許多字的同一位進行處理。這種方式有較高的並行性。全並行：同時對許多字的全部位進行處理。這是最高一級的並行。在數據庫中，並行結構主要是處理數據來分析的，具體採用哪一級並行性，主要與數據規模、機器設備和程序架構有關。

並行體系結構出現主要因為隨着各個領域對高性能計算的要求越來越高，尤其是多媒體領域大數據量高實時性的需求，使得傳統的單處理器體系結構已經很難適應大規模並行計算的需求，於是多處理器並行體系結構逐漸成為研究的熱點。 ^[1] 

多種級別的並行度現在已經成為計算機設計的推動力量，而能耗和成本則是主要約束條件。應用程序中主要有以下兩種並行。

(1) 數據級並行（Data Level Parallism），它的出現是因為可以同時操作許多數據項。

(2) 任務級並行（Task Level Parallism），它的出現是因為創建了一些能夠單獨處理但大量採用並行方式執行的工作任務。

計算機硬件又以如下4種主要方式來開發這兩種類型的應用並行。

(1) 指令級並行在編譯器的幫助下，利用流水線之類的思想適度開發數據級並行，利用推理執行之類的思想以中等水平開發數據級並行。

(2) 向量體系結構和圖形處理器（GPU）將單條指令並行應用於一個數據集，以開發數據級並行。

(3) 線程級並行在一種緊耦合硬件模型中開發數據級並行或任務級並行，這種模型允許在並行線程之間進行交互。

(4) 請求級並行在程序員或操作系統指定的大量去耦合任務之間開發並行。

共享存儲模型是一般的集中式多處理機的抽象 ，例如 SMP（Symmetric Multiprocessing）結構並行機 。其底層為一系列處理器 ，各個處理器可以對共享存儲器中的數據進行存取 ，數據對於每個處理器來説都是可訪問到的 ，不需要在處理器間進行數據傳遞，由於所有處理器可以訪問內存中的同一位置 ,因而它們可以通過共享變量進行交互和同步 。其初衷是為了共享存儲多處理機。

消息傳遞即用户顯式地通過發送和接收消息來實現處理器之間的數據交換 。在這個模型中 , 每個進程都有自己獨立的地址空間 ,一個進程不能夠直接訪問其他進程中的應用數據 , 數據訪問必須通過消息傳遞來實現 。它主要用來開發大規模和粗粒度的並行性 。MPI是通過擴展串行編程語言來實現並行化的 ，使得程序員可以操作並行處理器的底層函數 ，因而為程序開發提供了更大的靈活性。

針對消息傳遞模型和共享存儲模型各自的優點而形成的兩級並行模型具有更好的性能。這種模型是針對 SMP機羣而提出的 。模型的執行方式為在各個節點間使用消息傳遞的方式進行數據共享，而在各個節點內部使用共享存儲的方式來共享數據，由此可以更好地利用消息傳遞和共享存儲模型的處理數據的優勢，減少了開銷並且提升了性能 。 ^[2] 

MapReduce是Google提出的一個軟件架構，用於大規模數據集（大於1TB）的並行運算。概念“Map（映射）”和“Reduce（歸納）”，及他們的主要思想，都是從函數式編程語言借來的，還有從矢量編程語言借來的特性。

當前的軟件實現是指定一個Map（映射）函數，用來把一組鍵值對映射成一組新的鍵值對，指定併發的Reduce（歸納）函數，用來保證所有映射的鍵值對中的每一個共享相同的鍵組。

MapReduce是面向大數據並行處理的計算模型、框架和平台，它隱含了以下三層含義：

1）MapReduce是一個基於集羣的高性能並行計算平台（Cluster Infrastructure）。它允許用市場上普通的商用服務器構成一個包含數十、數百至數千個節點的分佈和並行計算集羣。

2）MapReduce是一個並行計算與運行軟件框架（Software Framework）。它提供了一個龐大但設計精良的並行計算軟件框架，能自動完成計算任務的並行化處理，自動劃分計算數據和計算任務，在集羣節點上自動分配和執行任務以及收集計算結果，將數據分佈存儲、數據通信、容錯處理等並行計算涉及到的很多系統底層的複雜細節交由系統負責處理，大大減少了軟件開發人員的負擔。

3）MapReduce是一個並行程序設計模型與方法（Programming Model & Methodology）。它藉助於函數式程序設計語言Lisp的設計思想，提供了一種簡便的並行程序設計方法，用Map和Reduce兩個函數編程實現基本的並行計算任務，提供了抽象的操作和並行編程接口，以簡單方便地完成大規模數據的編程和計算處理。 ^[3]