具有潛在性能優化的浮點算法

Question

對於大學講座，我正在尋找具有已知漸近運行時的浮點算法，但是可能會進行低級（微）優化。這意味着優化，如最大限度地減少高速緩存未命中和寄存溢出，最大化指令級並行性並利用新CPU上的SIMD（向量）指令。優化將是CPU特定的，並將使用適用的指令集擴展。

經典教科書中的例子是矩陣乘法，其中可以通過重新排序內存訪問序列（以及其他技巧）來實現很好的加速。另一個例子是FFT。不幸的是，我不能選擇其中任何一個。

任何人有任何想法，或者可以使用提升的算法/方法？

我只對可以設想每線程加速的算法感興趣。通過多線程並行處理問題很好，但不是本講座的範圍。

編輯1：我是以爲課程，沒有教它。在過去的幾年中，有不少項目在性能方面超越了當前的最佳實施。

編輯2：這paper列出（從第11頁開始）七類重要的數值方法和一些使用它們的相關算法。至少有一些提到的算法是候選人，但是很難看出哪些算法是候選人。

---

編輯3：謝謝大家對你很好的建議！我們提出實施曝光融合算法（paper from 2007），我們的建議被接受。該算法創建類似HDR的圖像，主要由小內核卷積組成，其次是源圖像的加權多分辨率混合（在拉普拉斯金字塔上）。我們感興趣的是該算法已經在廣泛使用的Enfuse工具中實現，該工具現在在4.1版本中。因此，我們將能夠驗證並比較我們的結果與原始結果，並且可能有助於工具本身的開發。如果可以，我會在未來更新這篇文章。

Answer 1

最簡單的可能的例子：

• 總和的累積。使用多個累加器展開和向量化可以在典型的流水線體系結構上加速（ADD延遲）*（SIMD向量寬度）（如果數據在緩存中;由於沒有數據重用，如果您正在讀取數據，它通常不會有幫助記憶），它可以很容易地成爲一個數量級。可愛的東西要注意：這也減少了結果的平均誤差！相同的技術適用於任何類似的縮減操作。

從圖像/信號處理的一些經典：

• 卷積小核（尤其是小2D卷積像一個3x3或5x5個內核）。從某種意義上說，這是一種欺騙行爲，因爲卷積是與矩陣相乘，並且與FFT密切相關，但實際上高性能小內核卷積的基本算法技術與兩者完全不同。

• 侵蝕和擴張。

• 什麼形象的人稱之爲「伽瑪校正」;這實際上是對指數函數的評估（可能是一個接近於零的分段線性片段）。在這裏，您可以利用圖像數據通常完全處於像[0,1]這樣的有限範圍內的事實，並且使用更便宜的函數逼近（低階分片最小多項式常見）很少需要亞ulp精度。

Answer 2

斯蒂芬佳能的圖像處理示例將分別用於有教育意義的項目。採取了不同的策略，不過，你可能看一定服從幾何問題：

• 最近對點的適度高維說--- 50000左右個16米左右的尺寸。對於您的目的而言，這可能與矩陣乘法有許多共同之處。 （如果維度太高，維度降低開始成問題;低得多的空間數據結構占主導地位，使用暴力內核的暴力或簡單的東西就是我想用於此的。）
• Variation ：對於每個點，找到最近的鄰居。
• 變化：紅點和藍點;找到距離每個藍點最近的紅點。
• Welzl最小的包含圓的算法實現起來相當簡單，並且真正的昂貴步驟（檢查當前圓外的點）適合矢量化。 （我懷疑你可以用一點努力就可以在兩個維度上殺死它）。

被警告說，計算幾何的東西通常比看起來更麻煩;不要在不理解退化情況存在的情況下隨意抽出一篇論文，並且要小心編程需要的東西。

查看其他線性代數問題。它們也非常重要。密集的Cholesky因式分解是一個很自然的事情（比LU分解更重要），因爲你不需要爲了使其工作而旋轉。

Answer 3

有一個免費的基準測試稱爲c-ray。 這是一個用於浮點性能基準的小型射線追蹤器。

一些隨機堆疊照片顯示它幾乎將其所有時間花費在稱爲ray_sphere的函數中，該函數確定光線是否與球體相交，如果是，則在哪裏。

他們也表現出較大加速一些機會，比如：

• 它不通過場景中的所有球線性搜索，試圖找到最近的交叉。通過在做所有三維幾何數學計算之前做一個快速測試，以確定一個球體是否比目前所見最好的球體更遠，這代表了加速的一個可能區域。

• 它不嘗試利用從一個像素到下一個像素的相似度。這可能會獲得巨大的加速。

所以，如果你想要看的是芯片級性能，它可能是一個體面的例子。然而，這也表明如何能有更多的機會。