ТЕХНИКА ОПТИМИЗАЦИИ ПРОГРАММ

       

Оптимизация структур данных под аппаратную предвыборку


Грамотное использование программной предвыборки позволят полностью забыть о существовании аппаратной и не брать особенностей последней в расчет. Это тем более предпочтительно, что механизмом аппаратной предвыборки на момент написания этой книги оснащен один лишь P-4 (прим. сейчас аппаратная предвыборка появилась и в старших моделях процессора AMDAthlon), да и перспектива его развития в последующих моделях весьма туманна. Однако, как уже было показано выше, в ряде случаев достижение эффективной работы программной предвыборки без индивидуальной "заточки" критического кода под конкретный процессор просто невозможно! Фактически это обозначает, что один и тот же фрагмент программы приходится реализовывать в нескольких ипостасях – отдельно под K6 (VIA C3), Athlon, P-II, P-III и P-4. Если все равно приходится оптимизировать программу под каждый процессор по отдельности, то почему бы задействовать возможности P-4 на всю мощь?

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

int x[BIGNUM];

for(a=0;a<BIGNUM, a++)

sum+= x[a];

Листинг 30 Пример кода, эффективно оптимизируемый аппаратной предвыборкой – один регулярный шаблон на страницу

А вот незначительная модификация предыдущего примера – теперь в цикле суммируется не один массив, а сразу два:

int x[256];

int y[256];

for(a=0;a<256, a++)

{

sum1+= x[a];

sum2+= y[a];



}

Листинг 31 Пример кода, "ослепляющий" аппаратную предвыборку – два шаблона на страницу

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


и y

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

struct ZZZ{int x; int x;} zzz[1024];

for(a=0;a<1024, a++)

{

sum1+= zzz.x[a];

sum2+= zzz.y[a];

}

Листинг 32 Исправленный пример листинга ???12 – один регулярный шаблон на страницу

На первый взгляд непонятно, что дает такое преобразование – ведь по-прежнему, на одну страницу приходится два регулярных шаблона. Да, это так – но в последнем случае оба шаблона сливаются в один общий шаблон. Если до этого происходило обращение к N, N+1024, N+4, N+1028, N+8, N+1032 ячейками памяти, то теперь: N, N+4, N+8, N+12… вот и весь фокус!

Кстати, всегда следует помнить, что шаблон определяется не адресами ячеек, к которым происходит обращение, а адресами ячеек, которые вызывают кэш-промах. Совсем не одно и то же! Благодаря этому обстоятельству в пределах всякого 128-байтового блока памяти, уже находящегося в L2-кэше, можно обращаться и по нерегулярному шаблону – лишь бы сами 128-байтовые блоки запрашивались регулярно.

Но вернемся к нашим баранам. Как вы думаете, сможет ли эффективно выполняться на P-4 следующий пример?

struct ZZZ{int x; int x; int sum; } zzz[BIGNUM];

for(a=0;a<BIGNUM, a++)

{

zzz.sum[a]=zzz.x[a]+zzz.y[a];

}

Листинг 33 Пример кода, "ослепляющего" аппаратную предвыборку – и чтение, и запись в пределах одной страницы

Конечно же, он будет исполняться неэффективно! Поскольку в пределах одной страницы осуществляется и чтение, и запись, аппаратная предвыборка не осуществляется. Как быть? Если массив zzz содержит не менее 1024 элементов, разбив структуру ZZZ на три независимых массива, мы добьемся того, что чтение и запись будут происходить в различные страницы:



int x[BIGNUM]; int x[BIGNUM]; int sum[BIGNUM];

for(a=0;a<BIGNUM, a++)

{

sum[a]=x[a]+y[a];

}

Листинг 34 Исправленный вариант листинга ??? 14 – чтение и запись происходят в различные страницы

Кстати, будет не лишним отметить, что такой прием существенно замедляет эффективность выполнения кода на всех остальных процессорах. Почему? Вспомним, что размещение данных в пределах одной DRAM-страницы значительно уменьшает ее латентность, т.к. для доступа к ячейке достаточно передать лишь номер ее столбца, а номер строки будет тот же самый, что и в прошлый раз.

Поочередное обращение к данным, расположенным в различных DRAM-страницах, напротив, требует передачи полного адреса ячейки, а это как минимум 2-3 такта системной шины. Но, если на P-4 латентность компенсируется аппаратной предвыборкой данных, на других процессорах ее скомпенсировать нечем! Вот еще одно подтверждение того, что код, оптимальный для P-4 не всегда оптимален для остальных процессоров, и, соответственно, наоборот…

_загрузка кода,


Содержание раздела