акробатика для программиста

КРИС КАСПЕРСКИ

Спецвыпуск: Хакер, номер #071, стр. 071-056-5

[программная конвейеризация.]

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

Чтобы избавиться от зависимости по данным, необходимо развернуть не только цикл, но и «расщепить» переменную, используемую для суммирования. Такая техника оптимизации называется программной конвейеризацией («software pipelining»), и из всех рассматриваемых компиляторов ее поддерживает только GCC, да и то лишь частично. В то же самое время, она элементарно реализуется «руками»:

// обрабатываем первые XXL – (XXL % 4) итерации

for(i=0; i<XXL;i+=4)

{

sum_1 += a[i+0];

sum_2 += a[i+2];

sum_3 += a[i+3];

sum_4 += a[i+4];

}

// обрабатываем оставшийся «хвост»

for(i-=XXL; i<XXL;i++)

sum += a[i];

// складываем все воедино

sum += sum_1 + sum_2 + sum_3 + sum_4;

[авто-параллелизм.]

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

Для оптимизации под многопроцессорные машины, следует разбивать циклы с большим количеством итераций на N циклов меньшего размера, помещая каждый из них в свой поток, где N — количество процессоров, обычно равное двум. Такая техника оптимизации называется авто-параллелизмом («auto-parallelization») и наглядно демонстрируется следующим примером:

for (i=0; i<XXL; i++)

a[i] = a[i] + b[i] * c[i];

Поскольку зависимость по данным отсутствует, цикл можно разбить на два. Первый будет обрабатывать ячейки от 0 до XXL/2, а второй — от XXL/2 до XXL. Тогда на двухпроцессорной машине скорость выполнения цикла практически удвоится:

/* поток A */

for (i=0; i<XXL/2; i++)

a[i] = a[i] + b[i] * c[i];

/* поток B */

for (i=XXL/2; i<XXL; i++)

a[i] = a[i] + b[i] * c[i];

Intel C++ – единственный из всех рассматриваемых компиляторов, поддерживающий технику авто-парализации, активируемую ключом –parallel. Однако, качество оптимизации оставляет желать лучшего, и эту работу лучше осуществлять вручную.

[упорядочивание обращений к памяти.]

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