漢振分享 | 算法的工程優化技術

當一個算法實現之后，需要集成到產品中去，這時就要面臨性能問題。在實際工程應用中，除采用降低算法的復雜度去解決性能問題外，通常也會選擇優化代碼以及良好運用硬件等方式。接下來將針對在不改動算法情況下，對純工程方面做性能優化的技術作一個介紹。

1. 流程優化

對初始算法進行流程優化主要有：

A.避免算法執行過程中的重復操作及冗余計算。

B.避免算法中循環語句內部有過多依賴和跳轉。

C.定點化：定點化的思想是將浮點型運算轉換為整型運算，具體做法是將數據乘上一個很大的數后，將所有運算轉為整型計算，例如某個乘法只關心小數點后3位，那把數據都乘上10000后，進行整型運算的結果也就滿足所需的精度。

D.以空間換時間：空間換時間(zui)經典的就是查找表，某些計算相當耗時，但其自變量的值域是比較有限的，這樣的情況可以預先計算好每個自變量對應的函數值，存在一個表格中，每次根據自變量的值去索引對應的函數值即可。

E.預先分配內存：把握算法整個執行過程中內存的使用，提前分配好內存，避免內存不斷開辟與釋放而產生的耗時。

2. 指令優化

SIMD即(Single Instruction Multiple Data)，單指令多數據流，是CPU中能夠復制多個操作數，并把它們打包在大型寄存器的一組指令集。

目前PC上I-n-t-e-l指令集有SSE、AVX等，SSE/AVX是對其X86體系的SIMD擴展指令集，它基于SIMD向量化技術，提高X86硬件的計算性能，增強了X86多核向量處理器的圖像和視頻處理能力。SSE/AVX指令支持向量化數據并行，一個指令可以同時對多個操作數進行操作，同時操作的數據個數由向量寄存器的長度和數據類型共同決定。

SIMD屬于細粒度的并行，對于圖像算法中利用SIMD技術優化，可以一次性對多個像素進行處理，性能提升明顯，大部分情況下都有3-4倍的提升。

3. 多線程優化

當系統有多個線程/進程時，CPU會按一定的調度策略，把它們盡可能放在不同的核上執行，多線程優化就是把算法拆成多個子任務，跑在不同的線程上，利用CPU多個核的能力，并行執行算法。

比較有名的框架就是OpenMP，OpenMP是一種共享內存并行系統的多線程程序設計方案，支持的編程語言包括C、C++和Python。OpenMP提供了對并行算法的高層抽象描述，特別適合在多核CPU機器上的并行程序設計。編譯器根據程序中添加的pragma指令，自動將程序并行處理，使用OpenMP簡化了并行程序設計。OpenMP采用fork-join的執行模式，開始的時候只存在一個主線程，當需要并行計算的時候，派生出若干個分支線程來執行并行任務。當并行代碼執行完成之后，分支線程匯合，并把控制流程交給單獨的主線程。一個典型的fork-join執行模型如圖1所示。

 圖1. fork-join執行模型示意圖

4. GPU加速

GPU即(Graphic Processing Unit)，圖形處理器。如圖2所示，CPU功能模塊很多，能適應復雜運算環境；GPU構成則相對簡單，目前流處理器和顯存控制器占據了絕大部分晶體管。CPU中大部分晶體管主要用于構建控制電路（比如分支預測等）和Cache，只有少部分的晶體管來完成實際的運算工作。而GPU的控制相對簡單，且對Cache的需求小，所以大部分晶體管可以組成各類電路、多條流水線，使得GPU的計算速度有了突破性的飛躍，擁有了更強大的處理浮點運算的能力。

 圖2. GPU和CPU架構

要使用GPU進行通用計算，需要基于一個框架，目前的框架主要有CUDA和OpenCL。

CUDA是一種由NVIDIA推出的通用并行計算架構，該架構使GPU能夠解決復雜的計算問題。 它包含了CUDA指令集架構（ISA）以及GPU內部的并行計算引擎。這個架構只能在裝配了NVIDIA顯卡的機器上使用。

OpenCL是一個為異構平臺編寫程序的框架，此異構平臺可由CPU，GPU或其他類型的處理器組成。OpenCL由一門用于編寫kernels（在OpenCL設備上運行的函數）的語言（基于C99）和一組用于定義并控制平臺的API組成。OpenCL提供了基于任務分割和數據分割的并行計算機制。