矩陣的乘法。性能

Question

我有一個方案矩陣乘法。另外，我認爲該程序的性能按公式（操作次數）/（運行時間）計算。爲什麼矩陣的增長維度會降低性能？謝謝。

#include <stdio.h> 
#include <stdlib.h> 
#include <iostream> 
#include <sys/time.h> 
using namespace std; 

double getsec(){ 
    struct timeval t; 
    gettimeofday(&t,NULL); 
    return t.tv_sec+t.tv_usec*0.000001; 
} 

int main(int argc, char* argv[]) 
{ 
double begintime=getsec(); 

int n; 
if(argc==2)n=atoi(argv[1]); 
else n=3; 

int**a=new int*[n]; 
double**b=new double*[n]; 
double**c=new double*[n]; 
for (int i=0;i<n;i++){ 
    a[i]=new int [n]; 
    b[i]=new double [n]; 
    c[i]=new double [n]; 
} 

for (int i=0;i<n;i++) 
    for(int j=0;j<n;j++){ 
     a[i][j]=i+1; 
     b[i][j]=1/(j+1.); 
     c[i][j]=0; 
    } 

for (int i=0;i<n;i++) 
    for(int j=0;j<n;j++) 
     for(int k=0;k<n;k++) 
     c[i][j]+=a[i][k]*b[k][j]; 

double qty_of_operations = (double)2*n*n*n; 

cout<<n<<" c11="<<c[0][0]<<" c1n="<<c[0][n-1]<<" cn1="<<c[n-1][0]<<" cnn="<<c[n-1][n-1]<<" "<<qty_of_operations/(getsec()-begintime)<<endl; 
return 0; 

}

Answer 1

我想你是問爲什麼平均每秒浮點運算次數（FLOPS）隨着矩陣大小的增加而下降。

答案是：緩存。您正在使用的矩陣乘法的「幼稚」方法對高速緩存性能而言非常糟糕;隨着矩陣的增長，您將會增加緩存未命中的數量。

如果您決定自己寫（而不是使用現存的線性代數庫），您應該研究「阻塞」，也稱爲「循環平鋪」。見例如http://en.wikipedia.org/wiki/Loop_tiling。基本思想是將操作分解爲與緩存大小相對應的較小塊。

Answer 2

由於矩陣規模的增大則有更多的工作（浮點Calcs（計算））爲CPU做的，即線性增加的時間（以元素數目號碼 - 未行或COLS ）。

您還有更多的內存可以遍歷，這意味着您在遍歷內存時獲得更多的緩存未命中，以便每條指令的週期數增加。

最後，你應該看看像ublas助推器這樣的圖書館，當你需要它的時候，你會這麼做。

http://www.boost.org/doc/libs/1_49_0/libs/numeric/ublas/doc/index.htm

編輯：你也迭代雖然陣3次，任何增加被放大。

Answer 3

我認爲這更多的是緩存一致性問題 - 您選擇用於存儲的格式不是連續的，有非恆定的跨度和兩個間接層次。選擇Fortran/BLAS兼容佈局，然後鏈接工業強度的BLAS/GEMM實現（ACML，ATLAS），您應該看到相反的結果：較大的問題具有較高的持續觸發率。

乘法矩陣是一個深入研究的問題，並且有很好的庫選項。

Answer 4

我不明白你的意思：

• 如果n越大，那麼你有你的最後一個循環（使用i，j和k），具有n * n * n複雜性。
• 但是你以前的循環（與i和j）也加n*n

複雜那麼qty_of_operation是不是你認爲什麼。然後你的表現就會下降。另外，使用更大的內存塊可能會有一些處罰。另外，你會得到「真實」的時間，而不是「cpu」時間，這是不同的，特別是當有多個進程正在運行時......在Unix中，在啓動代碼之前，只需使用time命令即可。