Э. Таненбаум - Архитектура компьютера (1127755), страница 84
Текст из файла (страница 84)
Единственная проблема состоит в том, что эта модель совершенно нереалистична. Программы вовсе не являются линейными кодами. В них полно команд переходов. Рассмотрим простые команды листинга 4.4. Переменная 1 сравнивается с О (вероятно, на практике это самое распространенное сравнение). В зависимости от результата другой переменной, 1, присваивается одно из двух возможных значений. Листинг 4.4. Фрагмент программы 1ГИ==01 к=1; е1зе к=2. Повышение производительности 337 Возможный вариант трансляции на язык ассемблера показан в листинге 4.5.
Язык ассемблера мы будем рассматривать позже в этой книге, а сейчас достаточно знать, что программа, более или менее похожая на программу из листинга 4.5, вполне возможна. Первая команда сравнивает переменную з с нулем. Вторая совершает переход к предложению Е1 зе, если з не равно О. Третья команда присваивает значение 1 переменной И. Четвертая команда выполняет переход к следующему оператору программы. Компилятор поместил там метку Мехб. Пятая команда присваивает значение 2 переменной И.
Листинг 4.5. Программа из листинга 4.4 после трансляции на язык ассемблера СИР К О ; сравнение 1 с О ВИЕ Еззе , переход н Е1зе, если онн не равны Тбеп: ИОв' Е, 1 . прнсванванне значения 1 перененной В ВИ Иехг ; безусловный переход н Иенс ЕЗзе. ИОН Е. 2 . прнсванванне значения 2 перененной й Иенс: Мы видим, что две из пяти команд являются командами перехода. Более того, одна из них, ВМЕ, — это команда условного перехода (переход, который осуществляется тогда и только тогда, когда выполняется определенное условие, в данном случае — это равенство двух операндов предыдущей команды СМР). Самый длинный линейный код состоит здесь из двух команд, поэтому очень трудно организовать высокоскоростной конвейер. На первый взгляд может показаться, что безусловные переходы, например, команда ВИ Мехс в листинге 4.5, не влекут за собой никаких проблем.
Вообще говоря, в данном случае нет никакой двусмысленности в том, куда дальше идти. Почему же блок выборки команд не может просто продолжать считывать команды с целевого адреса (то есть с того места, куда осуществляется переход)? Сложность объясняется самой природой конвейера. На рис. 4.24, например, мы видим, что декодирование происходит на второй ступени. Следовательно, блоку выборки команд приходится решать, откуда вызывать следующую команду еще до того, как он узнает, команду какого типа он только что вызвал.
Только в очередном цикле он сможет выяснить, что получил команду безусловного перехода, хотя еще до этого он вызывает команду, следующую за командой безусловного перехода. То есть в значительной части конвейеризированных машин (например, П)гга5РАВС П1) сначала выполняется команда, следующая после команды безусловного перехода, хотя по логике вещей так быть не должно. Позиция после перехода называется слогом отсрочки (с1е1ау в!ос). Репйцш П (а также машина, используемая в листинге 4.5) не поддерживают слот отсрочки, а обойти эту проблему путем внутреннего усложнения часто сложно.
Оптимизирующий компилятор постарается найти какую-нибудь полезную команду, чтобы поместить ее в слот отсрочки, но часто ничего подходящего нет, поэтому компилятор вынужден вставлять туда команду МОР. Хотя программа остается корректной, объем ее растет и работает она медленнее. С условными переходами дело обстоит еще хуже. Во-первых, они тоже содержат слоты отсрочки, во-вторых, блок выборки команд узнает, откуда нужно считывать команду, гораздо позже.
Первые конвейеризированные машины просто простаивали, пока выяснялось, нужно совершать переход или нет. Простой по три или четыре цикла при каждом условном переходе, особенно если 20 Вхв 338 Глава 4. Уровень микроархитектуры команд являются командами условного перехода, значительно снижает производительность. Поэтому большинство машин прогнозируют, будет выполнен встретившийся условный переход или нет. Для этого, например, можно предполагать, что все условные переходы назад будут выполняться, а все условные переходы вперед нет. Что касается первой части предположения, то команды перехода назад обычно помещаются в конце циклов, а большинство циклов выполняются многократно, поэтому предположение о переходе к началу цикла чаще всего будет правильным.
Со второй частью предположения дело обстоит сложнее. Некоторые переходы вперед осушествляются в случае обнаружения ошибки в программе (например, невозможность открытия файла). Ошибки случаются редко, поэтому в большинстве случаев подобные переходы не происходят. Естественно, существует множество переходов вперед, никак не связанных с ошибками, поэтому процент успеха здесь не так высок, как в случае перехода назад. Однако это все же лучше, чем ничего. Если переход спрогнозирован правильно, то ничего особенного делать не нужно. Просто продолжается выполнение программы. Проблема возникает тогда, когда переход спрогнозирован неправильно.
Вычислить, куда нужно перейти, и перейти именно туда несложно. Самое сложное — отменить уже выполненные команды, которые не нужно было выполнять. Сугпествует два способа отмены команд. Первый способ — продолжать выполнять команды, вызванные после спрогнозированного условного перехода до тех пор, пока одна из этих команд не попытается изменить состояние машины (например, сохранить значение в регистре). Тогда вместо того, чтобы перезаписывать регистр, нужно поместить вычисленное значение во временный (скрытый) регистр, а затем, когда выяснится, что прогноз был правильным, просто скопировать это значение в обычный регистр.
Второй способ — сохранять (например, в скрытом временном регистре) значение любого регистра, который может быть переписан. В результате машина сможет вернуться в предыдущее состояние в случае неправильно спрогнозированного перехода. Реализация обоих подходов очень сложна и требует громоздкой системы учета использования системных ресурсов.
А если встретится второй условный переход еще до того, как станет известно, был ли правильно спрогнозирован первый условный переход, ситуация может совершенно запутаться. Динамическое прогнозирование ветвлений Ясно, что точные прогнозы очень ценны, поскольку позволяют процессору работать с полной скоростью. В настоящее время проводится множество исследований, целью которых является усовершенствование алгоритмов прогнозирования ветвлений [41, 64, 103, 1601 Один из подходов — хранить (в особом устройстве) специальную таблицу, в которую центральный процессор будет записывать условные переходы, когда они встретятся. Если условный переход встретится снова, его можно будет найти в этой таблице.
Простейшая версия такой схемы показана на рис. 4.28, а. В данном случае таблица содержит по одной ячейке для каждой команды условного перехода. В ячейке находится адрес команды перехо- Повышение производительности 339 да, а также бит, который указывает, произошел ли переход, когда эта команда встретилась в последний раз. Прогноз заключается в выборе того же пути, по ко- торому программа пошла в предыдущий раз при выполнении команды перехода. Если прогноз оказывается неправильным, бит в таблице меняется. Бит достоверности Бит достоверности Биты прогнозирования Адрес) перехода тег перехода Бит перехода Адрес/ тег перехода Спот Слог Бит достоверности Биты прогнозирования Спо Рис.
4.28. Таблица динамики ветвлений с одноразрядным указателем перехода (а); таблица динамики ветвлений с 2-разрядным указателем перехода (б); соответствие между адресом команды перехода и целевым адресом (в) Существует несколько вариантов организации данной таблицы. Фактически они полностью аналогичны вариантам организации кэш-памяти. Рассмотрим машину с 32-разрядными командами, которые расположены таким образом, что два младших бита каждого адреса памяти равны 00. Таблица содержит 2" ячеек (строк).
Из команды перехода можно извлечь п е 2 младших бита и осуществить сдвиг вправо на два бита. Это и-разрядное число можно использовать в качестве индекса в таблице, проверяя, совпадает ли адрес, сохраненный там, с адресом перехода. Как и в случае с кэш-памятью, здесь нет необходимости сохранять п + 2 младших бита, поэтому их можно опустить (то есть сохраняются только старшие адресные биты — тег). Если адреса совпали, бит прогнозирования используется для прогнозирования перехода. Если тег неправильный или элемент недействи- 340 Глава 4. Уровень микроархитектуры телен, значит, имеет место промах.
В этом случае можно применять правило перехода вперед/назад. Если таблица динамики переходов содержит, скажем, 4096 элементов, то адреса О, 16384, 32768 и т. д. будут конфликтовать; аналогичная проблема встречается и при работе с кэш-памятью. Здесь возможно такое же решение: 2-альтернативный, 4-альтернативный или и-альтернативный ассоциативный элемент. Как и в случае кэш-памяти, предельный случай — один и-альтернативный ассоциативный элемент. При достаточно большом размере таблицы и достаточной степени ассоциативности эта схема хорошо подходит для большинства ситуаций. Тем не менее систематически приходится сталкиваться с проблемой. При выходе из цикла переход предсказывается неправильно, и, что еще хуже, этот неправильный прогноз изменяет бит в таблице, который после этого будет показывать, что переход совершать не требуется.
То есть в следующий раз, когда опять потребуется выполнять цикл, переход в конце первого прохода цикла окажется спрогнозированным неправильно. Если цикл находится внутри другого цикла или внутри часто вызываемой процедуры, эта ошибка будет повторяться достаточно часто. Для решения проблемы можно немного изменить метод прогнозирования, чтобы прогноз менялся не после одного, а только после двух последовательных неправильных прогнозов. Такой подход требует наличия в таблице двух битов прогнозирования переходов (рис. 4.28, б): один должен указывать, предполагается совершать переход или нет, а второй — был сделан переход в прошлый раз или нет. Этот алгоритм можно представить в виде конечного автомата с четырьмя состояниями (рис. 4.29).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
