矩阵的乘法。性能

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命令即可。