Конференции ИВТ СО РАН

VIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям

27 - 29 ноября 2007 года, Новосибирск

Тезисы докладов

Вычислительная математика

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

Рогалев А.А.

Сибирский Федеральный Университет (Красноярск)

Принцип многопроцессорной обработки, как способ повышения общей эффективности понятен: распределить вычислительный процесс на N-процессоров, осуществляющих отдельные фрагменты вычислительного алгоритма. Хорошо распараллеливаемыми являются задачи с многократно повторяемыми вычислениями при вариациях некоторых начальных условий для каждого цикла вычислений. Более того, в таких задачах параметры последующих циклов вычислений желательно должны бы иметь минимально выраженную зависимость от результатов предыдущих циклов («итерационность»). К таким задачам относятся задачи множеств достижимости управляемых систем, в которых требуется проводить множественное вычисление функций в процедурах оценки решений.

Рассматриваются системы обыкновенных дифференциальных уравнений, в которые входят члены, описывающие параметрические возмущения, или неточности задания коэффициентов системы. Известны лишь границы, в которых они могут лежать. Среди математических описаний подобных задач можно выделить задачи проверки гарантированных условий безопасности и задачи построения множеств достижимости.

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

В статье предлагается для этого протоколировать последовательность взаимодействий последовательных процессов. В терминах сетей Петри это называется трассировкой поведения и записывается как последовательность срабатывания переходов сети. Конечной задачей процесса отладки после обнаружения ошибочного состояния является поиск момента появления ошибки. Для этого требуется повторно запустить параллельную программу с фиксацией ее поведения в рамках сохраненной трассировки во время выполнения, отследить появление данных, приводящих к появлению ошибки. В терминах сетей Петри это эквивалентно назначению маркировки, при достижении которой параллельная программа должна остановить все свои процессы. Используя точки останова, за конечное число перезапусков программы находится момент появления ошибки, после чего отладка параллельной программы переходит в фазу исправления ошибки.

Литература
1. Малышкин В.Э. Введение в параллельное программирование мультикомпьютеров. Новосибирск: СО РАН Институт Вычислительной математики и математической геофизики. - 2005.
2. Богачев К.Ю. Основы параллельного программирования. Москва: Бином. Лаборатория знаний.- 2003.
3. Котов В.Е. Сети Петри. Москва: Наука.-1988.
4. Рогалев А.А. Использование сетей Петри для анализа параллельных алгоритмов. Новоисбирск: НГУ

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]