А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 173
Текст из файла (страница 173)
Оно интерпретирует машинный код, сохраняет значения, предназначенные для одного и того же регистра. в различных внутренних регистрах, и изменяет все их использования так, чтобы обращения к соответствующим регистрам выполнялись корректно. Поскольку, в первую очередь, ограничения, связанные с зависимостями регистров, возникают благодаря работе компилятора, они могут быть устранены путем использования алгоритма распределения регистров, который учитывает параллелизм на уровне команд. Аппаратное переименование регистров остается полезным в случае, когда набор машинных команд может работать только с небольшим количеством регистров.
Эта возможность позволяет реализовать архитектуру с динамическим отображением небольшого количества архитектурных регистров в коде на существенно большее количество внутренних регистров. количество физических регистров, доступное на целевой машине. Отображение нескольких псевдорегистров на один и тот же физический регистр имеет нежелательный побочный эффект создания искусственных зависимостей, ограничивающих параллелизм на уровне команд. И обратно, параллельное выполнение команд приводит к требованию большего количества памяти для хранения параллельно вычисляемых значений. Таким образом, цель минимизировать количество используемых регистров конфликтует с целью максимизировать параллелизм на 850 Глава 10.
Параллелизм на уровне команд уровне команд. В приведенных далее примерах 10.2 и 10.3 проиллюстрирован поиск компромиссов между использованием памяти и параллелизмом. Пример 10.2. Приведенный ниже код копирует значения переменных в ячейках памяти а и с в переменные в ячейках памяти Ь и с1 соответственно с использова- нием псевдорегистров с1 и с2. // с1 = а // Ъ = с1 // с2 = с // с1= с2 10 С1, а ЯТ Ь, с1 1(Э с2, с ЯТ с1, с2 Если известно, что все ячейки памяти, к которым выполняется обращение, отличаются одна от другой, то операции копирования могут быть выполнены параллельно. Однако если переменным с1 и с2 назначен один и тот же регистр для минимизации количества используемых регистров, то операции копирования обязательно должны выполняться последовательно.
с Пример 10.3. Традиционные методы распределения регистров преследуют цель минимизации количества регистров, используемых при выполнении вычислений. Рассмотрим показанное в виде синтаксического дерева на рис. 10.2 выражение (а+Ь) +с+ (с(+е) Вычисление можно выполнить с использованием трех регистров, как продемон- стрировано на рис. 10.3. I Рис. 10.2. Дерево выражения из примера 10.3 Повторное использование ре~истров требует последовательного вычисления. Единственные операции, которые могут быть выполнены параллельно, — это загрузки значений из ячеек а и Ь и загрузки значений из ячеек с( и е. Таким образом, всего для полного вычисления выражения с максимальным использованием параллельности требуется 7 шагов. Если же использовать различные регистры для каждой промежуточной суммы, то выражение можно вычислить за 4 шага, что равно высоте дерева выражения на рис.
10.2. Распараллеленное вычисление показано на рис. 10.4. с 851 10.2. Ограничения планирования кода // г1 // г2 // г1 // г2 // г1 // г2 // тЗ // г2 // т1 т1, а г2, Ь г1, г1, г2, с т1, т1, г2, с1 гЗ, е г2, г2, г1, г1, ЬЭ 1 1З А1Ю ЬЭ А1Ю ЬЭ Ь11 А1Ю А1112 а Ъ т1+г2 г2 с г1+г2 с1 г2 е г2+гЗ г1+т2 гЗ т2 Рис. !0.3. Машинный код для выражения на рнс.
10.2 г1 гб г8 г9 Рис. 10.4. Параллельное вычисление выражения на рис. 10.2 10.2.4 Упорядочение фаз распределения регистров и планирования кода Если регистры распределяются до планирования, то получающийся код проявляет склонность к множественным зависимостям, ограничивающим планирование кода.
С другой стороны, планирование кода до распределения регистров может привести к тому, что потребуется так много регистров, что сброс регистров (ге81згег зр1111п8), т.е. сохранение их содержимого в памяти, чтобы регистры могли использоваться для других целей, может свести на нет все преимущества параллельного параллелизма на уровне команд. Должен ли компилятор распределять регистры до планирования кода? Должен ли он делать зто после? Или надо решать обе задачи одновременно? Чтобы ответить на поставленные вопросы, следует рассмотреть характеристики компилируемой программы. Многие нечисловые приложения не допускают сильного распараллеливания.
Достаточно выделить для хранения временных результатов при вычислении выражений небольшое количество регистров. Можно начать с применения алгоритма раскрашивания из раздела 8.8.4 для распределения регистров для всех переменных, не являющихся временными, затем спланировать код и распределить регистры для временных переменных. Такой подход не работает в случае численных приложений, в которых в наличии имеется много очень больших выражений.
Здесь можно применить иерархический подход, при котором код оптимизируется изнутри наружу, начиная с наиболее внутренних циклов. В начале команды планируютсч в предположении, что 852 Глава 10. Параллелизм на уровне команд каждому псевдорегистру будет выделен собственный физический регистр. Распределение регистров выполняется после планирования кода; при необходимости осуществляется добавление кода для сброса регистров и планирование кода выполняется заново. Этот процесс повторяется для кода внешних циклов. Когда несколько внутренних циклов рассматриваются вместе в общем внешнем цикле, одной и той же переменной могут быть назначены разные регистры. Назначение регистров в таком случае может быть изменено, чтобы избежать копирований из одного регистра в другой. В разделе 10.5 мы обсудим взаимодействие распределения регистров и планирования в контексте конкретного алгоритма планирования.
10.2.5 Зависимость от управления Планирование операций внутри базового блока относительно простое, поскольку все команды гарантированно выполняются, если поток управления достигает начала блока. Команды базового блока могут быть произвольным образом переупорядочены при условии удовлетворения всем зависимостям данных. К сожалению, базовые блоки, в особенности в нечисленных программах, обычно очень малы — в среднем всего около пяти команд в базовом блоке. Кроме того, операции в одном и том же блоке зачастую сильно связаны и, таким образом, допускают параллелизм только в малой степени.
Соответственно, особую роль приобретает параллелизм, пересекающий границы базовых блоков. Оптимизированная программа должна выполнять все операции исходной программы. Она может выполнять больше команд, чем имеется в исходной программе, при условии, что эти дополнительные команды не изменяют функциональность программы. Как выполнение дополнительных команд может ускорить выполнение программы? Если мы знаем, что некоторая команда, скорее всего, будет выполняться, и при этом имеется простаивающий ресурс, позволяющий "бесплатно" выполнить эту операцию, то команду можно выполнить с опережением, "на всякий случай" (вресн!абче(у).
Если такое опережение оказалось оправданным, программа будет выполняться быстрее. Команда (з называется зависящей по управлению (сов(го!-шеренг)еп() от команды (з, если выход команды (з определяет, будет ли выполняться команда гп Понятие зависимости от управления соответствует концепции вложенных уровней в блочной структуре программы. В частности, в инструкции К-е1ае 1й (с) я1; е1яе я2; я1 и я2 зависят от с по управлению. Аналогично в инструкции звИе н)з11е (с) я; тело я зависит по управлению от с. 853 10.2.
Ограничения планирования кода Пример 10.4. В фрагменте кода з.Г (а > Ь) Ь=а*а; с)=а+сг инструкции Ь = а*а и с) = а+с не зависят по данным от других частей фрагмента. Инструкция Ь = а*а зависит от сравнения а ) г по управлению. Инструкция же с) = а+с не зависит от сравнения и может быть выполнена в любой момент времени. В предположении, что умножение и * а не дает никаких побочных эффектов, эта инструкция может быть выполнена с опережением, лишь бы переменная 6 при этом записывалась только после того, как будет выяснено, что а больше (. и 10.2.6 Поддержка опережающего выполнения Загрузка памяти — один из типов инструкций, которые могут получить существенные выгоды от опережающего выполнения. Загрузка памяти — очень распространенная операция с относительно долгими задержками. Адреса, по которым выполняется чтение из памяти, обычно известны заранее, а результат может быть сохранен в новой временной переменной без уничтожения значения в другой переменной.
К сожалению, загрузка памяти может вызвать генерацию исключения, если адрес считывания некорректен; поэтому опережающая загрузка может привести к аварийному останову корректной программы. Кроме того, неверно предсказанные загрузки памяти могут привести к промахам кэша и ошибкам отсутствия страницы, что может существенно замедлить работу, Пример 10.5. В фрагменте 1Г (р )= Ы()11 ) Ч = *Р' опережающее разыменование р приведет аварийному останову совершенно корректной программы, если значение р — Ы()1.1. и Многие высокопроизводительные процессоры предоставляют специальные возможности для поддержки опережающей загрузки памяти.
Мы упомянем только важнейшие из них. Упреждающая выборка Улреждаюи(ая выборка (ргеГе(с!йп8) команды была разработана для переноса данных из памяти в кэш перед их использованием. Команда упреждающей выборки указывает процессору, что в ближайшее время ожидается использование некоторого слова памяти. Если указанный адрес некорректен или если обращение по этому адресу приводит к ошибке отсутствия страницы, процессор просто 854 Глава 1О. Параллелизм на уровне команд игнорирует эту операцию. В противном случае процессор переносит данные из памяти в кэш, если, конечно, они уже не находятся там.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
