6

我正在从下面的函数中寻找最快的优化，因为它似乎是我的应用程序的瓶颈。请记住，以下函数已被内联声明。

定义：P = 10 和 N = 240

void autocorrelation( int32_t *data , float *r){
    for ( int m=0 ; m < P+1 ; m++)
    {
        register float temp = 0;
        for ( int n=0 ; n<N-m ; n++)
        {
            temp += (float)(data[n])*(float)(data[n+m]);
        }
        r[m] = temp;
    }
}

任何帮助表示赞赏。

谢谢！

编辑：

部件：

temp += (float)(data[n])*(float)(data[n+m]);
800063A8  lddsp R8, SP[0x0]      
800063AA  add R1, R2, R8<<0      
800063AE  ld.w R12, R1[R7<<0]        
800063B2  mcall 0x80006f58       
800063B6  mov R4, R12        
800063B8  ld.w R12, R2[R7<<0]        
800063BC  mcall 0x80006f58       
800063C0  mov R11, R12       
800063C2  mov R12, R4        
800063C4  mcall 0x80006f5c       
800063C8  mov R11, R12       
800063CA  mov R12, R5        
800063CC  mcall 0x80006f60       
800063D0  mov R5, R12        
for ( int n=0 ; n<N-m ; n++)
800063D2  sub R6, -1         
800063D4  sub R7, -4         
800063D6  cp.w R6, R3        
800063D8  brne 0x800063ae        
r[m] = temp;
800063DA  ld.w R10, PC[2954]         
800063DE  lddsp R9, SP[0x0]      
800063E0  st.w R10[R9<<0], R5        
800063E4  sub R0, 1      
800063E6  sub R9, -4         
800063E8  stdsp SP[0x0], R9      
for ( int m=0 ; m < P+1 ; m++)
800063EA  cp.w R0, 229       
800063EE  breq 0x800063fc        
800063F0  mov R3, R0         
for ( int n=0 ; n<N-m ; n++)
800063F2  cp.w R0, 0         
800063F4  brgt 0x800063a2        
800063F8  mov R5, 0      
800063FA  rjmp 0x800063da

///////////////////////////////////////// //////////////////////////

所以我将代码更改为：

void autocorrelation( float *data , float *r){
    for ( int m=0 ; m < P+1 ; m++)
    {
        register float temp = 0;
        for ( int n=0 ; n<N-m ; n++)
        {
            temp += data[n]*data[n+m];
        }
        r[m] = temp;
    }
}

并将时间缩短三分之一（每个滴答声是 1/16000Hz） - 最初 - 现在 108 个滴答声 - 70 个滴答声

新组件：

temp += data[n]*data[n+m];
800063C2  add R2, R3, R0<<0      
800063C6  ld.w R11, R3[R7<<0]        
800063CA  ld.w R12, R2[R7<<0]        
800063CE  mcall 0x80006f68       
800063D2  mov R11, R12       
800063D4  mov R12, R5        
800063D6  mcall 0x80006f6c       
800063DA  mov R5, R12        
for ( int n=0 ; n<N-m ; n++)
800063DC  sub R6, -1         
800063DE  sub R7, -4         
800063E0  cp.w R6, R4        
800063E2  brne 0x800063c6        
r[m] = temp;
800063E4  ld.w R9, PC[2960]      
800063E8  st.w R9[R0<<0], R5         
800063EC  sub R1, 1      
800063EE  sub R0, -4         
for ( int m=0 ; m < P+1 ; m++)
800063F0  cp.w R1, 229       
800063F4  breq 0x80006402        
800063F6  mov R4, R1         
for ( int n=0 ; n<N-m ; n++)
800063F8  cp.w R1, 0         
800063FA  brgt 0x800063bc        
800063FE  mov R5, 0      
80006400  rjmp 0x800063e4

///////////////////////////////////////// //// FINAL 最终解决方案：（再次更改）

我将标记的解决方案结合起来，将循环与我编写的应用程序展开并保持在 64 位，直到最后，性能从 60ticks 增加到 20ticks。超过 6 个具有相同调整的函数，我能够从一开始似乎优化的代码在 250 个滴答声下降到 50 个滴答声，我的乒乓缓冲区需要在 160 个滴答声内完成所有事情，所以我有一些头脑房间：

void fastAutocorrelation( int64_t *data , float *r){

int64_t *temp;
int64_t *datan = data;
int64_t *datanm = data;

*temp = (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
*r++ = (float)(*temp)/int64ToFloat;

datan = data;
datanm = data + 1;
*temp = (*datan++)*(*datanm++);
*temp += (*datan++)*(*datanm++);
...
4

4 回答 4

3

观察您的处理器没有任何浮点功能；浮点运算正在软件中进行模拟。这意味着瓶颈不是循环控制（编译器已经在降低强度方面做得很好）。瓶颈是浮点模拟器。

鉴于您的处理器没有本机浮点，它很可能也没有大型 L1 缓存。更改循环控件的顺序可能会改善数据局部性。原始代码对一个 240 个元素的数组进行了 10 次扫描，这是局部性较差的。最好是扫一遍阵列，一次研究 10 个项目。

void autocorrelation( int32_t *data , float *r){
  int m, n;
  for (m = 0; m < P + 1; m++) r[m] = 0.0f;
  for (n = 0; n < N; n++) {
    int limit = min(P + 1, N - n);
    for (m = 0; m < limit; m++) {
      r[m] += data[n] * data[n+m];
    }
  }
}

（请注意，转换为指针无济于事，因为编译器已经对原始代码进行了优化以使用指针。）

于 2013-10-22T15:16:42.837 回答
1

我看到你通过移除石膏来减少一点。如果您追求指针技巧，这里有一个尝试。根据您的编译器，您的里程会有所不同：

void autocorrelation( float *restrict data, float *restrict r)
{
    float *data_end = data + N;

    for ( int m=0 ; m < P+1 ; m++)
    {
        float temp = 0;

        for( float *data_n = data, *data_nm = data + m;
             data_nm != data_end;
             data_n++, data_nm++ )
        {
            temp += *data_n * *data_nm;
        }

        r[m] = temp;
    }
}

我添加了restrict关键字，以便编译器知道data并且r不重叠或指向同一事物。

于 2013-10-22T04:42:02.807 回答
1

如果您想进行一些冒险的实验，您可以尝试英特尔的 ICC 编译器（那是 x86 汇编器吗？）。使用正确的命令行开关，将通过为每个循环迭代使用单独的线程来自动并行化您的 for 循环。然而，循环确实需要相当丰富，线程的开销才值得。

另一种方法是使用 SSE 和 AVX 搞砸。更好的是，我认为最新的 Intel x86s 有一个乘法/加法指令，这是相关性、FFT 等所需要的。这样你就可以对你的代码进行矢量化，并且每个时钟周期会发生几个操作（超出普通的CPU流水线可以实现）。实际上，有一些额外的“功能”直接映射到 SSE/AVX 操作码，使它们可以在 C 代码中轻松使用。编译器确实必须知道这些（英特尔的肯定知道），否则您将放入自己的在线汇编程序。然后，您还会遇到在运行时处理不同版本的 CPU 的问题；并非每台 PC 都有最新的英特尔芯片。

或者你可能像我一样非常懒惰，使用英特尔的 IPP/MKL 等预先优化的例程库。像 ICC 一样，它需要花钱，但如果速度 = 项目中的大笔资金，这将是非常值得的。

于 2013-10-22T05:18:09.280 回答
0

你有没有尝试过：

1）推进指针而不是索引r数组？（就像@paddy 为data_nand所做的那样data_m）。例如*(r++) = temp，而不是r[m] = temp

2) 循环展开。您的编译器显然不会这样做，例如，这将大大提高内部循环的速度。具体来说，请查看http://www.quickiwiki.com/en/Duff 's_device 以了解整洁的循环展开。

3) 将循环展开发挥到极致！（也许不漂亮，我知道，但很酷）：您知道Nand的值P：您可以完全展开循环，并编写所有代码（尽管很长）而无需任何分支。根据您的架构（足够的预取管道，加上哑分支预测），这可能会很好地提高速度。您甚至可以编写一个小实用程序来为您生成完整的展开循环，并将生成的代码包含在您的.c文件中。或者只是使用宏和元编程。

于 2013-10-22T05:58:36.677 回答