Доклад
На тему: Программное кэширование

Содержание
1.                 Введение.
2.                 Программная предвыборка в процессорах К6+ и РIII+.
3.                 Предвыборка в процессорах AMD К6 и VIA C3.
4.                 Предвыборка в процессорах РIIIи Р4.
5.                 Pentium III.
6.                 Pentium 4.
7.                 Эффективность предвыборки в многозадачных системах.

Введение
Программному управлению кэшированием просто не повезло. Концепция "прозрачного" кэша, активно продвигаемая фирмой Intel, Абстрагировала программистов от потребностей аппаратной реализации кэш-контроллера и не предоставила им никаких рычагов управления последним. Впрочем, для достижения полной абстракции интеллектуальности кэш-контроллеров все же не хватило, и для системных программистов пришлось крохотную лазейку, позволив им, в частности, запрещать кэширование страниц памяти, принадлежащих периферийным устройствам.
До тех пор, пока большинство приложений перемалывало компактные, многократно обрабатываемые структуры данных, стратегия загрузки кэш-линеек по первому требованию вполне справлялась со своей задачей, но с появлением мультимедийных приложений стала "буксовать". Резко возросший объем обрабатываемых данных и распространение потоковых алгоритмов, обращающихся к каждой ячейке памяти лишь единожды, обернулся постоянными перезагрузками кэша, что ограничило производительность системы не быстродействием процессора, а пропускной способностью оперативной памяти. Впервые этой проблеме бросила вызов фирма AMD, включив в состав набора команд 3D Now! инструкцию divfetch, позволяющую программисту заблаговременно загружать в кэш ячейки памяти, к которым он расчитывает обратится в ближайшем будущем. Причем загрузка данных осуществляется без участия и остановки вычислительного конвейера! Это убивает двух зайцев сразу: во-первых, ручное управление кэш-контроллером позволяет выбрать оптимальную стратегию упреждающей загрузки данных, что существенно уменьшает количество кэш-промахов, а, во-вторых, с предвыборкой становится возможным загружать очередную порцию данных параллельно с обработкой предыдущей, маскируя тем самым латентность оперативной памяти.
Следом за К6, предвыборка (естественно в усовершенствованном варианте) появилась и в Pentium lll, да не одна, а с целой свитой команд ручного управления кэшированием - Intel явно не хотела отставать от конкурентов!
Совершенствование управления подсистемной памяти продолжилось и в Pentium 4. Помимо расширения набора команд, в нем реализован уникальный на сегодняшний день механизм аппаратной предвыборки с интеллектуальным алгоритмом упреждающей загрузки. Анализируя порядок, в котором приложение запрашивает данные из оперативной памяти, процессор пытается предсказать (приблизительно так же, как предсказывает направление условных переходов) адрес следующей обрабатываемой ячейки, чтобы спекулятивно загрузить ее в кэш задолго до реального затребования. Естественно, при всей прозрачности аппаратной предвыборки структуры данных желательно сделать так, чтобы процессор пореже ошибался в своих предсказаниях, а в идеале - не ошибался вообще.

Программная предвыборка в процессорах К6+ и РIII+
Поддержка программной предвыборки имеется как в К6/К7 (и совместимом с К6 микропроцессоре VIA C3), так и в Р!!!/Р4, однако, их реализации различны и к тому же не совместимы друг с другом. Процессоры от AMD(VIA) не понимают инструкций предвыборки процессоров Intel и, соответственно, наоборот.
Это печальное обстоятельство существенно снижает популярность предвыборки, поскольку программистам приходится либо писать два варианта кода: один для Intel, другой для AMD(VIA); либо ограничивать аудиторию пользователей одним из процессоров.
Поэтому к предвыборке целесообразно прибегать лишь в действительно крайних случаях, когда никакими другими путями обеспечить требуемое быстродействие уже не удается.
Предвыборка в процессорах AMD К6 и VIA C3
В К6/К7 и VIA C3 программная предвыборка осуществляется одной из двух инструкций: divfetch или divfetchw. Буква w в конце последней сообщает процессору, что загружаемые данные планируется модифицировать. Это отнюдь не означает, что данные, загружаемые посредством divfetch, модифицировать нельзя. Модифицировать их можно, но не желательно, т. к. в этом случае процессор вынужден совершать дополнительный цикл, изменяя атрибуты соответствующей кэш-линейки с эксклюзивной на модифицируемую.
Инструкция divfetch просто инициирует запрос ячейки памяти, точно также, как это делает любая команда, обращающаяся к памяти, но, в отличие от последней, divfetch не помещает загружаемые данные ни в какой регистр, более того, она вообще не дожидается конца загрузки этих данных, тут же возвращая управление. Преждевременное завершение инициатора запроса еще не освобождает кэш-контроллер от обязанности выполнения этого запроса, но если запрошенная ячейка уже находится в кэше первого уровня, ничего не происходит и инструкция divfetch ведет себя аналогично команде NOP (нет операции). В противном случае кэш-контроллер обращается к кэшу второго уровня, а если искомой ячейки не оказывается и там - к оперативной памяти (кэшу третьего уровня), целиком заполняя соответствующие кэш-строки кэшей всех нижестоящих уровней. Поскольку кэш-контроллер работает независимо от вычислительного конвейера процессора, предвыборка позволяет загружать очередную порцию данных параллельно с обработкой предыдущей. Если время загрузки данных не превышает времени их обработки, то простоя процессора вообще не происходит - вычислительны конвейер работает безостановочно, а время доступа к памяти полностью маскируется.
Инструкция divfetchw работает аналогично divfetch, но автоматически присваивает загружаемой ячейке статус модифицируемой. Если строку действительно планируется модифицировать, это экономит 15-25 тактов процессорного времени. Однако, если вы не уверены, будет ли строка меняется, лучше загрузите ее как эксклюзивную, т. к. выгрузка модифицируемой, но реально не модифицированной строки в оперативную память обойдется намного дороже.
Модифицируемые же кэш-строки независимо от того, были ли они реально модифицированы или нет, всегда вытесняются в оперативную память или кэш вышестоящего уровня, что требует определенного количества тактов процессора.
Несмотря на то, что AMD позиционирует команды предвыборки как аппаратно-независимые, они таковыми не являются, поскольку количество байт, загружаемых инструкциями divfetch и divfetchw, определяются размерами кэш-линий процессора, а их длинна различна: 32 байта для AMD K6 (VIA C3) и 64 байта для Athlon/Duron. Соответственно, различны оптимальный шаг и минимальная дистанция предвыборки.
В этом свете становится очень интересным следующее высказывание AMD, почерпнутое из руководства по оптимизации под Athlon: "Инструкции PREFETCHNTA/T0/T1/T2 из ММХ-расширения аппаратно зависимы. Если вы, господин разработчик, нуждаетесь в совместимости с 25 миллионами уже проданных процессоров AMD-K6-2 и AMD-K6-III, вместо инструкций предвыборки нового расширения ММХ, пользуйтесь командами PREFETCH/W из расширения 3Dnow!"
Вот хорошая демонстрация искусства умолчания! Если уж бросать камень в огород Intel, то не лишнее бы отметить, что, во-первых, и собственные инструкции предвыборки аппаратно-зависимы, а, во-вторых, процессорами Pentium они оно не поддерживаются. Так что никаких преимуществ у AMD`шной предвыборки перед Intel нет.
Предвыборка в процессорах Р!!! и Р4
В процессорах Р!!! и Р4 программная предвыборка осуществляется следующими инструкциями : divfetchnta, divfetcht0, divfetcht1, divfetcht2. Суффикс указывает на тип загружаемых данных, что определяет уровень кэш-иерархии, в которую эти данные будут загружены. Так NTA расшифровывается как Non-TemporAl [Data] - не временные данные, т.е. данные, многократное использование которых планируется. Соответственно Т0, Т1, Т2 обозначает временные данные, использовать которые планируется неоднократно.
Какой бы командой предвыборка ни осуществлялась, кэш-линейкам, загружаемым из основной памяти, всегда присваивается эксклюзивный статус. При предвыборке линеек из кэша второго уровня их прежний статус сохраняется. Возможность загрузки кэш-линейки с автоматической установкой статуса модифицируемой в процессорах Pentium не реализована. Однако ввиду многоступенчатой схемы буферизации записи, изменение атрибутов кэш-линеек происходит в основном, а не в дополнительном, как в К6/Athlon, цикле обмена, т.е. без ущерба для производительности.
Причем в отличии отdivfetch/w,инструкции divfetchnta/t0/t1/t2 не приказывают, а рекомендуют осуществить предвыборку. Процессор отклоняет рекомендацию и не осуществляет предвыборку, если :
·запрошенные данные уже содержатся в кэше соответствующей или ближайшей к процессору иерархии;
·сведения о странице, к которой принадлежат загружаемые данные, отсутствуют в DTLB (Data Translation Look aside Buffer - Буфере Ассоциативной Трансляции;)
·подсистема памяти процессора занята перемещением данных между L1- и L2- кэшем;
·запрошенные данные принадлежат региону некэшируемой памяти(странице с атрибутами UC и USWC);
·данные не могут быть загружены из-за ошибки доступа (при этом исключение не вырабатывается);
·инструкция предвыборки предваряется префиксом LOCK (в этом случае генерируется исключение "неверный опкод");
          Во c остальных случаях предвыборка выполняется. Алгоритм ее выполнения аппаратно-зависим и сильно варьируется от одной модели процессора к другой, поэтому, поведение "предвыборных" команд на Р!!! и Р4 ниже мы рассмотрим по отдельности

 

Pentium lll

Инструкция divfetchnta загружает данные в кэш первого уровня, минуя второй. Действительно, данные, повторное обращение к которым не планируется, целесообразно помещать в кэш самой ближайшей к процессору иерархии, не затирая содержимое остальных, т.к. оно может еще пригодится, а вот однократно используемые данные после их вытеснения из L1-кэша, из L2-кэша затребованы уж точно не будут. Инструкция divfetcht0 загружает данные в кэш-иерархии обоих уровней. Данные, обращение к которым происходит многократно, будучи загруженными в L2-кэш, окажутся как нельзя кстати, когда будут вытесненными из L1-кэша.
Инструкции divfetcht1 и divfetcht2 загружают данные в один лишь кэш второго уровня, не помещая их в кэш первого. Поскольку выгрузка буферов записи происходит в кэш второго уровня, минуя первый, то предвыборку соответствующих линеек в L1-кэш осуществлять нецелесообразно. Вот тут-то и пригодится divfetcht1/t2!
Размер загружаемых данных равен длине кэш-линеек соответствующей кэш-иерархии и составляют 32 байта ( в Plll и L2-, и L1- кэши имеют линейки по 32 байта).

 

Pentium 4

Ни одна из команд предвыборки Р4 не позволяет загружать данные в кэш первого уровня. Все – и временные, и не временные данные помещаются лишь в кэш второго уровня – создатели процессора решили поступить именно так. Эффективность такой стратегии не бесспорна, но в любом случае время доступа к кэшу второго уровня намного меньше времени доступа к оперативной памяти, поэтому даже такая предвыборка значительно лучше, чем ничего.
Возникает вопрос: если все команды предвыборки помещают загружаемые данные в кэш второго уровня, то какая между ними разница? Между командами divfetcht0, divfetcht1 и divfetcht2 – действительно никакой. А вот команда divfetchnta отличается тем, что помещает загружаемые данные не в любой, а исключительно в первый банк кэша второго уровня (восьми-ассоциативный L2-кэш Р4 содержит восемь таких банков), благодаря чему divfetchnta никогда не вытесняет более 1/8 объема кэша второго уровня. Однократно используемы данные, как уже говорилось выше, действительно не должны вытеснять многократно используемые данные из верхних кэш-иерархий, но в Р4 такое вытеснение все же происходит, и предотвратить его, увы, нельзя. Причем вытесняются отнюдь не те ячейки, к которым дольше всего не было обращений, а линейки фиксированного банка, возможно интенсивно используемые обрабатывающем их приложением! Словом, в Р4 программная предвыборка реализована далеко не наилучшим образом.
Размер загружаемых данных равен длине линеек кэша второго уровня, что составляет 128 байт.
Различия в реализации предвыборки на Р!!! и Р4 существенно затрудняют оптимизацию приложений, поскольку каждый процессор требует к себе индивидуального подхода. Для достижения максимальной эффективности все критические процедуры рекомендуется реализовывать как минимум в двух вариантах – отдельно для Р!!! и отдельно для Р4. В противном случае, либо Р!!! чрезвычайно тормозить, либо Р4 не раскроет подлинного потенциала своей производительности. Учитывая существование К6/Athlon, вариантов реализации набирается уже четыре. Не слишком ли много головной боли для программистов? Нет, это вовсе не призыв к отказу от предвыборки – ведь программисты, как и комсомольцы, легкими путями не избалованы.
Эффективность предвыборки в многозадачных системах
Процессы, исполняющиеся в многозадачных системах, владеют кэш-памятью не единолично, а вынуждены делить ее между собой? Снижает ли это эффективность предвыборки? Эффективность предвыборки в кэш первого уровня – однозначно нет. Промежуток времени между переключениями задач – это целая вечность для процессора, соответствующая, по меньшей мере, миллионам тактов. В любом случае, независимо от того, будет ли вытеснено содержимое L1-кэша или нет, - предвыборка позволяет конвейеризировать загрузку данных из памяти, предотвращая тем самым возможное падение производительности.
С L2-кэшем ситуация не так однозначна. Если оптимизируемый алгоритм позволяет распараллелить загрузку данных с их обработкой, то состояние L2-кэша вообще не играет никакой роли, поскольку быстродействие программы ограничивается именно скоростью вычислений, а не пропускной способностью подсистемной памяти. Однако если время обработки  данных меньше времени их загрузки из основной памяти, падения производительности никак не избежать. Предвыборка, конечно, увеличит производительность программы и в этом случае, но, увы, ненамного – максимум в два-три раза.
С другой стороны, одновременное выполнение двух или более приложений, интенсивно обменивающихся с памятью, на рабочих станциях случается очень редко (для серверов, правда, это – норма жизни). В большинстве случаев пользователь активно работает лишь с одним приложением, другие же находятся в фоне и довольствуются минимальным количеством памяти, а порой и вовсе «спят», не трогая L2-кэш и практически не снижая эффективности предвыборки.