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

В.И.Дужий, ст.преп;Д.В.Паук, студент
Национальный аэрокосмический университет им. Н.Е.Жуковского "ХАИ"
ИКТМ'2005

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

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

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

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