'

Распределение регистров при планировании инструкций для архитектуры “Эльбрус”

Понравилась презентация – покажи это...





Слайд 0

Распределение регистров при планировании инструкций для архитектуры “Эльбрус” Дипломная работа Иванова Д. С. Научный руководитель Шлыков С. Л. Москва 2008


Слайд 1

Задачи распределения регистров и планирования инструкций в компиляторе Планирование инструкций – эффективное переупорядочивание инструкций с учетом доступных вычислительных ресурсов. Распределение регистров – эффективное распределение доступных архитектурных регистров между переменными и результатами инструкций.


Слайд 2

Схемы взаимного расположения фаз планирования инструкций и распределения регистров 1. Распределение перед планированием Создает дополнительные зависимости между инструкциями, сильно ограничивая параллельность. Высокая алгоритмическая сложность. 2. Распределение после планирования Приводит к разрезу спланированного кода при появлении инструкций откачки в память. Ограничения на планирование. Высокая алгоритмическая сложность. 3. Распределение при планировании Позволяет избежать указанных проблем. Перспективная, но плохо исследованная техника.


Слайд 3

Цель работы Планирование инструкций Распределение регистров Распределение регистров при планировании инструкций BACK END — + FRONT END OPTIMIZER


Слайд 4

Основные понятия Виртуальные регистры – переменные программы и промежуточные результаты вычислений. Сеть – виртуальный регистр и множество инструкций его чтения и записи. Локальная сеть – это сеть, значение которой необходимо хранить на регистре или в памяти в пределах только одного линейного участка (узла) управляющего графа. Глобальная сеть – любая нелокальная сеть. Время жизни глобальной сети – множество дуг и узлов управляющего графа, на которых необходимо хранить значение сети. Давление на регистровый файл – количество сетей, значения которых в данный момент необходимо хранить на регистрах.


Слайд 5

Алгоритм распределения регистров при планировании инструкций 1. Подготовка к распределению регистров и планированию инструкций 2. Распределение регистров для глобальных сетей перед планированием инструкций 3. Распределение регистров для локальных сетей одновременно с планированием инструкций


Слайд 6

Подготовка к распределению регистров 1. Определение времен жизни глобальных сетей 2. Разделение регистрового файла на две части для глобального и локального распределения для каждого линейного участка. |------ Глоб. Сети ------|--- Лок. Сети ---| 3. Подсчет максимального давления локальных сетей на регистровый файл: TU – среднее время планирования последнего чтения сети, TL - среднее время планирования первой записи сети, H – время планирования линейного участка.


Слайд 7

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


Слайд 8

Глобальное распределение регистров 1. Подсчет приоритетов сетей (стоимость планирования инструкций откачки/подкачки) по формуле: spill_cst - стоимость планирования инструкции откачки, fill_cst – стоимость планирования инструкции подкачки, node_cnt – значение счетчика линейного участка. 2. Распределение глобальных сетей на доступные регистры с помощью битовых матриц 3. Маркировка сетей, которые не удалось распределить на регистры.


Слайд 9

Глобальное распределение регистров Приоритет типов архитектурных регистров для глобального распределения: 1. Глобальные регистры являются общими и доступны всем процедурам 2. Базированные регистры заблокированы для использования в циклах с наложением итераций 3. Локальные регистры не имеют ограничений на использование при распределении |--Gs[0-31]--|--------Bs[0-127]--------|----Rs[0-63]----|


Слайд 10

Локальное распределение регистров при планировании инструкций Планирование инструкции в широкую команду: 1. Поиск доступного исполнительного устройства 2. Поиск регистров для локальных аргументов и локального результата инструкции. Принятие решения об отказе в планировании при высоком давлении на регистровый файл. 3. Приоритет регистров при локальном распределении: |--Gs[0-31]--|----Rs[0-63]----|--------Bs[0-127]--------| 4. Создание и планирование на общих основаниях инструкций откачки и подкачки, если они необходимы


Слайд 11

Преимущества реализованного алгоритма 1. Уменьшение времени работы за счет отказа от построения графа несовместимости и совмещения схожих функций 2. Сохранение целостности спланированного кода за счет планирования инструкций откачки/подкачки на общих основаниях 3. Точный учет давления на регистры при планировании инструкции


Слайд 12

Результаты


Слайд 13

Результаты


Слайд 14

Результаты


Слайд 15

Результаты 1. Для архитектуры “Эльбрус” в составе оптимизирующего компилятора разработан и реализован алгоритм распределения регистров при планировании инструкций, позволяющий повысить производительность и уменьшить время компиляции программ 2. Проведено комплексное тестирование алгоритма, подтвердившее его эффективность на различных задачах 3. Реализованный алгоритм войдет в следующую версию оптимизирующего компилятора для архитектуры “Эльбрус”


Слайд 16

Спасибо за внимание!


×

HTML:





Ссылка: