基本介紹
- 中文名：有效並行算法
- 外文名：Effective parallel algorithm
- 學科：計算機科學與技術
- 有關術語：並行算法、並行計算機
- 定義：能真正實現並行計算
- 相關領域：雲計算、格線計算
- 目的：提高計算機處理效率
簡介,並行算法,並行計算機,性能度量,基本指標,加速比評測,可擴放性標準,
簡介
並行計算（parallel computing）一般是指許多指令得以同時進行的計算模式。在同時進行的前提下，可以將計算的過程分解成小部分，之後以並發方式來加以解決。要真正實現並行計算，必須有有效並行算法。例如現在計算機中CPU都是多核，一個有效並行算法能真正利用這些CPU資源，使計算機多個方面的效率都有明顯提升。有效並行算法一般有以下兩種解釋：1、並行計算機能夠正常使用的並行算法；2、並行算法運行時並行且有效的。有效並行算法的性能度量一般是從基本指標、加速比評測、可擴放性標準這三個方面進行。
並行算法
並行算法是一門還沒有發展成熟的學科，雖然人們已經總結出了相當多的經驗，但是遠遠不及串列算法那樣豐富。並行算法設計中最常用的的方法是PCAM方法，即劃分，通信，組合，映射。首先劃分，就是將一個問題平均劃分成若干份，並讓各個處理器去同時執行；通信階段，就是要分析執行過程中所要交換的數據和任務的協調情況，而組合則是要求將較小的問題組合到一起以提高性能和減少任務開銷，映射則是要將任務分配到每一個處理器上。總之，並行算法還需要相當多完善的地方。 並行算法與串列算法最大的不同之處在於，並行算法不僅要考慮問題本身，而且還要考慮所使用的並行模型，網路連線等等。
常見的非數值算法設計方法舉例
並行播送與並行求和
並行選擇算法：所謂選擇問題就是在一給定的序列中選擇出某組（個）滿足給定條件的元素。
關於圖論中的一些並行算法：
圖論作為一門到近代才發展起來的科學。在圖論中有很多關於如何設計算法的問題，比如求最小生成樹，單源最短路徑等等。事實上，這些算法中有很多是可以並行化的，而且並行化時運用的思想具有很大的啟發性，下面是幾個常見的並行圖論算法。
關於串處理的並行算法：
KMP算法的並行化。
並行計算機
並行處理計算機的結構特點
隨著電子器件的發展 ，計算機的處理能力有顯著提高。但是，僅僅依靠器件的進展而達到的速度提高，遠不能滿足現代科學、技術、工程和其他許多領域對高速運算能力的需要。這就要求人們改進計算機結構，採用各種並行處理技術，以便大幅度地提高處理速度和解題能力。
並行處理計算機的結構主要有流水線方式 、多功能部件方式 、陣列方式、多處理機方式和數據流方式。
性能度量
基本指標
執行時間
工作負載
存儲性能
加速比評測
Amdahl定理
Gastofson定理
Sun-Ni定理
可擴放性標準
等效率標準
等速度標準
平均延遲標準
