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

• Автор: Заборовский, Никита Владимирович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 104 с. : ил.

Оглавление
Оглавление
Введение.

Актуальность темы

Цель работы, задачи исследования.

Научная новизна

Практическая ценность

Положения, выносимые на защиту.

Публикации и апробация результатов.

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

Глава 1. Обзор существующих методов

Общие способы поиска проблем в параллельных
программах.
Статический анализ
Методы
Типы анализа
Алгоритмы
Особенности работы .
Анализаторы
Динамический анализ.
Методы.
Средства динамического анализа.
Проверка на основе моделей
Синхронизация в многопоточных алгоритмах
Неблокирующие алгоритмы.
Классификация исполнения параллельных программ
Глава 2. Подходы к моделированию исполнения потоков.
Идея подхода.
Построение графа совместного исполнения п потоков
Глава 3. Сложности и проблемы существующих подходов к моделированию исполнения потоков.
Проблемы современных систем статического анализа.
Ветвления
Другие проблемы
Анализ значений переменных.
Глава 4. Предлагаемая модель, ориентированная на реальные алгоритмы.
Предлагаемое расширение модели.
Ветвления
Общее представление о расчетном графе
Обозначение на рисунках и схемах.
Построение.
Метод неопределенных коэффициентов.
Класс анализируемых алгоримов
Представление циклов и ветвлений.
Конструктивное построение расчетного графа.
Расчеты на графе.
Доказательство корректности подхода
Обоснованность использования представителей класса эквивалентности в расчетном графе.
Глава 5. Практическая реализация анализа на построенной модели и результаты его работы на многопоточных алгоритмах
Комплекс программ для полуавтоматического анализа
Модельные эксперименты.
Выводы.
Заключение
Список использованных источников


Под «эффективностью» понимается выигрыш от использования многоядерной платформы по сравнению, с, одноядерной. Иногда программы, написанные для одноядерной архитектуры, запускают на чсгырехядерной в надежде получить прирост производительности, а в результате оказывается, что производительность таких программ даже уменьшается. Универсальных способов создавать эффективные программы! Подход для каждой - строго индивидуален. Как одно из решений можно упомянуть неблокирующие алгоритмы альтернативу алгоритмам, использующим явные средства синхронизации. Отсутствие универсальных подходов влечёт за собой также возможные ошибки программистов. Одной из наиболее сложных для обнаружения ошибок является состояние гонки. Состояния гонки (race condition, конкурентного доступа к памяти) -ситуация, когда состояние общей для нескольких потоков ячейки памяти зависит от распределения процессорного времени между потоками. Предугадать это состояние на уровне алгоритма невозможно. Именно поэтому так важно контролировать программы ещё на стадии описания. Создание средств контроля корректности программ становится всё более необходимым с выпуском каждого нового процессора и написанием каждого нового сложного программного комплекса. Различают два принципиально разных подхода к анализу многопоточных алгоритмов на предмет наличия состояний гонки: динамический и статический. Динамический подход представляет собой эмпирическую процедуру «прогона» программы при различных входных данных- (data-race-test в Google, Intel Thread Checker). Принципиальный недостаток подхода в целом невозможно проверить сложную систему, поскольку количество тестов экспоненциально зависит от числа- входных параметров. Статический подход анализирует архитектуру программы и программный код без его запуска. К статическому анализу относится формальное доказательство корректности кода программы. Для современных программных продуктов сложность формального доказательства значительна, что делает его неприменимым в промышленных масштабах. Кроме того, есть вероятность ложного срабатывания. Один и гот же алгоритм может содержать состояние гонки и не содержать его в зависимости от значений входных параметров. В статическом анализе есть ряд известных проблем. В частности, многие алгоритмы используют в своей логике значения разделяемых переменных (алгоритм Петерсона[4], стек Трейбера[7]). Большинству средств анализа алгоритмов не удается обнаруживать ошибки в логике алгоритмов, подобных алгоритму Петерсона. Поиск ошибок в таких алгоритмах - серьёзная исследовательская задача. Отдельные задачи, неразрывно связанные со статическим анализом программ — задача об- идентификации разделяемых ресурсов и задача о превдонимах. Помимо упомянутых методов, можно также отметить методы проверки на основе моделей (проверка, при которой варианты получаются из модели, описывающей функциональность системы) и метод аналитического доказательства корректности [9] программ. Оба метода сложно применить на практике из-за того, что они занимают много времени и требуют больших человеческих усилий. Однако, иногда втречаются экзотические случаи их использования []. Цель работы, задачи исследования. Существует несколько подходов к статическому анализу кода неблокирующих алгоритмов в поисках состояния гонки. Однако, большая часть из них носит чисто теоретический характер, подходит только для модельных задач и дает неточные результаты (большой процент ложных срабатываний и не обнаружений гонки, когда она есть, false-negative). Необходим подход к анализу исходных кодов современных прикладных программ, учитывающий их сложность и специфику. Для этого, во-первых, необходимо разработать математическую модель, представляющую ход исполнения потоков с точки зрения работы с общими разделяемыми переменными. Научная новизна. Научная новизна работы заключается в математическом моделировании поведения многопоточных алгоритмов, содержащих вервления и циклы, использующих разделяемую память. Математическая модель, предлагаемая в работе, учитывает начальные и промежуточные значения разделяемых переменных.