哪種算法可以最好的映射GPU及矢量處理器呢？換句話說，當使用加速器和OpenCL時，哪種類型的算法更加快速？
來自弗吉尼亞理工大學的Wu Feng教授和他的團隊例舉了一份算法列表，分享了OpenCL常被用于計算機領域的13個經典案例。有人將其稱之為OpenCL計算領域的13個“小巨人”。
一、Dense Linear Algebra（稠密線性代數）
經典的向量和矩陣運算，傳統上可分為1級（矢量/矢量vector/vector），2級（矩陣/矢量），3級（矩陣/矩陣），應用范圍極其廣泛。
應用范圍：
- 線性代數：LAPACK， ATLAS。
- Clustering algorithms （聚類算法）/ Data-mining（數據挖掘）：StreamCluster， K-均值算法。
二、Sparse Linear Algebra（稀疏線性代數）
乘法運算主要是由零矩陣組成。通過移動對角矩陣周圍的非零元素，使計算更加高效。
應用范圍：
- 有限元素分析。
- 偏微分方程式。
使用OpenCL有兩種方法：通過一些列的操作行為解決該問題，這將導致很大一部分開銷；第二種方法是使用一些列連續的逐次逼近法，將函數誤差最小化。
三、Spectral Methods（光譜法）
各種結構的物質都具有自己的特征光譜，光譜分析法就是利用特征光譜研究物質結構或測定化學成分的方法。
光譜方法可用來解決常微分方程（ODEs），偏微分方程（PDEs）以及包含微分方程增值問題。
應用范圍：
- 流體動力學。
- 量子力學。
- 天氣預測。
利用OpenCL針對每個硬件架構有各種FFT實施方法。訣竅是調優。
四、N-Body Methods
N-Body法是模擬粒子的動力學系統，通常在物理學的影響下如重力，計算方法有兩種（A影響B，同樣B也影響A），整個系統在每一輪之后都會再次更新。
基本算法是O(N^2)。對于大型系統的優化，可以通過neighbour-administration（相鄰管理）和遠離粒子計算，這里運行時方法是可取的。
應用范圍：
- 天文學：宇宙學（比如，星系的形成）。
- 計算化學：分子動力學（比如蛋白質折疊），分子模擬。
- 物理：流體動力學，等離子體物理學。
OpenCL可以實現每秒數以萬計的粒子。
五、Structured Grids（結構化網格）
結構化網格是指網格區域內所有的內部點都具有相同的毗鄰單元。在一個結構化或規則的網格中所有的元素具有相同的尺寸，比如方形模塊。計算方法依賴于相鄰的不規則網格。
應用范圍：
- 圖形處理：Gaussian image blurring 高斯圖像模糊。
- Physics Simulations：transient thermal differential equation solver。
- Finite Element Method（有限元素法）。
利用OpenCL，網格有規則，因此映射也相當容易。要解決的問題是如何做到相鄰網格之間的連通性。
六、Unstructured Grids（非結構化網格）
所有的網格都無規則性，不同的元素有著不同的相鄰數量。這一組有很多的重疊與回溯。網格中的每個元素都可以是二維的多邊形或者三維多面體。每個元素之間沒有隱含的連通性。
應用范圍：
- 計算流體動力學。
- Belief propagation（置信傳播）。
難點是在硬件上映射不規則網格。
七、Map-Reduce & Monte Carlo
每個進程可獨立于其他進程運行，因此，在相鄰的進程之間沒有連通性。在龐大的數據集和計算密集型算法中，GPU可結合大數據解決方法，比如Hadoop。
應用范圍：
- Monte-Carlo（蒙特卡洛法）：PI（圓周率）計算法，碰撞仿真，序列對比。
- 分布式搜索。
由于節點之間的通信是最小的，這也是使用GPU最快的方法之一。
八、Combinational Logic（組合邏輯）
組合邏輯電路是一種邏輯電路，它的任一時刻的穩態輸出，僅僅與該時刻的輸入變量的取值有關，而與該時刻以前的輸入變量取值無關。該算法中涉及大量的數據，可利用位級操作（ bit-level ）執行簡單的操作。
應用范圍：
- Computing checksums。
- 計算校驗法，CRCs。
- 加密和解密。
- 散列。
- Hamming weight。
并不是所有的硬件都適合這種類型的操作，因此，設備的選擇是至關重要的。
九、Graph Traversal（圖形追蹤）
圖形追蹤是以特定的方式訪問所有節點，更新/檢查值。樹形追蹤是屬于圖形追蹤一種特殊情況，有間接查找和微計算。
應用范圍：
- 搜索：深度優先搜索，廣度優先搜索，找到所有節點中某個連接組件。
- 排序：快速排序。
- 序列化/反序列化。
- Maze生成。
- 碰撞檢測。
使用OpenCL，最關鍵的是要保持核心程序處于繁忙狀態。
十、Dynamic Programming（動態規劃）
它是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。
動態規劃常適用于解決簡單的重疊子問題和最優子結構性質的問題。許多動態編程問題操作通過在網格中填寫具有代表性的問題領域，這個領域在網格中保留著最終答案。
應用范圍：
- 圖形問題：Floyd’s AllPairs，最短路徑， Bellman-Ford算法。
- 序列對比：Needleman-Wunsch, Smith-Waterman。
十一、Backtracking（回溯法）
回溯法（探索與回溯法）是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇并不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為“回溯點”。
這組通用的解決方法是分支定界（分而治之）。
應用范圍：
- 智力游戲：N-queens，填字游戲，九宮格游戲，Peg接龍。
- Travelling salesman（旅行推銷員）。
- Knapsack，子集和問題以及分區問題。
- 整數線性規劃。
- Boolean Satisfiability（布爾運算）。
- Combinatorial Optimisation（組合優化）。
在OpenCL中最重要的就是避免大的分支。
十二、Probabilistic Graphical Models（概率圖模型）
這個圖形結合了不確定性（概率）和邏輯結構（獨立約束）表示復雜的、現實世界的現象。
應用范圍：
- Bayesian（貝葉斯）網絡：信念網絡，概念網絡，因果網絡，知識地圖。
- Hidden Markov models（隱馬爾可夫模型）。
- Neural networks。
隨著越來越多的進程需要更新相同的節點（原子學就是典型的案例），因此，需消耗大量的時間。
十三、Finite State Machines（有限狀態機）
有限狀態機是指有限個狀態以及在這些狀態之間的轉移和動作等行為的數學模型。
其具有三個特征：狀態總數（state）是有限的；任一時刻，只處在一種狀態之中；某種條件下，會從一種狀態轉變（transition）到另一種狀態。
數學計算模型常用于設計連接計算機程序和時序邏輯電路。它常被看作是一個抽象性的機器，可用在有限的數量狀態下。
應用范圍：
- 視頻解碼，解析，壓縮。
- 數據挖掘。
- 查找循環模式。
