Сокращение потерь на выполнение команд перехода и минимизация конфликтов по управлению

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

№ такта
Команда ветвления	IF	ID	RD	EX	WR
				ëВычисление адреса сле­дующей команды
Следующая команда		*	*	*	IF	ID	RD	EX	WR

Рис. 29 простой процессора из-за конфликта по управлению

Простейший метод работы с условными переходами заключается в приостановке конвейера, как только обнаружена команда услов­ного перехода до тех пор, пока она не достигнет ступени конвейера, которая вычисляет новое значение счетчика команд (рисунок 29). Например, если конвейер будет приостановлен на три такта на каж­дой команде условного перехода, то это может существенно отра­зиться на производительности машины. Если частота команд услов­ного перехода достигает в среднем 15 – 20 %, и каждая команда вы­полняется ровно за один такт, то описанная нами ЭВМ с простей­шим конвейером будет терять за счет условных переходов до 50% прироста производительности, полученного за счет конвейеризации. Машины с длинными конвейерам могут иметь существенно боль­шие потери производительности, чем наша простейшая ЭВМ. По­тери могут составлять шесть или семь тактов для каждой команды условного перехода. Можно уменьшить потери либо если вычис­лить новое значение программного счетчика как можно раньше, либо, если как можно раньше предсказать, будет ли условный пере­ход выполняемым или невыполняемым. Машины, в которых выпол­нение большинства команд длится более одного такта, будут иметь меньшие потери от условных переходов.

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

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

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

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

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

Задержанные переходы.Четвертая схема, которая используется в некоторых машинах, называется "задержанным переходом". Смысл подхода состоит в том, чтобы во время задержки, вызванной командой условного перехода, выполнить команду, которая не зави­сит от направления условного перехода. Это может быть команда, находящаяся в программе перед условным переходом или команда, которая должна будет выполняться после условной конструкции. Естественно, что выбирать команду необходимо так, чтобы избе­жать возможных конфликтов по данным.

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

Более эффективным является n-битный счетчик истории перехо­дов. Он может находиться в одном из 2ⁿ возможных состояний. Если счетчик переходов содержит значение от 0 до 2^n-1 – 1, то переход предсказывается как не выполняемый, иначе как выполняемый. Если переход выполняется, то к содержимому счетчика прибавля­ется 1, иначе из содержимого счетчика вычитается 1. Чаще всего на практике используются 2-х битные счетчики истории переходов. Как показывает опыт, эффективность подобных схем с n-битными счетчиками незначительно возрастает по сравнению с 2-х битными счетчиками. Диаграмма состояний счетчика показана на рис. 30.

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

Адрес команды перехода	Целевой адрес	История перехода

Рис. 31. Структура буфера целевых адресов переходов

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