Если таблица динамики переходов содержит, скажем, 4096 элементов, то адреса 0, 16384, 32768 и т. д. будут конфликтовать; аналогичная проблема встречается и при работе с кэш-памятью. Здесь возможно такое же решение: 2-альтерна-тивный, 4-альтернативный или гг-альтернативный ассоциативный элемент. Как и в случае кэш-памяти, предельный случай — один //-альтернативный ассоциативный элемент.
При достаточно большом размере таблицы и достаточной степени ассоциативности эта схема хорошо подходит для большинства ситуаций. Тем не менее систематически приходится сталкиваться с проблемой. При выходе из цикла переход предсказывается неправильно, и, что еще хуже, этот неправильный прогноз изменяет бит в таблице, который после этого будет показывать, что переход совершать не требуется. То есть в следующий раз, когда опять потребуется выполнять цикл, переход в конце первого прохода цикла окажется спрогнозированным неправильно. Если цикл находится внутри другого цикла или внутри часто вызываемой процедуры, эта ошибка будет повторяться достаточно часто.
Для решения проблемы можно немного изменить метод прогнозирования, чтобы прогноз менялся не после одного, а только после двух последовательных неправильных прогнозов. Такой подход требует наличия в таблице двух битов прогнозирования переходов (рис. 4.28, б): один должен указывать, предполагается совершать переход или нет, а второй — был сделан переход в прошлый раз или нет.
Этот алгоритм можно представить в виде конечного автомата с четырьмя состояниями (рис. 4.29). После ряда последовательных успешных прогнозов отсутствия перехода конечный автомат будет находиться в состоянии 00 и в следующий раз также покажет, что перехода нет.
Рис. 4.29. 2-разрядный конечный автомат для прогнозирования переходов
Если этот прогноз окажется неправильным, автомат перейдет в состояние 01, но в следующий раз он все равно покажет отсутствие перехода. Только в том
случае, если этот последний прогноз тоже окажется ошибочным, конечный автомат перейдет в состояние 11, прогнозируя наличие перехода. Фактически левый бит — это прогноз, а правый бит — то, что случилось в прошлый раз (то есть был ли переход). В данной разработке используются только 2 бита, но возможно применение и 4, и 8 бит.
Это не первый конечный автомат, который мы рассматриваем. На рис. 4.19 тоже изображен конечный автомат. На самом деле все наши микропрограммы можно считать конечными автоматами, поскольку каждая строка представляет особое состояние, в котором может находиться автомат, с четко определенными переходами к конечному набору других состояний. Конечные автоматы очень широко используются при разработке аппаратного обеспечения.
До сих пор мы предполагали, что цель каждого условного перехода известна. Обычно либо в явном виде давался адрес, к которому нужно перейти (он содержался непосредственно в команде), либо было известно смещение относительно текущей команды (то есть число со знаком, которое нужно было прибавить к счетчику команд). Часто это предположение имеет силу, но некоторые команды условного перехода вычисляют целевой адрес, предварительно выполняя определенные арифметические действия над значениями регистров. Даже если взять конечный автомат, изображенный на рис. 4.29, который точно прогнозирует переходы, прогноз окажется невостребованным, поскольку неизвестен целевой адрес. Один из возможных выходов из подобной ситуации — сохранить в таблице адрес, к которому был осуществлен переход в прошлый раз, как показано на рис. 4.28, е. Тогда, если в таблице указано, что в прошлый раз, когда встретилась команда перехода по адресу 516, переход был совершен к адресу 4000, целевым снова будет адрес 4000 (в случае, если предсказывается переход).