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

• Автор: Трещев, Иван Андреевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Комсомольск-на-Амуре
• Количество страниц: 120 с. : ил.

Введение
ГЛАВА 1 Обзор существующих математических моделей взаимодействующих параллельных вычислительных процессов

1.1 Граф алгоритма, информационный граф алгоритма

1.2 Граф зависимости и граф процесса

1.3 Сети Петри и СЕсети Петри, раскрашенные сети Петри

1.4 Размеченные системы переходов и асинхронные системы переходов

1.5 Структуры событий и размеченные структуры событий

1.6 Автоматы высокой размерности и деревья синхронизации

1.7 Акторная модель , модель Кана, маркированные потоковые графы, Мсети

Выводы по первой главе

ГЛАВА 2 Волновые системы, временные волновые системы и гибридные временные волновые системы
2.1 Формальное описание математической модели волновых систем
2.2 Эквивалентность и двойственная природа волновых систем
2.3 Конвейерные вычисления и волновые системы
Выводы по второй главе
Глава 3 Конструкции на множестве волновых систем, алгоритм вычисления нижней оценки времени функционирования
3.1 Параллельная композиция волновых систем
3.2 Временные оценки параллельной композиции гибридных временных волновых систем
3.3 Последовательная композиция волновых систем
3.4 Временные оценки последовательной композиции гибридных временных волновых систем
3.5 Операция склеивания волновых систем
3.6 Временные оценки для операции склеивания гибридных временных волновых систем
3.7 Операция замены для множества волновых систем
3.8 Временные оценки для операции замены гибридных временных волновых систем
3.9 Операции пу,Л
Выводы по третьей главе 5
Глава 4 Параллельный алгоритм перебора последовательностей
для вычислительных систем с БМРархитектурой
4.1 Описание алгоритма
4.2 Распараллеливание рекурсивных подпрограмм
4.3 Параллельная реализация с помощью обхода в ширину
4.4 Параллельная реализация для систем с БМРархитектурой
4.5 Условия проведения эксперимента и результаты тестирования
Выводы по четвертой главе
Глава 5 Применение гибридных временных волновых систем при моделировании параллельных алгоритмов машинной графики и вычислительной математики на системах с 8МРархитектурой
5.1 Реализация каналов волновой системы
5.2 Поверхности Цао Ена и кривые Безье
5.3 Бикубические поверхности Безье и Всплайн поверхности
5.4 Вычисление смешанного произведения векторов центральная и параллельная проекции, углы Эйлера
5.5 Преобразование поворота, алгоритм отсечения СазерлендаКоэна
5.6 Кусочнолинейная интерполяция, интерполяционный сплайн Эрмпта, интерполяционный многочлен Лагранжа.
5.7 Фрактальная геометрия, метод адаптивного динамического распараллеливания, распараллеливание на основе волновых систем
Выводы по четвертой главе Заключение
Список использованных источников


Особое место среди параллельных систем занимают системы реального времени, поведение которых в значительной степени зависит от количественных временных характеристик. За последние лет зарубежными исследователями Я. Фостером 6, Ч. Хоаром , 9, Р. Милнером 4, К. Петри 9, Г. Винскелем 5, 6, М. Нильсеном 5, 6, Э. Гобо 8, М. Мсети 2, 4. В.Воеводина и Вл. Воеводина , , О. Омарова , , В. Котова , , И. Вирбицкайте , 4, А. Барского 8, В. Бочарова , В. Корнеева , , В. Топоркова , , Н. Миренкова и др. Наиболее общими математическими моделями параллельных вычислений являются граф алгоритма, информационный граф алгоритма, граф зависимости и граф процесса, см. Многие классические модели сети Петри, размеченные системы переходов, асинхронные системы переходов, автоматы высокой размерности, графы зависимости, графы процесса, графы алгоритма и информационные графы алгоритма позволяют исследовать проблемы связанные с достижимостью некоторого состояния вычислительного процесса , его нетуп и новостью , решать классические проблемы синхронизации сериализации , взаимной блокировки , бесконфликтности . Выявлять взаимосвязь моделей между собой. Анализировать состояния таких систем различными методами. Лишь немногие модели позволяют анализировать время функционирования таких систем временные сети Петри 4, временные структуры событий 5, временные системы переходов 5. Из них наиболее часто используемыми на практике являются временные раскрашенные сети Петри 1. Стоит отметить малоизученность и сложность реализации на основе этой модели, а так же сложность теоретического анализа ввиду асинхронной природы самих сетей Петри. Автор предлагает новые математические модели параллельных вычислений волновые системы, временные волновые системы и гибридные временные волновые системы, для систем с архитектурой 8, которые позволяют моделировать, изучать, разрабатывать и анализировать сложные вычислительные процессы, использующие параллелизм задачи и позволяющие провести априорный анализ времени функционирования таких систем. Гибридная временная волновая система состоит из взаимодействующих последовательных процессов и является обобщением конвейерной системы. Рассмотрены различные типы эквивалентностей 7 для гибридных временных волновых систем. Построены параллельные алгоритмы различных задач вычислительной математики и компьютерной графики, приводятся алгоритмы построения гибридных временных волновых систем для произвольных арифметических выражений и алгоритм вычисления нижней оценки времени функционирования таких систем. Цель работы. На основе исследования взаимодействия процессов исполняющихся параллельно на системах с 8МРархитектурой разработать и программно реализовать математическую модель, позволяющую получить априорную нижнюю и верхнюю оценки времени функционирования данных процессов, а так же в ряде случаев предельное достижимое ускорение. Для достижения поставленной цели планируется решение ряда
Задачи работы. Разработать и исследовать математическую модель для описания взаимодействующих процессов исполняющихся параллельно на системах с 8МРархитектурой. Разработать методы и алгоритмы для программной реализации для получения верхней и нижней оценок времени функционирования гибридных временных волновых систем. Разработать комплекс программ для моделирования гибридных временных волновых систем. Проверить универсальность и достоинства модели на ряде прикладных задач. Показано, что применение, предложенной в диссертационной работе математической модели гибридных временных волновых систем, позволяет прогнозировать время функционирования взаимодействующих параллельно исполняющихся процессов. ФГУЗ ЦГиЭ ФМБА России при создании модуля формирования списка цехов ОАО АСЗ для дератизации по датам. Предложенные принципы построения систем взаимодействующих параллельно исполняющихся процессов на системах с 8МРархитектурой могут быть полезны широкому кругу экспертов и исследователей при решении соответствующих задач. XXXI Дальневосточная школасеминар имени академика Е. В. Золотова г.