Подтвердить что ты не робот

Оптимизация кода C

Для назначения курса под названием High Performance Computing мне необходимо оптимизировать следующий фрагмент кода:

int foobar(int a, int b, int N)
{
    int i, j, k, x, y;
    x = 0;
    y = 0;
    k = 256;
    for (i = 0; i <= N; i++) {
        for (j = i + 1; j <= N; j++) {
            x = x + 4*(2*i+j)*(i+2*k);
            if (i > j){
               y = y + 8*(i-j);
            }else{
               y = y + 8*(j-i);
            }
        }
    }
    return x;
}

Используя некоторые рекомендации, мне удалось оптимизировать код (или, по крайней мере, я так думаю), например:

  • Постоянное распространение
  • Алгебраическое упрощение
  • Копирование распространения
  • Устранение общих подвыражений
  • Устранение мертвого кода
  • Инвариантное удаление цикла
  • побитовые сдвиги вместо умножения, поскольку они менее дороги.

Здесь мой код:

int foobar(int a, int b, int N) {

    int i, j, x, y, t;
    x = 0;
    y = 0;
    for (i = 0; i <= N; i++) {
        t = i + 512;
        for (j = i + 1; j <= N; j++) {
            x = x + ((i<<3) + (j<<2))*t;
        }
    }
    return x;
}

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

время выполнения = количество команд * циклов на команду

Когда я генерирую код сборки с помощью команды: gcc -o code_opt.s -S foobar.c,

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

Не вставляйте код сборки, поскольку они очень обширны. Поэтому я вызываю функцию "foobar" в основном, и я измеряю время выполнения, используя команду time в linux

int main () {
    int a,b,N;

    scanf ("%d %d %d",&a,&b,&N);
    printf ("%d\n",foobar (a,b,N));
    return 0;
}
4b9b3361

ОТВЕТЫ

Ответ 1

Первоначально:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 4*(2*i+j)*(i+2*k);
        if (i > j){
           y = y + 8*(i-j);
        }else{
           y = y + 8*(j-i);
        }
    }
}

Удаление y вычислений:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 4*(2*i+j)*(i+2*k);
    }
}

Разделение i, j, k:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 8*i*i + 16*i*k ;                // multiple of  1  (no j)
        x = x + (4*i + 8*k)*j ;                 // multiple of  j
    }
}

Перемещение их извне (и удаление цикла, который запускает N-i раз):

for (i = 0; i <= N; i++) {
    x = x + (8*i*i + 16*i*k) * (N-i) ;
    x = x + (4*i + 8*k) * ((N*N+N)/2 - (i*i+i)/2) ;
}

переписано:

for (i = 0; i <= N; i++) {
    x = x +         ( 8*k*(N*N+N)/2 ) ;
    x = x +   i   * ( 16*k*N + 4*(N*N+N)/2 + 8*k*(-1/2) ) ;
    x = x +  i*i  * ( 8*N + 16*k*(-1) + 4*(-1/2) + 8*k*(-1/2) );
    x = x + i*i*i * ( 8*(-1) + 4*(-1/2) ) ;
}

Переписывание - пересчет:

for (i = 0; i <= N; i++) {
    x = x + 4*k*(N*N+N) ;                            // multiple of 1
    x = x +   i   * ( 16*k*N + 2*(N*N+N) - 4*k ) ;   // multiple of i
    x = x +  i*i  * ( 8*N - 20*k - 2 ) ;             // multiple of i^2
    x = x + i*i*i * ( -10 ) ;                        // multiple of i^3
}

Еще одно перемещение к внешнему (и удаление цикла i):

x = x + ( 4*k*(N*N+N) )              * (N+1) ;
x = x + ( 16*k*N + 2*(N*N+N) - 4*k ) * ((N*(N+1))/2) ;
x = x + ( 8*N - 20*k - 2 )           * ((N*(N+1)*(2*N+1))/6);
x = x + (-10)                        * ((N*N*(N+1)*(N+1))/4) ;

Оба вышеупомянутых удаления цикла используют формулы summation:

Сумма (1, я = 0..n) = n + 1
  Sum (i 1 я = 0..n) = n (n + 1)/2
  Sum (i 2 я = 0..n) = n (n + 1) (2n + 1)/6
  Sum (i 3 я = 0..n) = n 2 (n + 1) 2/4

Ответ 2

y не влияет на окончательный результат удаления кода:

int foobar(int a, int b, int N)
{
    int i, j, k, x, y;
    x = 0;
    //y = 0;
    k = 256;
    for (i = 0; i <= N; i++) {
        for (j = i + 1; j <= N; j++) {
            x = x + 4*(2*i+j)*(i+2*k);
            //if (i > j){
            //   y = y + 8*(i-j);
            //}else{
            //   y = y + 8*(j-i);
            //}
        }
    }
    return x;
}

k является просто константой:

int foobar(int a, int b, int N)
{
    int i, j, x;
    x = 0;
    for (i = 0; i <= N; i++) {
        for (j = i + 1; j <= N; j++) {
            x = x + 4*(2*i+j)*(i+2*256);
        }
    }
    return x;
}

Внутреннее выражение можно преобразовать в: x += 8*i*i + 4096*i + 4*i*j + 2048*j. Используйте математику, чтобы вытолкнуть все из них во внешний цикл: x += 8*i*i*(N-i) + 4096*i*(N-i) + 2*i*(N-i)*(N+i+1) + 1024*(N-i)*(N+i+1).

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

a и b также должны быть удалены, если это возможно - поскольку a и b поставляются в качестве аргумента, но никогда не используются в вашем коде.

Сумма квадратов и сумма формулы кубов:

  • Сумма (x 2 x = 1..n) = n (n + 1) (2n + 1)/6
  • Сумма (x 3 x = 1..n) = n 2 (n + 1) 2/4

Ответ 3

Эта функция эквивалентна следующей формуле, которая содержит только 4 целых умножения и 1 целочисленное деление:

x = N * (N + 1) * (N * (7 * N + 8187) - 2050) / 6;

Чтобы получить это, я просто набрал сумму, рассчитанную вашими вложенными циклами, в Wolfram Alpha:

sum (sum (8*i*i+4096*i+4*i*j+2048*j), j=i+1..N), i=0..N

Здесь - прямая ссылка на решение. Подумайте перед кодированием. Иногда ваш мозг может оптимизировать код лучше, чем любой компилятор.

Ответ 4

Кратко сканируя первую процедуру, первое, что вы заметите, это то, что выражения, содержащие "y", полностью не используются и могут быть устранены (как и вы). Это также позволяет исключить if/else (как и вы).

Остается два цикла for и беспорядочное выражение. Факторизация частей этого выражения, которые не зависят от j, является следующим шагом. Вы удалили одно такое выражение, но (i<<3) (т.е. я * 8) остается во внутреннем цикле и может быть удалено.

Ответ Pascal напомнил мне, что вы можете использовать оптимизацию шага цикла. Сначала переместите (i<<3) * t из внутреннего цикла (вызовите его i1), а затем подсчитайте при инициализации цикла значение j1, равное (i<<2) * t. При каждом приращении итерации j1 на 4 * t (который является предварительно рассчитанной константой). Замените свое внутреннее выражение на x = x + i1 + j1;.

Кто-то подозревает, что может быть какой-то способ объединить две петли в одну, с шагом, но я не вижу его в стороне.

Ответ 5

Несколько других вещей, которые я вижу. Вам не нужно y, поэтому вы можете удалить его объявление и инициализацию.

Кроме того, значения, принятые для a и b, фактически не используются, поэтому вы можете использовать их как локальные переменные вместо x и t.

Кроме того, вместо добавления i to 512 каждый раз, вы можете заметить, что t начинается с 512 и увеличивается на 1 каждую итерацию.

int foobar(int a, int b, int N) {
    int i, j;
    a = 0;
    b = 512;
    for (i = 0; i <= N; i++, b++) {
        for (j = i + 1; j <= N; j++) {
            a = a + ((i<<3) + (j<<2))*b;
        }
    }
    return a;
}

Как только вы дойдете до этого момента, вы также можете заметить, что помимо инициализации j, i и j используются только в одном мутиле каждый - i<<3 и j<<2. Мы можем закодировать это непосредственно в логике цикла, таким образом:

int foobar(int a, int b, int N) {
    int i, j, iLimit, jLimit;
    a = 0;
    b = 512;
    iLimit = N << 3;
    jLimit = N << 2;
    for (i = 0; i <= iLimit; i+=8) {
        for (j = i >> 1 + 4; j <= jLimit; j+=4) {
            a = a + (i + j)*b;
        }
        b++;
    }
    return a;
}

Ответ 6

ОК... так вот мое решение, а также встроенные комментарии, чтобы объяснить, что я сделал и как.

int foobar(int N)
{ // We eliminate unused arguments 
    int x = 0, i = 0, i2 = 0, j, k, z;

    // We only iterate up to N on the outer loop, since the
    // last iteration doesn't do anything useful. Also we keep
    // track of '2*i' (which is used throughout the code) by a 
    // second variable 'i2' which we increment by two in every
    // iteration, essentially converting multiplication into addition.
    while(i < N) 
    {           
        // We hoist the calculation '4 * (i+2*k)' out of the loop
        // since k is a literal constant and 'i' is a constant during
        // the inner loop. We could convert the multiplication by 2
        // into a left shift, but hey, let not go *crazy*! 
        //
        //  (4 * (i+2*k))         <=>
        //  (4 * i) + (4 * 2 * k) <=>
        //  (2 * i2) + (8 * k)    <=>
        //  (2 * i2) + (8 * 512)  <=>
        //  (2 * i2) + 2048

        k = (2 * i2) + 2048;

        // We have now converted the expression:
        //      x = x + 4*(2*i+j)*(i+2*k);
        //
        // into the expression:
        //      x = x + (i2 + j) * k;
        //
        // Counterintuively we now *expand* the formula into:
        //      x = x + (i2 * k) + (j * k);
        //
        // Now observe that (i2 * k) is a constant inside the inner
        // loop which we can calculate only once here. Also observe
        // that is simply added into x a total (N - i) times, so 
        // we take advantange of the abelian nature of addition
        // to hoist it completely out of the loop

        x = x + (i2 * k) * (N - i);

        // Observe that inside this loop we calculate (j * k) repeatedly, 
        // and that j is just an increasing counter. So now instead of
        // doing numerous multiplications, let break the operation into
        // two parts: a multiplication, which we hoist out of the inner 
        // loop and additions which we continue performing in the inner 
        // loop.

        z = i * k;

        for (j = i + 1; j <= N; j++) 
        {
            z = z + k;          
            x = x + z;      
        }

        i++;
        i2 += 2;
    }   

    return x;
}

Код без каких-либо объяснений сводится к следующему:

int foobar(int N)
{
    int x = 0, i = 0, i2 = 0, j, k, z;

    while(i < N) 
    {                   
        k = (2 * i2) + 2048;

        x = x + (i2 * k) * (N - i);

        z = i * k;

        for (j = i + 1; j <= N; j++) 
        {
            z = z + k;          
            x = x + z;      
        }

        i++;
        i2 += 2;
    }   

    return x;
}

Надеюсь, это поможет.

Ответ 7

int foobar (int N)//Чтобы избежать использования аргумента использования

{

int i, j, x=0;   //Remove unuseful variable, operation so save stack and Machine cycle

for (i = N; i--; )               //Don't check unnecessary comparison condition 

   for (j = N+1; --j>i; )

     x += (((i<<1)+j)*(i+512)<<2);  //Save Machine cycle ,Use shift instead of Multiply

return x;

}