Распределение регистров методом раскраски графа несовместимости для современных вычислительных систем

• Автор: Боханко, Андрей Сергеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 100 с. : ил.

содержание работы.

ГЛАВА ПЕРВАЯ ОСНОВНЫЕ ПОНЯТИЯ

1.1 Современные архитектуры и оптимизирующая компиляция.

1.2 ОС ОВБк i руктуры данных.

1.2.1 Промежуточное пред ставление.

1.2.2 УРЛВЛЯЮЩИЙI РАФ

1.2.3 Дерево доминатоюв 1 юстдоминаторов

1.2.4 Дерево циклов

1.2.5 Форма со статически единственным присваиванием.

1.2.6 Граф куго ка данных

1.3 Распределение регистров

1.4 Распределение регистров, основанное на раскраске графа несовместимости
1.4.1 ОБЩЕЕ ОПИСАНИЕ .
1.4.2 ПОИСК СЕТЕЙ
1.4.3 Построение графа несовместимости.
.4.4 раскраска графа несовместимости.
1.4.5 Замена виртуальных регистров на соответствующие им физические регистры
1.5 Выводы.
ГЛАВА ВТОРАЯ ВЛИЯНИЕ СОВРЕМЕННЫХ АРХИТЕКТУРНЫХ МЕХАНИЗМОВ НА РАСПРЕДЕЛЕН И Е РЕГИСТРОВ. .
2.1 ИРОКОЕ КОМАНДНОЕ СЛОВО
2.1.1 Влияние широкого командного слова i распределение регистров.
2.1.2 Взаимодействие распределителя рег истров и планировщика
2.2 Предика г носп.
2.2.1 Точное определение окончания времени жизни регистров и сетей.
2.2.1.1 анализ работы ii .
2.2.1.2 Предвари гельное маркирование первых определений.
2.2.2 Удаление ложных несовместимостей.
2.2.2.1 Граф разделения предикатов.
2.2.2.2 НОВЫЙ ПОДХОД К УДАЛЕНИЮ ложных несовместимостей.
2.2.2.3 ОПТИМАЛЬНОЕ ОБЪЕДИНЕНИЕ БИТОВЫХ ВЕКТОРОВ С ИНФОРМАЦИЕЙ О ЖИВЫХ СЕТЯХ ВЫХОДНЫХ ЛУГ ГИПЕРБЛОКОВ
2.3 Распределение регистров разных типов.
2.3.1 ПОРЯДОК РАСПРЕДЕЛЕНИЯ РЕГИСТРОВ РАЗНЫХ ТИПОВ.
2.3.2 Точный учет влияния различных форматов рег истров
2.4 ВЫВОДЫ.
ГЛАВА ТРЕТЬЯ ВЗАИМОДЕЙСТВИЕ РАСПРЕДЕЛИТЕЛЯ РЕГИСТРОВ С ДРУГИМИ ФАЗАМИ ОПТИМИЗИРУЮЩЕГО КОМПИЛЯТОРА .
3.1 Взаимодействие распределителя регистров с оптимизациями
3.2 Взаимодействие общецплпгюго и циклового распределителей регистров
3.3 Распределитель регистров, не зависящий огнем вой машины
3.4 Выводы.
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


Результаты работы докладывались на международной молодежной научной конференции «XXX Гагаринские чтения» (Москва, в и гг. Региональная информатика ” (СМТегербург, г. ЗАО “МЦСТ” и Института Микропроцессорных Вычислительных Систем РАН. Дроздов Л. К). Корпев Р. М., Боханко А. С. Индексный анализ зависимостей по данным // Информационные технологии и вычислительные системы, № 3, . С. -. Боханко А. С., Дроздов А. Ю., Корнев Р. М. Анализ зависимостей по данным в цикловых регионах программы // Компьютеры в учебном процессе, № 8,. С. -. Дроздов А. Боханко Л. С. Дерево значений: новая структура данных, объединяющая информацию о потоке управления и доминировании // Информационные технологии, № , . С. -. Боханко А. С., Новиков С. В., Шлыков C. JI. Некоторые вопросы распределения регистров в архитектурах с широким командным словом // Компьютеры в учебном процессе, № 8,. С. -. Боханко А. С., Дроздов А. Новиков С. В., Шлыков С. Л. Распределение регистров методом раскраски графа несовместимости для VLlW-архитектур / Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выи. М., . С. -. Дроздов А. К). Новиков С. В., Боханко А. С., Галазин А. Б. Глобальный граф потока данных и его роль в проведении оптимизирующих преобразований программ / Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Выи. М., . С. -. В Первой главе рассматриваются основные понятия, необходимые для понимания последующих глав диссертационной работы. В нервом разделе первой главы дан обзор подходов к организации параллельных вычислений и показана предпочтительность архитектур с параллелизмом на уровне отдельных операций. Раздел 1. В частности, дано краткое описание промежуточного представления, управляющего графа, дерева доминагоров / постдомннаторов, дерева циклов, формы со статически единственным присваиванием, графа потока данных. В разделе 1. В разделе 1. Приведены алгоритмы выполнения основных шагов данного подхода. Основным результатом первой главы следует считать определение структур данных и алгоритмов, необходимых для базового алгоритма распределения регистров методом раскраски графа несовместимости. Вторая глава посвящена исследованию влияния аппаратных механизмов на процесс распределения регистров. В разделе 2. Представлены модификации алгоритма пропагации времени жизни, позволяющие корректно и эффективно работать в архитектурах с широким командным словом. Проведено исследование взаимодействия распределителя регистров и планировщика; проведены замеры влияния на эффективность работы порядка запуска этих фаз. Замеры проводились на пакете тестов 5РЕС; результаты замеров представлены в таблице. Раздел 2. Дано определение и краткое описание этого механизма; показаны проблемы, встающие перед распределителем регистров при работе на предикатном коде. Дана классификация этих проблем. Последующие подразделы посвящены исследованию упомянутых проблем. В частности, в разделе 2. Проведен анализ опубликованных ранее работ, показаны их недостатки. Предложен новаторский метод решения поставленной проблемы, представлен алгоритм его реализации - причем в двух вариантах, с разными свойствами и разной алгоритмической сложностью. Приведено доказательство корректности представленного алгоритма. В разделе 2. Для этого алгоритма доказана алгоритмическая сложность и корректность. В разделе 2. Приведены алгоритмы, решающие некоторые встающие при этом залами. Важнейшими результатами второй главы является создание, доказательство и практическое испытание алгоритмов, решающих целый ряд проблем, встающих перед распределителем регистров при работе на современных вычислительных системах. В частности, это работа в архитектурах с поддержкой широкого командного слова, иредикатности, регистров разных типов и форматов. В первом разделе этой главы представлен общих подход оценки влияния на распределитель регистров целой группы оптимизаций, продлевающих времена жизни переменных. К числу таких оптимизаций относятся Глобальное распространение копий, вынос инвариантов, сбор общих подвыражений.