Оптимизация вложенного цикла вручную

Question

Я работаю над домашним заданием, где я должен вручную оптимизировать вложенный цикл (моя программа будет скомпилирована с отключенной оптимизацией).Цель задания - запустить всю программу менее чем за 6 секунд (дополнительный кредит менее чем за 4,5 секунды).

Мне разрешено изменять только небольшой блок кода, и отправной точкой являетсянапример:

    for (j=0; j < ARRAY_SIZE; j++) {
        sum += array[j];
    }

Где ARRAY_SIZE равно 9973. Этот цикл содержится в другом цикле, который выполняется 200 000 раз.Эта конкретная версия запускается за 16 секунд.

Пока что я изменил реализацию, чтобы развернуть цикл и использовать указатели в качестве моего итератора:

(Эти объявления не зациклены на 200 000раз)

 register int unroll_length = 16;
 register int *unroll_end = array + (ARRAY_SIZE - (ARRAY_SIZE % unroll_length));
 register int *end = array + (ARRAY_SIZE -1);
 register int *curr_end;

curr_end = end;

while (unroll_end != curr_end) {
 sum += *curr_end;
 curr_end--;
}

do {
 sum += *curr_end + *(curr_end-1) + *(curr_end-2) + *(curr_end-3) +
  *(curr_end-4) + *(curr_end-5) + *(curr_end-6) + *(curr_end-7) +
  *(curr_end-8) + *(curr_end-9) + *(curr_end-10) + *(curr_end-11) +
  *(curr_end-12) + *(curr_end-13) + *(curr_end-14) + *(curr_end-15);
}
while ((curr_end -=  unroll_length) != array);

sum += *curr_end;

Используя эти приемы, я смог сократить время исполнения до 5,5 секунд, что даст мне полную оценку.Тем не мение;Я действительно хочу заработать дополнительный кредит, но мне также любопытно, какие дополнительные оптимизации я могу сделать, чтобы я мог пропустить?

Редактировать # 1 (Добавление внешнего цикла)

 srand(time(NULL));
 for(j = 0; j < ARRAY_SIZE; j++) {
  x = rand() / (int)(((unsigned)RAND_MAX + 1) / 14);
  array[j] = x;
  checksum += x;
 }

 for (i = 0; i < N_TIMES; i++) {

  // inner loop goes here

  if (sum != checksum)
   printf("Checksum error!\n");

  sum = 0;

 }

Answer 1

вы можете попытаться сохранить ваши переменные в регистре процессора с помощью:

register int *unroll_limit = array + (ARRAY_SIZE - (ARRAY_SIZE % 10));
register int *end = array + ARRAY_SIZE;
register int *curr;

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

Answer 2

Я собираюсь предположить, что вы используете x86, если вы этого не сделаете, это все равно будет применяться, но детали будут другими.

1. Используйте SIMD / SSE, это увеличит скорость в 4 раза без особых усилий, для этого нужны 16-байтовые выровненные данные, которые можно получить при _aligned_malloc или обычном malloc + ручном выравнивании. Кроме того, все, что вам нужно в этом случае - это _mm_add_epi32, чтобы сделать четыре добавления одновременно. (У разных архитектур разные SIMD-блоки, поэтому проверьте свои.)
2. Используйте многопоточность / несколько ядер в этом случае было бы проще всего, чтобы каждый поток суммировал половину массива во временную переменную и суммировал эти два результата, когда закончил. Это будет линейно масштабироваться по количеству доступных ядер.
3. Предварительная выборка в кэш L1; это работает только тогда, когда у вас есть огромный массив и вы уверены, что сможете нагружать процессор по крайней мере ~ 200 циклов (например, туда и обратно к основной оперативной памяти).
4. Полностью старайтесь изо всех сил оптимизировать его и использовать подход, основанный на GPU. Это потребует от вас установки среды CUDA или OpenCL и загрузки массива в графический процессор. Это около ~ 400 LoC без учета вычислительного ядра. Но это может не стоить того, если у вас небольшой набор данных (например, слишком много накладных расходов на настройку / разборку) или если у вас огромный изменяющийся набор данных (например, слишком много времени уходит на потоковую передачу на GPU).
5. Выровняйте по границам страниц, чтобы предотвратить сбои страниц (дорого) в окнах. Обычно они имеют размер 4 КБ.
6. Вручную разверните цикл, учитывая двойную команду выдачи и задержки инструкций. Эта информация доступна от производителя вашего процессора (Intel также предоставляет их). Но на x86 это не очень полезно, потому что процессоры не работают.
7. В зависимости от вашей платформы фактическая передача данных в ЦП для обработки является самой медленной частью (это в основном верно для последних консолей и PS, я никогда не разрабатывал для небольших встроенных устройств), поэтому вы захотите оптимизировать для этого , Трюки, такие как повторение в обратном направлении, хороши на 6502, когда циклы были узким местом, но в наши дни вы захотите получить доступ к ОЗУ линейно.
8. Если вы оказались на машине с быстрой оперативной памятью (например, НЕ ПК / Консоли), преобразование из обычного массива в более причудливую структуру данных (например, такую, которая выполняет больше погони за указателями) может быть полностью оправдано это.

В целом, я думаю, что 1 & 2 являются самыми простыми и выполнимыми и принесут вам более чем достаточную производительность (например, 8x на Core 2 Duo). Однако все это сводится к пониманию того, что ваше аппаратное обеспечение и программирование PIC потребуют совершенно иной оптимизации (например, конвейерная обработка на уровне команд), чем обычный ПК.

Answer 3

• Попробуйте выровнять массив по границе страницы (т.е. 4K)

• Попробуйте вычислить с более широким типом данных, то есть с 64-битными, а не с 32-битными целыми числами. Таким образом, вы можете добавить 2 номера одновременно. В качестве последнего шага сложите обе половинки.

• Преобразование части массива или вычислений в число с плавающей запятой, чтобы вы могли использовать FPU и CPU параллельно

• Я не ожидаю, что следующие предложения будут разрешены, но я все равно упомяну их

  • Многопоточность
  • Специализированные инструкции процессора, т. Е. SSE

Answer 4

Если значения массива не меняются, вы можете запомнить сумму (т.е. рассчитать ее при первом запуске и использовать вычисленную сумму при последующих запусках).

Answer 5

Несколько приятных трюков по оптимизации:

• сделать ваш цикл обратным отсчетом от ARRAY_SIZE до 0, чтобы вы могли удалить сравнения из вашего кода. Меньше сравнений ускоряют программу.
• Более того, x86 в настоящее время оптимизированы для коротких циклов, которые они могут «предварительно загружать», чтобы они работали быстрее, чем обычно.
• Попробуйте использовать регистры везде, где это возможно
• Использовать указатели вместо индексов массива

Так что, если вы хотите использовать массивы, попробуйте использовать:

register int idx = ARRAY_SIZE - 1;
register int sum = 0;
do {
    sum += array[idx];
} while (idx-- % 10 != 0);

do {
    sum += array[idx] + array[idx - 1] + array[idx - 2] + array[idx - 3] + array[idx - 4] + array[idx - 5] + array[idx - 6] + array[idx - 7] + array[idx - 8] + array[idx - 9];
} while (idx -= 10);
// now we don't use a comparison and the ZERO flag will be set in FLAG
// register on which we can conditional jump. With a comparison you do VALUE - VALUE
// and then check if the ZERO flag is set or the NEGATIVE flag or whatever you are testing on