以下是相关程序的摘录.矩阵img[][]的大小为SIZE×SIZE,并在以下位置初始化:

img[j][i] = 2 * j + i

然后,你创建一个矩阵res[][],这里的每个字段都是img矩阵中它周围9个字段的平均值.为简单起见,边框保留为0.

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

这就是该计划的全部内容.为了完整起见,以下是之前的内容.没有代码.如您所见,它只是初始化.

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[j][i] = (2*j+i)%8196;

基本上,当SIZE是2048的倍数时,此程序很慢,例如执行时间:

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

编译器是GCC.据我所知,这是因为内存管理,但我对这个主题并不太了解,这就是我在这里问的原因.

另外如何解决这个问题会很好,但如果有人能够解释这些执行时间,我已经足够开心了.

我已经知道malloc/free了,但问题不在于使用的内存量,它只是执行时间,所以我不知道这会有多大帮助.

我有一个矩阵(相对较大),我需要转置.例如假设我的矩阵是

a b c d e f
g h i j k l
m n o p q r 

我希望结果如下:

a g m
b h n
c I o
d j p
e k q
f l r

最快的方法是什么？

我有一个矩阵乘法代码,如下所示:

for(i = 0; i < dimension; i++)
    for(j = 0; j < dimension; j++)
        for(k = 0; k < dimension; k++)
            C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j];

这里,矩阵的大小由表示dimension.现在,如果矩阵的大小是2000,运行这段代码需要147秒,而如果矩阵的大小是2048,则需要447秒.所以虽然差别没有.乘法是(2048*2048*2048)/(2000*2000*2000)= 1.073,时间上的差异是447/147 = 3.有人可以解释为什么会发生这种情况吗？我预计它会线性扩展,但这不会发生.我不是要尝试制作最快的矩阵乘法代码,只是试图理解它为什么会发生.

规格:AMD Opteron双核节点(2.2GHz),2G RAM,gcc v 4.5.0

程序编译为 gcc -O3 simple.c

我也在英特尔的icc编译器上运行了这个,并看到了类似的结果.

编辑:

正如评论/答案中所建议的那样,我运行了维度= 2060的代码,需要145秒.

继承完整的计划:

#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

/* change dimension size as needed */
const int dimension = 2048;
struct timeval tv; 

double timestamp()
{
        double t;
        gettimeofday(&tv, NULL);
        t = tv.tv_sec + (tv.tv_usec/1000000.0); …

我测试了memcpy()在i*4KB时注意速度急剧下降的速度.结果如下:Y轴是速度(MB /秒),X轴是缓冲区的大小memcpy(),从1KB增加到2MB.子图2和子图3详述了1KB-150KB和1KB-32KB的部分.

环境:

CPU:Intel(R)Xeon(R)CPU E5620 @ 2.40GHz

操作系统:2.6.35-22-通用#33-Ubuntu

GCC编译器标志:-O3 -msse4 -DINTEL_SSE4 -Wall -std = c99

我想它必须与缓存相关,但我无法从以下缓存不友好的情况中找到原因:

• 为什么我的程序在完全循环8192个元素时会变慢？

• 为什么转换512x512的矩阵要比转换513x513的矩阵慢得多？

由于这两种情况的性能下降是由不友好的循环引起的,这些循环将分散的字节读入高速缓存,浪费了高速缓存行的其余空间.

这是我的代码:

void memcpy_speed(unsigned long buf_size, unsigned long iters){
    struct timeval start,  end;
    unsigned char * pbuff_1;
    unsigned char * pbuff_2;

    pbuff_1 = malloc(buf_size);
    pbuff_2 = malloc(buf_size);

    gettimeofday(&start, NULL);
    for(int i = 0; i < iters; ++i){
        memcpy(pbuff_2, pbuff_1, buf_size);
    }   
    gettimeofday(&end, NULL);
    printf("%5.3f\n", ((buf_size*iters)/(1.024*1.024))/((end.tv_sec - \
    start.tv_sec)*1000*1000+(end.tv_usec - start.tv_usec)));
    free(pbuff_1);
    free(pbuff_2);
}

UPDATE

考虑到来自@ usr,@ ChrisW和@Leeor的建议,我更准确地重新测试了测试,下面的图表显示了结果.缓冲区大小从26KB到38KB,我每隔64B测试一次(26KB,26KB + …

我正在经历循环,发现访问循环有显着差异.我无法理解在两种情况下造成这种差异的原因是什么？

第一个例子:

执行时间处理时间; 8秒

for (int kk = 0; kk < 1000; kk++)
{
    sum = 0;
    for (int i = 0; i < 1024; i++)
        for (int j = 0; j < 1024; j++)
        {
            sum += matrix[i][j];
        }
}

第二个例子:

执行时间:23秒

for (int kk = 0; kk < 1000; kk++)
{
    sum = 0;
    for (int i = 0; i < 1024; i++)
        for (int j = 0; j < 1024; j++)
        {
            sum += matrix[j][i];
        }
} …

我试图找到我最近在stackoverflow上发布的程序的效率.

如何有效地删除给定另一个向量的向量中的元素

为了比较我的代码与其他答案的效率,我正在使用chrono对象.

这是检查运行时效率的正确方法吗？

如果没有,那么请用一个例子来建议一种方法.

Coliru代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <ctime>
using namespace std;

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{
    if(!vDestination.empty() && !vSource.empty())
    {
        for(auto i: vSource) {
            vDestination.erase(std::remove(vDestination.begin(), vDestination.end(), i), vDestination.end());
        }
    }
}

int main() {
    vector<int> v1={1,2,3};
    vector<int> v2={4,5,6};
    vector<int> v3={1,2,3,4,5,6,7,8,9};
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
    remove_elements(v3,v1);
    remove_elements(v3,v2);
    std::chrono::steady_clock::time_point end= std::chrono::steady_clock::now();
    std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() <<std::endl;
    for(auto i:v3)
        cout << i << endl;
    return …

我试图更多地了解 CPU 缓存如何影响性能。作为一个简单的测试，我将矩阵第一列的值与不同数量的总列数相加。

// compiled with: gcc -Wall -Wextra -Ofast -march=native cache.c
// tested with: for n in {1..100}; do ./a.out $n; done | tee out.csv
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

double sum_column(uint64_t ni, uint64_t nj, double const data[ni][nj])
{
    double sum = 0.0;
    for (uint64_t i = 0; i < ni; ++i) {
        sum += data[i][0];
    }
    return sum;
}

int compare(void const* _a, void const* _b)
{
    double const a = *((double*)_a);
    double …

我用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上获得了结果.我将进行更多检查(以确保我得到正确的结果),并将发布结果.

在Agner Fog的手册" C++中的优化软件 "第9.10节"大数据结构中的Cahce争论"中,他描述了当矩阵宽度等于称为临界步幅的情况时转置矩阵的问题.在他的测试中,当宽度等于临界步幅时,L1中矩阵的成本增加40%. 如果矩阵更大并且仅适用于L2,则成本为600%! 这在表9.1中的文字中得到了很好的总结.这与在为什么将512x512的矩阵转置比转置513x513的矩阵要慢得多一样是必不可少的 ？

后来他写道:

这种效果对于二级高速缓存争用而言比一级高速缓存争用强得多的原因是二级高速缓存不能一次预取多行.

所以我的问题与预取数据有关.

根据他的评论,我推断L1可以一次预取多个缓存行. 预取了多少？

据我所知,尝试编写代码来预取数据(例如使用_mm_prefetch)很少有用.我读过的唯一例子是Prefetching Examples？它只有O(10%)的改进(在某些机器上).Agner后来解释了这个:

原因是现代处理器由于无序执行和高级预测机制而自动预取数据.现代微处理器能够自动预取包含具有不同步幅的多个流的常规访问模式的数据.因此,如果可以使用固定步幅以常规模式排列数据访问,则不必显式预取数据.

那么CPU如何决定预取哪些数据,以及有哪些方法可以帮助CPU为预取做出更好的选择(例如"具有固定步幅的常规模式")？

编辑:根据Leeor的评论,让我添加我的问题并使其更有趣. 与L1相比,为什么关键步幅对L2的影响要大得多？

编辑:我试图使用代码重现Agner Fog的表格为什么转换512x512的矩阵要比转置513x513的矩阵慢得多？ 我在Xeon E5 1620(Ivy Bridge)上以MSVC2013 64位版本模式运行它,它具有L1 32KB 8路,L2 256 KB 8路和L3 10MB 20路.L1的最大矩阵大小约为90x90,L3为256x256,L3为1619.

Matrix Size  Average Time
64x64        0.004251 0.004472 0.004412 (three times)
65x65        0.004422 0.004442 0.004632 (three times)
128x128      0.0409
129x129      0.0169
256x256      0.219   //max L2 matrix size
257x257      0.0692
512x512      2.701
513x513      0.649
1024x1024    12.8
1025x1025    10.1

我没有看到L1中的任何性能损失,但是L2明显具有关键的步幅问题,可能是L3.我不确定为什么L1没有出现问题.有可能还有一些其他的背景源(开销)占据了L1时代的主导地位.

以下示例代码生成一个size的矩阵N,并将其转换SAMPLES次数.当N = 512转置操作的平均执行时间是2144 ?s(coliru链接)时.乍一看,没有什么特别的,对吗？...

好吧,这是结果

• N = 513 → 1451 ?s
• N = 519 → 600 ?s
• N = 530 → 486 ?s
• N = 540→ 492 ?s(终于!理论开始工作:).

那么为什么在实践中这些简单的计算与理论如此不同呢？此行为是否与CPU缓存一致性或缓存未命中有关？如果是这样请解释.

#include <algorithm>
#include <iostream>
#include <chrono>

constexpr int N       = 512; // Why is 512 specifically slower (as of 2016)
constexpr int SAMPLES = 1000;
using us = std::chrono::microseconds;

int A[N][N];

void transpose()
{
    for ( int i = …