Оптимизация структур данных под аппаратную предвыборку
Грамотное использование программной предвыборки позволят полностью забыть о существовании аппаратной и не брать особенностей последней в расчет. Это тем более предпочтительно, что механизмом аппаратной предвыборки на момент написания этой книги оснащен один лишь 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 не всегда оптимален для остальных процессоров, и, соответственно, наоборот…
_загрузка кода,
