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

• Автор: Кудряшова, Екатерина Сергеевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Комсомольск-на-Амуре
• Количество страниц: 112 с. : ил.

Содержание
Введение

1 Математические модели параллельных вычислительных систем

1.1 Предварительные сведения

1.2 Дистрибутивные асинхронные автоматы

1.3 Сети Петри как дистрибутивные асинхронные автоматы

1.4 Волновые системы

1.5 Максимальная нормальная форма

2 Расчет времени выполнения параллельного процесса

2.1 Основные определения

2.2 Асинхронная система с функцией времени

2.3 Псевдо-конвейер. Вычисление минимального времени выполнения
2.4 Асинхронный конвейер. Вычисление времени выполнения
2.5 Волновая система. Вычисление времени выполнения
3 Временные дистрибутивные асинхронные автоматы и сети Петри
3.1 Временные сети Петри
3.2 Временные дистрибутивные асинхронные автоматы
3.3 Временные сети Петри как временные дистрибутивные
асинхронные автоматы
3.4 Волновые системы как временные дистрибутивные
асинхронные автоматы
3.5 Дистрибутивные асинхронные автоматы с задержками
3.6 Применение временных сетей Петри
Заключение
Список использованных источников
Введение
Актуальность работы. В последние годы параллельное программирование все больше проникает во все сферы человеческой деятельности. Для реализации параллелизма современные компьютеры снабжены многоядерными процессорами. Для решения задач, связанных с параллельными вычислительными процессами, применяются различные математические модели: сети Петри [66], структуры событий [76], асинхронные системы [39] и т.д. Несмотря на их широкое применение, существуют задачи, для решения которых нужны более общие модели. Различные обобщения моделей с отношением независимости рассматривались в работах [41-43, 48-53].
Часто при разработке программного и аппаратного обеспечения появляется необходимость точной оценки времени работы параллельных процессов и возможности пошагового слежешш за процессом во времени - так называемой трассировки. Для решения задач, в которых участвует время, применяются различные математические модели:
• Временные сети Петри [2, 3, 23, 38, 62, 65, 67-69].
• Сети Петри с задержками [54, 65, 71, 73].
• Автоматы с отношением параллельности [41-43].
• Временные системы переходов [56].
• Временные структуры событий [4].
Во временных сетях Петри переходы определяются как независимые, если они не имеют общих входных мест. Возникает проблема построения модели для изучения временных сетей Петри с другими отношениями независимости. Эта проблема будет решаться в данной работе.
В последнее время большое внимание уделяется конвейерному параллелизму [55]. В литературе широко изучены синхронные линейные конвейеры [35]. Менее изученным является класс асинхронных линейных конвейеров [47]. При этом они очень широко применяются, начиная с уровня обработки запросов в параллельных системах управления базами данных [24] и
кончая уровнем вентильной реализации [7]. Остаются открытыми вопросы об оценке ускорения таких систем. В [8] рассматривается соответствующая формула, но она охватывает лишь такие асинхронные конвейеры, для которых предполагается, что скорость обмена данными между каналами и функциональными устройствами одинакова, а чтение из канала и запись в этот канал может происходить одновремешю. Одним из перспективных направлений является применение волновых вычислений в смысле [5]. Волновые системы применялись для решения различных задач в работе И. А. Трещева [28]. Для нахождения времени вычисления возникающих здесь волновых систем Трещевым были получены лишь приближенные оценки. Необходимы также методы трассировки волновых систем. Исследование этого вопроса - одна из основных задач, решаемых в данной работе.
Цель работы. Найти методы трассировки и расчета времени выполнения параллельных вычислительных процессов.
Задачи исследования. Для достижения поставленной цели необходимо решить ряд задач:
1. Разработать и исследовать математическую модель параллельной вычислительной системы, обобщающую асинхронные системы и позволяющую изучать сети Петри с различными отношениями независимости.
2. Исследовать асинхронные системы с функцией времени.
3. Обосновать метод вычисления времени выполнения параллельного процесса в асинхронной системе с помощью нормальной формы Фоаты. Применить этот метод для конвейеров и волновых систем.
4. Предложить метод вычисления времени выполнения параллельного процесса волновой системы с помощью максимальной нормальной формы, обобщающей нормальную форму Фоаты.
5. Разработать и исследовать компьютерную модель волновой вычислительной системы, позволяющую рассчитывать время выполнения параллельного процесса на многопроцессорном компьютере.
6. Провести эксперименты с помощью этой модели.

независимый блок (5, аг и {і}). Получаем диаграмму, составленную из событий и состояний дистрибутивного асинхронного автомата П(7г) (рисунок 1.23).

5 * £

5і ■ І
Рисунок 1.23 - Построение нового блока
Если С Є а2, то приходим к разложению, приводящему к маршруту, в котором первый блок имеет на один элемент больше, чем раньше, а второй — на один элемент меньше. Число блоков не увеличится (рисунок 1.24).

5і * І

Рисунок 1.24 - Преобразование двух первых блоков
Элемент С может не принадлежать и2. Тогда, поскольку все маршруты пути имеют одинаковые наборы событий, существует наименьший номер к, для которого t е ак, а Сё (Ук-1- Диаграмма, показанная на рисунке 1.23, продолжается до диаграммы, изображенной на рисунке 1.25.

За 'І'
*■4-1 і
' З'Ь-1 * і

' 3,п

Рисунок 1.25 - Построение пути, первый блок которого имеет на один элемент больше
В результате приходим к маршруту пути п:
(5, ОІ и {С}) О (5г • С, СГ2) О ... о (5к_! • С, ак {С}) О ^к, (Тк+1) о ... о (5т_х, СГт).
Поскольку множество ак {С} может быть пустым, то этот маршрут имеет не более т непустых блоков. Итерируя это построение, можно построить