А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 172

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 172)

Что еще более важно, независимо от степени интеллектуальности аппаратного планировщика, он не в состоянии работать с командами, которые еще не были выбраны. Когда процессор выполняет неожиданное ветвление, параллельное выполнение доступно только для вновь выбираемых команд.

Компилятор может повысить производительность динамического планировщика, обеспечивая возможность параллельного выполнения вновь выбираемых команд. 10.2 Ограничения планирования кода Планирование кода (сог)е зспебп))п8) представляет собой оптимизацию программы, применяемую к машинному коду, произведенному генератором кода. На планирование кода накладываются три типа ограничений. !. Ограничения управления. Все операции, выполнимые в исходной программе, должны выполняться и в оптимизированной. 2.

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

Это вызывает проблемы, например, при генерации исключения или при вставленной пользовательской точке прерывания, так что оптимизированные программы сложнее отлаживать. Заметим, что данная проблема относится не только к планированию кода, но и к оптимизации вообще, включая, например, устранение частичной избыточности (см.

раздел 9.5) или распределение регистров (см. раздел 8.8). 846 Глава 1О. Параллелизм на уровне команд 10.2.1 Зависимость через данные Легко видеть, что если мы изменяем порядок выполнения двух операций, которые не затрагивают ни одной общей переменной, то это никак не влияет на результат их выполнения. Более того, если даже обе команды считывают значение одной и той же переменной, мы все равно можем переставить их местами. Только если операция записывает переменную, которую считывает или которую перезаписывает другая операция, то изменение порядка этих операций может привести к изменению результата. О таких парах операций говорят, что они зависимы через данные (дага с)ерепдепГ) и их относительный порядок выполнения должен быть сохранен'. Имеется три вида зависимости через данные. 1. Истинная зависимость: чтение после записи.

Если за записью следует чтение из той же ячейки памяти, то чтение зависит от записанною значения; такая зависимость известна как истинная зависимость. 2. Антизависимость: запись после чтения. Если за чтением следует запись в ту же ячейку памяти, то мы говорим о наличии антизависимости от чтения к записи. Запись как таковая не зависит от чтения, но если запись выполняется до чтения, то последнее даст неверное значение. Антизависимость является побочным продуктом императивного программирования, когда одна и та же ячейка памяти используется для хранения разных значений. Это не '*истинная" зависимость и потенциально она может быть устранена путем хранения значений в разных ячейках памяти.

3. Зависимость через выход: запись после записи. Две записи в одну и ту же ячейку памяти приводят к зависимости через выход. При нарушении порядка записи после выполнения обеих операций в ячейке будет записано неверное значение. Антизависимость и зависимость через выход объединяются в одну категорию зависимостей, связанных с хранением 1згогайе-ге!агент с)ерепцепсез). Это не "истинные" зависимости, которые могут быть устранены путем использования разных ячеек памяти для разных значений. Заметим, что зависимость через данные применима к обращениям как к памяти, так и к регистрам.

10.2.2 Поиск зависимостей среди обращений к памяти Чтобы проверить, зависимы ли два обращения к памяти, надо только выяснить, обращаются ли они к одной и той же ячейке памяти; знать точное расположение 'для краткости мы часто будем говорить просто о зависимости донных, где нз контекств очевидно, что речь идет о зависимости операций через данные. — Прим. лер. 10.2. Ограничения планирования кода этой ячейки не требуется. Например, можно с уверенностью сказать, что обращения *р и *(р+4) не могут обращаться к одной и той же ячейке памяти, несмотря на то, что мы не знаем, куда именно указывает р. В общем случае во время компиляции проверка зависимости не разрешима. Компилятор обязан предполагать, что операции могут обращаться к одним и тем же ячейкам памяти, если он не в состоянии доказать обратное.

Пример 10.1. В случае кода 1) а=1 2) *р=2 3) к=а если только компилятор не может гарантировать, что р не может указывать на а, он должен считать, что данные операции должны выполняться последовательно. Злесь имеется зависимость через выход между инструкциями 1 и 2 и две истинные зависимости между инструкциями 1 и 2 и инструкцией 3. П Анализ зависимости данных очень чувствителен к языку программирования, использованному при написании программы. Для небезопасных с точки зрения ~илов языков наподобие С и С++, в которых указатель может быть преобразован в указатель на объект любого типа, для доказательства независимости между произвольной парой обращений к памяти посредством указателей необходим сложный анализ.

Даже к локальным или глобальным скалярным переменным может иметься косвенное обращение, если только мы не сможем доказать, что их адреса не были сохранены где-либо какой-то из инструкций программы. В языках программирования, безопасных с точки зрения типов, наподобие 1ама объекты различных типов с необходимостью отличаются друг от друга. Аналогично локальные примитивные переменные в стеке не могут оказаться псевдонимами при обращении через другие имена.

Корректный поиск зависимостей данных требует проведения большого количества разных видов анализа. Мы остановимся на основных вопросах, которые должны быть разрешены, если компилятор ищет все зависимости, существующие в программе, и на использовании этой информации при планировании кода. В следующих главах будет рассмотрено выполнение этих анализов. Анализ зависимости данных длн массива Зависимость данных для массива представляет собой задачу устранения неоднозначностей между значениями индексов при обращениях к элементам массива. Например, цикл аког(1=0; 1<п; ++1) А[2*11 = А[2*1+1); Глава 10. Параллелизм на уровне команд копирует нечетные элементы массива А в четные элементы, предшествующие им. Поскольку все считываемые и записываемые ячейки памяти отличаются друг от друга, между обращениями к памяти нет зависимостей, и все итерации цикла могут быть выполнены параллельно.

Анализ зависимости данных для массива, о котором зачастую просто говорят как об анализе зависимости данных (да1адерепдепсе апа!угйя, очень важен для оптимизации численных приложений. Эта тема будет рассмотрена в разделе 11.6. Анализ псевдонимов указателей Мы говорим, что два указателя являются псевдонимами (а)1азед), если они могут обращаться к одному и тому же объекту. Анализ псевдонимов указателей сложен в силу многочисленности потенциальных псевдонимов в программе, причем по ходу программы каждый из них может указывать на неограниченное количество динамических объектов.

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

Для выявления таких псевдонимов требуется межпроцедурный анализ, рассматривающийся в главе 12. 10.2.3 Компромиссы между использованием регистров и параллелизмом В этой главе мы будем полагать, что машинно-независимое промежуточное представление исходной программы использует неограниченное количество нсевдорегистров для представления переменных, которые могут быть размещены в регистрах. Эти переменные включают скалярные переменные исходной программы, обращение к которым невозможно ни по какому иному имени, а также временные переменные, генерируемые компилятором для хранения промежуточных результатов при вычислении выражений. В отличие от ячеек памяти регистры имеют уникальные имена.

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

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

Характеристики

Список файлов книги