Исследование и реализация модели статического анализа нахождения состояния гонки в многопоточных алгоритмах с использованием линеаризованного графа потока управления

• Автор: Битнер, Вильгельм Александрович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 103 с. : ил.

Оглавление
Оглавление
Введение
Актуальность темы
Цель работы и задачи исследования
Объект исследования
Предмет исследования
Метод исследования
Научная новизна
Практическая ценность
Публикации и апробация результатов
Структура и объем диссертации
Глава 1. Общие понятия и существующие методы анализа многопоточных алгоритмов для обнаружения состояний гонок
1.1. Понятие об оптимизации и промежуточном коде
1.2. Оптимизирующие компиляторы
1.3. Средства статического анализа
1.4. Метод статического анализа на основе графа совместного исполнения потоков
Глава 2. Реализации модели статического анализа нахождения состояния гонки в многопоточных алгоритмах с использованием линеаризованного графа потока управления
2.1. Анализ оптимизаций на промежуточном представлении
2.2. Линеаризация графа потока управления через линейку оптимизаций 1ХУМ
2.3. Анализ инструкций 88А-формы ЬЬУМ Ж, не влияющих на математическую модель поиска ЯС

2.4. Получения сокращенного оптимизированного промежуточного
представления LLVM - Reduced Opt LLVM IR
2.5. Контекстно-зависимая линеаризация графа потока управления на
сокращенном промежуточном представлении программы
2.6. Поиск состояний гонок в исследуемом методе на Reduced CFG
2.7. Модель автоматизация поиска состояний гонок
Глава 3. Практические результаты и анализ применения программной реализации модели поиска состояний гонок в многопоточных алгоритмах
3.1. Спинлок (спин-блокировка)
3.2. Некорректный алгоритм спин-блокировки
3.3. Алгоритм Петерсона
3.4. Стек Трейбера
3.5. Выводы
Заключение
Список использованных источников
Приложение

Введение
Современная тенденция развития микропроцессоров и вычислительного оборудования обуславливает создание новых подходов к промышленной разработке программного обеспечения, отвечая все более высоким требованиям потребителя и современным условиям конкуренции. В частности, повышение количества ядер в микропроцессорах заставляет программных разработчиков использовать многопоточные алгоритмы и применять технологии многопоточной программной разработки не только для высокопроизводительных систем, но и для персональных компьютеров и мобильных устройств [2, 30].
Повышение количества ядер в микропроцессорах зачастую сопровождается понижением тактовой частоты каждого ядра микропроцессора, что усугубляет положение ранее написанных однопоточных программ. Далеко не редкость в современной 1Т-индустрии ухудшение производительности промышленных комплексов программ при переходе на более современные вычислительные системы с новыми поколениями микропроцессоров. Данный факт дополнительно стимулирует разработку многопоточных программ для достижения наилучших показателей производительности.
Разработка многопоточных программ с наилучшими показателями производительности не имеет общего подхода. Каждый случай индивидуален в зависимости от архитектуры вычислительной системы и сложности комплексов программ. Такое положение приводит к появлению трудно выявляемых ошибок в коде программ, особенно связанных с параллельным исполнением потоков. Таким образом, всегда остается актуальным разработка новых и совершенствование старых средств верификации и контроля качества программ во время разработки программного обеспечения (ПО).

о -Ист (Loop Invariant Code Motion)
Оптимизация выполняет перемещение инвариантного кода в цикле, пытаясь удалить как можно больше кода из тела цикла, о -loop-deletion (Delete dead loops)
Оптимизация отвечает за удаление циклов, которые не вносят вклад в возвращаемое значение функции, о -loop-reduce (Loop Strength Reduction)
Оптимизация проводит понижение стоимости выражений с индуктивными переменными, заменяя дорогие операции на более дешевые. В частности, выражения с массивами изменяют так, чтобы была возможность воспользоваться преимуществами расширенного режима адресации индекса (scaled-index addressing modes), упрощающее обращение к элементам массивов, о -loop-rotate (Rotate Loops)
Оптимизация выполняет простое вращение цикла, о -loop-simplify (Canonicalize natural loops)
Оптимизация выполняет несколько трансформаций над естественными циклами, преобразуя их в более простую форму, которая позволяет делать последующий анализ и трансформации проще и эффективнее, например, для LICM (Loop Invariant Code Motion). Данная оптимизация создает дополнительный узел (предцикл) перед головой цикла, что гарантирует наличие только единственной входной дуги в цикл. Также гарантируется, что после применения оптимизации измененный цикл будет иметь только одну обратную дугу, о -loop-unroll (Unroll loops)
Оптимизация реализует простую раскрутку цикла, которая заключается в создании несколько копий итераций цикла (число копий п называет фактором развертки) и в увеличении шага цикла в это же число раз. Например, развертка с фактором 2:
for (i = 0; i < n; i++) for (i = 0; i < n-1; i+=2) {