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

означает сказать лишь половину правды.


Сказать, что AMD опередила Intel с поддержкой программной предвыборки, – означает сказать лишь половину правды. Предвыборка отнюдь не является оригинальным изобретением AMD и в мире не-PC компьютеров она достаточно широко распространена. Поскольку, непосредственное управление кэшем не может осуществляться без учета характеристик подсистемы памяти с одной стороны, и архитектуры процессора с другой, – оно всегда аппаратно – зависимо. В мире "больших" компьютеров, конфигурации которых более или менее предсказуемы, "заточка" оптимизации программы под конкретное оборудование – явление вполне нормальное.

Но вот PC – дело другое. Оптимальная стратегия предвыборки зависит и от типа оперативной памяти, и от времени доступа к ней, и от ее латентности, и от характеристик чипсета, и от разрядности и тактовой частоты системной шины, и от частоты и архитектуры ядра процессора, и от политики кэширования, и от длины кэш-линеек, и от разрядности и частоты внутренней шины, и от латентности кэш-памяти… Многообразие конфигураций персональных компьютеров приводит к тому, что программная предвыборка создает проблем больше, чем их решает.

Создатели P-4 сделали большой шаг вперед, реализовав механизм аппаратной предвыборки, или, иначе говоря, – усовершенствованную стратегию упреждающего считывания. До сих пор кэш-контроллеры всех бытовых микропроцессоров приступали к загрузке кэш-линейки лишь после явного обращения к ней, а предвидеть: какая линейка будет запрошена следующей, они не могли – интеллектуальности не хватало!

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

Алгоритм предсказаний недокументирован, но, тем не менее, суть его (по крайней мере, в общих чертах) понять несложно. Пусть, например, процессор фиксирует ряд кэш-промахов при обращении к линейкам N, N+3, N+6, N+9… Не нужно быть ясновидящим, чтобы с высокой степенью достоверности предположить, что следующей на очереди стоит N+12 линейка.
Т.е. P- 4 умеет распознавать арифметическую прогрессию и вычислять ее члены. Насчет же распознавания геометрической прогрессии в документации ничего не сказано, а проверить экспериментально – под рукой процессора нет.

Определить шаг арифметической прогрессии по нескольким ее элементам – не проблема! Вот выделить прогрессию из произвольной последовательности – куда сложнее. Справляется ли с этим P-4? Нет! Его разработки честно признаются в документации, что "Follows only one stream per 4K page (load or store)". Т.е. в пределах одной страницы доступ к данным, обрабатываемых в цикле, должен происходить по одному регулярному шаблону, в противном случае механизм предсказаний "ослепнет" и аппаратная предвыборка осуществляться не будет. Если же такая необходимость все же возникает (а практически всегда она и возникает), обрабатываемые данные следует разбить на несколько блоков (числом не более восьми) и расположить их в различных четырех килобайтовых регионах. Восьми – потому что P-4 умеет одновременно отслеживать не более восьми регулярных шаблонов (в терминологии разработчиков: потоков данных – data stream). Причем, упреждающая загрузка осуществляется только в пределах одного четырех килобайтового блока памяти – при выходе за его пределы механизм предсказаний дезактивируется и отслеживание шаблона обращений начинается сначала. Т.е. процессор вновь дожидается нескольких кэш-промахов, определяет шаг прогрессии и только после этого приступает к очередному сеансу предвыборки. Вследствие этого ячейки памяти, читаемые с большим шагом (порядка 1Кб), никогда не предвыбираются и потому обрабатываются крайне неэффективно.

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


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