CPU無法達到peak performance的原因矩陣乘法的討論介紹理論基礎塊狀矩陣計算優化技巧代價模型strength reduction內聯函數inline f循環展開loop unrolling去掉下標計算sub-exPRession eliminate查表look up table合并循環減少條件判斷

轉載請注明出處：http://blog.csdn.net/c602273091/article/details/54851077

上一節說到的是OpenMP的寫法，這一次主要是介紹代碼優化。

CPU無法達到peak performance的原因

本來CPU的性能應該如上圖所示的，但是實際使用的時候并沒有達到這個效果。

主要是因為：

存儲器的層次設計。發生cache、TLB miss的時候，就需要等待很多個周期；

流水線、ILP等等并行設計有缺陷，使得吞吐量無法達到預期；

有的操作比如存儲操作看似不需要浪費周期，其實數據傳輸等等會浪費不少周期。

矩陣乘法的討論

介紹

原始的矩陣乘法就如上圖的實現。

但是使用加速之后效果怎么樣呢？ATLAS做加速的效果遠遠超過了三個循環的矩陣計算。

理論基礎

在這里需要介紹一些存儲器方面的知識。

矩陣存儲分為行優先和列優先的。行列優先的不同使得每次存入cache的一行是列方向或者是行方向。

現在解構一下取數據的關系：

對存儲數組A、B、C計算讀取次數。

塊狀矩陣計算

使用塊狀計算矩陣，如下圖。那么之前計算矩陣就改成了四個循環。

想對這塊更了解，可以看我之前寫的18-600里cache的介紹。 想直觀看這個算法，可以看：

優化技巧

代價模型

計算代價的部分如下圖：（左邊是具體每部分、右邊是具體例子）

計算一開始的代價：19n

去掉結構體，去掉了索引這個步驟：6n

改變循環體內部可以移出的操作：5n

使用循環展開：3.5n

strength reduction

減少需要浪費很多資源的操作，比如去掉除法、log等等或者替換成別的操作。

內聯函數（inline f）

減少函數調用，把簡單函數改成內聯函數。

循環展開（loop unrolling）

這里主要是涉及CPU在取內存中數據到寄存器的時候，循環展開可以減少CPU周期。

去掉下標計算（sub-expression eliminate）

有時候計算循環中的下表很浪費CPU周期，一部分放到循環外就可以加快速度。

查表（look up table）

提前計算好要用到的一些數據，尤其減少循環多次計算的浪費。這個做法和暴力破解很像。

合并循環

減少循環次數，可以減少不少計數器的操作。

減少條件判斷

減少循環中的條件判斷，如果你提前知道哪個是需要跳過的。