А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 174
Текст из файла (страница 174)
Биты незавершенного обращения к памяти Еше одна архитектурная особенность, именуемая роиол (лезз, разработана для упреждаюшей загрузки памяти в регистр. Каждый регистр машины снабжен дополнительным битом незавершенности обращения к памяти. Если выполнено обращение к памяти по некорректному адресу или соответствующей страницы нет в памяти, процессор не генерирует исключение, а просто устанавливает бит незавершенного обращения к памяти целевого регистра. Исключение генерируется только при использовании содержимого регистра с установленным битом незавершенною обращения к памяти. Предикатное выполнение Из-за высокой стоимости операций ветвления и еше более высокой стоимости ошибки в предсказании ветвления (см.
раздел 10.1) для снижения количества ветвлений в программе были разработаны лредикалтвые команды (ргес(1са1ес( (пз1гцсбопа). Предикатные команды похожи на обычные, но содержат дополнительный предикатный операнд; команда выполняется, только если предикат является истинным. В качестве примера приведем команду СМОЧЕ й2, йЗ, й1, семантика которой заключается в перемещении содержимого регистра йЗ в регистр Р2 только в том случае, когда регистр Р,1 содержит нулевое значение. Код наподобие 1й (а == О) Ь=с+с( в предположении, что переменные а, б, с и е( размещены в регистрах й1, й2, й4 и Гя5 соответственно, может быть реализован машинными командами А1Ю ГсЗ, й4, Гт5 СМОЧ2 Н2, НЗ,И.
Такое преобразование заменяет последовательность команд с зависимостями по управлению командами с зависимостями только по данным. Затем такие команды могут быль объединены с соседними базовыми блоками в базовый блок большею размера. Что еше более важно, в случае такого кода процессор не может ошибиться в своих предсказаниях; таким образом, гарантируется эффективная работа конвейера команд. Прсдикатное выполнение имеет свою стоимость. Предиканяые команды выбираются и декодируются, даже если в конечном итоге они не будут выполнены. Дословно — "ядовитый бит".
— Прил. лер 855 10.2. Ограничения планирования кода Машины с динамическим планированием Набор команд машины со статическим планированием явным образом определяет, какие именно команды будут выполняться параллельно. Вспомним, однако, из раздела 10.1.2, что некоторые архитектуры позволяют принимать решение о том, какие команды будут выполняться параллельно, в процессе работы программы.
При динамическом планировании один и тот же машинный код может выподняться на различных машинах одного семейства (т.е. на машинах, реализующих один и тот же набор команд) с разной степенью параллелизма. По сути, одним из главных преимуществ машин с динамическим планированием является совместимость по машинному коду. Статические планировщики, программно реализованные в компиляторе, могут работать в паре с динамическими планировщиками (реализованными аппаратно), повышая эффективность использования машинных ресурсов.
При построении статического планировгцика для машины с динамическим планированием можно использовать практически тот же алгоритм, что и для машин со статическим планированием, с тем отличием, что при этом не требуется явная генерация команд "нет операции". Этот вопрос будет рассматриваться в разделе 10.4.7. Статические планировщики должны резервировать все ресурсы, необходимые для выполнения этих команд, и гарантировать удовлетворение всех потенциальных зависимостей данных. Предикатное выполнение не должно применяться слишком "агрессивно", если только машина не имеет существенно больше ресурсов, чем могло бы использоваться в противном случае.
10.2.7 Базовая модель машины Многие машины можно представить с использованием следующей простой модели. Машина М = (гг'. Т) состоит из 1. множества типов операций Т, таких как загрузки, сохранения, арифметические операции и т.д.; 2. вектора Л = [гы гз,...~, представляюшего аппаратные ресурсы, где г,— количество доступных единиц 1-го ресурса. Примеры типичных типов ресурсов включают модули обрашения к памяти (далее для краткости будем обозначать этот ресурс как МОП), АЛУ, модули для работы с числами с плавающей точкой.
856 Глава 1О. Параллелизм на уровне команд Каждая операция имеет множество входных операндов, множество выходных операндов и требующиеся для ее выполнения ресурсы. С каждым входным операндом связана задержка, указывающая, когда должно быть доступно входное значение (относитсльно начала операции). Типичные входные операнды имеют нулевую задержку, означающую, что их значения нужны немедленно, в момент выполнения операции.
Аналогично с каждым выходным операндом связана выходная задержка, указывающая, когда становится доступен результат (относительно начала операции). Использование ресурсов для каждой машинной команды типа г моделируется двумерной таблицей резервирования ресурсов (гезоигсе-гезеггаг(оп гаЫе) ВТо Ширина таблицы равна количеству видов ресурсов машины, а длина — продолжительности использования ресурсов в операции. Элементы ЛТ, [1, з] указывают количество единиц 1-го ресурса, используемого операцией типа 1 спустя 1 тактов после начала ее выполнения. Для простоты обозначений мы считаем, что НТ [г, з] = О, если г указывает на несуществующий элемент таблицы (т.е.
1 больше количества тактов, затрачиваемых на выполнение операции). Конечно, для любых г, 1 и з значение ВТг [г',Я должно быть не больше Л[)] — количества ресурсов типа г', имеющегося в машине. Типичные машинные команды используют только одну единицу ресурсов во время выполнения операции. Некоторые операции могут использовать более одного функционального устройства. Например, операция умножения со сложением может на первом такте использовать умножитель, а на втором — сумматор.
Некоторые операции, такие как деление, могут занимать ресурс несколько тактов. Операции полностью конвейеризованные (бз11у р(ре1шег1) — это операции, которые могут выполняться все такты подряд без каких-либо приостановок выполнения, несмотря на то, что результат их выполнения может стать доступным только спустя несколько тактов. Нам не нужно явно моделировать ресурсы на каждой стадии конвейера; достаточно одного модуля для представления первой стадии. Все операции, находящиеся на первой стадии конвейера, гарантированно пройдут все остальные стадии в последующие моменты времени. 10.2.8 Упражнения к разделу 10.2 Упражнение 10.2.1.
Присваивания на рис. 10.5 имеют определенные зависимости. Для каждой из указанных пар инструкций классифицируйте зависимости как 1) истинные зависимости, 2) антизависимости, 3) зависимости через выход или 4) отсутствие зависимостей (т.е. инструкции могут выполняться в любом порядке). а) Инструкции 1 и 4. б) Инструкции 3 и 5. 857 10.3. Планирование базовых блоков в) Инструкции 1 и 6. г) Инструкции 3 и 6. д) Инструкции 4 и 6. 1) а=Ь 2) с=б 3) Ь=с 4) с!= а 5) с=с! 6) а=Ъ Рнс. 10.5. Последовательность присваиваний с зависимостями через данные Упражнение 10.2.2.
Вычислите выражение Ии+ и) + !ю+ х)) + !у+ з) в точном соответствии со скобками (т.е. не используя законов коммутативности или ассоциативности для переупорядочения сложений). Приведите машинный код на уровне регистров для обеспечения максимальной степени параллельности. Упражнение 10.2.3. Повторите упражнение 10.2.2 для следующих выражений: а) (и+ (и+ (ш+ х))) + !у+ г); б) (и + (и+ ш)) + !х + (у+ г)).
Сколько шагов потребуется для вычислений при максимальной степени параллельности? Сколько шагов потребуется для выполнения вычислений, если вместо достижения максимальной степени параллельности мы будем минимизировать использование регистров? Упражнение 10.2.4.
Вычисления в упражнении 10.2.2 могут быть выполнены при помощи последовательности команд, показанной на рис. !0.6. Если в нашем распоряжении имеется машина параллельностью, удовлетворяющей любые наши запросы, сколько шагов потребуется для вычисления приведенных команд? ! Упражнение 10.2.5. Транслируйте фрагмент кода, рассматривавшийся в примере 10.4, с использованием команды условного копирования СМОЧЕ из раздела 10.2.6.
Какие зависимости по данным имеются в полученном вами коде? 10.3 Планирование базовых блоков Теперь мы готовы к тому, чтобы поговорить об алгоритме планирования кода. Начнем с простейшей задачи: планирования операций в базовом блоке, состоящем из машинных команд. Оптимальное решение этой задачи — 1ЧР-полное. Но на 858 Глава 10. Параллелизм на уровне команд г1 = и г2=ч г1 = г1 + г2 г2=и г1, г2 гз = х г2 = г2 + гз т1 = т1 + г2 г2 = у гз = х т2 = г2 + гз т1=г1+г2 Рис. 10.6. Реализация арифметического выражения с минимальным использованием регистров практике типичный базовый блок содержит только небольшое количество огра- ниченных операций, так что обычно должно быть вполне достаточно применения простых методов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
