Реклама

Наш канал:

Таненбаум Э.- Архитектура компьютера. стр.238

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

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

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

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

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

Рис. 4.28. Таблица динамики ветвлений с одноразрядным указателем перехода (а); таблица динамики ветвлений с 2-разрядным указателем перехода (б); соответствие между адресом команды перехода и целевым адресом (в)

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