Анализ обращений программы к памяти в оптимизирующей распараллеливающей системе

• Автор: Полуян, Степан Вячеславович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Ростов-на-Дону
• Количество страниц: 147 с. : ил.

ВВЕДЕНИЕ

ГЛАВА 1. АНАЛИЗ ПСЕВДОНИМОВ.

1.1. Обзор методов исследований псевдонимов.

1.2. Алгоритм анализа псевдонимов системы ДВОР и его реализация.

1.2.1. Описание программной реализации анализатора псевдонимов в ДВОР.

1.2.2. Алгоритм анализа целей указателей при анализе псевдонимов в ДВОР.

1.2.2.1. Представление значений указателей.

1.2.2.2. Внутрипроцедурная часть анализа целей указателей

1.2.2.3. Межпроцедурная часть анализа целей указателей.

1.2.2.4. Анализатор выражений для анализа целей указателей.

1.2.2.5. Учет состояний программы

1.2.2.6. Результат анализа целей указателей
1.2.3. Алг оритм анализа типов переменных при анализе псевдонимов в ДВОР
1.2.3.1. Представление типов данных
1.2.3.2. Определение псевдонимов на основе информации о типе.
1.3. Применение анализа псевдонимов в ДВОР
1.3.1. Уточнение информационных зависимостей
1.3.2. Уточнение потока данных
1.4 Оценка точности и эффективности анализатора псевдонимов.
1.5. Выводы к первой главе
ГЛАВА 2. СТАТИЧЕСКОЕ ПРОФИЛИРОВАНИЕ.
2.1. Обзор методов профилирования.
2.2. Алгоритм статического профилирования системы ДВОР и его реализация.
2.2.1. Описание программной реализации профилировщика в ДВОР
2.2.2. Задание весов операций в ДВОР
2.2.3. Внутрипроцедурная часть алгоритма профилирования в ДВОР
2.2.3.1. Вычисление времени выполнения операторавыражения.
2.2.3.2. Вычисление времени выполнения блока операторов
2.2.3.3. Вычисление времени выполнения операторов ветвления
2.2.3.4. Вычисление времени выполнения операторов циклов.
2.2.3.5. Алгоритм выделения горячих точек
2.2.3.6. Типизация операций
2.2.4. Межпроцедурная часть алгоритма профилирования в ДВОР.
2.2.4.1. Типы времени выполнения подпрограмм.
2.2.4.2. Алгоритм обхода графа вызовов.
2.2.4.3. Вычисление времени выполнения подпрограмм.
2.2.5. Метод получения горячих точек в ДВОР
2.2.6. Диалоговый режим профилирования в ДВОР
2.3. Сравнение результатов профилирования .
2.4. Выводы ко второй главе
ГЛАВА 3. АНАЛИЗ РАЗМЕЩЕНИЯ ДАННЫХ НА ЭТАПЕ КОМПИЛЯЦИИ
3.1. Обзор методов размещения данных в общей и распределенной памяти.
3.2. Исследование целесообразности анализа размещения данных
3.3. Модель рассматриваемых программ
3.4. Алгоритм анализа обращений программы к памяти в ДВОР и его реализация
3.5. Алгоритм анализа размещения данных в общей памяти с минимизацией кэшпромахов системы ДВОР и его реализация.
3.5.1. Об особенностях работы кэшпамяти
3.5.2. Условие оптимального размещения массивов с учетом особенностей кэша
3.5.3. Алгоритм вычисления количества заполнений кэшлинеек в ДВОР
3.5.4. Описание программной реализации в системе ДВОР анализатора размещения данных в общей памяти
3.6. Алгоритм анализа размещения данных в распределенной памяти с минимизацией количества межпроцессорных пересылок системы ДВОР и его реализация
3.6.1. Рассматриваемые способы размещения данных в распределенной памяти
3.6.2. Условие оптимального размещения массивов в распределенной памяти.
3.6.3. Алгоритм подсчета количества межпроцессорных пересылок в ДВОР
3.6.4. Описание программной реализации в системе ДВОР анализатора размещения данных в распределенной памяти.
3.7. Алгоритм уменьшения количества переборов вариантов размещений массивов в системе ДВОР
3.8. Оценка корректности и эффективности анаэиза размещения данных в ДВОР
3.9. Выводы к третьей главе.
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


Постановка задачи о выборе оптимального размещения данных принадлежит научному руководителю. Все результаты диссертации получены автором лично. Большинство научных публикаций по теме диссертации выполнены без соавторов. Программная реализация анализатора псевдонимов, профилировщика, анализатора размещения данных в общей памяти с минимизацией кэшпромахов, анализатора размещения данных в распределенной памяти с минимизацией межпроцессорных пересылок выполнены автором лично в рамках проекта ДВОР с использованием подпроектов внутреннее представление, граф потока управления, граф вызовов и графический интерфейс других разработчиков. Структура диссертации. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы 9 наименований и одного приложения. Содержит 7. Первая глава посвящена анализу псевдонимов i i ИЗ, , который проводится на этапе компиляции программы и позволяет получить информацию о программных переменных, являющихся разными именами одной и той же ячейки памяти псевдонимах. В первом разделе данной главы сделан обзор существующих алгоритмов анализа псевдонимов, различающихся по точности, эффективности и уровню их применения в зависимости от решаемой задачи. Рассмотрены алгоритмы эффективного решения задачи анализа целей указателей , 6 и алгоритмы эффективного представления результата анализа , 5, а также особенности применения анализа псевдонимов в компиляторе , в обфускаторе , разрабатываемом в ИСП РАН, и в системах автоматического обнаружения дефектов в исходном коде , . Далее в этой главе описываются алгоритмы разработанного автором данной работы анализа псевдонимов, который основывается как на информации о целях указателей , так и на информации о типах переменных , что позволяет, не снижая точности анализа псевдонимов, обойтись более простыми вычислениями там, где это возможно. В итоге, реализованный автором в рамках проекта ДВОР анализатор псевдонимов позволяет на основе его результатов провести в программе на этапе компиляции уточнение не только потока данных, но и информационных зависимостей, что и определяет новизну предложенных алгоритмов. В четвертом разделе первой главы произведено сравнение анализа псевдонимов, реализованного автором данной работы в рамках проекта ДВОР, с анализом псевдонимов, реализованным в известных коммерческих компиляторах i Vi и I i ХЕ. А также продемонстрирована ошибка при распараллеливании программы компилятором I i ХЕ ввиду отсутствия у него информации о псевдонимах переменных при анализе информационных зависимостей. Также в данном разделе описано тестирование скорости анализа псевдонимов на известных тестовых программах из пакетов и 4, которое показало, что разработанный в ДВОР алгоритм с использованием системы состояний программы существенно быстрее, чем классический алгоритм анализа псевдонимов. Потребность в статическом профилировании для автоматического размещения данных продиктована необходимостью оптимизации процесса выбора наилучшего размещения данных. В первом разделе данной главы сделан обзор существующих алгоритмов профилирования программ. Рассмотрены особенности таких профилировщиков, как I V ii ХЕ 0, , i , I i и других. Далее в этой главе описываются алгоритмы разработанного автором данной работы статического профилирования. Его статичность обусловлена спецификой проекта ДВОР, которая заключается в том, что ДВОР является конвертором программы на языке высокого уровня в преобразованную программу также на языке высокого уровня. Однако статичность профилирования не позволяет вычислить характеристики работы программ, не принадлежащих линейному классу , 6. Ввиду этого, автором данной работы предложен и реализован алгоритм, расширяющий возможности статического профилирования, новизна которого заключается в использовании режима диалога с пользователем вместо комбинированного использования статического и динамического профилирования, как в современных профилировщиках. При этом сохраняется основное достоинство статического профилирования анализ программы еще до ее запуска.