算法優化書籍

目錄

前言

1 嵌入式系統優化流程

1， 選用更優的算法

2， 選擇嵌入式平台型号

3， 算法優化一般流程

2 高效的程式設計

1，資料類型

2， 編寫高效代碼

(1) 變量遞增和遞減

(2) 使用代碼塊最小化變量周期

(3) 循環中計數器的引用

(4) 數組索引的變量類型

(5) 減少循環體内容

(6) 循環内跳轉指令的應用

(7) 指針别名的限制

(8) 循環類型對比

(9) 結構體指針的用法

(10) 循環體的展開

(11) 循環内部函數

(12) 循環内代碼條件判斷處理

(13) 動态記憶體配置設定

3，編譯器優化

(1)優化選項的使用

(2)多子產品交叉優化

4，彙編優化分析

(1)點乘優化

(2)循環内依賴性優化

5，利用OpenMP多線程優化

(1)OpenMP的常用指令

(2)多線程之間的同步

3 記憶體優化

1， 記憶體分類

2， SRAM存儲器

(1) Cache 結構

(2) Cache讀取miss與命中

(3)LRU 替換算法

(3) 硬體預取

3， Cache優化

（1）通過選擇适當的資料類型減少記憶體帶寬要求

（2）從算法流程分析cache

（3）cache開銷評估

（4）避免L1Pmiss

（5）避免L1Dmiss

（6）避免cache 抖動

（7）避免使用過大數組導緻miss

（8）避免writebuffer過大引起的stall

（9）cache一緻性

4， SRAM讀寫流程

（1）Xm4片上資料記憶體的結構

（2）非對齊位址通路

（3）寫緩沖

（4）寫後讀操作

（5）片上記憶體仲裁器

（6）Data DMA

（7）位址對齊

4 常用算法優化技巧

1，一維卷積濾波

(1)一維卷積概念

(2)FIR濾波器優化

2， 二維卷積濾波

3， 中值濾波

(1) 傳統中值算法

(2) 雙調排序算法

(3) 分塊排序算法

4， 均值濾波

5， 矩陣相乘

(1) strassen算法

(2) coppersmith-winograd算法

(3) 基于記憶體的優化

6,數學函數優化

（1）泰勒公式展開

（2）牛頓疊代法

（3）除法運算

（4）開平方運算

（5）正弦與餘弦運算

（6）反正切計算

（7）多項式計算

5 算法定點化

1， 普通運算定點化

2， 高精度的浮點數定點化

6 基于CEVA-xm4平台的優化

1，CEVA-xm4核心介紹

2，仿真環境搭建

3，SIMD指令的使用

1，intrinsic 函數

2，xm4核心流水線機制

3，向量滑動視窗指令

4，向量滑動模闆指令

5， 向量插值指令

6， 向量（SAD）滑動視窗指令

7，Load and Store 單元

8，滑動load指令

9，間隔位址讀取指令

10，并行位址讀取指令

11，基于vs2013 的intrinsic 函數仿真

7 基于ARM-NEON指令的優化

1，寄存器

2，系統配置

3，Intrinsic函數

4，優化代碼

5，使用NEON指令實作光流比對算法

8，參考文獻

前言

伴随着AI、三維視覺技術的發展，算法複雜度也随之增加，同時産品小型化使各種複雜算法在嵌入式平台上實作成為必要步驟。算法的開發者通常會首先利用matlab、C++、python等語言在PC機平台調試完成功能後移植在嵌入式平台，比如arm處理器，DSP處理器等。這些嵌入式平台受到其主頻、架構、記憶體、指令集的限制，導緻算法往往性能低下，尤其在一些音視訊算法中，視訊和圖像相關的算法往往需要消耗大量記憶體和計算量，而音頻算法則要求計算非常精簡高效，對功耗要求也很低。而對于現在使用較為廣泛的AI算法，往往需要非常大的計算量，研究更優更高效的各種算子實作方法顯得尤其重要，AI算法通常需要大量的卷積操作和大量點乘操作，而這種操作往往具有極大的優化空間，是以就可以從多個角度來進行更深度的優化，以達到所在平台的最佳性能。是以本書從嵌入式平台硬體特性以及軟體特性方面多角度的表述了對于這些算法性能提升的一些技巧和方法。同時，書中也大量借鑒了多種嵌入式處理器的一些官方的優化建議的文檔，由此總結出算法在嵌入式平台的優化常用方法，包括代碼的高效實作，平台指令的靈活使用，記憶體方面的優化，如何更好利用DMA操作，算法自身流程、實作方式上的改進等。

當然，目前的嵌入式系統和PC機系統已經并沒有嚴格的界限，比如某些手持電腦也采用了多核的arm處理器，這種性能較好的arm處理器也用在大型的伺服器中，也可以采用一些工業使用的工控機也會使用x86架構處理器，是以本書的一些技術同樣适用于x86架構處理器。

本書對于算法優化的各種方法不限于某一個平台的DSP或者ARM，對于底層硬體原理以及編譯器來說，各種不同的處理器核心從本質上講大同小異，例如TI的C64系列DSP、CEVA-xm4、ADI的blackfin、ARM處理器等關于cache、DMA、SRAM的通路流程和原理并無較大差别。本書一些關于硬體方面優化介紹的内容也會結合多種處理器核心來講述。本書将以下幾個章節描述算法在嵌入式平台的優化及實作。

第一章主要講述嵌入式系統較為關鍵的幾個方面，包括算法的選擇，處理器選型，算法優化的一般流程等。

第二部分為高效的C語言，主要介紹一些常用的代碼編寫技巧，如何用更高效的方式實作，避免編譯器編譯更多的指令。

第三部分為記憶體方面的優化，cache的原理以及優化，DMA的使用等内容，盡管對于記憶體的方面的介紹，讨論了其通路讀取的流程對我們直接優化代碼似乎沒有直接幫助，但是他能幫助我們了解算法性能瓶頸，避免過多的讀寫記憶體引起的核心stall。

第四部分介紹了一些常用的基礎算法的優化方法，其中包括卷積濾波、中值濾波、矩陣的運算、數學函數優化等。

第五部分介紹了算法的定點化，針對一些不具有硬體浮點運算單元處理器的一些浮點數算法的定點化方法。

第六部分講述基于CEVA-xm4核心的軟體優化以及指令向量化優化的内容，本部分主要介紹了一些比較特殊的廣泛實用的一些向量指令，這些指令可以在卷積操作，視窗濾波方面達到事半功倍的效果。

在本書的編著過程中，身邊的同僚對我做了很大幫助，特别感謝我的同僚蒙敏榮對本書的一些數學函數優化以及定點化提供了大量資料和資料以及對CEVA平台資料的共享。同時也特别感謝我的同僚陳欣在數學函數優化中提供了理論支援。

最後非常感謝蒙敏榮、陳欣、張玉祺等人對本書的稽核檢查工作，為本書的完善提出了不少重要的建議。