Ответы 190 страниц, страница 7

A4 = B4+C4 A4 = B4+C4

A2 = A1+C2 A2 = (B1+C1)+ C2

позволит проводить вычисления без пропуска рабочих тактов для ожидания вычисления. Оптимизационные преобразования последовательности вычисления могут проводиться динамически, аппаратурой АЛУ, а также, в ряде случаев и статически проводиться системами программирования.

14. Спекулятивное выполнение команд

В конвейерных архитектурах устройство выборки команд является та­ким же конвейером, как и другие функциональные устройства. Так, для условного операторы: IF (A<B) GO TO L;S1;L:S2 еще до вычисления значе­ния условного выражения А<В необходимо решать задачу о заполнении кон­вейера команд кодами S1 или S2 – спекулятивного выполнения программы (чтобы не было пропуска тактов конвейе­ра из за неверно выбранной ветки, коды которой потребуется убирать из конвейера).

Механизмы предсказания переходов.

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

Аппаратный механизм учета вероятности перехода состоит из блока предсказания переходов. Этот блок, кроме (вместо) статически определенных предпочтений для ветвлений, имеет таблицу переходов, в которой хранится история переходов для каждого (в рамках объема таблицы) перехода программы. Большинства современных микропроцессоров обещают точ­ность предсказаний переходов этим способом выше 90%. Причина повышенного внимания к этому вопросу обусловлена большими за­держками, возникающими при неверном предсказании переходов, что грозит существенной потерей производительности. Используемые в микропроцессо­рах методы предсказания переходов, как уже было сказано, бывают стати­ческие и динамические. Как динамический, так и статический подходы имеют свои преимущества и недостатки.

Статические методы предсказания используются реже. Такие предска­зания делаются компилятором еще до момента выполнения программы. Соот­ветствующие действия компилятора можно считать оптимизацией программ. Такая оптимизация может основываться на сборе информации, получаемой при тестовом прогоне программы (Profile Based Optimisation, PBO) или на эвристических оценках. Результатом деятельности компилятора являются "советы о направлении перехода", помещаемые непосредственно в коды выполняемой программы. Эти советы использует затем аппаратура во время выполнения. В случае, когда переход происходит, или наоборот - как правило, не происходит, советы компилятора часто бывают весьма точны, что ведет к отличным результатам. Преимущество статического подхода - отсутствие необходимости интегрировать на чипе дополнительную аппаратуру предсказания переходов.

Большинство производителей современных микропроцессоров снабжают их различными средствами динамического предсказания переходов, производимого на базе анализа "предыстории". Тогда аппаратура собирает статистику переходов, которая помещается в таблицу истории переходов BHT (Branch History Tab­le).В обоих случаях компилятор не может выработать эффективные рекомендации на этапе трансляции программы. В то же время схемы динамического предсказания переходов легко справля­ются с такими задачами. В этом смысле динамическое предсказание пере­ходов "мощнее" статического. Однако у динамического предсказания есть и свои слабые места - это проблемы, возникающие из-за ограниченности ресурсов для сбора статистики .

Буфера прогнозирования условных переходов

Простейшей схемой динамического прогнозирования направления условных переходов является буфер прогнозирования условных переходов (branch-prediction buffer) или таблица "истории" условных переходов (branch history table). Буфер прогнозирования условных переходов представляет собой небольшую память, адресуемую с помощью младших разрядов адреса команды перехода. Каждая ячейка этой памяти содержит один бит, который говорит о том, был ли предыдущий переход выполняемым или нет. Это простейший вид такого рода буфера. В нем отсутствуют теги, и он оказывается полезным только для сокращения задержки перехода в случае, если эта задержка больше, чем время, необходимое для вычисления значения целевого адреса перехода. В действительности мы не знаем, является ли прогноз корректным (этот бит в соответствующую ячейку буфера могла установить совсем другая команда перехода, которая имела то же самое значение младших разрядов адреса). Но это не имеет значения. Прогноз - это только предположение, которое рассматривается как корректное, и выборка команд начинается по прогнозируемому направлению. Если же предположение окажется неверным, бит прогноза инвертируется. Конечно такой буфер можно рассматривать как кэш-память, каждое обращение к которой является попаданием, и производительность буфера зависит от того, насколько часто прогноз применялся и насколько он оказался точным.

Однако простая однобитовая схема прогноза имеет недостаточную производительность. Рассмотрим, например, команду условного перехода в цикле, которая являлась выполняемым переходом последовательно девять раз подряд, а затем однажды невыполняемым. Направление перехода будет неправильно предсказываться при первой и при последней итерации цикла. Неправильный прогноз последней итерации цикла неизбежен, поскольку бит прогноза будет говорить, что переход "выполняемый" (переход был девять раз подряд выполняемым). Неправильный прогноз на первой итерации происходит из-за того, что бит прогноза инвертируется при предыдущем выполнении последней итерации цикла, поскольку в этой итерации переход был невыполняемым. Таким образом, точность прогноза для перехода, который выполнялся в 90% случаев, составила только 80% (2 некорректных прогноза и 8 корректных). В общем случае, для команд условного перехода, используемых для организации циклов, переход является выполняемым много раз подряд, а затем один раз оказывается невыполняемым. Поэтому однобитовая схема прогнозирования будет неправильно предсказывать направление перехода дважды (при первой и при последней итерации).

Для исправления этого положения часто используется схема двухбитового прогноза. В двухбитовой схеме прогноз должен быть сделан неверно дважды, прежде чем он изменится на противоположное значение. На рисунке 5.27 представлена диаграмма состояний двухбитовой схемы прогнозирования направления перехода.

Двухбитовая схема прогнозирования в действительности является частным случаем более общей схемы, которая в каждой строке буфера прогнозирования имеет n-битовый счетчик. Этот счетчик может принимать значения от 0 до 2n - 1. Тогда схема прогноза будет следующей:

Если значение счетчика больше или равно 2n-1 (точка на середине интервала), то переход прогнозируется как выполняемый. Если направление перехода предсказано правильно, к значению счетчика добавляется единица (если только оно не достигло максимальной величины); если прогноз был неверным, из значения счетчика вычитается единица.

Если значение счетчика меньше, чем 2n-1, то переход прогнозируется как невыполняемый. Если направление перехода предсказано правильно, из значения счетчика вычитается единица (если только не достигнуто значение 0); если прогноз был неверным, к значению счетчика добавляется единица.

Исследования n-битовых схем прогнозирования показали, что двухбитовая схема работает почти также хорошо, и поэтому в большинстве систем применяются двухбитовые схемы прогноза, а не n-битовые.

Буфер прогнозирования переходов может быть реализован в виде небольшой специальной кэш-памяти, доступ к которой осуществляется с помощью адреса команды во время стадии выборки команды в конвейере (IF), или как пара битов, связанных с каждым блоком кэш-памяти команд и выбираемых с каждой командой. Если команда декодируется как команда перехода, и если переход спрогнозирован как выполняемый, выборка команд начинается с целевого адреса как только станет известным новое значение счетчика команд. В противном случае продолжается последовательная выборка и выполнение команд. Если прогноз оказался неверным, значение битов прогноза меняется в соответствии с рисунком 5.27. Хотя эта схема полезна для большинства конвейеров, рассмотренный нами простейший конвейер выясняет примерно за одно и то же время оба вопроса: является ли переход выполняемым и каков целевой адрес перехода (предполагается отсутствие конфликта при обращении к регистру, определенному в команде условного перехода. Напомним, что для простейшего конвейера это справедливо, поскольку условный переход выполняет сравнение содержимого регистра с нулем во время стадии ID, во время которой вычисляется также и эффективный адрес). Таким образом, эта схема не помогает в случае простых конвейеров, подобных рассмотренному ранее.

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

Управление виртуальной памятью.

Виртуальная память: основные концепции

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

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

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

Для установления соответствия между виртуальными и реальными адресами разработаны различные способы. Так, механизмы динамического преобразования адресов (DAT) обеспечивают преобразование виртуальных адресов в реальные во время выполнения процесса. Все подобные системы обладают общим свойством: смежные адреса виртуального адресного пространства процесса не обязательно будут смежными в реальной памяти, это свойство называют «искусственной смежностью» (рис. 8.3). Таким образом, пользователь освобождается от необходимости учитывать размещение своих процедур и данных в реальной памяти. Он получает возможность писать программы наиболее естественным образом, прорабатывая только детали алгоритма и структуры программы и игнорируя конкретные особенности структуры аппаратных средств, служащих для выполнения программы. При этом компьютер рассматривается (или может рассматриваться) только как логическое средство, обеспечивающее реализацию необходимых алгоритмов, а не как физическая машина с уникальными характеристиками, часть которых может лишь затруднить процесс проектирования программы.

8.4 Многоуровневая организация памяти

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

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

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

8.6 Страничная организация: основные концепции

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

Номер страницы p