Развертывание цикла с зависимыми циклами

Я работаю над большим приложением, для которого мне нужно выполнить развертывание цикла для последующих зависимых циклов для определенной процедуры. Я написал ниже небольшой образец кода, чтобы воспроизвести большую версию.

Рассмотрим исходный код:

void main()
{

 int a[20] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
 int b[20] = {10,9,8,7,6,5,4,3,2,1,20,19,18,17,16,15,14,13,12,11};
 int i,j,k,l;
 int nab =4, vab =10;
 int dimi, dimj, dimij, dimk, diml, dimkl, dimijkl;
 int count = 0;

 for (i = nab+1; i< nab+vab; i++) 
 {
   dimi = a[i];
   for (j = i; j< nab+vab; j++)
   {
    dimj = b[j];
    dimij = dimi*dimj;
    count = count +1;

    for (k = nab+1; k< nab+vab; k++)
    {
     dimk = a[k-1];
     for (l =k; l< nab+vab; l++)
     {
      diml = a[l-1];
      dimkl = dimk*diml;
      dimijkl = dimij * dimkl;
     }
    }
   }
  }
 printf ("Final dimension:%d \n ", dimijkl);
 printf ("Count:%d \n ", count);
}

Теперь я разворачиваю цикл i в 2 раза:

for (i = nab+1; i< nab+vab; i+=2)
{
  dimi = a[i];
  for (j = i; j< nab+vab; j++)
  {
   dimj = b[j];
   dimij = dimi*dimj;
   count = count +1;

   for (k = nab+1; k< nab+vab; k++)
   {
     dimk = a[k-1];
     for (l =k; l< nab+vab; l++)
     {
      diml = a[l-1];
      dimkl = dimk*diml;
      dimijkl = dimij * dimkl;
     }
    }
  }

  dimi = a[i+1];
  for (j = i+1; j< nab+vab; j++)
  {
    dimj = b[j];
    dimij = dimi*dimj;
    count = count +1;

     for (k = nab+1; k< nab+vab; k++)
     {
      dimk = a[k-1];
      for (l =k; l< nab+vab; l++)
      {
        diml = a[l-1];
        dimkl = dimk*diml;
        dimijkl = dimij * dimkl;
      }    
     }
    }
   }
   printf ("Final dimension:%d \n ", dimijkl);
   printf ("Count:%d \n ", count);

Теперь я хочу развернуть цикл i и j в 2 раза, но поскольку цикл j зависит от цикла i, я немного не уверен, как мне подойти к его написанию. Как я могу переписать код, чтобы развернуть как i, так и j с коэффициентом 2. Кроме того, код будет становиться все более неуклюжим по мере увеличения коэффициента развертывания. Есть ли умный способ развернуть его вручную, чтобы код не стал слишком уродливым.

Я не могу использовать флаги компилятора (пример: -funroll-loops) в этом конкретном случае. Я хочу приблизиться к этому путем ручного развертывания цикла.

Спасибо за уделенное время.


c loops loop-unrolling
person PGOnTheGo    schedule 12.06.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Возможно, не самое элегантное решение, но вы могли бы использовать макросы:

#define INNER_L_LOOP(l) \
    { \
        diml = a[l-1]; \
        dimkl = dimk*diml; \
        dimijkl = dimij * dimkl; \
    } 

#define INNER_K_LOOP(k) \
    { \
        dimk = a[k-1]; \
        for (l =k; l< nab+vab; l++) \
        { \
            INNER_L_LOOP(l) \
        } \
    } 

#define INNER_J_LOOP(j) \
    { \
        dimj = b[j]; \
        dimij = dimi*dimj; \
        count = count +1; \
        \
        for (k = nab+1; k< nab+vab; k += 2) \
        { \
            INNER_K_LOOP(k) \
            if (k+1 < nab+vab) \
                INNER_K_LOOP(k+1) \
        } \
    } 

#define INNER_I_LOOP(i) \
    { \
        dimi = a[i]; \
        for (j = i; j< nab+vab; j+= 2) \
        { \
            INNER_J_LOOP(j) \
            if (j+1 < nab+vab) \
                INNER_J_LOOP(j+1) \
        } \
    } 

 for (i = nab+1; i< nab+vab; i+=2) 
 {
     INNER_I_LOOP(i)
     INNER_I_LOOP(i+1)
 }

Здесь я развернул циклы i, j и k в 2 раза каждый, и вы заметите, что код самого внутреннего цикла не нужно повторять 8 раз (это то, чего вы пытались избежать, если Я правильно понимаю).

Также вы заметите, что для циклов j и k я проверяю, не превышает ли индекс границы массива. Эта проверка оказывает небольшое влияние на производительность, я оставлю ее на ваше усмотрение. ;)

person Taylor Brandstetter    schedule 12.06.2013