平行算法

平行算法一般是指許多指令得以同時進行的計算模式。在同時進行的前提下，可以將計算的過程分解成小部分，之後以併發方式來加以解決，或指用多台處理機聯合求解問題的方法和步驟，其執行過程是將給定的問題首先分解成若干個儘量相互獨立的子問 題，然後使用多台計算機同時求解它，從而最終求得原問題的解。由於人們的思維能力以及思考問題的方法對並行不太習慣，且並行算法理論不成熟，所以總是出現了需求再來研究算法，不具有導向性，同時實現並行算法的並行程序性能較差，往往滿足不了人們的需求。並行算法的研究歷史可簡單歸納為：上世紀70到80年代，並行算法研究處於高潮；到上世紀90年代跌入低谷；又處於研究的熱點階段。人們已經可以自己搭建PC cluster，利用學習到的理論知識來解決實際問題，不再是紙上談兵，這也為我們提供了新的機遇和挑戰。20世紀60年代開始發展含大量處理機的並行計算機，它分單指令流多數據流與多指令流多數據流兩類，每一時刻分別按一條或多條指令處理多個數據。並行計算機的出現促使了適應其並行這個特點的並行算法的發展。隨着時代的進步，我們需要不斷調整研究方向。並行算法研究的新走向是：並行算法研究內容不斷拓寬，並行計算被納入研究範疇；與廣大用户領域結合，注重應用，強調走到用户中去，為用户解決問題；重視新的、非常規計算模式，如神經計算、量子計算等，這些模式能夠解決某類特定問題，有其自身的優越性。

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

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

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

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

並行機就其控制方式分為單指令多數據(Single-Instruction-Multiple-Data縮寫為SIMD)和多指令多數據(MIMD)兩大類，每一時刻分別按一條和多條指令處理多個數據;就主存儲器設置方式又可分為共享存儲器型和分佈存儲器型兩大類，共享型集中設置存儲器為各處理機公用，分佈型則將存儲器附設於各處理機.迄今，大多並行機是MIMD機，它們有單程序多數據(Single-Program-Multiple-Data縮寫為SPMD)和多程序多數據(MPMD)兩種計算模式，各處理機分別執行同一和不同程序處理各自的數據集.針對不同類型及計算模式的並行機需設計不同類型的算法，好的算法應考慮到並行機的處理機之間的通信方式與能力這一影響效率的重要因素。

並行算法可以分成三大類：SIMD算法。同步MIMD算法，同步指算法中有些進程的某些步驟必須在完成其他進程的一些步驟之後方可執行。異步算法，其各進程之間不需同步，基本上是混亂迭代法.問題是算法怎樣設計與分析。並行計算依賴於一個簡單事實：獨立的計算可以同時執行，所謂獨立計算是指其每個結果元只出現一次的計算.由此產生“分而治之”和“重新排序”兩種非常基本的並行算法設計思想。

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

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

多處理機（Multi processor）是具有多個處理機的計算機，能夠大大提高計算機的處理速度。

共享存儲器結構:多個處理單元通過網絡（內部連接）共享集中的主存儲器，主存儲器由多個並行的存儲體組成，而每個CU都有自己的控制單元（這是與並行處理機的不同點）。系統資源易管理、利用，程序員易編程；但是處理機數目少，不易擴充。

分佈式存儲多處理機：每個處理機都有自己的控制器、自己的存儲單元，CU及存儲器等構成多個較為獨立的部分，各個部分通過網絡（內部連接）協調工作。其特點是結構靈活、易擴充，但是，任務傳輸以及任務分配算法複雜，通常要設計專有算法。

使用多台計算機協同工作來完成所要求的任務的計算機系統都是多處理機系統。傳統的狹義多處理機系統是指利用系統內的多個CPU並行執行用户多個程序，以提高系統的吞吐量或用來進行冗餘操作以提高系統的可靠性。