矩阵的乘法。性能
我有一个方案矩阵乘法。另外,我认为该程序的性能按公式(操作次数)/(运行时间)计算。为什么矩阵的增长维度会降低性能?谢谢。矩阵的乘法。性能
#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;
}
我想你是问为什么平均每秒浮点运算次数(FLOPS)随着矩阵大小的增加而下降。
答案是:缓存。您正在使用的矩阵乘法的“幼稚”方法对高速缓存性能而言非常糟糕;随着矩阵的增长,您将会增加缓存未命中的数量。
如果您决定自己写(而不是使用现存的线性代数库),您应该研究“阻塞”,也称为“循环平铺”。见例如http://en.wikipedia.org/wiki/Loop_tiling。基本思想是将操作分解为与缓存大小相对应的较小块。
+1用于缓存问题。 – ALOToverflow 2012-03-20 12:40:29
本文将讨论CPU缓存对矩阵乘法的影响。本文使用矩阵乘法作为示例,并展示了基本算法的一些修改以获得一些速度改进。 O(N^3)http://lwn.net/Articles/255364/ – JoeD 2012-03-20 16:17:58
由于矩阵规模的增大则有更多的工作(浮点Calcs(计算))为CPU做的,即线性增加的时间(以元素数目号码 - 未行或COLS )。
您还有更多的内存可以遍历,这意味着您在遍历内存时获得更多的缓存未命中,以便每条指令的周期数增加。
最后,你应该看看像ublas助推器这样的图书馆,当你需要它的时候,你会这么做。
http://www.boost.org/doc/libs/1_49_0/libs/numeric/ublas/doc/index.htm
编辑:你也迭代虽然阵3次,任何增加被放大。
我认为这更多的是缓存一致性问题 - 您选择用于存储的格式不是连续的,有非恒定的跨度和两个间接层次。选择Fortran/BLAS兼容布局,然后链接工业强度的BLAS/GEMM实现(ACML,ATLAS),您应该看到相反的结果:较大的问题具有较高的持续触发率。
乘法矩阵是一个深入研究的问题,并且有很好的库选项。
我不明白你的意思:
- 如果
n
越大,那么你有你的最后一个循环(使用i
,j
和k
),具有n * n * n
复杂性。 - 但是你以前的循环(与
i
和j
)也加n*n
复杂那么qty_of_operation
是不是你认为什么。然后你的表现就会下降。另外,使用更大的内存块可能会有一些处罚。另外,你会得到“真实”的时间,而不是“cpu”时间,这是不同的,特别是当有多个进程正在运行时......在Unix中,在启动代码之前,只需使用time
命令即可。
我不明白你的问题。你问为什么随着矩阵大小的增加运行时间增加了? – 2012-03-20 12:27:53
不,我的意思是,为什么表现下降。 (in flops) – 2012-03-20 12:30:22
为什么标记为C++?目前有C代码和一个“cout”。按照111111的建议查看Boost.uBLAS。 – 2012-03-20 12:33:26