並行算法

並行算法是並行計算中非常重要的問題。並法研究應該確立一個“理論－設計－實現－應用”的系統方法，形成一個完善的 “架構—算法—編程” 方法論，這樣才能保證並行算法不斷髮展並變得更加實用。

簡單的説，算法就是求解問題的方法和步驟。並行算法，就是在並行機上用很多個處理器聯合求解問題的方法和步驟。實際上，在自然界中並行是客觀存在的普遍現象，關鍵問題在於能不能很好的利用。由於人們的思維能力以及思考問題的方法對並行不太習慣，且並行算法理論不成熟，所以總是出現了需求再來研究算法，不具有導向性，同時實現並行算法的並行程序性能較差，往往滿足不了人們的需求。並行算法的研究歷史可簡單歸納為：上世紀70到80年代，並行算法研究處於高潮；到上世紀90年代跌入低谷；目前，又處於研究的熱點階段。現在，人們已經可以自己搭建PC cluster，利用學習到的理論知識來解決實際問題，不再是紙上談兵，這也為我們提供了新的機遇和挑戰 ^[1]  。

相對於串行計算，並行計算可以劃分成時間並行和空間並行。時間並行即流水線技術，空間並行使用多個處理器執行併發計算，當前研究的主要是空間的並行問題。以程序和算法設計人員的角度看，並行計算又可分為數據並行和任務並行。數據並行把大的任務化解成若干個相同的子任務，處理起來比任務並行簡單。

空間上的並行導致兩類並行機的產生，按照麥克·弗萊因（Michael Flynn）的説法分為單指令流多數據流（SIMD）和多指令流多數據流（MIMD），而常用的串行機也稱為單指令流單數據流（SISD）。MIMD類的機器又可分為常見的五類：並行向量處理機（PVP）、對稱多處理機（SMP）、大規模並行處理機（MPP）、工作站機羣（COW）、分佈式共享存儲處理機（DSM）。

並行計算機有以下五種訪存模型：均勻訪存模型（UMA）、非均勻訪存模型（NUMA）、全高速緩存訪存模型（COMA）、一致性高速緩存非均勻存儲訪問模型（CC-NUMA）和非遠程存儲訪問模型（NORMA）。

不像串行計算機那樣，全世界基本上都在使用馮·諾伊曼的計算模型；並行計算機沒有一個統一的計算模型。不過，人們已經提出了幾種有價值的參考模型：PRAM模型，BSP模型，LogP模型，C^3模型等 ^[2]  。

（1）並行計算模型 並行算法作為一門學科，首先研究的是並行計算模型。並行計算模型是算法設計者與體系結構研究者之間的一個橋樑，是並行算法設計和分析的基礎。它屏蔽了並行機之間的差異，從並行機中抽取若干個能反映計算特性的可計算或可測量的參數，並按照模型所定義的計算行為構造成本函數，以此進行算法的複雜度分析。

並行計算模型的第一代是共享存儲模型，如SIMD-SM和MIMD-SM的一些計算模型，模型參數主要是CPU的單位計算時間，這樣科學家可以忽略一些細節，集中精力設計算法。第二代是分佈存儲模型。在這個階段，人們逐漸意識到對並行計算機性能帶來影響的不僅僅是CPU，還有通信。因此如何把不同的通信性能抽象成模型參數，是這個階段的研究重點。第三代是分佈共享存儲模型，也是我們目前研究所處的階段。隨着網絡技術的發展，通信延遲固然還有影響，但對並行帶來的影響不再像當年那樣重要，注重計算系統的多層次存儲特性的影響。

（2）設計技術並行算法研究的第二部分是並行算法的設計技術。雖然並行算法研究還不是太成熟，但並行算法的設計依然是有章可循的，例如劃分法、分治法、平衡樹法、倍增法/指針跳躍法、流水線法等都是常用的設計並行算法的方法。另外人們還可以根據問題的特性來選擇適合的設計方法。

（3）並行算法分為多機並行和多線程並行。多機並行，如MPI技術；多線程並行，如OpenMP技術。

以上是並行算法的常規研究內容 ^[3]  。

隨着時代的進步，我們需要不斷調整研究方向。目前並行算法研究的新走向是：並行算法研究內容不斷拓寬，並行計算被納入研究範疇；與廣大用户領域結合，注重應用，強調走到用户中去，為用户解決問題；重視新的、非常規計算模式，如神經計算、量子計算等，這些模式能夠解決某類特定問題，有其自身的優越性。