並行處理演算法

㈠ 並發演算法之並行排序

大部分排序演算法都是串列執行的，當排序元素很多時，使用並行排序演算法可以有效利用CPU，提高運算效率，但將串列演算法改成並行演算法將會極大的增加原有演算法的復雜度。

1、分離數據相關性：奇偶交換排序

冒泡排序：如果數據較小，會逐步被交換到前面，對於大的數字會下沉，交換到數組的尾部。

在每次迭代交換過程中，由於每次交換的兩個元素存在數據沖突，對於每個元素，它既可能與前面的元素交換，也可能與後面的元素交換，因此很難直接改成並行演算法。如果能夠解開這種數據的相關性，就可以更容易的使用並行演算法，奇偶交換排序就是基於這種思想的。

對於奇偶交換排序，它將排序過程分成兩個階段，奇交換和偶交換。奇交換總是比較奇數索引及其相鄰的後續元素，而偶交換總是比較偶數索引及其相鄰的後續元素。並且奇交換和偶交換會成對出現，這樣才能保證比較和交換涉及到數組中的每一個元素。在每個階段內，所有的比較和交換是沒有數據相關性的，每次比較和交換都可以獨立執行。

flag用來記錄當前迭代釋放發生了數據交換，start用來表示奇交換或偶交換。初始start=0，表示進行偶交換，每次迭代結束切換start狀態。如果上次比較交換發生了數據交換，或當前正在進行的是奇交換，循環不會停止，直到不再發生交換，並且當前進行的是偶交換為止。

2、改進的插入排序：希爾排序

插入排序思想：一個未排序的數組可以分為兩部分，前半部分是已排序的，後半部分是未排序的，在進行排序時，只需在未排序的部分中選擇一個元素，將其插入到前面有序的數組中即可。最終未排序的部分越來越少，直至為0排序完成。

插入排序很難並行化，因為上一次的數據插入依賴於上一次得到的有序序列，多個步驟之間無法並行。

希爾排序將整個數組根據間隔h分割為若干個子數組，子數組相互穿插在一起，每次排序時分別對每一個子數組進行排序。每次排序時總是交換間隔為h的兩個元素。在每組排序完成後，可以遞減h的值，進行下輪排序，直到h=1，此時等價於一次插入排序。

希爾排序優點：即使一個較小的元素在數組末尾，由於每次元素移動都以間隔h進行，數組末尾的元素可以在很少的交換次數下，被置換到最接近元素最終位置的地方。

改造成並行希爾排序：

--參考文獻《實戰Java高並發程序設計》

㈡ 用並行可實現的演算法有哪些

首先，應用的場合和解決的問題不一樣。分布式計算比較傾向於在計算尋找模式的東西，窮舉暴力之類的計算。分布式的計算被分解後的小任務互相之間有獨立性，節點之間的結果幾乎不互相影響，實時性要求不高。而並行計算則比較傾向於一些海量數據進行分析處理的場合，每個節點的每一個任務塊都是必要的，計算的結果相互影響，要求每個節點的計算結果要絕對正確，並且在時間上做到同步。舉例來說，像MD5破解，就比較適合使用大規模的分布式計算來窮舉，但對海量日誌數據進行處理來分析用戶行為就比較適合並行計算處理。 其次，實現方式區別比較大。分布式計算會是一個比較鬆散的結構，並行計算則是各節點之間通過高速網路或其它匯流排之類的東西連接。因此並行計算一般在企業內部進行，而分布式計算可能會跨越區域網，或者直接部署在互聯網上，節點之間幾乎不互相通信。很多公益性的項目，就是的使用分布式計算的方式在互聯網上實現，比如以尋找外星人為目的的SETI項目。

㈢ 並行計算的定義

並行計算（Parallel Computing）是指同時使用多種計算資源解決計算問題的過程，是提高計算機系統計算速度和處理能力的一種有效手段。它的基本思想是用多個處理器來協同求解同一問題，即將被求解的問題分解成若干個部分，各部分均由一個獨立的處理機來並行計算。並行計算系統既可以是專門設計的、含有多個處理器的超級計算機，也可以是以某種方式互連的若乾颱的獨立計算機構成的集群。通過並行計算集群完成數據的處理，再將處理的結果返回給用戶。
並行計算可分為時間上的並行和空間上的並行。
時間上的並行：是指流水線技術，比如說工廠生產食品的時候步驟分為：
1． 清洗：將食品沖洗干凈。
2． 消毒：將食品進行消毒處理。
3． 切割：將食品切成小塊。
4． 包裝：將食品裝入包裝袋。
如果不採用流水線，一個食品完成上述四個步驟後，下一個食品才進行處理，耗時且影響效率。但是採用流水線技術，就可以同時處理四個食品。這就是並行演算法中的時間並行，在同一時間啟動兩個或兩個以上的操作，大大提高計算性能。
l 空間上的並行：是指多個處理機並發的執行計算，即通過網路將兩個以上的處理機連接起來，達到同時計算同一個任務的不同部分，或者單個處理機無法解決的大型問題。
比如小李准備在植樹節種三棵樹，如果小李1個人需要6個小時才能完成任務，植樹節當天他叫來了好朋友小紅、小王，三個人同時開始挖坑植樹，2個小時後每個人都完成了一顆植樹任務，這就是並行演算法中的空間並行，將一個大任務分割成多個相同的子任務，來加快問題解決速度。