К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 57
Текст из файла (страница 57)
3.)8. Ага! Вот он, "потерянный хвост Иа"! Если скоростная кривая чтения ячеек К (обозначается на рисунке цифрой 1) напоминает обветшалый и разрушенный эрозией старый пологий холм, то остальные кривые являют собой молодую горную формацию, непрерывно меняюшую крутизну своих склонов. Если присмотреться повнимательнее (впрочем, вряд ли вы что-то разглядите при печати такою качества), то можно заметить, что первый подъем расположен в районе 32 Кбайт.
Это и есть размер сверхоперативной памяти каша данных первого уровня микропроцессора АМ() Кб (кстати, неплохого, между прочим, процессора). Миновав кэш, график чтения начинает линейное восхождение вверх с коэффициентом пропорциональности, близким к единице, т. е.
на участке Кзш гВб (Е!.САСНЕ.ЯЕ; Е2.САСНЕ.Я1ХЕ) — время обработки блока в зависимости от его размера изменяется так: Т(яке(ВЕОСК1)) з!хе(ВЕОСК1) Т(яае(В1.ОСК2)) яае(В).ОСК2) ' где Т вЂ” время обработки. При выходе за пределы кэша первого уровня быстродействие программы резко и значительно сокращается, — действительно, "по горам лазать — это вам не по равнине налегке ходить" (кэш первого уровня — это "равнина"). Рис.
3.18. Зависимость времени обработки от размера блока (АкЛГЗ Кб! без вычета линейной составляющей Наклон графика чтения задирается кверху еще круче и визуально (то бишь субъективно) его коэффициент пропорциональное~и близко к полутора, а то и двум. Между тем, это — не более чем досадный обман зрения, и формула зависимости времени обработки от размеров записываемого блока идентична формуле чтения. Не верите? Так давайте проверим! Смотрите: обработка 89 Кбайт блока данных заняла 200 000 тактов процессора, а блок в гвв Глава 3 177 Кбайт обрабатывался бы 400 000 тактов.
А теперь — 89: 177 = 200 000: : 400 000 = 0,5, что и требовалось доказать! Увы, мы должны признать, что наглядность полученного нами графика оставляет желать лучшего. Причина в том, что он состоит из двух составляющих. Пинейный рост времени обработки возникает вследствие увеличения количества операций обращения к памяти. На него наложена пелинейпал составляющая, обусловленная непостоянством скорости доступа к различным видам памяти. Поскольку в данном случае нас интересует именно скоростной показатель доступа к памяти, а не общее время обработки блока данных, от линейной составляющей мы должны избавиться. Если не требуется большой точности вычислений, достаточно разделить результаты каждого замера на число итераций цикла.
В результате, форма полученного графика должна выглядеть приблизительно так, как на рис. 3.19. Рис. 3.19. Зависимость скорости обработки от размера блока иа АМ1З Кб В кеше первого уровня Смотрите (см. рис. 3.19): до тех пор, пока размер обрабатываемого блока не превышает размера кэш-памяти первого уровня (32 Кбайт для АМ13 Кб), все Кэш 287 четыре графика идут практически горизонтально, — т. е. скоростной показатель остается практически неизменным, причем сейчас, после удаления линейной составлявшей, это видно наглядно и нам уже не приходится вычислять коэффициент пропорциональности с линейкой и калькулятором в руках, Обратите внимание на небольшой "завал", расположенный в начале всех четырех графиков.
Как бы вы его интерпретировали? Конечно же, удельное время обработки блока не уменьшается с ростом его размера, — это сказываются неучтенные накладные расходы на замер времени выполнения цикла. Помимо этого, увеличенный масштаб графика (ведь мы собственноручно растянули его в сто раз по вертикали — зоо*к. сат (см. листинг Зд)) позволяет безо всякого труда установить, что запись ячеек памяти происходит в три раза быстрее чтения и в четыре раза быстрее чтения, следуюшего за записью.
Виною тому — накладные расходы на организацию цикла. Компилятор М1сгозой Нцша! С++ б.б, которым транслировалась тестовая программа, сумел распознать цикл записи и заменил его всего одной машинной командой: ввг зтозс, в то время как цикл чтения занял несколько машинных команд.
В зависимости от микроархитектуры процессора, обрашение к кэш-памяти может занимать от одного до трех тактов, а максимальное количество одновременно обрабатываемых ячеек варьируется от двух до четырех. Характеристики некоторых наиболее популярных процессоров приведены в табл. 3.4. Таблица а.4. Основные характеристики кэш-памяти некоторых моделей процессоров Как рассчитать реальное время доступа к ячейке? Давайте сделаем это на примере процессора АМР Кб. Только сначала уточним, что именно мы ус- Глава 3 2ВВ ловимся понимать под "реальным временем доступа". Графа "Латентность" сообщает количество тактов, прошедших с момента обращения к ячейке до завершения операции чтения (записи). В частности, операция чтения ячейки осуществляется за два этапа (также называемых стадиями): вычисление эффективного адреса и загрузка данных.
На АМП Кб каждый из этих этапов выполняется за один такт, и поэтому полное время чтения ячейки составляет два такта. Тем не менее, при отсутствии зависимости по данным процессор может приступать к загрузке следующей ячейки не через два такта, а всего лишь через один, ведь устройство вычисления эффективного адреса уже освободилось и к началу следующего такта вновь готово к работе! Таким образом, Х независимых ячеек могут быть прочитаны за и*тлкоичлрыс ч ьалеллу тактОв.
Очевидно, что при большом )ч величиной латентности можно полностью пренебречь, приняв среднее время доступа к ячейке в 1 такт на Кб и 0,5 таков на А1111оп (Акоп способен загружать две 32-битовых ячейки за такт), Правда тут есть одно "но". Параллельное выполнение команд осуществляется как минимум при наличии этих самых команд. В свернутом цикле вида: Го~~а=с; в < ВЬОСК Ззгс; а~+~ к+=о[ам происходит лишь одно обращение к памяти за каждую итерацию (при условии, что переменные е и . расположены в регистрах, конечно)„поэтому время выполнения данного цикла окажется значительно больше, чем к*тлеоччлгые ч ьаьенсу. Решение проблемы состОит в развороте цикла по крайней мере на две итерации.
Подробнее этот вопрос уже рассмотрен в равд. "Разворачивание циклов" главы 2, сейчас же нас больше интересует другой аспект, а именно: как изменится производительность при выходе за кэш первого уровня. Выход из кэшв первого уровня При выходе за границы кэш-памяти первого уровня все четыре кривые лавинообразно "взлетают" (см.
рис. 3.19), останавливаясь только тогда, когда размер обрабатываемого блока более чем в 1,5 раза превысит размер кэшпамяти первого уровня. Это обстоятельство слишком интересно, чтобы оставить его незамеченным. Почему именно полтора, а не, скажем, два или, на худой конец, три? На самом деле уже сам факт постепенного изменения скоростного показателя весьма знаменателен, ибо из самых общих рассуждений следует, что его градиент должен носить скачкообразный характер.
Рассмотрим полностью заполненный кэш и мысленно попытаемся загрузить еще одну кэш-строку. Для освобождения свободного места стратегия 1.К0 предписывает "вытолкнуть" наиболее "дряхлую" кэш-строку, к которой дольше всего не происходило обращений. При последовательной обработке блока памяти это будет самая первая строка. Да, именно та, с которой начнется обработка следующей итерации цикла! Кэш гВВ Поэтому в очередном проходе цикла первой кэш-строки там уже не окажется, и кэш-контроллер будет вынужден вновь обращаться к кэшу второю уровня, замещая самую "древнюю", на этот раз вторую по счету, строку (ведь свободных линеек в кэше по-прежнему нет!).
Соответственно, при обращении к следующей ячейке памяти ее вновь не окажется в кэше и кэшконтроллер будет вынужден перезагружать все кэш-строки по цепочке, работая "вхолостую". Поскольку каждое обращение к памяти сопровождается кэш-промахом, размер обрабатываемого блока уже не критичен — превосходит ли он размер кэш-памяти на одну, две или десять кэш-линеек — безразлично, ибо избыток всего в одну-единственную кэш-линейку уже не обеспечивает ни одного кэш-попадания, — худшего результата просто не бывает! Однако, вопреки всем доводам, полученный нами график с завидным упорством демонстрирует плавный, а отнюдь не скачкообразный градиент. Что это: ошибка эксперимента или ошибка рассуждений? Ошибка в рассуждениях действительно есть. Ведь вследствие ограниченной ассоциативности каша ячейки кэшируемой памяти связаны не с любыми, а со строго определенными кэш-строками.
Легче всего понять это обстоятельство на примере каша прямого отображения. Вообразим себе такой полностью заполненный кэш. При обращении к следующей ячейке кэш-котроллер загружает ее в кэш-строку под номером ~сасье эь~е+ы ъ саоье э~яе == 1. Затем, при следующем проходе цикла, перВая ячейка вновь идет в эту жв сомую строку (т. к, 1 $ сает э~ге == 1), а вовсе не в самую "древнюю" кэш-строку под "номером два". Да, строка "номер один" будет работать "вхолостую", но она не затронет всех остальных.
Соответственно, если размер обрабатываемого блока превышает размер кэш-памяти на две строки, то количество "холостых" кэш-линеек будет равно двум. Наконец, при обработке блока данных, вдвое превышающего размер сверхоперативной памяти, кэш будет работать полностью "вхолостую". В наборно-ассоциативном каше "насыщение" наступает гораздо раньше.
И не удивительно — ведь каждая ячейка кэшируемой памяти может претендовать на одну из нескольких кэш-строк. Рассмотрим кэш, состоящий из двух банков. При недостатке свободного места очередная считываемая ячейка идет в первую кэш-линейку первого банка, т. к. к ней дольше всего не было обращения, поэтому при следующем проходе цикла первой обрабатываемой ячейки в кэш-памяти уже не окажется и ее придется перезагружать за счет вытеснения первой кэш-линейки второго банка. В результате, "вхолостую" будет работать уже не одна, а целых две кэшлинейки и, если размер обрабатываемого блока превысит емкость кэш-памяти в полтора раза, кэш будет крутиться полностью "вхолостую".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
