快捷導(dǎo)航

C中實現(xiàn)矩陣乘法的一種高效的方法

更新時間：2013年05月04日 17:14:03 作者：

本篇文章介紹了，在C中實現(xiàn)矩陣乘法的一種高效的方法。需要的朋友參考下

如何計算矩陣乘法，這個大家都知道。通常情況下，我們都是用以下代碼實現(xiàn)的：

for(i=0;i<n;++i)
    for(j=0;j<n;++j){
        sum=0;
        for(k=0;k<n;++k)
            sum+=A[i][k]*B[k][j];
        C[i][j]+=sum;
}

但是考慮了高速緩存的問題后，其實有一種更好的實現(xiàn)方式：

復(fù)制代碼代碼如下:

for(i=0;i<n;++i)
    for(k=0;k<n;++k){
        r=A[i][k];
        for(j=0;j<n;++j)
            C[i][j]+=r*B[k][j];
}

細(xì)看一番就會發(fā)現(xiàn)這兩種實現(xiàn)語義是等價的，但是后者的實際運行效率卻比前者高。

那為什么會如此呢？

那是因為CPU讀數(shù)據(jù)時，并不是直接訪問內(nèi)存，而是先查看緩存中是否有數(shù)據(jù)，有的話直接從緩存讀取。而從緩存讀取數(shù)據(jù)比從內(nèi)存讀數(shù)據(jù)快很多。

當(dāng)數(shù)據(jù)不在緩存中時，CPU會將包含數(shù)據(jù)在內(nèi)的一個數(shù)據(jù)塊讀到緩存，如果程序具有良好空間局部性，那么第一次cache miss后，之后的幾次數(shù)據(jù)訪問就可以直接在緩存中完成。除了空間局部性（程序傾向于引用與當(dāng)前數(shù)據(jù)鄰近的數(shù)據(jù)）之外，還有時間局部性（程序傾向于引用最近被引用過的數(shù)據(jù)）。

回到矩陣乘法。（我們只考慮內(nèi)循環(huán)）

前者對矩陣A，有良好的空間局部性，假設(shè)一次能緩存四個元素，則每次迭代對于A只有0.25次miss，但是對于B，則不然，因此B是按列訪問的，每次訪問都會miss，因此每次迭代總的miss數(shù)是1.25。

后者對于矩陣C和矩陣B都有良好的局部性，每次迭代都只有0.25詞miss，因此總的miss數(shù)是0.5。后者每次迭代多了一次存儲（對C[i][j]寫入），但是即便如此，后者的運行效率也比前者高。

總而言之，要想程序跑得快，就要在程序中多利用局部性，讓緩存hold住你的數(shù)據(jù)，減少訪存次數(shù)。要知道CPU可以在3個時鐘周期內(nèi)訪問到L1 cache，10個時鐘周期左右的時間訪問到L2 cache。訪問內(nèi)存卻要上百個時鐘周期，孰快孰慢，很清楚了吧？

您可能感興趣的文章: