Файл: Tannenbaum.pdf

298 Глава 4. Микроархитектурный уровень

Когда центральный процессор выдает адрес памяти, аппаратное обеспечение

выделяет из этого адреса 11 битов поля «СТРОКА» и использует их для поиска
в кэш-памяти одного из 2048 элементов. Если этот элемент действителен, то про-
изводится сравнение поля «Тег» основной памяти и поля «Тег» кэш-памяти. Если

юля равны, это значит, что в кэш-памяти есть слово, которое запрашивается. Такая
:итуация называется

 удачным обращением в кэш-память. В

 случае удачного обра-

дения слово берется прямо из кэш-памяти, и тогда не нужно обращаться к основ-
ной памяти. Из элемента кэш-памяти берется только нужное слово. Остальная часть
элемента не используется. Если элемент кэш-памяти недействителен (недостове-
рен) или поля «Тег» не совпадают, то нужного слова нет в памяти. Такая ситуация
называется

 промахом кэш-памяти.

 В этом случае 32-байтная строка вызывается

-13 основной памяти и сохраняется в кэш-памяти, заменяя тот элемент, который
гам был. Однако если существующий элемент кэш-памяти изменяется, его нужно
тписать обратно в основную память до того, как он будет отброшен.

Несмотря на сложность решения, доступ к нужному слову может быть чрезвы-

1айно быстрым. Поскольку известен адрес, известно и точное нахождение слова,

'.ели оно имеется в кэш-памяти.

 Это значит, что можно считывать слово из кэш-

тамяти и доставлять его процессору и одновременно с этим устанавливать, пра-
вильное ли это слово (путем сравнения полей «Тег»), Поэтому процессор в дей-
ствительности получает слово из кэш-памяти одновременно или даже до того, как
станет известно, требуемое это слово или нет.

При такой схеме последовательные строки основной памяти помещаются в пос-

1едовательные элементы кэш-памяти. Фактически в кэш-памяти может хранить-
ся до 64 Кбайт смежных данных. Однако две строки, адреса которых различаются
ювно на 64 К (65, 536 байт) или на любое целое кратное этому числу, не могут
>дновременно храниться в кэш-памяти (поскольку они имеют одно и то же значе-
ние в поле «СТРОКА»). Например, если программа обращается к данным с адре-
сом X, а затем выполняет команду, которой требуются данные с адресом Х+ 65,
536 (или с любым другим адресом в той же строке), вторая команда требует пере-
1агрузки элемента кэш-памяти. Если это происходит достаточно часто, то могут
возникнуть проблемы. В действительности, если кэш-память плохо работает, то
тучше бы вообще не было кэш-памяти, поскольку при каждой операции с памя-
тью считывается целая строка, а не одно слово.

Кэш-память прямого отображения — это самый распространенный тип кэш-

тамяти, и она достаточно эффективна, поскольку коллизии, подобные описанной
выше, случаются крайне редко

1

 или вообще не случаются. Например, очень хоро-

пий компилятор может учитывать подобные коллизии при размещении команд и
щнных в памяти. Отметим, что указанный выше случай не произойдет в системе,
•де команды и данные находятся раздельно, поскольку конфликтующие запросы
>удут обслуживаться разными блоками кэш-памяти. Таким образом, мы видим
второе преимущество наличия двух блоков кэш-памяти вместо одного: большая
'ибкость при разрешении конфликтных ситуаций.

На самом деле подобные коллизии не столь уж и редки из-за TOI О, ЧТО при страничном способе орга-

низации виртуальной памяти и организации параллельного выполнения нескольких задач страницы
как бы «перемешиваются». Разбиение программы на страницы осуществляется случайным образом,
поэтому и «локальность кода» может быть нарушена. —

 Примеч. научн. ред.

Увеличение производительности

299

Ассоциативная кэш-память с множественным доступом

Как было сказано выше, различные строки основной памяти конкурируют за право

занять одну и ту же область в кэш-памяти. Если программе, которая применяет кэш-

память, изображенную на рис. 4.26, а, часто требуются слова с адресами 0 и 65 536,

то будут иметь место постоянные конфликты и каждое обращение потенциально

повлечет за собой вытеснение какой-то определенной строки кэш-памяти. Чтобы
разрешить эту проблему, нужно сделать так, чтобы в каждом элементе кэш-памя-

ти помещалось по две и более строк. Кэш-память с п возможными элементами для

каждого адреса называется

 n-входовой ассоциативной кэш-памятью.

 Четырех-

входовая ассоциативная кэш-память изображена на рис. 4.27.

Бит

достоверности

Бит

достоверности

Бит

достоверности

Бит

достоверности

2047

-

7
6

5

4
3
2

1

0

1

Тег

Данные

1

Тег

Данные

\

Тег

Данные

\

Тег

t ',

Данные

Элемент А Элемент В Элемент С Элемент D

Рис. 4.27.

 Четырехвходовая ассоциативная кэш-память

Ассоциативная кэш-память с множественным доступом по сути гораздо слож-

нее, чем кэш-память прямого отображения, поскольку хотя элемент кэш-памяти

 и

можно вычислить из адреса основной памяти, требуется проверить п элементов

кэш-памяти, чтобы узнать, есть ли там нужная нам строка. Тем не менее практи-
ка показывает, что двувходовая или четырехвходовая ассоциативная кэш-память
дает хороший результат, поэтому внедрение этих дополнительных схем вполне

оправданно.

Использование ассоциативной кэш-памяти с множественным доступом ставит

разработчика перед выбором. Если нужно поместить новый элемент в кэш-память,
какой именно из старых элементов нужно убрать? Для многих целей хорошо под-
ходит алгоритм

 LRU (Least Recenly Used — алгоритм удаления наиболее давно

использовавшихся элементов).

 Имеется определенный порядок каждого набора

ячеек, которые могут быть доступны из данной ячейки памяти. Всякий раз, когда

осуществляется доступ к любой строке, в соответствии с алгоритмом список об-

новляется и маркируется элемент, к которому произведено последнее обращение.

Когда требуется заменить какой-нибудь элемент, убирается тот, который находится

в конце списка, то есть тот, который использовался давно по сравнению со всеми
другими.

3 0 0 Глава 4. Микроархитектурный уровень

Возможна также 2048-входовая ассоциативная кэш-память, которая содержит

один набор из 2048 элементов. Здесь все адреса памяти располагаются в этом на-

боре, поэтому при поиске требуется сравнивать нужный адрес со всеми 2048 тега-
ми

 в

 кэш-памяти. Отметим, что для этого каждый элемент кэш-памяти должен

содержать специальную логическую схему. Поскольку поле «СТРОКА» в данный
момент имеет длину 0, поле «ТЕГ» — это весь адрес за исключением полей «СЛОВО»
и «БАЙТ». Более того, когда строка кэш-памяти замещается, все 2048 ячеек явля-
ются возможными кандидатами на смену. Для сохранения упорядоченного списка
потребовался бы громоздкий учет использования системных ресурсов, поэтому
применение алгоритма LRU становится недопустимым. (Помните, что этот спи-

сок следует обновлять при каждой операции с памятью.) Интересно, что кэш-па-

мять с высокой ассоциативностью часто не сильно превосходит по производитель-

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

Наконец, особой проблемой для кэш-памяти является запись. Когда процессор

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

того момента, когда строка кэш-памяти будет готова к замене алгоритмом LRU.

Выбор труден, и ни одно из решений не является предпочтительным. Немедленное

обновление элемента основной памяти называется

 сквозной записью.

 Этот под-

ход обычно гораздо проще реализуется, и к тому же, он более надежен, поскольку
современная память всегда может восстановить предыдущее состояние, если про-

изошла ошибка. К сожалению, при этом требуется передавать больший поток ин-

формации к памяти, поэтому в более сложных проектах стремятся использовать
альтернативный подход —

 обратную

 запись.

С процессом записи связана еще одна проблема: а что происходит, если нужно

записать что-либо в ячейку, которая в текущий момент не находится в кэш-памя-

ти? Должны ли данные переноситься в кэш-память или просто записываться в ос-
новную память? И снова ни один из ответов не является во всех отношениях луч-
шим. В большинстве разработок, в которых применяется обратная запись, данные
переносятся в кэш-память. Эта технология называется

 заполнением по записи

(write allocation). С другой стороны, в тех разработках, где применяется сквозная

запись, обычно элемент в кэш-память при записи не помещается, поскольку эта

возможность усложняет разработку. Заполнение по записи полезно только в том

случае, если имеют место повторные записи в одно и то же слово или в разные

слова в пределах одной строки кэш-памяти.

Прогнозирование ветвления

Современные компьютеры сильно конвейеризированы. Конвейер, изображенный

на рис. 4.25, имеет семь стадий; более сложно организованные компьютеры содер-
жат конвейеры с десятью и более стадиями. Конвейеризация лучше работает с

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

Увеличение производительности

 301

Единственная проблема состоит в том, что эта модель совершенно не реали-

стична. Программы вовсе не являются последовательностями линейного кода.

В них полно команд перехода. Рассмотрим простые утверждения листинга 4.4.
Переменная i сравнивается с 0 (вероятно, это самый распространенный тест на

практике). В зависимости от результата другой переменной, к, присваивается одно

из двух возможных значений.

Листинг 4.4.

 Фрагмент программы

i f (1—0)

к-1,

else

к=2:

Возможный перевод на язык ассемблера показан в листинге 4.5. Язык ассемб-

лера мы будем рассматривать позже в этой книге, и детали сейчас не важны, но
при определенных машине и компиляторе программа, более или менее похожая
на программу листинга 4.5, вполне возможна. Первая команда сравнивает пере-
менную i с 0. Вторая совершает переход к Else, если i не равно 0. Третья команда
присваивает значение 1 переменной к. Четвертая команда совершает переход к
следующему высказыванию программы. Компилятор поместил там метку Next.

Пятая команда присваивает значение 2 переменной к.

Листинг 4.5.

 Перевод программы листинга 4.4 на язык ассемблер

СМР 1. О . сравнение i с О

переход к Else, если они не равны

присваивание значения 1 переменной к

безусловный переход к Next

присваивание значения 2 переменной

 к

Мы видим, что две из пяти команд являются переходами. Более того, одна из

них, BNE, — это условный переход (переход, который осуществляется тогда и толь-

ко тогда, когда выполняется определенное условие, в данном случае это равенство
цвух операндов предыдущей команды СМР). Самый длинный линейный код состо-

ит здесь из двух команд. Вследствие этого вызывать команды с высокой скорос-

тью для передачи в конвейер очень трудно.

На первый взгляд может показаться, что безусловные переходы, например ко-

манда BR Next в листинге 4.5, не влекут за собой никаких проблем. Вообще говоря,
в данном случае нет никакой двусмысленности в том, куда дальше идти. Почему
же блок выборки команд не может просто продолжать считывать команды из це-
левого адреса (то есть из того места, куда будет затем осуществлен переход)?

Сложность объясняется самой природой конвейеризации. На рис. 4.23, на-

пример, мы видим, что декодирование происходит на второй стадии. Следователь-
но, блоку выборки команд приходится решать, откуда вызывать следующую ко-
манду еще до того, как он узнает, команду какого типа он только что вызвал. Только
в следующем цикле он сможет узнать, что получил команду безусловного перехода,
и до этого момента он уже начал вызывать команду, следующую за безусловным
переходом. Вследствие этого существенная часть конвейеризированных машин
(например, UltraSPARC II) обладает таким свойством, что сначала выполняется

команда,

 следующая после

 безусловного перехода, хотя по логике вещей этого не

Then

Else
Next

BNE

MOV

BR

MOV

Else
k. 1

Next

к 2

3 0 2 Глава 4. Микроархитектурный уровень

должно быть. Позиция после перехода называется отсрочкой ветвления. Pentium II

(а также машина, используемая в листинге 4.5) не обладает таким качеством, но
обойти эту проблему путем усложнения внутреннего устройства чрезвычайно тя-

жело. Оптимизирующий компилятор постарается найти какую-нибудь полезную

команду, чтобы поместить ее в отсрочку ветвления, но часто ничего подходящего
нет, поэтому компилятор вынужден вставлять туда команду NOP. Это сохраняет
правильность программы, но зато программа становится больше по объему и рабо-
тает медленнее.

С условными переходами дело обстоит еще хуже. Во-первых, они тоже содер-

жат отсрочки ветвления, а во-вторых, блок выборки команд узнает, откуда нужно
считывать команду, гораздо позже. Первые конвейеризированные машины просто
простаивали до тех пор, пока не становилось известно, нужно ли совершать пере-
ход или нет. Простаивание по три или четыре цикла при каждом условном перехо-

де, особенно если 20% команд являются условными переходами, сильно снижает

производительность.

Поэтому большинство машин прогнозируют, будет производиться условный

переход, который встретился на пути, или нет. Для этого, например, можно пред-
полагать, что все условные переходы назад будут осуществляться, а все условные
переходы вперед не будут. Что касается первой части предположения, причина

такого выбора состоит в том, что переходы назад часто помещаются в конце цикла.

Большинство циклов выполняется много раз, поэтому переход к началу цикла бу-

дет встречаться очень часто.

Со второй частью данного предположения дело обстоит сложнее. Некоторые

переходы вперед осуществляются в случае обнаружения ошибки в программном

обеспечении (например, файл не может быть открыт). Ошибки случаются редко,

поэтому в большинстве случаев подобные переходы не происходят. Естественно,

существует множество переходов вперед, не связанных с ошибками, поэтому про-

цент успеха здесь не так высок, как в переходах назад. Однако это правило по край-
ней мере лучше, чем ничего.

Если переход правильно предсказан, то ничего особенного делать не нужно.

Просто продолжается выполнение программы. Проблема возникает в том случае,

когда переход предсказан неправильно. Вычислить, куда нужно перейти, и перей-
ти именно туда несложно. Самое сложное — отменить команды, которые уже вы-
полнены, но которые не нужно было выполнять.

Существует два способа отмены команд. Первый способ — продолжать выпол-

нять команды, вызванные после спрогнозированного условного перехода, до тех

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

временный регистр), поэтому машина может вернуться в предыдущее состояние
в случае неправильно предсказанного перехода. Реализация обоих способов очень
сложна и требует громоздкого учета использования системных ресурсов. А если
встречается второй условный переход до того, как стало известно, был ли первый

условный переход предсказан правильно, все может совершенно запутаться.