有效並行算法

並行計算（parallel computing）一般是指許多指令得以同時進行的計算模式。在同時進行的前提下，可以將計算的過程分解成小部分，之後以併發方式來加以解決。 ^[2]  要真正實現並行計算，必須有有效並行算法。例如現在計算機中CPU都是多核，一個有效並行算法能真正利用這些CPU資源，使計算機多個方面的效率都有明顯提升。有效並行算法一般有以下兩種解釋：1、並行計算機能夠正常使用的並行算法；2、並行算法運行時並行且有效的。有效並行算法的性能度量一般是從基本指標、加速比評測、可擴放性標準這三個方面進行。

並行算法是一門還沒有發展成熟的學科，雖然人們已經總結出了相當多的經驗，但是遠遠不及串行算法那樣豐富。並行算法設計中最常用的的方法是PCAM方法，即劃分，通信，組合，映射。首先劃分，就是將一個問題平均劃分成若干份，並讓各個處理器去同時執行；通信階段，就是要分析執行過程中所要交換的數據和任務的協調情況，而組合則是要求將較小的問題組合到一起以提高性能和減少任務開銷，映射則是要將任務分配到每一個處理器上。總之，並行算法還需要相當多完善的地方。 並行算法與串行算法最大的不同之處在於，並行算法不僅要考慮問題本身，而且還要考慮所使用的並行模型，網絡連接等等。

常見的非數值算法設計方法舉例

並行播送與並行求和

並行排序算法；

並行選擇算法：所謂選擇問題就是在一給定的序列中選擇出某組（個）滿足給定條件的元素。

關於圖論中的一些並行算法：

圖論作為一門到近代才發展起來的科學。在圖論中有很多關於如何設計算法的問題，比如求最小生成樹，單源最短路徑等等。事實上，這些算法中有很多是可以並行化的，而且並行化時運用的思想具有很大的啓發性，下面是幾個常見的並行圖論算法。

關於串處理的並行算法：

KMP算法的並行化。

並行處理計算機主要指以下兩種類型的計算機：①能同時執行多條指令或同時處理多個數據項的單中央處理器計算機；②多處理機系統。

並行處理計算機的結構特點

隨着電子器件的發展 ，計算機的處理能力有顯著提高。但是，僅僅依靠器件的進展而達到的速度提高，遠不能滿足現代科學、技術、工程和其他許多領域對高速運算能力的需要。這就要求人們改進計算機結構，採用各種並行處理技術，以便大幅度地提高處理速度和解題能力。

並行處理計算機的結構特點主要表現在兩個方面：①在單處理機內廣泛採用各種並行措施；②由單處理機發展成各種不同耦合度的多處理機系統。並行處理的主要目的是提高系統的處理能力。有些類型的並行處理計算機系統（如多處理機系統）還可以提高系統的可靠性。由於器件的發展，並行處理計算機系統具有較好的性能價格比，而且還有進一步提高的趨勢。

並行處理計算機的結構主要有流水線方式 、多功能部件方式 、陣列方式、多處理機方式和數據流方式。

執行時間

工作負載

存儲性能

Amdahl定理

Gastofson定理

Sun-Ni定理

等效率標準

等速度標準

平均延遲標準