CPU無(wú)法達(dá)到peak performance的原因矩陣乘法的討論介紹理論基礎(chǔ)塊狀矩陣計(jì)算優(yōu)化技巧代價(jià)模型strength reduction內(nèi)聯(lián)函數(shù)inline f循環(huán)展開loop unrolling去掉下標(biāo)計(jì)算sub-exPRession eliminate查表look up table合并循環(huán)減少條件判斷

轉(zhuǎn)載請(qǐng)注明出處：http://blog.csdn.net/c602273091/article/details/54851077

上一節(jié)說到的是OpenMP的寫法，這一次主要是介紹代碼優(yōu)化。

CPU無(wú)法達(dá)到peak performance的原因

本來CPU的性能應(yīng)該如上圖所示的，但是實(shí)際使用的時(shí)候并沒有達(dá)到這個(gè)效果。

主要是因?yàn)椋?/p>

存儲(chǔ)器的層次設(shè)計(jì)。發(fā)生cache、TLB miss的時(shí)候，就需要等待很多個(gè)周期；

流水線、ILP等等并行設(shè)計(jì)有缺陷，使得吞吐量無(wú)法達(dá)到預(yù)期；

有的操作比如存儲(chǔ)操作看似不需要浪費(fèi)周期，其實(shí)數(shù)據(jù)傳輸?shù)鹊葧?huì)浪費(fèi)不少周期。

矩陣乘法的討論

介紹

原始的矩陣乘法就如上圖的實(shí)現(xiàn)。

但是使用加速之后效果怎么樣呢？ATLAS做加速的效果遠(yuǎn)遠(yuǎn)超過了三個(gè)循環(huán)的矩陣計(jì)算。

理論基礎(chǔ)

在這里需要介紹一些存儲(chǔ)器方面的知識(shí)。

矩陣存儲(chǔ)分為行優(yōu)先和列優(yōu)先的。行列優(yōu)先的不同使得每次存入cache的一行是列方向或者是行方向。

現(xiàn)在解構(gòu)一下取數(shù)據(jù)的關(guān)系：

對(duì)存儲(chǔ)數(shù)組A、B、C計(jì)算讀取次數(shù)。

塊狀矩陣計(jì)算

使用塊狀計(jì)算矩陣，如下圖。那么之前計(jì)算矩陣就改成了四個(gè)循環(huán)。

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

優(yōu)化技巧

代價(jià)模型

計(jì)算代價(jià)的部分如下圖：（左邊是具體每部分、右邊是具體例子）

計(jì)算一開始的代價(jià)：19n

去掉結(jié)構(gòu)體，去掉了索引這個(gè)步驟：6n

改變循環(huán)體內(nèi)部可以移出的操作：5n

使用循環(huán)展開：3.5n

strength reduction

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

內(nèi)聯(lián)函數(shù)（inline f）

減少函數(shù)調(diào)用，把簡(jiǎn)單函數(shù)改成內(nèi)聯(lián)函數(shù)。

循環(huán)展開（loop unrolling）

這里主要是涉及CPU在取內(nèi)存中數(shù)據(jù)到寄存器的時(shí)候，循環(huán)展開可以減少CPU周期。

去掉下標(biāo)計(jì)算（sub-expression eliminate）

有時(shí)候計(jì)算循環(huán)中的下表很浪費(fèi)CPU周期，一部分放到循環(huán)外就可以加快速度。

查表（look up table）

提前計(jì)算好要用到的一些數(shù)據(jù)，尤其減少循環(huán)多次計(jì)算的浪費(fèi)。這個(gè)做法和暴力破解很像。

合并循環(huán)

減少循環(huán)次數(shù)，可以減少不少計(jì)數(shù)器的操作。

減少條件判斷

減少循環(huán)中的條件判斷，如果你提前知道哪個(gè)是需要跳過的。