相关疑难解决方法(0)

我用C++写了两个矩阵乘法程序:常规MM (源)和Strassen的MM (源),它们都在大小为2 ^ kx 2 ^ k的矩形矩阵上运算(换句话说,是偶数大小的方阵).

结果很可怕.对于1024 x 1024矩阵,常规MM需要46.381 sec,而Strassen的MM需要1484.303 sec(25 minutes!!!!).

我试图让代码尽可能简单.在网上找到的其他Strassen的MM示例与我的代码没有太大的不同.Strassen代码的一个问题显而易见 - 我没有切换点,切换到常规MM.

我的Strassen的MM代码有哪些其他问题？

谢谢 !

直接链接到源
http://pastebin.com/HqHtFpq9
http://pastebin.com/USRQ5tuy

EDIT1.拳头,很多很棒的建议.感谢您抽出宝贵时间和分享知识.

我实施了更改(保留了我的所有代码),添加了截止点.具有截止512的2048x2048矩阵的MM已经给出了良好的结果.常规MM:191.49s Strassen的MM:112.179s显着改善.使用英特尔迅驰处理器,使用Visual Studio 2012,在史前联想X61 TabletPC上获得了结果.我将进行更多检查(以确保我得到正确的结果),并将发布结果.

我正在研究大型矩阵乘法并运行以下实验来形成基线测试:

1. 从std normal(0 mean,1 stddev)随机生成两个4096x4096矩阵X,Y.
2. Z = X*Y.
3. Z的Sum元素(以确保它们被访问)和输出.

这是天真的C++实现:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    constexpr size_t dim = 4096;

    float* x = new float[dim*dim];
    float* y = new float[dim*dim];
    float* z = new float[dim*dim];

    random_device rd;
    mt19937 gen(rd());
    normal_distribution<float> dist(0, 1);

    for (size_t i = 0; i < dim*dim; i++)
    {
        x[i] = dist(gen);
        y[i] = dist(gen);
    }

    for (size_t row = 0; row < dim; row++)
        for (size_t col = 0; col < …

可能重复:
为什么我的程序在完全循环8192个元素时会变慢？

我一直在修补一个程序,我用它来简单地总结一个二维数组的元素.一个错字导致了至少在我看来,一些非常奇怪的结果.

处理数组时,矩阵[SIZE] [SIZE]:

for(int row = 0; row < SIZE; ++row)
    for(int col = 0; col < SIZE; ++col)
        sum1 += matrix[row][col];

运行得非常快,但上面的行sum1 ...被修改:

sum2 += matrix[col][row]

正如我在没有意识到的情况下偶然做过的那样,我注意到我的运行时间显着增加.为什么是这样？

我正在研究多核机器上的并行算法的性能.我使用循环重新排序(ikj)技术进行了矩阵乘法的实验.

串行执行结果如下图所示.L1数据高速缓存命中循环次序ikj和kij所有大小的nXn矩阵接近100%(图1盒号1和2),你可以看到循环次序ikj的大小为2048和4096突然L2数据缓存命中减少%50(图2盒号1和2)也在L2指令缓存中命中同样如此.对于这2个大小的L1数据高速缓存命中的情况与其他大小(256,512,1024)大约是%100.在指令和数据缓存命中中,我找不到任何合理的斜率原因.任何人都可以告诉我如何找到原因？

你认为L2统一缓存对加剧问题有什么影响吗？但是仍然是什么导致这种减少算法和性能的特征应该我找到原因.

实验机是Intel e4500,带2Mb L2缓存,缓存行64,os是fedora 17 x64,带gcc 4.7 -o无编译器优化

简明扼要的完整问题？ my problem is that why sudden decrease of about 50% in both L2 data and instruction cache happens in only ikj & kij algorithm as it's boxed and numbered 1 & 2 in images, but not in other loop variation？

                                   *Image 1*

                                    *Image 2*

                                    *Image 3*

                                   *Image 4*

                                   *Image 5*

尽管存在上述问题,但ikj&kij算法的时序没有增加.但也比其他人快.

ikj和kij算法是循环重排序技术的两种变体/

kij算法

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

ikj算法

For (i=0;i<n;i++)
     For(k=0;k<n;k++){
      r=A[i][k];
      For (j=0;j<n;j++) …

我正在调查缓存未命中如何影响计算速度.我知道有很多算法可以更好地将两个矩阵相乘(即使下面两个循环的简单交换也会有帮助),但请考虑以下代码:

float a[N][N];
float b[N][N];
float c[N][N];
// ...
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            float sum = 0.0;
            for (int k = 0; k < N; k++) {
                sum = sum + a[i][k] * b[k][j];
            }
            c[i][j] = sum;
        }
    }
}

我已经重新编译了这段代码,用于N运行它的许多值和测量时间.我预计会发现周围的时间突然增加,此时N=1250矩阵c不再适合缓存(c当时的大小1250*1250*sizeof(float)=6250000,或大约6MB,这是我的L3缓存的大小).

实际上,总体趋势是在此之后,平均时间与之前推断的时间相比大致为三倍.但价值N%8似乎对结果产生了巨大影响.例如:

1601 - 11.237548
1602 - 7.679103 …

这是记忆,所以我可能会误用几句话,但意思应该是可以理解的

我现在在大学,做BIT主修编程 - 我们开始使用C++,当我们开始使用数组时,我们的C++老师(一个有着奇怪想法和编程规则的老师,比如没有任何评论允许)告诉我们我们应该使我们的数组大小为4的倍数,以提高效率:

char exampleArrayChar[ 4 ]; //Allowed
float exampleArrayChar[ 6 ]; //NOT Allowed
int exampleArrayChar[ 8 ]; //Allowed

他说这背后的原因是因为计算机进行内存分配的方式.

计算机以4个字节为一组分配每个数组元素的内存地址/位置 - 因此在2个内存组中完成了8个元素的数组.

所以问题是,如果你创建了一个大小为6的数组,它会分配2组4,但是然后将这些字节中的2个(在8个中)标记为无效/无效,使它们无法使用直到整个数组从记忆.

虽然这对我来说听起来似乎是合理的其他计算机数学(例如1gb = 1024mb而不是1000)我有兴趣知道:

• 通过这样做,这是多么真实,以及获得的收益(如果有的话)
• 这只是C++吗？(我会假设没有,但仍然值得问)
• 关于这一点的更多信息 - 例如,为什么4？计算机数学通常不是二进制数,因此2是？

在网上环顾四周,我一直无法找到任何主要用途或相关性.

我在C中构造函数的偏导数.该过程主要由大量小循环组成.每个循环负责填充矩阵的列.因为矩阵的大小很大,所以应该有效地编写代码.我对实施有很多计划,我不想深入了解细节.

我知道智能编译器会尝试自动利用缓存.但我想了解更多使用缓存和编写高效代码和高效循环的细节.如果提供一些资源或网站,我将不胜感激,因此我可以更多地了解如何在减少内存访问时间和利用优势方面编写有效代码.

我知道我的请求看起来很草率,但我不是电脑人.我做了一些研究但没有成功.所以,任何帮助表示赞赏.

谢谢