Математические модели параллельных вычислительных процессов и их применение для построения многопоточных приложений на системах с SMP-архитектурой

Актуальность работы.

Теория математического моделирования вычислительных процессов восходит к построению математических моделей, разработанных с целью формализации понятия алгоритма [25, 56, 60, 93, 99]:

• Машины Тьюринга.

• Конечные автоматы.

• Автоматы с магазинной памятью.

• Системы Маркова.

• Машины с произвольным доступом.

К сожалению, эти математические модели не пригодны для исследования параллельных процессов. В реальном мире лишь природа небольшого количества вычислительных систем является последовательной [12], и они могут быть описаны при помощи соответствующих моделей. Большинство систем являются распределенными, в том смысле, что их можно представить как раздельно функционирующие и взаимодействующие блоки, представляющие собой составные части (возможно, функционирующие последовательно), некоторого общего процесса, решающего поставленную задачу. Такие системы называют «реактивными» [123].

Параллельная обработка информации широко используется для увеличения производительности вычислительных систем [7]. Особое место среди параллельных систем занимают системы реального времени, поведение которых в значительной степени зависит от количественных временных характеристик. Процесс проектирования систем такого типа — нетривиальная задача, требующая для своего решения фундаментальных исследований, основанных на различных формальных методах и средствах, которые варьируются в зависимости от класса моделируемых систем, степени детализации их структуры и поведения, а также от характера изучаемых проблем.

За последние 30 лет — зарубежными исследователями Я. Фостером [116], Ч. Хоаром [98, 119], Р. Милнером [124], К. Петри [129], Г. Винскелем [135, 136], М. Нильсеном [125, 126], Э. Гобо [118], М. Беднарчиком [115] были предложены и изучены многие формальные модели «реактивных» систем:

• CSP (Communicating sequential processes (взаимодействующие последовательные процессы)) [119, 133];

• LTS (Labeled Transition Systems (размеченые системы переходов)). [125];

• ATS (Asynchronous Transition Systems (Асинхронные системы переходов)) [115];

• РЕ (Prime Events (Структуры событий)) [135];

• PN (Petri Network (Сети Петри)) [129];

• CE-PN (Condition Event Petri Network (YcflOBHO событийные сети Петри)) [125];

• SyncTrees (Synchronization Trees (Деревья синхронизации)) [136];

• HAD (Higher dimensional automata (ABTOMaTbi высокой размерности) [113, 118];

• SDF-графы, маркированные потоковые графы и М-сети [122, 134]. Так же стоит отметить исследования в области построения формальных моделей распределенных вычислений отечественных ученых В. Воеводина и Вл. Воеводина [19, 20], О. Омарова [57, 58], В. Котова [40, 41], И. Вирбицкайте [17, 114], А. Барского [8], В. Бочарова [13], В. Корнеева [38, 39], В. Топоркова [70, 71], Н. Миренкова [50] и др.

Реактивные" системы используются для описания поведения операционных систем и коммуникационных протоколов [94], управляющего программного обеспечения и других схожих систем, а так же для моделирования параллельных вычислений [125].

Наиболее общими математическими моделями параллельных вычислений являются граф алгоритма, информационный граф алгоритма, граф зависимости и граф процесса, см. например [103].

Многие классические модели: сети Петри, размеченные системы переходов, асинхронные системы переходов, автоматы высокой размерности, графы зависимости, графы процесса, графы алгоритма и информационные графы алгоритма позволяют исследовать проблемы связанные с достижимостью некоторого состояния вычислительного процесса [26], его нетупиковостью [40], решать классические проблемы синхронизации [14]: сериализации [72], взаимной блокировки [24], бесконфликтности [67]. Выявлять взаимосвязь моделей между собой. Анализировать состояния таких систем различными методами.

Лишь немногие модели позволяют анализировать время функционирования таких систем — временные сети Петри [114], временные структуры событий [125], временные системы переходов [125]. Из них наиболее часто используемыми на практике являются временные раскрашенные сети Петри [121]. Стоит отметить малоизученность и сложность реализации на основе этой модели, а так же сложность теоретического анализа ввиду асинхронной природы самих сетей Петри.

Автор предлагает новые математические модели параллельных вычислений — волновые системы, временные волновые системы и гибридные временные волновые системы, для систем с SMP архитектурой [128], которые позволяют моделировать, изучать, разрабатывать и анализировать сложные вычислительные процессы, использующие параллелизм задачи и позволяющие провести априорный анализ времени функционирования таких систем. Гибридная временная волновая система [76] состоит из взаимодействующих последовательных процессов и является обобщением конвейерной системы. Для данной математической модели автором получена априорные нижняя и верхняя оценки времени их функционирования. Рассмотрены различные типы эквивалентностей [117] для гибридных временных волновых систем. Построены параллельные алгоритмы различных задач вычислительной математики и компьютерной графики, приводятся алгоритмы построения гибридных временных волновых систем для произвольных арифметических выражений и алгоритм вычисления нижней оценки времени функционирования таких систем.

Цель работы.

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

Для достижения поставленной цели планируется решение ряда задач.

Задачи работы.

• Разработать и исследовать математическую модель для описания взаимодействующих процессов исполняющихся параллельно на системах с 8МР-архитектурой.

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

• Разработать комплекс программ для моделирования гибридных временных волновых систем. '.

• Проверить универсальность и достоинства модели на ряде прикладных задач.

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

К новым научным результатам, полученным автором в диссертационной работе, относятся следующие:

• математические модели параллельных вычислительных процессов, применяемые на системах с 8МР-архитектурой: о волновой системыо временной волновой системыо гибридной временной волновой системы.

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

• введен ряд эквивалентностей на множестве волновых систем;

• на множестве волновых систем введены операции позволяющие получать новые волновые системы из уже существующих, так же доказано, что множество волновых систем является моноидом относительно операции параллельной композиции;

• исследован параллельный алгоритм перебора последовательностей с помощью многопотоковых приложений на системах с БМР-архитектурой, используемый для вычисления нижней оценки времени функционирования гибридных временных волновых систем;

• построены волновые системы для ряда алгоритмов вычислительной математики и компьютерной графики.

Практическая значимость.

Практическая ценность данных исследований состоит в возможности их использования в различных областях прикладной математики, компьютерной графики, при создании систем автоматического распараллеливания. Показано, что применение, предложенной в диссертационной работе математической модели гибридных временных волновых систем, позволяет прогнозировать время функционирования взаимодействующих параллельно исполняющихся процессов. В частности, результаты диссертационной работы, использовались в ФГУЗ «ЦГиЭ № 99 ФМБА России» при создании модуля формирования списка цехов ОАО АСЗ для дератизации по датам.

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

Апробация работы.

Основные результаты работы обсуждались на следующих научно-технических и научно-практических конференциях в форме докладов по основным положениям диссертации:

• 35-й научно-технической конференции аспирантов и студентов г. Комсомольск-на-Амуре;

• 36-й научно-технической конференции аспирантов и студентов г. Комсомольск-на-Амуре;

• XXXI Дальневосточная школа-семинар имени академика Е. В. Золотова г. Владивосток;

• XXXII Дальневосточная школа-семинар имени академика Е. В. Золотова г. Владивосток;

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

• работы автора принимали участие и заняли призовые места в конкурсе «Программист года 2008» г. Владивосток;

• обсуждались на научно-технических семинарах факультета компьютерных технологий КнАГТУ.

Автором опубликовано 16 научных статей [73−74, 76−88, 92], в центральной печати 3(в соавторстве одна), получены 4 авторских свидетельства о регистрации программ для ЭВМ [75, 89−91](в соавторстве одно).

Ключевые положения исследования использованы при проведении учебных занятий по дисциплинам «Системы реального времени», «Дискретная математика», «Архитектура вычислительных систем» в Комсомольском-на-Амуре государственном техническом университете, нашли практическое применение в реальных условиях деятельности предприятий г. Комсомольска-на-Амуре.

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

Во введении представлена актуальность работы, ее цель, задачи, научная новизна и практическая значимость.

В первой главе проведено исследование используемых и изучаемых фундаментальных математических моделей распределенных вычислений. Такие модели служат для формального описания поведения распределенных систем. Рассматриваются классические модели параллельных вычислений.

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

В третьей главе проводиться теоретический анализ множества волновых систем и категории, которую они составляют. Вводится ряд операций на множестве волновых систем. Доказывается, что множество волновых систем моноид и не группа относительно параллельной композиции. Уточняются теоретические верхняя и нижняя оценки времени функционирования параллельной и последовательной композиции временных волновых систем, «склеивания» и «замены» на данном множестве.

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

В пятой главе приводятся сети Петри, построенные на основе гибридных временных волновых систем, для конструирования поверхностей при помощи поверхностей Цао Ена, кривых Безье, для получения центральной и параллельной проекции некоторой точки, задания базиса углами Эйлера, преобразование вращения, алгоритмы отсечения Сазерленда-Коэна плоским и трехмерным окном, для алгоритма Варнока удаления невидимых линий, для построения кусочно-линейного сплайна, сплайна Эрмита, В-сплайна m-ой степени, интерполяционного многочлена Лагранжа. Приводиться описание класса-канала построенного на основе семафоров для организации обмена сообщениями между параллельно функционирующими вычислительными процессами. Рассматриваются вопросы построения параллельных алгоритмов для визуализации фрактальных множеств.

Структура диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Текст диссертации изложен на 120 страницах, включает одну таблицу и 59 рисунков.

Выводы по пятой главе.

1. Предложенная в данной главе реализация каналов волновых систем позволяет максимально упростить и унифицировать протоколы взаимодействия параллельно выполняющихся процессов.

2. Построенные волновые системы для ряда алгоритмов компьютерной графики и вычислительной математики иллюстрируют общий подход к созданию параллельных алгоритмов, на их основе.

3. Использование волновых систем упрощает задачу построения параллельных алгоритмов и выявления внутреннего параллелизма присущего задаче.

4. Волновые системы могут быть использованы как для реализации функционального параллелизма, так и для реализации параллелизма по данным.

5. Волновые системы и параллельные алгоритмы, построенные на их основе, можно широко применять на практике.

ЗАКЛЮЧЕНИЕ

.

В работе получены следующие основные результаты.

1. Разработана и исследована математическая модель для описания функционирования взаимодействующих процессов исполняющихся параллельно на системах с БМР-архитектурой.

2. Разработаны методы и алгоритмы для программной реализации математической модели гибридной временной волновой системы.

3. Получены верхняя и нижняя оценки времени функционирования гибридных временных волновых систем.

4. Разработан комплекс программ для моделирования гибридных временных волновых систем.

5. Получены верхняя и нижняя оценки времени функционирования гибридных временных волновых систем, а так же для конвейерных вычислений получено максимальное теоретически достижимое ускорение при использовании временных волновых систем;

6. Введен ряд эквивалентностей на множестве волновых систем;

7. На множестве волновых систем введены операции позволяющие получать новые волновые системы из уже существующих, так же доказано, что множество волновых систем является моноидом относительно операции параллельной композиции;

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

9. Сформулирован подход к построению гибридной временной волновой системы для произвольного арифметического выражения.

10. Построены волновые системы для некоторых алгоритмов вычислительной математики и компьютерной графики.