Оптимизация циклов

Loop tiling (разбиение цикла на блоки)

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

Loop unrolling (раскрутка цикла) — техника оптимизации компьютерных программ, состоящая в искусственном увеличении количества инструкций, исполняемых в течение одной итерации цикла. В результате применения этой оптимизации увеличивается количество инструкций, которые потенциально могут выполняться параллельно, и становится возможным более интенсивное использование регистров, кэша данных и исполнительных устройств.

Например, for (i = 1; i < n; i++) { a[i] = (i % b[i]); } преобразуется в такой код:

for (i = 1; i < n - 3; i += 4) {

a[i] = (i % b[i]);

a[i + 1] = ((i + 1) % b[i + 1]);

a[i + 2] = ((i + 2) % b[i + 2]);

a[i + 3] = ((i + 3) % b[i + 3]);

}

for (i = 4*(n/4); i < n; i++) { a[i] = (i % b[i]); }

Одним из недостатков данного метода оптимизации при его применении совместно с loop fission для дальнейшего распараллеливания является то, что выборка данных из памяти начинает производиться не по порядку следования данных, что может отрицательно сказаться на эффективности работы кэша. Кроме того, в ходе раскрутки цикла увеличивается число команд, выполняемых на каждой его итерации. Если данное число превысит емкость кэша команд, то вместо ожидаемого роста эффективности выполнения цикла возможно ее существенное снижение.

Loop unswitching (размыкание цикла) состоит в вынесении условия за пределы цикла и дублирования тела цикла с помещением соответствующих вариантов в соответствующие ветви условия.

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

x[i] = x[i] + y[i];

if (w) { y[i] = 0; }

}

Условие внутри тела цикла мешает его распараллеливанию. После размыкания оно принимает следующий вид:

if (w) {

for (i = 0; i < 1000; i++) { x[i] = x[i] + y[i]; y[i] = 0; }

}

else {

for (i = 0; i < 1000; i++) { x[i] = x[i] + y[i]; }

}

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

Билет

10 Функции в С++

Описание функции:

Функция-подпограмма, позволяющая выполнять определенные действия для упрощения программы.Она является заменителем многократно повторяющихся действий.

< тип результата> < имя ф-ции> (< тип> < параметр>, …)

{

}

Вызов функции:

Вызов: < имя ф-ции> (параметры)

Формальные и фактические параметры:

фактический параметр — аргумент, используемый как значение (число, символ и т. д.);

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

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

Способы передачи данных в функцию:

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

При передаче параметров-переменных в подпрограмму фактически через стек передаются их адреса в порядке, объявленном в заголовке подпрограммы. Следовательно, подпрограмма имеет доступ к этим параметрам и может их изменять.

Передача значением и по адресу:

Передача параметра по значению означает что вызывающая функция копирует в память, доступную вызываемой, (обычно стек) непосредственное значение. Изменение копии переменной, соответственно, оригинал не затрагивает.

Передача параметра по адресу если необходимо именно изменить переменную из внешней, по отношению к вызываемой функции, области видимости, можно копировать адрес переменной, подлежащей изменению. Соответственно при вызове функции g(& x) приходится использовать операцию взятия адреса.

Можно заметить, что передача параметра по адресу является частным случаем передачи по значению: передаваемым значением является адрес, по которому можно найти другое значение — значение переменной x.

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

Передача по ссылке позволяет избежать копирования всей информации, описывающей состояние объекта (а это может быть существенно больше чем sizeof(int)) и является необходимой для конструктора копирования.