基本介紹
- 中文名：可擴展並行處理
- 外文名：Extensible parallel processing
- 學科：計算機科學
- 目的：縮短計算時間
- 有關術語：並行處理
- 特點：可擴展性
簡介,可擴展性,計算複雜性,並行算法,並行處理系統,
簡介
對於並行處理系統來說，可擴展並行處理可以從以下幾點來解釋：對於體系結構來說，就是在確定的套用背景下，隨著處理機數目的增加，計算機系統的性能能相應提高；對於並行算法來說，就是它能處理的問題規模隨處理機數目的增長呈比例增長；對於並行算法和並行機組合體來說，就是當問題規模增長時，適當增加處理機數目，該組合體能夠獲得某種指定的性能。
可擴展性
可擴展性是隨著問題規模和計算資源的增加，對算法執行時間的一種定量描述，或指某個算法在某個機器上的可擴放性反映該算法是否能有效利用不斷增加的CPU。研究可擴展性的目的就是要使算法儘可能的利用最多的處理器，並且也可以預測當某個算法移植到大規模處理機上後的運行效果（即問題規模擴大時對處理器的利用情況）。一個好的可擴展度量方法可以反映算法和機器組合體匹配程度的信息，也可以預測並行系統的性能。可擴展性度量方法的基本要求有：它必須提供系統規模如何影響性能的信息；它必須是描述並行算法與機器組合的函式。這是因為系統規模增加了，並行開銷也會增加，使得性能降低。引起性能降低的原因在於算法與機器兩個方面，如算法中負載不平衡、處理機通信費用增加等；它是可評估的、可比較的、定量的性能度量。為了儘可能最優地匹配實際的並行體系結構，通常採用與體系結構相結合的算法設計。相同的算法在不同體系結構上的性能是不同的。因此，在可擴展性研究方面，通常研究的是這兩者相結合的可擴展性。
計算複雜性
對於同一個問題往往可以用許多算法求解。由於各種算法對同一個問題都有可能求出最優解，怎樣衡量一個算法的效率怎樣判定一個問題是否可計算，如果這個問題可計算，則該問題的難易程度如何，都涉及到計算複雜性理論的有關知識。計算複雜性理論是用於研究算法有效性和問題難度的一種工具，是提高問題的計算效率的前提條件。一個算法複雜性的高低體現為運行該算法所需要的計算機資源即時間和空間資源的多少上。所需的資源越多，說明該算法的複雜性越高所需的資源越少，該算法的複雜性便越低。一般來說，一個問題的複雜度可以用計算該問題所耗費的時間和空間資源的多少來衡量，亦即算法的時間複雜度和空間複雜度。我們可以定義一個以數據量如問題的規模大小為輸入，時間或空間占據量為輸出的函式，用來度量算法的時間或空間複雜度。其形式的定義可以用圖靈機的計算模型描述。
並行算法
並行計算（parallel computing）一般是指許多指令得以同時進行的計算模式。在同時進行的前提下，可以將計算的過程分解成小部分，之後以並發方式來加以解決。計算機軟體可以被分成數個運算步驟來運行。為了解決某個特定問題，軟體採用某個算法，以一連串指令運行來完成。傳統上，這些指令都被送至單一的中央處理器，以循序方式運行完成。在這種處理方式下，單一時間中，只有單一指令被運行(processor level: 比較微處理器，CISC, 和RISC，即流水線Pipeline的概念，以及後來在Pipeline基礎上以提高指令處理效率為目的的硬體及軟體發展，比如branch-prediction, 比如forwarding，比如在每個運算單元前的指令堆疊，彙編程式設計師對programm code的順序改寫)。並行運算採用了多個運算單元，同時運行，以解決問題。
並行算法是一門還沒有發展成熟的學科，雖然人們已經總結出了相當多的經驗，但是遠遠不及串列算法那樣豐富。並行算法設計中最常用的的方法是PCAM方法，即劃分，通信，組合，映射。首先劃分，就是將一個問題平均劃分成若干份，並讓各個處理器去同時執行；通信階段，就是要分析執行過程中所要交換的數據和任務的協調情況，而組合則是要求將較小的問題組合到一起以提高性能和減少任務開銷，映射則是要將任務分配到每一個處理器上。總之，並行算法還需要相當多完善的地方。 並行算法與串列算法最大的不同之處在於，並行算法不僅要考慮問題本身，而且還要考慮所使用的並行模型，網路連線等等。
並行處理系統
並行處理系統是利用多個功能部件或多個處理機同時工作來提高系統性能或可靠性的計算機系統。任何一個計算機系統都包含某種程度的並行性，但如果只具有硬體基本操作的並行性，如一個數據的所有位同時傳送，許多門電路同時工作等，不能認為是並行處理系統。並行處理系統至少應包含指令級或指令級以上的並行。
並行處理系統可以在4個級別上實現並行處理：指令內部、指令之間、任務或過程之間和作業或程式之間。採用多個功能單元並行實現一條指令中的不同操作屬於指令內部並行，超長指令字( VLIW) 計算機是實現指令內部並行的典型例子。同一時間執行兩條以上指令稱為指令間並行，超標量計算機中有多條指令流水線，這是指令間並行的實例。一個程式往往可以分解成多個任務、子程式或過程，同一程式內多個任務或過程可以在一個系統的不同處理機中同時運行，以縮短計算時間，稱為任務級並行。多個作業或大型計算問題的多個獨立的程式，在並行處理系統的不同的處理機或計算機中同時運行，以提高系統的吞吐量或有效地利用系統資源，稱為作業級並行。並行處理系統的研究與發展涉及計算理論、算法、計算機體系結構、硬體、軟體 (包括作業系統、編譯、編程環境與程式語言等)以及性能評價等方面。
