Является ли это правильной оптимизацией для цикла

Для задания домашней работы мне нужно оптимизировать цикл, который будет работать менее 7,5 секунд. Я думаю, что я, возможно, сделал это, потому что мой код работает через 4 секунды. Тем не менее, я беспокоюсь, что я не делаю это правильно, потому что мой инструктор сказал нам, что что-то слишком далеко за 7,5 секунд, вероятно, неверно. Поэтому я беспокоюсь, что, возможно, я не буду делать все правильно. Вот исходный код:

#include  #include  #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; 

Выполняют ли они столько же арифметических операций? Я каким-то образом изменил код, или я просто хорошо оптимизирую?

Неправильная оптимизация:

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

Теперь вы петлите половину столько раз во внутреннем цикле, сколько должны.

Он может быть оптимизирован двумя способами: один – улучшить алгоритм, техникой является его улучшение на уровне инструкций, т. Е. Выполнение каждой операции на более высокой скорости, как вы можете. Посмотрев на свой код, кажется, вы пытаетесь достичь второго, и вы делаете это совершенно правильно. Одна из особенностей, найденных в современном процессоре, – использование «конвейерной обработки команд», есть несколько этапов. Порядок выполнения кода –

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

Эти op можно сделать в parralel, т. Е. Пока вы делаете идентификатор для op, вы можете сделать IF для следующего op заранее. В первом методе sum + = array [j];

в этой реализации IF удерживает предыдущую операцию для полного выполнения, т. е. в результате остановленных циклов процессора. IF, ID, EX, Mem, WB, все они принимают 1 цикл процессора, поэтому цикл 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 

в этой реализации, выполняя первый идентификатор, выполнение IF доступно для второго в одном цикле, т.е. одновременно. Во втором цикле процессора вы выполняете идентификатор первой операции и IF второй операции; на 3-м цикле у вас есть IF на третьем op, ID на втором op и Ex на первом op, поэтому он использует параллелизм уровня инструкций и уменьшает количество циклов остановленного процессора.

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

Чтобы получить доказательство того, что я пытался развернуть, давайте проверим тест. Я скомпилировал ваш код и создал два исполняемых файла с двумя разными циклами, я использовал 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 

и теперь с unroll-loop-test:

  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, доступному в системе, и это то, что называется ” Параллельное программирование “. Надеюсь, мой ответ прояснит вашу концепцию.

ты можешь сделать:

 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; } 

Calloc устанавливает все элементы в массиве равными нулю (фактически все биты установлены на ноль). Таким образом, вы действительно добавляете нуль кучу раз.

Поэтому позвольте мне запустить несколько способов, чтобы потенциально ускориться, помимо того, что вы делаете (что хорошо, вы избегаете сравнений, хотя, если размер вашего массива не был кратным 20 или что-то еще, у вас возникли проблемы).

  • Это может быть или не быть немного быстрее, чтобы инициализировать ваш массив статически и установить значения на ноль;

    двойной массив [ARRAY_SIZE] = {0};

Технически {} должен работать, но {0}, вероятно, более явный.

  • цикл for будет повторно инициализировать j до 0 каждый раз. Объявите int j за пределами обоих циклов, и вы, вероятно, сохраните операции ARRAY_SIZE.

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

Например, Карл Фридрих Гаус предположил, что в детстве, если ваша последовательность равна 1 2 3 4 .. n (n – последнее число), тогда сумма равна (n * (n + 1)) / 2 Если n равно 4, 1 + 2 + 3 + 4 = 10 и (4 * 5) / 2 также равно десяти.

Существуют и другие последовательности, такие как сумма последовательных квадратов чисел 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 } 
  • ! = может быть быстрее, чем <, хотя не использовать равенство для сравнения нецелых чисел.

  • Использование беззнаковых чисел МОЖЕТ быть быстрее, хотя, вероятно, не в вашем случае. Подписано vs Неподписанные операции в C

  • Целые числа, вероятно, быстрее, чем удваиваются, но могут не быть достаточно большими для реальной математики.

Calloc устанавливает все элементы в массиве равными нулю (фактически все биты установлены на ноль). Таким образом, вы действительно добавляете нуль кучу раз.

Поэтому позвольте мне запустить несколько способов, чтобы потенциально ускориться, помимо того, что вы делаете (что хорошо, вы избегаете сравнений, хотя, если размер вашего массива не был кратным 20 или что-то еще, у вас возникли проблемы).

  • Это может быть или не быть немного быстрее, чтобы инициализировать ваш массив статически и установить значения на ноль;

    двойной массив [ARRAY_SIZE] = {0};

Технически {} должен работать, но {0}, вероятно, более явный.

  • цикл for будет повторно инициализировать j до 0 каждый раз. Объявите int j за пределами обоих циклов, и вы, вероятно, сохраните операции ARRAY_SIZE.

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

Например, Карл Фридрих Гаус предположил, что в детстве, если ваша последовательность равна 1 2 3 4 .. n (n – последнее число), тогда сумма равна (n * (n + 1)) / 2 Если n равно 4, 1 + 2 + 3 + 4 = 10 и (4 * 5) / 2 также равно десяти.

Существуют и другие последовательности, такие как сумма последовательных квадратов чисел 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 } 
  • ! = может быть быстрее, чем <, хотя не использовать равенство для сравнения нецелых чисел.

  • Использование беззнаковых чисел МОЖЕТ быть быстрее, хотя, вероятно, не в вашем случае. Подписано vs Неподписанные операции в C

  • Целые числа, вероятно, быстрее, чем удваиваются, но могут не быть достаточно большими для реальной математики.

  • edit: еще один. если вы знаете размер кеш-данных системы, вы можете потенциально оптимизировать для этого.