Boroda_2

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

Бит Бит Бит Бит

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

Использование ассоциативной кэш-памяти с множественным доступом ста­вит разработчика перед выбором. Если нужно поместить новый элемент в кэш­память, какой именно из старых элементов удалить? Для большинства задач хо­рошо подходит алгоритм обработки элемента, который дольше всего не исполь­зовался (Least Recenly Used, LRU). Имеется определенный порядок каждого набо­ра ячеек, доступных из данной ячейки памяти. Всякий раз, когда осуществляется доступ к любой строке, в соответствии с алгоритмом LRU список обновляется, и маркируется элемент, к которому произведено последнее обращение. Когда требуется заменить какой-нибудь элемент, удаляется тот, который находится в конце списка, то есть тот, который использовался раньше других.

Возможен также предельный случай — 2048-входовая ассоциативная кэш-па- мять, содержащая единственный набор из 2048 элементов. В данном случае все адреса памяти оказываются в этом наборе, поэтому при поиске требуется срав­нивать нужный адрес со всеми 2048 тегами в кэш-памяти. Отметим, что для это­го каждый элемент кэш-памяти должен содержать специальную логическую схе­му. Поскольку поле строки в данном случае нулевое, поле тега — это весь адрес за исключением полей слова и байта. Более того, когда строка кэша заменяется, возможными кандидатами на смену являются все 2048 элементов. Для хранения упорядоченного списка потребовался бы громоздкий учет использования сис­темных ресурсов, поэтому применение алгоритма LRU оказывается невозмож­ным. (Вспомните, что список требуется обновлять при каждой операции с памя­тью.) Интересно, что кэш-память с большим числом входов далеко не всегда превосходит по производительности кэш-память, в которой число входов неве­лико, а в некоторых случаях работает даже хуже. Поэтому число входов больше четырех встречается редко.

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

С процессом записи связана еще одна проблема: что происходит, если нужно записать что-либо в ячейку, которой нет в кэш-памяти? Должны ли данные пе­редаваться в кэш или просто записываться в основную память? И снова ни один из ответов не является во всех отношениях лучшим. В большинстве разработок, в которых применяется обратная запись, данные передаются в кэш-память. Эта технология называется заполнением по записи (write allocation). С другой сто­роны, в тех разработках, где применяется сквозная запись, элемент в кэш-память при записи обычно не помещается, поскольку это усложняет систему. Заполне­ние по записи полезно только в том случае, если имеют место повторные записи в одно и то же слово или в разные слова в пределах одной строки кэша.

Эффективность кэширования является крайне важным условием повышения общей производительности системы в силу огромного разрыва между быстро­действием процессора и памяти. Дискуссия об альтернативных стратегиях кэши­рования ведется постоянно [6, 96, 145, 149, 197].

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

Современные компьютеры в значительной степени конвейеризированы. Конвей­ер, изображенный на рис. 4.24, имеет семь ступеней; более сложно организован­ные компьютеры содержат конвейеры с десятью и более ступенями. Конвейери­зация лучше работает с линейным кодом, поэтому блок выборки команд может просто считывать последовательные слова из памяти и отправлять их в блок де­кодирования заранее, еще до того, как они понадобятся.

Единственная проблема состоит в том, что эта модель совершенно нереали­стична. Программы вовсе не являются линейными кодами. В них полно команд переходов. Рассмотрим простые команды листинга 4.4. Переменная i сравнива­ется с 0 (вероятно, на практике это самое распространенное сравнение). В зави­симости от результата другой переменной, к, присваивается одно из двух воз­можных значений.

Листинг 4.4. Фрагмент программы

if(i—0)

к=1;

else

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

Листинг 4.5. Программа из листинга 4.4 после трансляции на язык ассемблера

	CMP i, 0	: сравнение i с 0
	BNE Else	: переход к Else, если они не равны
Then:	MOV k, 1	: присваивание значения 1 переменной к
	BR Next	: безусловный переход к Next
Else: Next:	MOV k, 2	; присваивание значения 2 переменной к

Мы видим, что две из пяти команд являются командами перехода. Более то­го, одна из них, BNE, — это команда условного перехода (переход, который осуще­ствляется тогда и только тогда, когда выполняется определенное условие, в дан­ном случае — это равенство двух операндов предыдущей команды СМР). Самый длинный линейный код состоит здесь из двух команд, поэтому очень трудно ор­ганизовать высокоскоростной конвейер.

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

Сложность объясняется самой природой конвейера. На рис. 4.24, например, мы видим, что декодирование происходит на второй ступени. Следовательно, блоку выборки команд приходится решать, откуда вызывать следующую коман­ду еще до того, как он узнает, команду какого типа он только что вызвал. Только в очередном цикле он сможет выяснить, что получил команду безусловного пе­рехода, хотя еще до этого он вызывает команду, следующую за командой безус­ловного перехода. То есть в значительной части конвейеризированных машин (например, UltraSPARC III) сначала выполняется команда, следующая после ко­манды безусловного перехода, хотя по логике вещей так быть не должно. Пози­ция после перехода называется слотом отсрочки (delay slot). Pentium II (а также машина, используемая в листинге 4.5) не поддерживают слот отсрочки, а обойти эту проблему путем внутреннего усложнения часто сложно. Оптимизирующий компилятор постарается найти какую-нибудь полезную команду, чтобы помес­тить ее в слот отсрочки, но часто ничего подходящего нет, поэтому компилятор вынужден вставлять туда команду N0P. Хотя программа остается корректной, объем ее растет и работает она медленнее.

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

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

Со второй частью предположения дело обстоит сложнее. Некоторые переходы вперед осуществляются в случае обнаружения ошибки в программе (например, невозможность открытия файла). Ошибки случаются редко, поэтому в большин­стве случаев подобные переходы не происходят. Естественно, существует мно­жество переходов вперед, никак не связанных с ошибками, поэтому процент ус­пеха здесь не так высок, как в случае перехода назад. Однако это все же лучше, чем ничего.

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

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

Динамическое прогнозирование ветвлений

в

Ясно, что точные прогнозы очень ценны, поскольку позволяют процессору рабо­тать с полной скоростью. В настоящее время проводится множество исследова­ний, целью которых является усовершенствование алгоритмов прогнозирования ветвлений [41, 64, 103, 160]. Один из подходов — хранить (в особом устройстве) специальную таблицу, в которую центральный процессор будет записывать ус­ловные переходы, когда они встретятся. Если условный переход встретится сно­ва, его можно будет найти в этой таблице. Простейшая версия такой схемы пока­

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

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

Существует несколько вариантов организации данной таблицы. Фактически они полностью аналогичны вариантам организации кэш-памяти. Рассмотрим машину с 32-разрядными командами, которые расположены таким образом, что два младших бита каждого адреса памяти равны 00. Таблица содержит 2^п ячеек (строк). Из команды перехода можно извлечь п + 2 младших бита и осуществить сдвиг вправо на два бита. Это гг-разрядное число можно использовать в качестве индекса в таблице, проверяя, совпадает ли адрес, сохраненный там, с адресом пе­рехода. Как и в случае с кэш-памятью, здесь нет необходимости сохранять п + 2 младших бита, поэтому их можно опустить (то есть сохраняются только старшие адресные биты — тег). Если адреса совпали, бит прогнозирования используется для прогнозирования перехода. Если тег неправильный или элемент недействителен, значит, имеет место промах. В этом случае можно применять правило пе­рехода вперед/назад.

Если таблица динамики переходов содержит, скажем, 4096 элементов, то ад­реса 0, 16384, 32768 и т. д. будут конфликтовать; аналогичная проблема встреча­ется и при работе с кэш-памятью. Здесь возможно такое же решение: 2-альтерна- тивный, 4-альтернативный или w-альтернативный ассоциативный элемент. Как и в случае кэш-памяти, предельный случай — один //-альтернативный ассоциа­тивный элемент.

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

Для решения проблемы можно немного изменить метод прогнозирования, чтобы прогноз менялся не после одного, а только после двух последовательных неправильных прогнозов. Такой подход требует наличия в таблице двух битов прогнозирования переходов (рис. 4.28, б): один должен указывать, предполагает­ся совершать переход или нет, а второй — был сделан переход в прошлый раз или нет.

Этот алгоритм можно представить в виде конечного автомата с четырьмя со­стояниями (рис. 4.29). После ряда последовательных успешных прогнозов отсут­ствия перехода конечный автомат будет находиться в состоянии 00 и в следую­щий раз также покажет, что перехода нет.

Если этот прогноз окажется неправильным, автомат перейдет в состояние 01, но в следующий раз он все равно покажет отсутствие перехода. Только в том случае, если этот последний прогноз тоже окажется ошибочным, конечный авто­мат перейдет в состояние И, прогнозируя наличие перехода. Фактически левый бит — это прогноз, а правый бит — то, что случилось в прошлый раз (то есть был ли переход). В данной разработке используются только 2 бита, но возможно применение и 4, и 8 бит.

Это не первый конечный автомат, который мы рассматриваем. На рис. 4.19 то­же изображен конечный автомат. На самом деле все наши микропрограммы можно считать конечными автоматами, поскольку каждая строка представляет особое состояние, в котором может находиться автомат, с четко определенными переходами к конечному набору других состояний. Конечные автоматы очень широко используются при разработке аппаратного обеспечения.

До сих пор мы предполагали, что цель каждого условного перехода известна. Обычно либо в явном виде давался адрес, к которому нужно перейти (он содер­жался непосредственно в команде), либо было известно смещение относительно текущей команды (то есть число со знаком, которое нужно было прибавить к счетчику команд). Часто это предположение имеет силу, но некоторые команды условного перехода вычисляют целевой адрес, предварительно выполняя опре­деленные арифметические действия над значениями регистров. Даже если взять конечный автомат, изображенный на рис. 4.29, который точно прогнозирует пе­реходы, прогноз окажется невостребованным, поскольку неизвестен целевой ад­рес. Один из возможных выходов из подобной ситуации — сохранить в таблице адрес, к которому был осуществлен переход в прошлый раз, как показано на рис. 4.28, в. Тогда, если в таблице указано, что в прошлый раз, когда встретилась команда перехода по адресу 516, переход был совершен к адресу 4000, целевым снова будет адрес 4000 (в случае, если предсказывается переход).

Еще один подход к прогнозированию перехода — следить, были ли совершены последние k условных переходов независимо от того, какие это были команды. Это ^-разрядное число, которое хранится в сдвиговом регистре динамики перехо­дов, затем сравнивается параллельно со всеми элементами таблицы с ^-разрядным ключом, и в случае совпадения применяется тот прогноз, который найден в этом элементе. Удивительно, но эта технология работает достаточно хорошо.

Статическое прогнозирование ветвлений

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

Можно пойти другим путем, призвав на помощь компилятор. Обратите вни­мание на следующий оператор:

for (1=0; i < 1000000; i++) { ... }

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

Хотя такой подход связан с изменением архитектуры (а не только реали­зации), в некоторых машинах, например, UltraSPARC III, помимо обычных ко­манд условного перехода (которые нужны для обратной совместимости), имеется еще один набор команд. Новые команды содержат бит, по которому компилятор определяет, совершать переход или не совершать. Когда встречается такой бит, блок выборки команд просто делает то, что ему положено. Более того, нет необ­ходимости тратить драгоценное пространство в таблице динамики переходов для этих команд, что сокращает количество конфликтных ситуаций.

Наконец, наша последняя технология прогнозирования ветвлений основана на профилировании [65]. Это тоже статическая технология, только в данном случае программа не заставляет компилятор вычислять, какие переходы нужно совершать, а какие нет. Программа реально выполняется, а ветвления фиксиру­ются, эта информация поступает в компилятор, который затем использует спе­циальные команды условного перехода для того, чтобы сообщить аппаратуре, что нужно делать.

Исполнение с изменением последовательности и подмена регистров

Большинство современных процессоров являются и конвейеризированными и суперскалярными, как показано на рис. 2.5. Это означает, что имеется блок вы­борки команд (IFU), который заранее вызывает команды из памяти и передает их в блок декодирования. Блок декодирования, в свою очередь, передает декоди­рованные команды соответствующим функциональным блокам для выполнения. В некоторых случаях блок декодирования может разбивать отдельные команды на микрооперации перед тем, как отправить их функциональным блокам.

Ясно, что проще всего выполнять все команды в том порядке, в котором они вызываются из памяти (предполагается, что прогнозирование ветвлений всегда оказывается верным). Однако из-за взаимозависимости команд такое последова­тельное выполнение не всегда дает оптимальную производительность. Если ко­манде требуется значение, которое вычисляется предыдущей командой, вторая команда не сможет выполняться, пока первая не выдаст нужную величину. Та­ким образом, в ситуации реальной взаимозависимости второй команде прихо­дится ждать. Существуют и другие виды взаимозависимостей, но о них мы пого­ворим позже.

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

Чтобы изложить суть проблемы, начнем с машины, которая запускает коман­ды в том порядке, в котором они расположены в программе, и требует, чтобы вы­полнение команд также завершалось в порядке, соответствующем программно­му. Важность второго требования прояснится позднее.

Наша машина содержит 8 доступных программисту регистров, от R0 до R7. Все арифметические команды используют три регистра: два для операндов и один для результата, как и в микроархитектуре Mic-4. Мы предполагаем, что, если ко­манда декодируется в цикле п, выполнение начинается в цикле п + 1. В случае простой команды, например команды сложения или вычитания, запись обратно в выходной регистр происходит в конце цикла п + 2. В случае с более сложной командой, например командой умножения, запись в регистр происходит в конце цикла /2 + 3. Чтобы сделать наш пример реалистичным, мы позволим блоку деко­дирования выдавать до двух команд за цикл. Некоторые суперскалярные про­цессоры могут генерировать 4 или даже 6 команд за цикл.

Последовательность выполнения команд иллюстрирует табл. 4.11. В первом столбце приводится номер цикла, во втором — номер команды, в третьем — сама команда. В четвертом столбце показаны выданные команды (максимум две ко­манды за цикл). Цифры в пятом столбце сообщают, какие команды завершены. Помните, что в нашем примере мы требуем, чтобы команды и запускались, и за­вершались в строго определенном порядке, поэтому выдача команды k + 1 может произойти только после выдачи команды k, а результат команды k + 1 не может быть записан в выходной регистр до того, как завершится команда k. Оставшие­ся 16 столбцов мы обсудим позже.

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

Следить за состоянием регистров призвано специальное устройство — счет­чик обращений (scoreboard), впервые появившийся в системе CDC 6600. Для каждого регистра счетчик обращений содержит небольшую схему, которая под­считывает, сколько раз этот регистр используется выполняющимися командами в качестве источника. Если одновременно может выполняться максимум 15 ко­манд, будет достаточно 4-разрядного счетчика. Когда запускается команда, эле­менты счетчика обращений, соответствующие регистрам операндов, увеличива­ются на 1. Когда выполнение команды завершено, соответствующие элементы счетчика уменьшаются на 1.

Счетчик обращений содержит аналогичные схемы подсчета для целевых ре­гистров. Поскольку допускается только одна запись за раз, эти схемы могут быть размером в один бит. Правые 16 столбцов в табл. 4.11 демонстрируют показания счетчика обращений.

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

В первой строке табл. 4.11 представлена команда 1, которая перемножает зна­чения регистров R0 и R1 и помещает результат в регистр R3. Поскольку ни один из этих регистров еще не используется, команда запускается, а счетчик обраще­ний показывает, что регистры R0 и R1 считываются, а регистр R3 записывается.

Ни одна из последующих команд не может записывать результат в эти реги­стры и не может считывать регистр R3 до тех пор, пока не завершится выполне­ние команды 1. Поскольку это команда умножения, она закончится в конце цик­ла 4. Значения счетчика обращений, приведенные в каждой строке, отражают состояние регистров после запуска команды, записанной в этой же строке. Пус­тые клетки соответствуют значению 0.

Поскольку в качестве примера рассматривается суперскалярная машина, ко­торая может запускать две команды за цикл, вторая команда выдается также во время цикла 1. Она складывает значения регистров R0 и R2, а результат сохра­няет в регистре R4. Чтобы определить, можно ли запускать эту команду, приме­няются следующие правила:

1. Если какой-нибудь операнд записывается, запускать команду нельзя (RAW- взаимозависимость).

2. Если считывается регистр результатов, запускать команду нельзя (WAR- взаимозависимость).

3. Если записывается регистр результатов, запускать команду нельзя (WAW- взаимозависимость).

Мы уже рассматривали реальные взаимозависимости (RAW-взаимозависи- мости), имеющие место, когда команде в качестве источника нужно использо­вать результат предыдущей команды, которая еще не завершилась. Два других типа взаимозависимостей менее серьезные. По существу, они связаны с кон­фликтами ресурсов. При WAR-взаимозависимости (Write After Read — запись после чтения) одна команда пытается перезаписать регистр, который предыду­щая команда еще не закончила считывать. W AW-взаимозависимость (Write After Write — запись после записи) похожа на WAR-взаимозависимость. Подоб­ной взаимозависимости можно избежать, если вторая команда будет помещать результат где-либо в другом месте еще (возможно, временно). Если ни одна из трех упомянутых ситуаций не возникает и нужный функциональный блок дос­тупен, команду можно выдать. В этом случае команда 2 использует регистр R0, который в данный момент считывается незаконченной командой, но подобное перекрытие допустимо, поэтому команда 2 может запускаться. Сходным образом команда 3 запускается во время цикла 2.