This thread has been locked.

If you have a related question, please click the "Ask a related question" button in the top right corner. The newly created question will be automatically linked to this question.

关于循环优化:请问有没有方法解决循环体中累加运算的loop carry dependency的问题?



问题一:

比如将一个长数组中元素按照一种方式累加到一个短数组中去:

int longArray[M];

int shortArray[N];// N << M

for(int i = 0; i < M; i++)

{

   pos = getpos(longArray[i]);

   shortArray[pos] += longArray[i];

}

这样就会出现关于shortArray读写的loop carry dependency问题,请问有什么方法可以消除么?

问题二:

优化循环后实际的运算速度有些情况与ii * trip_cnt相同,而有些时候就会有很大的差别。比如上面的例子改成:

int longArray[M];

int shortArray1[N];

int shortArray2[N];// N << M

for(int i = 0; i < M; i++)

{

   pos1 = getpos(longArray[i * 2]);

   shortArray1[pos1] += longArray[i * 2];

   

   pos2 = getpos(longArray[i * 2 + 1]);

   shortArray2[pos1] += longArray[i * 2+ 1];

}

由于loop carry dependency的问题没有解决随意前后两个循环编译器给出的ii是相同的的,

但是实际运行上,在使用我的getpos的情况下第二个循环的运行时间还是会多出很多。

请问对于这样的情况我该如何确定并解决呢?

感谢!

  •   如果第2次结果必须依赖第1次结果,那么是逻辑受限,需要更改下逻辑结构,比如是否可以把一次循环拆成2个循环,如果逻辑受限没有的,可以用restrict方式定义数组指针来优化,不清楚你的例子里为什么 shortArray1/2没有初始化,后面就直接用了,并且gettops是什么函数,不好提出具体建议

  • 感谢您的回答!不过我有很多地方没能理解,想请您详细地说一说

    因为是累加运算所以应该不能用restrict限定吧,那应该是逻辑受限的情况,我把代码具体化了只优化下面的代码请问有方法吗?

    #define M 1000000

    #defien N 8192

    int main()

    {

       int longArray[M];

       int shortArray[N] = {0};

       srand((unsigned)time(NULL)); 

       for(int i = 0; i < M; i++)

       {

          longArray[i] = rand() % N;//初始化longArray,数组中的值就是该值需要在shortArray中累加的位置

       }

       for(int i = 0; i < M; i++)

       {

          pos = longArray[i];

          value = longArray[i];

          shortArray[pos] += value;//累加会造成loop carry dependency

       }

    }

  • 你的实现其实是这样的:

       for(int i = 0; i < M; i++)

       {

          pos = longArray[i];

          value = longArray[i];

          temp = shortArray[pos];

          shortArray[pos] = value+temp;

       }

    我理解pos会限制temp,temp会限制shortArray[pos],你可以多拆成3个循环,用memory来换cycle

    另外你编译时加上-k,-mw,-s生成下.asm文件看看呢,看限制边有几条?

  • 您好!我回去看了.asm文件,把关键的地方标记出来:

    #pragma UNROLL(1)
    for(i = 0; i < M; i++)
    {

       pos = longArray[i];                        //LDW .D2T2 *B8++,B6
                                                                //MVD .M2 B6,B4
       value = longArray[i];                     //...
                                                                //...
       temp = shortArray[pos];               //LDW .D2T2 *B5,B5 ^
                                                                //MV .L1X B5,A3
       shortArray[pos] = value + temp; //ADD .L2 B4,B5,B5 ^
                                                                //STW .D1T2 B5,*A3 ^
    }

    我的理解应该pos不会限制temp,temp于shortArray相互限制,就是B5、A3这两个地址必须是相同的。

    我想了很久还是没想到出用memeory换clk的方法,思路是先将temp算好预存下来吗?可是temp又依赖shortArray。

    请问有什么解决办法么,麻烦了!