0

对于家庭作业，我需要优化循环以在 7.5 秒内运行。我想我可能已经这样做了，因为我的代码在 4 秒内运行。但是，我担心我做的不对，因为我的教练告诉我们，任何低于 7.5 秒的东西都可能是错误的。所以我担心我可能没有正确地做事。这是原始代码：

#include <stdio.h>
#include <stdlib.h>

#define N_TIMES     600000
#define ARRAY_SIZE   10000

int main (void)
{
    double  *array = calloc(ARRAY_SIZE, sizeof(double));
    double  sum = 0;
    int     i;

    for (i = 0; i < N_TIMES; i++) {

        int     j;

        for (j = 0; j < ARRAY_SIZE; j++) {
            sum += array[j];
            }
        }

    return 0;
}

这是我的优化：

   for (i = 0; i < N_TIMES; i++) {

        int     j;

        for (j = 0; j < ARRAY_SIZE/2; j += 20) {
            sum += array[j] + array[j+1] + array[j+2] + array[j+3] + array[j+4] + array[j+5] + array[j+6] + array[j+7] + array[j+8] + array[j+9];
            sum1 += array[j+10] + array[j+11] + array[j+12] + array[j+13] + array[j+14] + array[j+15] + array[j+16] + array[j+17] + array[j+18] + array[j+19];
            }

        }
    sum += sum1;

这些算术运算的数量是否相同？我是否以某种方式更改了代码，或者我只是优化得很好？

4

5 回答 5

2

您的优化不正确：

for (j = 0; j < ARRAY_SIZE/2; j += 20) {

您现在在内部循环中循环的次数是您应该循环的一半。

于 2013-08-20T01:33:54.003 回答
1

它可以通过两种方式进行优化，一种是改进算法，技术是在指令级改进它，即尽可能以更快的速度执行每项操作。通过查看您的代码，您似乎正在尝试实现第二个代码，并且您做得非常正确。现代处理器中的一项功能是使用“指令流水线”，它的阶段很少。代码执行顺序是——

        IF  Instruction Fetch
        ID  Instruction Decode
        EX  Execution
        Mem Memory access
        WB  Write Back

这些操作可以并行完成，即当您为操作执行 ID 时，您可以提前为下一个操作执行 IF。在第一种技术中， sum += array[j];

在这个实现中，IF 保持先前的操作完全执行，即由于 CPU 周期停止。IF、ID、EX、Mem、WB 它们都需要 1 个 cpu 周期，因此需要 5 个 cpu 周期来完成完整的指令。但是随着循环展开，

                    sum += array[j];    // first op
        sum += array[j+1];  // second op
        sum += array[j+2];
        sum += array[j+3];
        sum += array[j+4];  // fifth op

在此实现中，在执行第一个 ID 的同时，执行 IF 可在同一周期（即同时）上为第二个执行。在第二个 cpu 周期中，您正在执行第一个操作的 ID 和第二个操作的 IF；在第 3 个周期，您在第三个操作上使用 IF，在第二个操作上使用 ID，在第一个操作上使用 Ex，因此它利用了指令级并行性并减少了停滞的 cpu 周期数。

基于这种技术，优化循环的典型方法是“展开”它，即。循环展开，您可以在此链接中获得“循环展开”和指令管道的完整示意图和详细信息。

为了证明我试图解释的内容，让我们做一个测试。我已经编译了您的代码并创建了两个具有两个不同循环的可执行文件，我使用 perf 来了解事情的进展情况，结果如下：

     Performance counter stats for './test':

          17739.862565 task-clock                #    1.000 CPUs utilized          
               183 context-switches          #    0.010 K/sec                  
             5 cpu-migrations            #    0.000 K/sec                  
               138 page-faults               #    0.008 K/sec                  
===>        58,408,599,809 cycles                    #    3.293 GHz                    
===>        34,387,134,201 stalled-cycles-frontend   #   58.87% frontend cycles idle   
===>         4,229,714,038 stalled-cycles-backend    #    7.24% backend  cycles idle   
        72,056,092,464 instructions              #    1.23  insns per cycle        
                                         #    0.48  stalled cycles per insn
         6,011,271,479 branches                  #  338.857 M/sec                  
           618,206 branch-misses             #    0.01% of all branches        

          17.744254427 seconds time elapsed

现在使用展开循环测试：

     Performance counter stats for './unroll-loop-test':

           2395.115499 task-clock                #    1.000 CPUs utilized          
            22 context-switches          #    0.009 K/sec                  
             2 cpu-migrations            #    0.001 K/sec                  
               138 page-faults               #    0.058 K/sec                  
====>        7,885,935,372 cycles                    #    3.293 GHz                    
====>        1,569,263,256 stalled-cycles-frontend   #   19.90% frontend cycles idle   
====>       50,629,264 stalled-cycles-backend    #    0.64% backend  cycles idle   
        24,911,629,893 instructions              #    3.16  insns per cycle        
                                         #    0.06  stalled cycles per insn
           153,158,495 branches                  #   63.946 M/sec                  
           607,999 branch-misses             #    0.40% of all branches        

           2.395806562 seconds time elapsed

仔细查看执行的周期数，展开循环 - 停滞周期少得多，因此需要更少的 cpu 周期数，另一方面 - 没有展开 - 停滞周期数消耗更多 cpu 周期，因此很差表现。所以，是的，您正在做非常好的优化，并且他们正在执行相同数量的算术运算。但也要记住，如果你在多处理器系统上运行这个程序，那么另一个优化级别是将整个程序分成几个部分，并将每个部分分配给系统上可用的每个 CPU，这就是所谓的“并行编程”。希望我的回答能澄清你的概念。

于 2013-08-20T08:57:28.717 回答
0

Calloc 将数组中的所有元素设置为零（实际上所有位都设置为零）。因此，您实际上是在多次加零。

因此，让我通过一些方法可能会更快，超出你正在做的事情（这很好，你正在避免比较，但如果你的数组大小不是 20 的倍数或其他什么，你会遇到问题）。

  • 静态初始化数组并将值设置为零可能会或可能不会稍微快一点；

    双数组[ARRAY_SIZE] = {0};

从技术上讲，{} 应该可以工作，但 {0} 可能更明确。

  • for 循环每次都会将 j 重新初始化为 0。在两个循环之外声明 int j ，您可能会保存 ARRAY_SIZE 操作。

    1. 通常，如果数组中的数字遵循某个算术序列，则可以将循环简化为等式。

例如，卡尔·弗里德里希·高斯（Carl Friedrich Gauss）据推测，如果您的序列是 1 2 3 4 .. n（n 是最后一个数字），那么总和是 (n * (n + 1)) / 2 如果 n 是 4， 1 + 2 + 3 + 4 = 10 和 (4 * 5) /2 也等于 10。

还有其他序列，例如连续平方数的总和 IE (1^2 + 2^2 + 3^2 + 4^2.. n^2)。阅读https://en.wikipedia.org/wiki/Square_pyramidal_number了解更多信息。

无论如何，我的观点是理解数学对优化很重要。

  • 在您的情况下，您的所有数字都是相同的，这意味着您可以将数字乘以 ARRAY_SIZE 和 N_TIMES。唯一可能给出不同答案的地方是你会溢出双精度的最大大小。此外，它们都是 0，因此您不必这样做；

您可能会执行以下操作：

int i, j;
double d;
for (i = 0; i < ARRAY_SIZE; i++) {
  if (array[i] == 0)
      continue;
    for (j = 0; j < N_TIMES; j++) {
      d += array[i];
    }
  }

这是未经测试的，因为我怀疑它是否可以接受，但是在常见情况下跳到循环的下一次迭代以避免后续不必要的指令的模式是一种常见的优化实践。

  • 在未优化的编译器中，使用指针可能比使用索引更快。
    IE，你可以循环：

    double * arrayend = array + (ARRAY_SIZE - 1);
double * valuep;
for(valuep = array; valuep <= arrayend; valuep++) {

 //inner stuff
}

  • != 可能比 < 更快，但不要使用相等来比较非整数。

  • 使用无符号数字可能会更快，但可能不是您的情况。C中的有符号与无符号操作

  • 整数可能比双倍快，但对于实际数学来说可能不够大。

  • 编辑：还有另一个。如果您知道系统缓存值的大小，则可以对此进行优化。

于 2013-08-20T04:20:13.220 回答
0

你可以做：

double  *array = calloc(ARRAY_SIZE, sizeof(double));
double  sum = 0;
int     i;
int     j;

for (j = 0; j < ARRAY_SIZE; j++) {
    sum += array[j];
}
sum *= N_TIMES;

return 0;

但这减少了操作......为了维持操作，这将维持缓存命中，甚至寄存器命中。 

int main (void)
{
    double  *array = calloc(ARRAY_SIZE, sizeof(double));
    double  sum = 0;
    int     i;
    int     j;
    double d;

        for (j = 0; j < ARRAY_SIZE; j++) {
            d = array[j];
            for (i = 0; i < N_TIMES; i++) {
                sum += d;
            }
        }

    return 0;
}
于 2013-08-20T01:32:43.967 回答
0

Calloc 将数组中的所有元素设置为零（实际上所有位都设置为零）。因此，您实际上是在多次加零。

因此，让我通过一些方法可能会更快，超出您正在做的事情（这很好，您正在避免比较，但如果您的数组大小不是 20 的倍数或其他什么，您会遇到问题）。

  • 静态初始化数组并将值设置为零可能会或可能不会稍微快一点；

    双数组[ARRAY_SIZE] = {0};

从技术上讲，{} 应该可以工作，但 {0} 可能更明确。

  • for 循环每次都会将 j 重新初始化为 0。在两个循环之外声明 int j ，您可能会保存 ARRAY_SIZE 操作。

    1. 通常，如果数组中的数字遵循某个算术序列，则可以将循环简化为方程。

例如，卡尔·弗里德里希·高斯（Carl Friedrich Gauss）据推测，如果您的序列是 1 2 3 4 .. n（n 是最后一个数字），那么总和是 (n * (n + 1)) / 2 如果 n 是 4， 1 + 2 + 3 + 4 = 10 和 (4 * 5) /2 也等于 10。

还有其他序列，例如连续平方数的总和 IE (1^2 + 2^2 + 3^2 + 4^2.. n^2)。阅读https://en.wikipedia.org/wiki/Square_pyramidal_number了解更多信息。

无论如何，我的观点是理解数学对优化很重要。

  • 在您的情况下，您的所有数字都是相同的，这意味着您可以将数字乘以 ARRAY_SIZE 和 N_TIMES。唯一可能给出不同答案的地方是你会溢出双精度的最大尺寸。此外，它们都是 0，因此您不必这样做；

您可能会执行以下操作：

int i, j;
double d;
for (i = 0; i < ARRAY_SIZE; i++) {
  if (array[i] == 0)
      continue;
    for (j = 0; j < N_TIMES; j++) {
      d += array[i];
    }
  }

这是未经测试的，因为我怀疑它是否可以接受，但是在常见情况下跳到循环的下一次迭代以避免后续不必要的指令的模式是一种常见的优化实践。

  • 在未优化的编译器中，使用指针可能比使用索引更快。
    IE，你可以循环：

    double * arrayend = array + (ARRAY_SIZE - 1);
double * valuep;
for(valuep = array; valuep <= arrayend; valuep++) {

 //inner stuff
}

  • != 可能比 < 更快，但不要使用相等来比较非整数。

  • 使用无符号数字可能会更快，但可能不是您的情况。C中的有符号与无符号操作

  • 整数可能比双倍快，但对于实际数学来说可能不够大。

于 2013-08-20T04:05:20.333 回答