Сокращение потерь на выполнение команд перехода и минимизация конфликтов по управлению
Конфликты по управлению могут вызывать даже большие потери производительности конвейера, чем конфликты по данным. Когда выполняется команда условного перехода, она может либо изменить, либо не изменить значение счетчика команд. Если команда условного перехода заменяет счетчик команд значением адреса, вычисленного в команде, то переход называется выполняемым; в противном случае, он называется невыполняемым.
№ такта | |||||||||
Команда ветвления | IF | ID | RD | EX | WR | ||||
ëВычисление адреса следующей команды | |||||||||
Следующая команда | * | * | * | IF | ID | RD | EX | WR |
Рис. 29 простой процессора из-за конфликта по управлению
Простейший метод работы с условными переходами заключается в приостановке конвейера, как только обнаружена команда условного перехода до тех пор, пока она не достигнет ступени конвейера, которая вычисляет новое значение счетчика команд (рисунок 29). Например, если конвейер будет приостановлен на три такта на каждой команде условного перехода, то это может существенно отразиться на производительности машины. Если частота команд условного перехода достигает в среднем 15 – 20 %, и каждая команда выполняется ровно за один такт, то описанная нами ЭВМ с простейшим конвейером будет терять за счет условных переходов до 50% прироста производительности, полученного за счет конвейеризации. Машины с длинными конвейерам могут иметь существенно большие потери производительности, чем наша простейшая ЭВМ. Потери могут составлять шесть или семь тактов для каждой команды условного перехода. Можно уменьшить потери либо если вычислить новое значение программного счетчика как можно раньше, либо, если как можно раньше предсказать, будет ли условный переход выполняемым или невыполняемым. Машины, в которых выполнение большинства команд длится более одного такта, будут иметь меньшие потери от условных переходов.
Каким образом можно снизить потери на выполнение команд условного перехода? Начнем с простейших, статических методов, которых прогнозируемое направление заранее фиксируется для каждой команды.
Выжидание. Простейшая схема обработки команд условного перехода заключается в замораживании или подавлении операций в конвейере, путем блокировки выполнения любой команды, следующей за командой условного перехода, до тех пор, пока не станет известным направление перехода. Приведенный выше рисунок отражал именно такой подход. Привлекательность такого решения заключается в его простоте.
Возврат. Более хорошая и не намного более сложная схема состоит в том, чтобы прогнозировать условный переход как невыполняемый. При этом аппаратура должна просто продолжать выполнение программы, как если бы условный переход вовсе не выполнялся. В этом случае необходимо позаботиться о том, чтобы не изменить состояние машины до тех пор, пока направление перехода не станет окончательно известным. В некоторых машинах эта схема с невыполняемыми по прогнозу условными переходами реализована путем продолжения выборки команд, как если бы условный переход был обычной командой. Поведение конвейера выглядит так, как будто ничего необычного не происходит. Однако если условный переход на самом деле выполняется, то необходимо просто очистить конвейер от команд, выбранных вслед за командой условного перехода и заново повторить выборку команд.
Альтернативная схема прогнозирует переход как выполняемый. Как только команда условного перехода декодирована и вычислен целевой адрес перехода, мы предполагаем, что переход выполняемый, и осуществляем выборку команд и их выполнение, начиная с целевого адреса. Если мы не знаем целевой адрес перехода раньше, чем узнаем окончательное направление перехода, у этого подхода нет никаких преимуществ. Если бы условие перехода зависело от непосредственно предшествующей команды, то произошла бы приостановка конвейера из-за конфликта по данным для регистра, который является условием перехода, и мы бы узнали сначала целевой адрес. В таких случаях прогнозировать переход как выполняемый было бы выгодно.
Выполнение по предположению. Можно считать разновидностью предыдущего способа. При этом подходе переход, выполняющийся вперед по программе, считается невыполняеым, а переход назад по программе, наоборот, выполняемым. Подход основывается на разумном предположении, что команда условного перехода чаще всего встречается в начале или в конце цикла. При этом условный переход вперед в начале цикла осуществляет выход из цикла, и в большинстве случаев он не будет выполняться. Аналогично условный переход в конце цикла проверяет условие завершения цикла и чаще выполняется.
Задержанные переходы.Четвертая схема, которая используется в некоторых машинах, называется "задержанным переходом". Смысл подхода состоит в том, чтобы во время задержки, вызванной командой условного перехода, выполнить команду, которая не зависит от направления условного перехода. Это может быть команда, находящаяся в программе перед условным переходом или команда, которая должна будет выполняться после условной конструкции. Естественно, что выбирать команду необходимо так, чтобы избежать возможных конфликтов по данным.
Динамическое аппаратное прогнозирование переходов. Для предсказания переходов используется аппаратная конструкция, которая называется буфером предсказания переходов. Конструкция этого устройства напоминает кэш-память. В буфере хранятся адреса встретившихся в программе команд условных переходов. Для каждой команды хранится информация об истории перехода. В простейшем случае это однобитный признак, который устанавливается, когда переход выполнялся. Если переход выполнялся при предыдущем выполнении, то предполагается, что он выполнится и в следующий раз. Предположим, что исследуемая команда условного перехода выполняется в конце цикла из пяти итераций. Если этот цикл уже однажды выполнился, то однобитный флаг истории переходов будет сброшен, поскольку в последнем проходе цикла заключительная команда условного перехода была не выполнена. Если фрагмент программы, содержащий указанный цикл опять начнет выполняться, то при первом проходе по циклу переход будет предсказываться как не выполняемый и предсказание будет ошибочным. При последнем проходе цикла переход по однобитному признаку ошибочно будет предсказываться как выполняемый. Таким образом, для однобитного счетчика истории переходов в цикле из пяти итераций будет происходить 20% ошибочных предсказаний.
Более эффективным является n-битный счетчик истории переходов. Он может находиться в одном из 2n возможных состояний. Если счетчик переходов содержит значение от 0 до 2n-1 – 1, то переход предсказывается как не выполняемый, иначе как выполняемый. Если переход выполняется, то к содержимому счетчика прибавляется 1, иначе из содержимого счетчика вычитается 1. Чаще всего на практике используются 2-х битные счетчики истории переходов. Как показывает опыт, эффективность подобных схем с n-битными счетчиками незначительно возрастает по сравнению с 2-х битными счетчиками. Диаграмма состояний счетчика показана на рис. 30.
Рассмотрим поведение такого счетчика истории переходов для цикла описанного выше. Независимо от первоначального состояния счетчика максимум после 3 итераций счетчик придет в состояние 11. Переход будет уверенно предсказываться как выполняемый. При последней итерации цикла переход будет предсказан как выполняемый, однако он не выполнится. Счетчик перейдет в состояние 10. Если фрагмент программы, содержащий цикл начнет выполняться повторно, то при первой же итерации переход будет правильно предсказан как выполняемый. С учетом этого вероятность неправильного предсказания для цикла с пятью итерациями составит всего 10%.
Адрес команды перехода | Целевой адрес | История перехода |
Рис. 31. Структура буфера целевых адресов переходов
Буфер целевых адресов переходов. Дальнейшее повышение эффективности схемы предсказания переходов возможно при наличии буфера целевых адресов переходов. Схема буфера показана на рис. 31. Буфер хранит адреса команд перехода, счетчики истории перехода и целевые адреса перехода, вычисленные при последнем выполнении команды условного перехода. Благодаря хранению вычисленного целевого адреса перехода можно избежать накладных расходов на вычисление адреса и, тем самым, ускорить выполнение программы.
Дата добавления: 2021-02-19; просмотров: 340;