Введение в технику оптимизации циклов

Большая часть времени исполнения программы приходится на циклы: это могут быть вычисления, прием и обработка информации и т.д. Правильное применение техник оптимизации циклов позволит увеличить скорость работы программы. Но прежде, чем приступать к оптимизациям необходимо выделить «узкие» места программы и попытаться найти причины падения быстродействия. Время исполнения кода в циклах зависит от организации памяти, архитектуры процессора, в том числе, поддерживаемого набора инструкций, конвейеров, кэшей и опыта программиста. Рассмотрим некоторые методы оптимизаций циклов: развертка циклов (loop unrolling), объединение циклов (loop fusion), разрезание циклов (loop distribution), выравнивание циклов (loop alignment), перестановка циклов (loop interchange), разделение на блоки (loop blocking). Перед применением какой-либо оптимизации сделайте самое простое: вынесите из цикла все переменные, которые в нем не изменяются.

1. Итерации цикла зависимы и не могут исполняться параллельно.
2. Тело цикла большое и требуется слишком много регистров.
3. Тело цикла или количество итераций мало и выгоднее совсем отказаться от использования цикла.
4. Цикл содержит вызовы функций и процедур из сторонних библиотек.
5. Цикл интенсивно использует какое-то одно исполняющее устройство процессора.
6. В цикле имеются условные переходы.

Такая оптимизация выполняется, когда тело цикла мало. Необходимо более эффективно использовать исполняющие устройства на каждой итерации. Поэтому многократно дублируют тело цикла в зависимости от количества исполняющих устройств. Но такая оптимизация может вызвать зависимость по данным, чтобы от нее избавиться вводятся дополнительные переменные. До После После №2 for ( int i = 0; i < iN; i++) for ( int i = 0; i < iN; i+=3) for ( int i = 0; i < iN; i+=3) res = res1 * res2 * res3; В gcc можно применить следующие ключи: -funroll-all-loops -funroll-loops.

300 тактов процессора, а доступ к L2 всего

10. Доступ к памяти с большим шагом еще больше замедляет программу. Оптимально «ходить» по памяти с шагом 2 n , где n — достаточно маленькое число (<7). До После for ( int j = 0; j < jN; j++) for ( int j = 0; j < jN; j++)

Во вложенных циклах важен порядок вложения. Поэтому необходимо помнить как хранятся массивы в памяти. Классический пример: c/c++ хранят матрицы построчно, а fortran — по столбцам. До После for ( int i = 0; i < iN; i++) for ( int i = 0; i < iN; i++) < for ( int k = 0; k < kN; k++) > > Теперь обращения к массиву a идут последовательно.

Если тело цикла сложное, то можно применить эту оптимизацию для более лучшего расположения данных в памяти и улучшения использования кэшей. Результат оптимизации сильно зависит от архитектуры процессора. До После for ( int i = 0; i < iN; i++) // размер блоков зависит от размера исходных массивов int iBlk, jBlk; for ( int k = 0; k < iN/iBlk; k++) Примерно по такому принципу работает технология MPI: делит большие массивы на блоки и рассылает отдельным процессорам.

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

1. Ознакомтесь с архитектурой процессора (узнайте сколько и каких исполняющих устройств у него есть, сколько конвейеров, размеры кэшей L1 и L2).
2. Попробуйте компилировать программу разными компиляторами и с различными ключами.
3. Учитывайте влияние операционной системы.

Если хотите сами потренироваться в оптимизации, то попробуйте вычислить число Пи:

Ниже приведен «плохой» код.

О чем я не рассказал: о векторизации вычислений (инструкции SSE); о prefetch'ах, облегчающих работу с памятью. Если будут люди «которым интересно», то напишу отдельную статью про векторизацию циклов.