相关疑难解决方法(0)

我想知道Ulrich Drepper 从2007年开始对每个程序员应该知道的内容有多少仍然有效.另外,我找不到比1.0更新的版本或勘误表.

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

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); …

编辑:为了参考目的(如果有人偶然发现这个问题),伊戈尔奥斯特罗夫斯基写了一篇关于缓存未命中的精彩帖子.它讨论了几个不同的问题并显示了示例数字. 结束编辑

我做了一些测试<long story goes here>,我想知道性能差异是否是由于内存缓存未命中.以下代码演示了该问题,并将其归结为关键时序部分.以下代码有几个循环,以随机顺序访问内存,然后按升序地址顺序访问内存.

我在XP机器(使用VS2005:cl/O2编译)和Linux机器(gcc -Os)上运行它.两者产生了相似的时间 这些时间以毫秒为单位.我相信所有循环都在运行并且未被优化(否则它将"立即"运行).

*** Testing 20000 nodes
Total Ordered Time: 888.822899
Total Random Time: 2155.846268

这些数字有意义吗？差异主要是由于L1缓存未命中还是还有其他事情发生？存在20,000 ^ 2个存储器访问,并且如果每个都是高速缓存未命中,则每个未命中约3.2纳秒.我测试的XP(P4)机器是3.2GHz,我怀疑(但不知道)有一个32KB的L1缓存和512KB的L2.有20,000个条目(80KB),我假设没有大量的L2未命中.所以这就是(3.2*10^9 cycles/second) * 3.2*10^-9 seconds/miss) = 10.1 cycles/miss.这对我来说似乎很高兴.也许不是,或者我的数学很糟糕.我尝试用VTune测量缓存未命中,但我得到了BSOD.现在我无法连接到许可证服务器(grrrr).

typedef struct stItem
{
   long     lData;
   //char     acPad[20];
} LIST_NODE;



#if defined( WIN32 )
void StartTimer( LONGLONG *pt1 )
{
   QueryPerformanceCounter( (LARGE_INTEGER*)pt1 );
}

void StopTimer( LONGLONG t1, double *pdMS )
{
   LONGLONG t2, llFreq;

   QueryPerformanceCounter( (LARGE_INTEGER*)&t2 );
   QueryPerformanceFrequency( (LARGE_INTEGER*)&llFreq );
   *pdMS …

我有以下两个文件: -

single.cpp: -

#include <iostream>
#include <stdlib.h>

using namespace std;

unsigned long a=0;

class A {
  public:
    virtual int f() __attribute__ ((noinline)) { return a; } 
};

class B : public A {                                                                              
  public:                                                                                                                                                                        
    virtual int f() __attribute__ ((noinline)) { return a; }                                      
    void g() __attribute__ ((noinline)) { return; }                                               
};                                                                                                

int main() {                                                                                      
  cin>>a;                                                                                         
  A* obj;                                                                                         
  if (a>3)                                                                                        
    obj = new B();
  else
    obj = new A();                                                                                

  unsigned long result=0;                                                                         

  for (int i=0; i<65535; i++) {                                                                   
    for (int …

作为一项学校作业,我需要找到一种方法来获取L1数据缓存行大小,而无需读取配置文件或使用api调用.假设使用内存访问读/写时序来分析和获取此信息.那我该怎么做呢？

在完成另一部分任务的不完整尝试中,为了找到缓存的级别和大小,我有:

for (i = 0; i < steps; i++) {
    arr[(i * 4) & lengthMod]++;
}

我想也许我只需要改变第2行,(i * 4)部分？所以一旦我超过缓存行大小,我可能需要更换它,这需要一些时间？但它是如此直截了当？所需的块可能已经存在于内存中？或者perpahs我仍然可以依靠这样一个事实:如果我有足够大的steps,它仍然可以非常准确地运作？

UPDATE

下面是对GitHub的尝试 ...主要部分如下

// repeatedly access/modify data, varying the STRIDE
for (int s = 4; s <= MAX_STRIDE/sizeof(int); s*=2) {
    start = wall_clock_time();
    for (unsigned int k = 0; k < REPS; k++) {
        data[(k * s) & lengthMod]++;
    }
    end = wall_clock_time();
    timeTaken = ((float)(end - start))/1000000000;
    printf("%d, %1.2f \n", s * sizeof(int), timeTaken); …

我最近一直关注内存分配,对基础知识我有点困惑.我无法绕过简单的东西.分配内存意味着什么？怎么了？我很感激这些问题的答案:

1. 正在分配的"记忆"在哪里？
   
2. 这个"记忆"是什么？阵列中的空间？或者是其他东西？
   
3. 当这个"记忆"被分配时会发生什么？
   
4. 当内存被解除分配时会发生什么？
   

5. 如果有人可以回答malloc在这些C++行中所做的事情,它也会对我有所帮助:

   char* x; 
   x = (char*) malloc (8);
   

   Run Code Online (Sandbox Code Playgroud)

谢谢.

(出于测试目的)我编写了一个简单的方法来计算nxn矩阵的转置

void transpose(const size_t _n, double* _A) {
    for(uint i=0; i < _n; ++i) {
        for(uint j=i+1; j < _n; ++j) {
            double tmp  = _A[i*_n+j];
            _A[i*_n+j] = _A[j*_n+i];
            _A[j*_n+i] = tmp;
        }
    }
}

当使用优化级别O3或Ofast时,我期望编译器展开一些循环,这将导致更高的性能,尤其是当矩阵大小是2的倍数(即,每次迭代可以执行双循环体)或类似时.相反,我测量的恰恰相反.2的权力实际上表明执行时间显着增加.

这些尖峰也是64的固定间隔,间隔128更明显,依此类推.每个尖峰延伸到相邻的矩阵大小,如下表所示

size n  time(us)
1020    2649
1021    2815
1022    3100
1023    5428
1024    15791
1025    6778
1026    3106
1027    2847
1028    2660
1029    3038
1030    2613

我使用gcc版本4.8.2编译但是同样的事情发生在clang 3.5上,所以这可能是一些通用的东西？

所以我的问题基本上是:为什么执行时间周期性增加？是否有一些通用的东西与任何优化选项一起出现(就像clang和gcc一样)？如果是这样的优化选项导致了这个？

这怎么可能如此重要,即使O0版本的程序在512的倍数时优于03版本？

编辑:注意此(对数)图中峰值的大小.转换具有优化的1024x1024矩阵实际上花费的时间与在没有优化的情况下转置1300x1300矩阵一样多.如果这是一个缓存故障/页面错误问题,那么有人需要向我解释为什么内存布局对于程序的优化版本是如此显着不同,它失败的功能为2,只是为了恢复高性能稍大的矩阵.缓存故障是否应该创建更多类似步骤的模式？为什么执行时间会再次下降？(为什么优化会创建以前不存在的缓存错误？)

编辑:以下应该是gcc生成的汇编代码

没有优化(O0):

_Z9transposemRPd:
.LFB0:
    .cfi_startproc
    push    rbp …

看起来预取用法的一般逻辑是,如果代码忙于处理直到预取指令完成其操作,则可以添加预取.但是,似乎如果使用过多的预取指令,那么它会影响系统的性能.我发现我们需要先获得没有预取指令的工作代码.稍后我们需要在各种代码位置中进行预取指令的各种组合,并进行分析以确定由于预取而实际可能改进的代码位置.有没有更好的方法来确定应该使用预取指令的确切位置？

如果我有一个拥有3D世界的游戏,并且世界相当大,那么需要分成几个块,是否有一个主要的,如果有的话,有128个字节块的性能优势,比如150个字节的块？显然,块中的对象仍然是整数个字节.

即chunks[128][128][128]比chunks[150][150][150]或更快chunks[112][112][112]？之后是否存在其他副作用,例如过多的RAM浪费？是否还有其他因素需要考虑？

我只是看到将所有内容存储在变量和大小为2的幂的数组中是一种惯例,但我不确定它是否有任何优点,如果使用更多人类数字如100或150更好.

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