並行演算法的原理

㈠ 並行演算法並行演算法簡介

在計算機科學中，演算法被定義為解決問題的一種方法和步驟。並行演算法則是指在多處理器的並行計算機系統中，多個處理器協同工作以解決同一問題的策略和步驟。在自然界中，並行現象普遍存在，關鍵在於能否有效利用這種特性。然而，由於人類思維模式和問題解決方法往往傾向於串列，加上並行演算法理論尚未完全成熟，使得過去的研究更多是基於問題出現後才去探索，缺乏前瞻性。

歷史上，1970至1980年代，對並行演算法的研究達到了高潮，但進入90年代，其熱度有所下降。然而，當前並行演算法又重新成為研究焦點。隨著技術的進步，人們現在能夠自行構建個人計算機集群（PC cluster），利用學到的理論知識解決實際問題，不再局限於理論探討。這既帶來了新的機遇，也提出了新的挑戰，要求我們不斷探索並提升並行演算法的效率和實用性，以滿足日益增長的需求。

並行演算法就是用多台處理機 聯合求解問題的方法和步驟,其執行過程是將給定的問題首先分解成若干個盡量相互獨立的子問 題,然後使用多台計算機同時求解它,從而最終求得原問題的解.

㈡ pso的並行演算法

與大多數隨機優化演算法相似，當適應值評價函數的計算量比較大時，PSO演算法的計算量會很大。為了解決該問題，研究者提出了並行PSO演算法。與並行遺傳演算法類似，並行PSO演算法也可以有三種並行群體模型：主從並行模型、島嶼群體模型和鄰接模型。
Schutte採用同步實現方式，在計算完一代中所有點的適應值之後才進入下一代。這種並行方法雖然實現簡單，但常常會導致並行效率很差。故而有人提出非同步方式的並行演算法，可以在對數值精度影響不大的條件下提高PSO演算法的並行性能。這兩種方式採用的都是主從並行模型，其中非同步方式在求解上耦合性更高，更容易產生通信瓶頸。
Baskar提出一種兩個子種群並行演化的並發PSO演算法，其中一個子種群採用原始的PSO演算法，另一個子種群採用基於適應值距離比的PSO演算法（FDR-PSO）；兩個子種群之間頻繁地進行信息交換。而El-Abd研究了在子種群中採用局部鄰域版本的協作PSO演算法，並研究了多種信息交換的方式及其對演算法性能的影響。黃芳提出一種基於島嶼群體模型的並行PSO演算法，並引入一種集中式遷移策略，提高了求解效率，同時改善了早收斂現象。
Li提出延遲交換信息的並行演算法屬於鄰接模型，該演算法可以提高速度，但可能使得解的質量變差。

㈢ 並發演算法之並行排序

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

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

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

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

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

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

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

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

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

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

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

改造成並行希爾排序：

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

㈣ 並行演算法的並行演算法的研究內容

(1) 並行計算模型 並行演算法作為一門學科，首先研究的是並行計算模型。並行計算模型是演算法設計者與體系結構研究者之間的一個橋梁，是並行演算法設計和分析的基礎。它屏蔽了並行機之間的差異，從並行機中抽取若干個能反映計算特性的可計算或可測量的參數，並按照模型所定義的計算行為構造成本函數，以此進行演算法的復雜度分析。
並行計算模型的第一代是共享存儲模型，如SIMD-SM和MIMD-SM的一些計算模型，模型參數主要是CPU的單位計算時間，這樣科學家可以忽略一些細節，集中精力設計演算法。第二代是分布存儲模型。在這個階段，人們逐漸意識到對並行計算機性能帶來影響的不僅僅是CPU，還有通信。因此如何把不同的通信性能抽象成模型參數，是這個階段的研究重點。第三代是分布共享存儲模型，也是我們目前研究所處的階段。隨著網路技術的發展，通信延遲固然還有影響，但對並行帶來的影響不再像當年那樣重要，注重計算系統的多層次存儲特性的影響。
(2) 設計技術並行演算法研究的第二部分是並行演算法的設計技術。雖然並行演算法研究還不是太成熟，但並行演算法的設計依然是有章可循的，例如劃分法、分治法、平衡樹法、倍增法/指針跳躍法、流水線法破對稱法等都是常用的設計並行演算法的方法。另外人們還可以根據問題的特性來選擇適合的設計方法。
（3）並行演算法分為多機並行和多線程並行。多機並行，如MPI技術；多線程並行，如OpenMP技術。
以上是並行演算法的常規研究內容。