развертывание вложенных циклов for - C

У меня возникли проблемы с развертыванием вложенных forloops. Я понимаю эту концепцию, я пытаюсь применить ее на практике, но я сбиваюсь с толку при редактировании операторов в моих for циклах, чтобы они соответствовали развертыванию.

Если бы кто-нибудь мог просто показать мне эффективную развертку и провести меня через нее, это было бы огромной помощью.

Вот секция цикла, которую я хочу развернуть:

for (i=1 ; i < WIDTH-1 ; ++i) 
{
      for (j = 1 ; j < HEIGHT-1 ; ++j) 
      {
         n = getNeighbors(prv, i, j);    /* This is where I'm confused */
         mask = (prev[i][j] << 1);       
         next[i][j] = !(((n >> prev[i][j]) ^ 3) ^ mask);
      }
}

ОБНОВЛЕНИЕ: Это будет правильно?

for (i=1 ; i < WIDTH-1 ; i+=4) 
{
      for (j = 1 ; j < HEIGHT-1 ; j+=4) 
      {
         n = getNeighbors(prv, i, j);  
         mask = (prev[i][j] << 1);       
         next[i][j] = !(((n >> prev[i][j]) ^ 3) ^ mask);
         n = getNeighbors(prv, i, j+1);  
         mask = (prev[i][j+1] << 1);       
         next[i][j+1] = !(((n >> prev[i][j+1]) ^ 3) ^ mask);
         n = getNeighbors(prv, i, j+2);  
         mask = (prev[i][j+2] << 1);       
         next[i][j+2] = !(((n >> prev[i][j+2]) ^ 3) ^ mask);
         n = getNeighbors(prv, i, j+3);  
         mask = (prev[i][j+3] << 1);       
         next[i][j+3] = !(((n >> prev[i][j+3]) ^ 3) ^ mask);
      }
      for (j = 1 ; j < HEIGHT-1 ; j+=4) 
      {
         n = getNeighbors(prv, i+1, j);  
         mask = (prev[i+1][j] << 1);       
         next[i+1][j] = !(((n >> prev[i+1][j]) ^ 3) ^ mask);
         n = getNeighbors(prv, i+1, j+1);  
         mask = (prev[i+!][j+1] << 1);       
         next[i+1][j+1] = !(((n >> prev[i+1][j+1]) ^ 3) ^ mask);
         n = getNeighbors(prv, i+1, j+2);  
         mask = (prev[i+1][j+2] << 1);       
         next[i+1][j+2] = !(((n >> prev[i+1][j+2]) ^ 3) ^ mask);
         n = getNeighbors(prv, i+1, j+3);  
         mask = (prev[i+1][j+3] << 1);       
         next[i+1][j+3] = !(((n >> prev[i+1][j+3]) ^ 3) ^ mask);
      }
      for (j = 1 ; j < HEIGHT-1 ; j+=4) 
      {
         n = getNeighbors(prv, i+2, j);  
         mask = (prev[i+2][j] << 1);       
         next[i+2][j] = !(((n >> prev[i+2][j]) ^ 3) ^ mask);
         n = getNeighbors(prv, i+2, j+1);  
         mask = (prev[i+2][j+1] << 1);       
         next[i+2][j+1] = !(((n >> prev[i+2][j+1]) ^ 3) ^ mask);
         n = getNeighbors(prv, i+2, j+2);  
         mask = (prev[i+2][j+2] << 1);       
         next[i+2][j+2] = !(((n >> prev[i+2][j+2]) ^ 3) ^ mask);
         n = getNeighbors(prv, i+2, j+3);  
         mask = (prev[i+2][j+3] << 1);       
         next[i+2][j+3] = !(((n >> prev[i+2][j+3]) ^ 3) ^ mask);
      }
      for (j = 1 ; j < HEIGHT-1 ; j+=4) 
      {
         n = getNeighbors(prv, i+3, j);  
         mask = (prev[i+3][j] << 1);       
         next[i+3][j] = !(((n >> prev[i+3][j]) ^ 3) ^ mask);
         n = getNeighbors(prv, i+3, j+1);  
         mask = (prev[i][j+1] << 1);       
         next[i+3][j+1] = !(((n >> prev[i+3][j+1]) ^ 3) ^ mask);
         n = getNeighbors(prv, i+3, j+2);  
         mask = (prev[i][j+2] << 1);       
         next[i+3][j+2] = !(((n >> prev[i+3][j+2]) ^ 3) ^ mask);
         n = getNeighbors(prv, i+3, j+3);  
         mask = (prev[i+3][j+3] << 1);       
         next[i+3][j+3] = !(((n >> prev[i+3][j+3]) ^ 3) ^ mask);
      }
}

c loop-unrolling
person slippeel    schedule 31.05.2015    source источник
comment
что такое prv? чего вы пытаетесь достичь, разворачивая цикл(ы)? Вы, наконец, хотите один цикл или вообще без цикла?   -  person m.s.    schedule 31.05.2015
comment
Почему бы просто не позволить компилятору позаботиться о развертывании циклов за вас?   -  person Paul R    schedule 31.05.2015
comment
Являются ли WIDTH и HEIGHT константами? Значения необходимы для развертывания.   -  person QuentinUK    schedule 31.05.2015
comment
Извините, что не указал конкретики. prv - это двумерный массив, я пытаюсь научиться оптимизировать код и добиться более быстрого времени выполнения, я думаю, мне вообще не нужен цикл, но я бы хотел увидеть обе версии. Я пытаюсь изучить его без помощи компилятора. WIDTH и HEIGHT являются константами.   -  person slippeel    schedule 31.05.2015

Ответы (2)


arrow_upward
0
arrow_downward

Пусть цикл будет:

for(int i = 0; i < x; ++i)
    for(int j = 0; j < y; ++j)
        dosomething(i, j);

Его можно развернуть как:

for(int i = 0; i < x; i += 4) {
    for(int j = 0; j < y; j += 4) {
        dosomething(i, j);
        dosomething(i, j + 1);
        dosomething(i, j + 2);
        dosomething(i, j + 3);
    }
    for(int j = 0; j < y; j += 4) {
        dosomething(i + 1, j);
        dosomething(i + 1, j + 1);
        dosomething(i + 1, j + 2);
        dosomething(i + 1, j + 3);
    }
    for(int j = 0; j < y; j += 4) {
        dosomething(i + 2, j);
        dosomething(i + 2, j + 1);
        dosomething(i + 2, j + 2);
        dosomething(i + 2, j + 3);
    }
    for(int j = 0; j < y; j += 4) {
        dosomething(i + 3, j);
        dosomething(i + 3, j + 1);
        dosomething(i + 3, j + 2);
        dosomething(i + 3, j + 3);
    }
}

Не уверен, сколько пользы от этого будет. Вы должны профилировать свой код после такого развертывания.

person a_pradhan    schedule 31.05.2015
comment
Спасибо за ваш комментарий. Если у меня есть несколько операторов в циклах, например, 3 присваивания в моем коде, как мне это структурировать? Я предполагаю, что я бы сделал это так, как вы показали мне в своем комментарии, где каждое задание выполняется (например) 4 раза с +1, +2, +3 - person slippeel; 31.05.2015
comment
Такое развертывание возможно только в том случае, если известно, что x и y кратны 4. Развертывание внешнего цикла гораздо менее полезно, чем развертывание внутреннего. - person chqrlie; 31.05.2015

arrow_upward
0
arrow_downward

Просто пример:

int r[3][3];

// loop version
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        r[i][j] = i + j;
    }
}

// unrolled version
r[0][0] = 0;
r[0][1] = 1;
r[0][2] = 2;
r[1][0] = 1;
r[1][1] = 2;
r[1][2] = 3;
r[2][0] = 2;
r[2][1] = 3;
r[2][2] = 4;

Обратите внимание, что такое полное развертывание легко возможно только для векторов или матриц, размер которых известен во время компиляции. Также обратите внимание, что последние компиляторы часто могут сами разворачивать такие циклы.

person dlask    schedule 31.05.2015