Модели параллельных систем и их применение для трассировки и расчета времени выполнения параллельных вычислительных процессов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Кудряшова, Екатерина Сергеевна

• Кудряшова, Екатерина Сергеевна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Кудряшова, Екатерина Сергеевна

Содержание

Введение

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. Провести эксперименты с помощью этой модели.

Методы исследования. В диссертационной работе используются методы математического и компьютерного моделирования параллельных процессов и систем. Применяется теория моноидов трасс, теория категорий и вычислительная математика. (Термины трасса и трассировка означают различные понятия.)

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

1. Построена математическая модель, обобщающая асинхронные системы и автоматы с отношением параллельности. Обобщена нормальная форма Фоаты для исследования процессов этой модели.

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

3. Дано новое доказательство формулы для вычисления ускорения асинхронного линейного конвейера, основанное на теории моновдов трасс.

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

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

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

7. Введены временные дистрибутивные асинхронные автоматы и доказано, что они обобщают временные сети Петри.

8. Разработано программное обеспечение для моделирования системы мониторинга группы виртуальных машин.

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

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

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

• Международная научно-практическая конференция «Актуальные проблемы математики, физики, информатики в вузе и школе» (г. Комсомольск-на-Амуре, 2012).

• 42-я научно-техническая конференция аспирантов и студентов (г. Комсомольск-на-Амуре, 2012).

• XXXVI Дальневосточная Математическая школа-семинар им. академика Золотова (г. Владивосток, 2012).

• Шестая Международная конференция «Параллельные вычисления и задачи управления РАСО 2012» (г. Москва, 2012).

• 43-я научно-техническая конференция аспирантов и студентов (г. Комсомольск-на-Амуре, 2013).

• Международная научная конференция «Информационные технологии XXI века» (г. Хабаровск, 2013).

• Международная конференция «Компьютерно-аналитические методы в теории управлешы и математической физике» (г. Сочи, 2013).

• XXXVIII Дальневосточная Математическая школа-семинар им. академика Золотова (г. Владивосток, 2014).

• Доклады автора занимали призовые места на конкурсах молодых ученых и аспирантов ФГБОУ ВПО «КнАГТУ» в 2013,2014 годах.

Публикации. Результаты диссертационного исследования опубликованы в 20 научных работах, в числе которых 5 статей, опубликованных в ведущих рецензируемых журналах, включенных в перечень ВАК. Получено 2 свидетельства о регистрации программ для ЭВМ.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка использованных источников. Объем диссертации составляет 112 страниц. Текст работы содержит 4 таблицы и 54 рисунка. Список литературы включает 77 источников, среди которых работы как отечественных, так и зарубежных авторов.

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

В первой главе в качестве предварительных сведений к диссертации дан краткий обзор математических моделей параллельных вычислительных систем и приведены примеры их применения. Рассмотрены системы переходов [63, 77] и их расширение - асинхронные системы [39, 74]. Рассмотрены автоматы высших размерностей и автоматы с отношением параллельности [41-43, 49-54]. Приведено определение сети Петри [12, 22].

Введены дистрибутивные асинхронные автоматы, обобщающие асинхронные системы Беднарчука. Доказано, что автоматы с отношением параллельности в смысле [43] являются дистрибутивными асинхронными автоматами (теорема 1.1). Для всякой сети Петри определен дистрибутивный асинхронный автомат с отношением независимости, используемом во временных сетях Петри (теорема 1.2). На основе теории сетей Петри описано проектирование волновых систем. Установлен ряд свойств волновых систем: отсутствие тупиков, существование наибольшего и наименьшего элементов во множестве достижимых маркировок. Разработан и обоснован метод построения маршрута волновой системы, имеющего наименьшее количество блоков (теорема 1.3). Найдены условия, при которых путь между состояниями дистрибутивного асинхронного автомата допускает разложение в композицию независимых блоков, число которых минимально (теорема 1.4).

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

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

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

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

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

Работа выполнена при поддержке программы стратегического развития ФГБОУ ВПО «КнАГТУ» 2012-2014 г. по договору: «Методы теории категорий и алгебраической топологии для исследования параллельных систем», а также при поддержке стипендиями имени Н. Н. Муравьева-Амурского (распоряжение Губернатора Хабаровского края №250-р от 5.06.2013 г., №256-р от 2.06.2014) и Президента РФ (приказ Минобрнауки России №712 от 1.07.2014).

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

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

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

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

Системы переходов. Система переходов - это одна из старейших семантических моделей для последовательных и параллельных процессов. Система переходов состоит из множества состояний с размеченными переходами между ними. Размеченным называется переход, в соответствие которому ставится функция Z\T А над некоторым алфавитом А.

Системой переходов называется четверка (5, i, L, Tran), где S — множество состояний с начальным состоянием i,L — множество меток, Tran Q S X L X S — отношение переходов [77].

Элементы (s,a,s') G Tran называются переходами. Переход (s, а, s')

а

обычно записывается как s s . Системы переходов представляют собой модели процессов; при этом переходы олицетворяют атомарные действия процессов, а метки - имена действий. На рисунке 1.1 изображена система переходов с множеством состояний S = {¿, s, и]. Начальным состоянием будет Стрелка

а

i s обозначает переход (i,a,s). Она показывает, что этот переход переводит систему из начального состояния i в новое состояние s. Аналогично задаются переходы (i, b, s), (s, с, s), (s, b, и) 6 Tran.

¿0

а

__с

Q

• и

Рисунок 1.1— Система переходов

ах а2 ап

Последовательность переходов s Si ----> sn будем записывать в виде

v

s —> sn, где v = а1а2...ап представляет собой последовательность меток из L.

Приведем пример системы переходов [57]. Для этого рассмотрим торговый автомат для продажи чая и кофе. Система переходов имеет множество состояний S = {s0, slt s2}. Множество переходов с метками L = {coin, tea, coffee] показаны на рисунке 1.2.

coin coin

Рисунок 1.2 - Система переходов торгового автомата

Начальное состояние s0 означает, что автомат готов к работе. В состоянии автомат готов выдать чай, в состоянии s2 - выдать кофе. Работа автомата заключается в следующем: получив монету coin, автомат может выдать чай после нажатия кнопки tea или дождаться еще одной монеты coin и выдать кофе. После этого автомат снова готов к работе.

Асинхронные системы. Асинхронные системы были введены в диссертации Беднарчука [39] и работе Шилдса [74] независимо друг от друга. Они основываются на идее расширения систем переходов с указанием переходов, независимых между собой.

Асинхронная система — это пятерка (S, i, Е, Tran, /), где (S,i,E,Tran) — система переходов, IQ Е2 - антирефлексивное симметричное отношение независимости на множестве Е событий, такое что:

1. (5, е, s') Е Tran & (s, е, s") Е Tran => s' = s";

2. ej/e2 & (s,eltsx) e Tran & (slt e2,u) 6 Tran => (3 s2) (s, e2, s2) £ Tran & (s2, elt и) E Tran.

Аксиома (1) показывает, что одно событие переводит систему из некоторого начального состояния в конечное, которое будет уникальным. Аксиома (2) выражает свойство независимости: если два независимых события могут выполняться один после другого, должно быть возможно их выполнение в обратном порядке, приводящее из того же начального состояния в то же конечное (рисунок 1.3).

и

S

Рисунок 1.3 - Отношение независимости e^Ie-z

Если в асинхронной системе не выделять начальное состояние, то мы приходим к пространству состояний. Таким образом, пространством состояний называется четверка (S,E,l,Tran), такая что S,E — множества, / - отношение независимости на Е, Tran QS X Е х 5 - подмножество, удовлетворяющее аксиомам (1)-(2).

Автоматы высших размерностей. Автоматы высших размерностей

являются обобщением конечных автоматов. Недетерминированным конечным

автоматом называется пятерка А = (Q,2,5,q0,F), состоящая из конечного

множества состояний Q, конечного множества входных символов Е, начального

состояния q0 6 Q, множества допустимых финальных или заключительных

состояний F Q Q, функции действия S: Q X 2 2° [29]. Конечный автомат

является автоматом размерности 1.

Автоматом высшей размерности называется набор множеств Мп (п Е М)

d9

вместе с функциями Мп \ Mn_l5 где п EN и 0 < i,j < п — 1, такими что

dj

df ° dj = о df (i < j, k,l = ОД) и V 71, m 71 & m, Mn П Mm = 0.

Элемент x из Mn называется «-переходом (или состоянием, если п = 0)

[52].

Автоматы с отношением параллельности. Недетерминированным автоматом с отношением параллельности называется четверка Л = Т, ||), где Q и Е - счетные непересекающиеся непустые множества состояний (или ситуаций) и действий соответственно, Т Q Q xZx Q — множество переходов, и 11= (llq)q6Q - семейство антирефлексивных симметричных бинарных отношений

параллельности ||q на Е.

Отношение а b означает, что действия а и b могут выполняться независимо друг от друга в состоянии или ситуации q. Если а \\q b, имеются состояния q,q',r £ Q и переходы (р, а, q), (р, b, q'), (q, b,г), (q', а,г)вТ [41].

Недетерминированный автомат с отношением параллельности Л — (Q,E, Т, ||) называется детерминированным если из (р, а, q), (р, а, г) ET следует

q = г. В этом случае мы называем Л детерминированным автоматом с отношением параллельности или просто автоматом с отношением параллельности [42].

Сети Петри. Сеть Петри определяется как пятерка (Р, Т, pre, post, М0), состоящая из конечных множеств Р и Т , функций MQ:P N,pre:T Np,post:T Np. Здесь Np обозначает множество всех функций Р№. Элементы р Е Р называются местами, t ЕТ — переходами, ME Мр — маркировками, а М0 — начальной маркировкой. Исходя из структуры сети, граф сети Петри обладает двумя типами вершин: место обозначается кружком, а переход - прямоугольником. Ориентированные дуги (стрелки) соединяют места и переходы. При этом некоторые дуги направлены от мест к переходам, а другие — от переходов к местам. Дуга, направленная от места pi к переходу tj, определяет место перехода, которое является входным. Напротив, дуга от перехода tj к месту Pi+1 определяет выходное место перехода [22].

Маркировка - это функция М: Р N, которая ставит в соответствие каждому месту сети неотрицательное натуральное число (рисунок 1.5). Значение маркировки обозначается с помощью М(р) точек, которые называются фишками. Графически фишки обозначаются в виде точек внутри места либо записываются числом, если их количество велико. Фишки используются для определения выполнения сети Петри. При этом их количество и положение может изменяться. Это происходит посредством срабатываний переходов сети.

Определим отношение порядка на полагая М < М', если для всех р Е Р верно А/(р) < М'(р). Сумму и разность функций определим как (Af ± М')(р) =

М(р) ± М'(р). Для М,М'ENP и tET запись М -* М' будет означать, что выполнены следующие два условия:

М > pre(t);

М' = М- pre(t) + post(t).

В этом случае, мы будем говорить, что маркировка М' получена из М с помощью срабатывания перехода t.

Срабатывание перехода означает удаление фишек из его входных мест и появлением фишек в выходных местах. Срабатывание перехода возможно, если каждое входное место перехода имеет число фишек, по крайней мере, равное числу стрелок из места в переход, т.е. М > pre(t). Такой переход называется разрешенным.

На рисунке 1.4 переход t2 разрешен в маркировке М0 = (2,0,1,1). При срабатывании перехода t2 произойдет удаление фишек из мест р3,р4 и появление фишки в месте р2. Маркировка сети примет вид = (2,1,0,0) (рисунок 1.6). Дальнейшее выполнение сети происходит аналогичным образом.

Pi Рз

Pi Рз

Место р сети Петри называется безопасным, если для всех маркировок сети М справедливо М(р) < 1. Соответственно, сеть безопасна, если все ее места безопасны.

Если в качестве состояний сети Петри рассматривать маркировки М: Т М, удовлетворяющие для всех р € Р неравенству М(р) < 1, то мы получим так называемую элементарную сеть Петри. Элементарная сеть Петри называется также С/Е-сетъю, а обычная - Р/Т-сетью. Всякую элементарную сеть Петри можно превратить в безопасную сеть, имеющую те же переходы, в которой не достижимы маркировки М, не удовлетворяющие неравенству М(р) < 1. Поэтому мы можем рассматривать элементарную сеть Петри как обычную.

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

Р1 Рз

Сеть Петри называется синхронизационным графом (или маркированным графом [18]), если |рге(£)(р)| = |ро$С(£)(р)| = 1, т.е. если в каждое место сети входит ровно одна дуга и из каждого места выходит ровно одна дуга (рисунок 1.7) [12].

Рг

Рисунок 1.7 — Синхронизационный граф

Рассмотрим свойство синхронизационного графа. Пусть (xltx2, ...,хп) — последовательность элементов сети такая, что Xi xi+1 для 1 < i < п — 1 и Xi Xj для любых двух элементов сети, кроме i = 1 и j = п. Такая последовательность называется простой путь. В случае если х1 = хп, простой путь называется простым циклом. Будем говорить, что простой путь (и цикл) содержит п фишек при разметке М, если п — сумма фишек в проекции М(Р') разметки М на множестве мест Р' Q Р, входящих в этот путь.

Имеет место утверждение, что при функционировании синхронизационного графа число фишек, содержащихся в любом его цикле, остается постоянным. Доказательство подробно рассмотрено в [12, теорема 4.4].

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

В данном пункте мы введем математическую модель параллельных систем, обобщающую асинхронную систему М. Беднарчука [39] и докажем, что класс этих моделей включает автоматы с отношением параллельности, введенные в [43].

Дистрибутивным асинхронным автоматом называется пятерка <Л = (S,s0,E,3,Tran), состоящая из множеств S и Е, элемента s0 6 5, отношения Tran Q S X Е X S и семейства антирефлексивных симметричных отношений J = Qs)ses> 4 — Е х Е- Элементы s € S называются состояниями, е G Е — инструкциями (действиями, событиями), s0 — начальным состоянием.

Должны быть выполнены следующие условия:

/. (s, а, s') е Tran & (s, а, 5") е Tran => s' = s".

iL Для любых s ES, (alt а2) E Is, (5, av sE Tran и (sj, a2, s') G Tran существует такое s2 E S, что (s, a2, s2) E Tran и (52, alt 5') G Tran (рисунок 1.8).

S

\

\

«2 \

/ Ol

Л ✓

S2

Рисунок 1.8 — Условие (ii) для асинхронных автоматов

Всякую асинхронную систему (S,s0,E,l,Tran) можно рассматривать как дистрибутивный асинхронный автомат, полагая ls — I для всех s Е S.

Обозначим отличие определения дистрибутивного асинхронного автомата от автомата с отношением параллельности, который ввели М. Droste и R. М. Shortt [43]. Напомним, что автоматом с отношением параллельности называется четверка Л = (Q,2,T, ||), где Q и Е - множества состояний (или ситуаций) и действий соответственно, TQQxZxQ - множество переходов, и ||= (||ч) —

семейство антирефлексивных симметричных бинарных отношений параллельности \\q на Е. Следуя Губо [50], в автомате с отношением параллельности будем также выделять начальное состояние q0.

Для удобства обозначим множество состояний Q через S, множество действий Е через Е, множество переходов Т через Tran, отношение параллельности || через 0, а начальное состояние q0 чрез s0.

Определение автомата с отношением параллельности отличается от определения дистрибутивного асинхронного автомата тем, что условие ii заменяется следующим:

Для любых (а1( а2) 6 Is существуют slt s2, s' Е S, для которых (5, alt sx) G Tran, (slt a2, s') G Tran, (s, a2, s2) G Tran, (s2, alf s') G Tran.

Пример асинхронной системы S = {s0,s2}, E = {av a2}, I = {(alt a2), (a2, ßi)}, имеющей переходы, изображенные на рисунке 1.9, показывает, что не всякая асинхронная система будет автоматом с отношением параллельности. Поэтому определение автомата с отношением параллельности не является более широким, чем наше.

19 «1

S0-*-S 1

S2

Рисунок 1.9-Асинхронная система, не автомат с отношением параллельности

Широкий класс дистрибутивных асинхронных автоматов, не являющихся автоматами с отношением параллельности, можно построить следующим образом:

Если в дистрибутивном асинхронном автомате Л = (S,so,E,0,Tran) существуют состояния s, slf s2 6 S, пара событий (alf a2) E Is, пара переходов (Sjd^Sí) eTran и (s,a2,s2) STran, для которых не существует состояний s' 6 S, допускающих переходы (sx, а2, s') или (s2, alt s'), то <А не будет удовлетворять аксиоме (¿¿') для автоматов с отношением параллельности. В этом случае мы будем говорить, что в состоянии s нарушена конфлюэнтность. Всякий дистрибутивный асинхронный автомат, имеющий хотя бы одно состояние, в котором нарушена конфлюэнтность не будет удовлетворять аксиоме (¿¿') и, значит, не будет автоматом с отношением параллельности.

Например, дистрибутивный асинхронный автомат Л = (S,s0,E,3,Tran), состоящий из множества состояний 5 = {s0,5lls2,s3ls4}, множества событий Е = {(alt a2], отношений независимости ISq = ISl = {(alf a2), (a2, %)}, IS2 = IS3 = /S4 = 0, переходы которого показаны на диаграмме (рисунок 1.10) не будет автоматом с отношением параллельности, поскольку в s1 нарушена конфлюэнтность.

Список литературы диссертационного исследования кандидат наук Кудряшова, Екатерина Сергеевна, 2014 год

Список использованных источников

1 Беляев, А. А. Теория, разработка и создание проблемно-ориентированных процессорных ядер с оптимальным вычислительным конвейером и многоядерных сигнальных процессоров на их основе: дис. ... доктора техн. наук : 05.13.05 / Беляев Андрей Александрович. - Москва, 2012. — 377 с.

2 Вирбицкайте, И. Б. Использование техники частичных порядков для верификации временных сетей Петри / И. Б. Вирбицкайте, Е. А. Покозий // Программирование. - 1999. - № 1. - С. 28-41.

3 Вирбицкайте, И. Б. Метод параметрической верификации поведения временных сетей Петри / И. Б. Вирбицкайте, Е. А. Покозий // Программирование. -1999.-№4.-С. 16-29.

4 Вирбицкайте, И. Б. Семантические области временных структур событий / И. Б. Вирбицкайте, Р. С. Дубцов // Программирование. - 2008. - № 3. -С. 3-20.

5 Водяхо, А. И. Высокопроизводительные системы обработки данных: учеб. пособие для вузов / А. И. Водяхо, Н. Н. Горнец, Д. В. Пузанков. - М.: Высш. шк., 1997. - 304 с.

6 Воеводин, В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. - Санкт-Петербург : БХВ-Петербург, 2002. - 602 с.

7 Герасимов, А. А. Способы формального описания асинхронных схем / А. А. Герасимов, П. В. Кустарев ; под ред. д.т.н., проф. Т. И. Алиева // Сборник трудов молодых ученых и сотрудников кафедры ВТ. - СПб: СПбГУ ИТМО, 2010. -С. 31-35.

8 Герценбергер, К. В. Аналитическая модель оценки производительности многопроцессорной обработки данных для набора параллельных алгоритмических структур / К. В. Герценбергер, Е. В. Чепин // Бизнес-информатика. - 2011. - Т. 18. - № 4. - С. 24-30.

9 Дубцов, Р. С. Теоретико-категорные исследования временных систем переходов с независимостью / Р. С. Дубцов // IX Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям, Кемерово, 28-30 октября 2008 г. - Режим доступа: http://www.ict.nsc.ru/ws/YM2008/14295/dubtsov.pdf

10 Калиткин, Н. Н. Численные методы / Н. Н. Калиткин. - М: Наука, 1978. -512 с.

11 Карпов, В. Е. Введение в распараллеливание алгоритмов и программ /

B. Е. Карпов // Компьютерные исследования и моделирование. — 2010. — Т. 2. — № З.-С. 231-272.

12 Котов, В. Е. Сети Петри / В. Е. Котов. - М. : Наука. Главная редакция физико-математической литературы, 1984. — 160 с.

13 Коуги, П. М. Архитектура конвейерных ЭВМ: Пер. с англ. — Радио и связь, 1985.

14 Кудряшова, Е. С. Временные оценки и гомоморфизмы асинхронных систем / Е. С. Кудряшова, А. А. Хусаинов // Наука и образование: Электронное научно-техническое издание.-2014.-№ 1.-С. 134-149.

15 Кудряшова, Е. С. Временные сети Петри для мониторинга группы виртуальных машин / Е. С. Кудряшова // Современное состояние естественных и технических наук: материалы IV Междунар. науч.-практ. конф., Москва, 10 октября 2011 г. - Москва: Научный журнал «Естественные и технические науки» и изд-во «Спутники-», 2011. - С. 80-86.

16 Кудряшова, Е. С. Время работы асинхронного линейного конвейера / Е.

C. Кудряшова // XXXVIII дальневосточная математическая школа-семинар им. академика Е.В. Золотова, 1-5 сентября 2014 г.: сб. материалов [Электронный ресурс]. - Владивосток: НАЛУ ДВО РАН, 2014. - С. 410-414.

17 Кудряшова, Е. С. Обобщенные асинхронные системы / Е. С. Кудряшова, А. А. Хусаинов // Моделирование и анализ информационных систем. — 2012. — Т. 19.-№4.-С. 78-86.

18 Кудряшова, Е. С. Применение временных сетей Петри для разработки систем реального времени мониторинга состояния объектов / Е. С. Кудряшова // Ученые записки Комсомольского-на-Амуре гос. техн. университета. Науки о природе и технике. - 2014. - № 1-1(17). - С. 40-46.

19 Кудряшова, Е. С. Моделирование конвейерных и волновых вычислений / Е. С. Кудряшова, Н. Н. Михайлова, А. А. Хусаинов // Интернет-журнал «Науковедение», 2014 №1 (20) [Электронный ресурс] - М.: Науковедение, 2014. Режим доступа: http://naukovedenie.ru/PDF/56TVNl 14.pdf

20 Кудряшова, Е. С. Расчет времени и трассировка волновых схем параллельных вычислений / Е. С. Кудряшова, А. А. Хусаинов // Естественные и технические науки. - 2014. - № 9-10. - С. 294-302.

21 Кун, С. Матричные процессоры на СБИС / Пер. с англ. - М.: Мир, 1991.

- 672 с.

22 Питерсон, Дж. Теория сетей Петри и моделирование систем / Дж. Питерсон ; пер. с англ. М. В. Горбатовой, В. Л. Торхова, В. Н. Четверикова ; под ред. В. А. Горбатова. - М. : Мир, 1984. - 264 с.

23 Покозий, Е. А. Метод верификации свойств параллелизма временных сетей Петри / Е. А. Покозий // Препринт № 61. - Новосибирск : Институт Систем Информатики СО РАН, 1999. - 28 с.

24 Соколинский, Л. Б. Методы организации параллельных систем баз данных на вычислительных системах с массовым параллелизмом: дис. ... доктора физ.-мат. наук : 05.13.18 / Соколинский Леонид Борисович. - Челябинск, 2003. — 247 с.

25 Трещев, И. А. Математическая модель гибридной временной волновой системы / И. А. Трещев // Системы управления и информационные технологии. — 2007.-N4(30).-С. 19-21.

26 Трещев, И. А. Математические модели параллельных вычислительных процессов и их применение для построения многопоточных приложений на системах с 8МР-архитектурой: дис. ... к.т.н.: 05.13.18 / Трещев Иван Андреевич.

- Комсомольск-на-Амуре, 2009. — 114 с.

27 Трещев, И. А. Методы построения систем автоматизированного распараллеливания приложений для архитектур с симметрично-адресуемой памятью / И. А. Трещев // Ученые записки Комсомольского-на-Амуре гос. техн. университета. Науки о природе и технике. - 2011. - № 1-1(2). - С. 29-32.

28 Трещев, И. Математические модели параллельных вычислительных процессов / И. Трещев. - Саарбрюкен : LAP LAMBERT Academic Publishing, 2013.- 128 с.

29 Хопкрофт, Д. Э. Введение в теорию автоматов, языков и вычислений / Д. Э. Хопкрофт, Р. Мотвани, Д. Д. Ульман. — М. : Издательский дом «Вильяме», 2002. - 528 с.

30 Хусаинов, А. А. Архитектура вычислительных систем: учеб. пособие / А. А. Хусаинов, Н. Н. Михайлова. - Комсомольск-на-Амуре: изд-во Комсомольского-на-Амуре гос. техн. ун-та, 2006. - 123 с.

31 Хусаинов, А. А. Математическая модель задачи о читателях и писателях / А. А. Хусаинов // Информационные технологии и высокопроизводительные вычисления: материалы Междунар. науч.-практ. конф., Хабаровск, 4-6 октября 2011 г. - Хабаровск: Изд-во Тихоокеан. гос. ун-та, 2011. - С. 327-332.

32 Хусаинов, А. А. Модель для временных оценок параллельных вычислительных систем / А. А. Хусаинов, Е. С. Кудряшова // Информационные технологии XXI века: материалы Междунар. науч. конф., Хабаровск, 20-24 мая 2013 г. - Хабаровск: Изд-во Тихоокеан. гос. ун-та, 2013ю - С. 203-207.

33 Хусаинов, А. А. Нормальная форма для процесса волновых вычислений / А. А. Хусаинов, Е. С. Кудряшова // XXXVIII дальневосточная математическая школа-семинар им. академика Е.В. Золотова, 1-5 сентября 2014 г.: сб. материалов [Электронный ресурс]. - Владивосток: ИАПУ ДВО РАН, 2014. - С. 462-468.

34 Хусаинов, А. Исследование параллельных систем методами теории категорий / А. Хусаинов. - Саарбрюкен : LAP LAMBERT Academic Publishing, 2012.-152 с.

35 Цилькер, Б. Я. Организация ЭВМ и систем: учебник для вузов / Б. Я. Цилькер, С. А. Орлов. - СПб.: Питер, 2011. - 668 с.

36 Alur, R. The theory of timed automata / R. Alur, D. Dill // Lecture Notes in Computer Science. - Berlin: Springer-Verlag. - 1991. -V. 600. - P. 45-73.

37 Andrews, G. R. Foundations of multithreaded, parallel, and distributed programming / G. R. Andrews. - Wesley, University of Arizona, USA. - 2000.

38 Bachmann, J. P. Time-independent Liveness in Time Petri Nets / J. P. Bachmann, L. Popova-Zeugmann // Fundamenta Informaticae. - 2010. — № 102. — P. 1-17.

39 Bednarczyk, M. A. Categories of Asynchronous Systems: Ph.D. thesis / Marek A. Bednarczyk. - University of Sussex, 1988.

40 Cartier, P. Problemes combinatories de commutation et rearrangements / P. Cartier, D. Foata // Lecture Notes in Math. - Berlin : Springer-Verlag. - 1969. - V. 85. -88 p.

41 Droste, M. Automata with concurrency relations / M. Droste, D. Kuske // Advances in logic, artificial intelligence and robotics. - Amsterdam : IOS Press. -2002.-V. 85.-P. 152-172.

tíi

42 Droste, M. Concurrency, automata and domains / M. Droste // In 17 ICALP, Lecture Notes in Computer Science. - Berlin : Springer. - 1990. - V. 443. - P. 195208.

43 Droste, M. Petri nets and automata with concurrency relations — an adjunction. In M. Droste and Y. Gurevich, editors / M. Droste, R.M. Shortt // Semantics of Programming Languages and Model Theory. - Amsterdam: Gordon and Breach Science Publ., OPA, 1993. P. 69-87.

44 Diekert, V. Combinatorics on Traces / V. Diekert // Lecture Notes in Computer Science. - Berlin : Springer-Verlag. - 1990. -V. 454. - 169 p.

45 Diekert, V. Partial Commutation and Traces / V. Diekert, Y. Metivier // Handbook of formal languages. - New York : Springer-Verlag. - 1997. - V. 3. — P. 457-533.

46 Dijkstra, E. W. Co-operating Sequential Processes / E. W. Dijkstra // Programming Languages. - New York: Academic Press. - 1968. - P. 65-138.

47 Ebergen, J. Response-Time Properties of Linear Asynchronous Pipelines / J. Ebergen, R. Berks //Proceedings of IEEE. - 1999. -V. 87. - № 2. -P. 308-318.

48 Goubault, E. A homology of higher dimensional automata / E. Goubault, T. P. Jensen // Concur 92, Springer LNCS 630. - 1992. - P. 254-268

49 Goubault, E. Cubical Sets are Generalized Transition Systems / E. Goubault // Homology of higher dimensional automata Technical report, preproceedings of CMCIM'02,2001.-20 p.

50 Goubault, E. Durations for truly-concurrent transitions / E. Goubault // Programming Languages and Systems - ESOP '96, Lecture Notes in Computer Science. - Berlin : Springer-Verlag. - 1996. - V. 1058. - P. 173-187.

51 Goubault, E. Formal Relationships Between Geometrical and Classical Models for Concurrency / E. Goubault, S. Mimram // Preprint, arXiv: 1004.2818vl [cs.DC]. -New York: Cornell Univ. -2010. - 15 p. http://arxiv.org/abs/1004.2818vl

52 Goubault, E. Labeled cubical sets and asynchronous transitions systems: an adjunction / E. Goubault // In Preliminary Proceedings CMCIM'02. - 2002. http://www.lix.polytechnique.frr goubault/papers/cmcim02.ps.gz

53 Goubault, E. The Geometry of Concurrency: Ph.D. Thesis / Eric Goubault. -Ecole Normale Superieure, 1995. - 349 p.

54 Heiner, M. Worst-case Analysis of Concurrent Systems with Duration Interval Petri Nets / M. Heiner, L. Popova-Zeugmann // Reihe Informatik. - 1996. — I-02.-16 p.

55 Hennessy, John L. Computer architecture: a quantitative approach / John L. Hennessy, David A. Patterson. - USA: Elsevier, 2007. - 705 p.

56 Henzinger, T. A. Timed transition systems / T. A. Henzinger, Z. Manna, A. Pnueli; In G. Goos, J. Hartmanis, editor // Real-Time: Theory in Practice, Lecture Notes in Computer Science 600, Springer-Verlag. - 1991. - P. 226-251.

57 Hildebrant, T. T. Transition Systems with Independence and Multi-Arcs / T. T. Hildebrant, V. Sassone // BRICS. - Denmark, 1997. - 23 p.

58 Husainov, A. On the homology of small categories and asynchronous transition systems / A. Husainov // Homology Homotopy Appl. - 2004. - V. 6. - № 1. -P. 439-471.

59 Hu, Y. H. Systolic arrays / Y. H. Hu, S. Y. Kung // Handbook of Signal Processing Systems. - New York: Springer. - 2013. - P. 1111-1143.

60 Mazurkiewicz, A. Basic notions of trace theory / A. Mazurkiewicz // Linear time, branching time and partial order in logics and models for concurrency, Lecture Notes in Computer Science. - Berlin: Springer-Verlag. - 1989. - V. 354. - P. 285-363.

61 Mazurkiewicz, A. Trace theory / A. Mazurkiewicz // Lecture Notes in Computer Science. - Berlin : Springer-Verlag. - 1987. - V. 255. - P. 278-324.

62 Merlin, P. A Study of the Recoverability of Communication Protocols: Ph.D. Thesis / Philip M. Merlin. - University of California, Computer Science Dept., Irvine, 1974.

63 Milner, R. Communicating and Mobile Systems: the rc-Calculus / R. Milner. - Cambridge university press, 1999. -161 c.

64 Modular System Development with Pullbacks / M. A. Bednarczyk, L. Bernardinello, B. Caillaud, W. Pawlowski, L. Pomello // Applications and Theory of Petri Nets 2003, Lecture Notes in Computer Science. — Berlin : Springer-Verlag. — 2003.-V. 2679.-P. 140-160.

65 Penczek, W. Advances in Verification of Time Petri Nets and Timed Automata / W. Penczek, A. Pólrola // Poland: Springer. - 2006. - V. 20. - P. 257.

66 Petri, C. A. Non-sequential processes / C. A. Petri // GMD-ISF Report ISF-77-05, 1977.

67 Popova, L. On Time Petri Nets / L. Popova //J. Inform. Process. Cybem. -1991.-№4.-P. 227-244.

68 Popova-Zeugmann, L. Analyzing Paths in Time Petri Nets / L. Popova-Zeugmann, D. Schlatter // Fundamenta Informaticae. - 1999. - № 34. - P. 1-18.

69 Popova-Zeugmann, L. Essential States in Time Petri Nets / L. Popova-Zeugmann // Informatik-Berichte 96. - 1998. - 14 p.

70 Popova-Zeugmann, L. Quantitative evaluation of time-dependent Petri nets and applications to biochemical networks / L. Popova-Zeugmann // Natural Computing. -2011. — V. 10.-№3.-P. 1017-1043.

71 Popova-Zeugmann, L. State Equation for Interval-Timed Petri Nets / L. Popova- Zeugmann, E. Pelz // Proceedings of the international workshop CS&P. — Poland, 2011.-P. 416-419.

72 Popova-Zeugmann, L. Time Petri Nets for Modelling and Analysis of Biochemical Networks / L. Popova- Zeugmann, M. Heiner, I. Koch // Fundamenta Informaticae 67. - Amsterdam: IOS Press, 2005. - P. 149-162.

73 Ramchandani, C. Analysis of asynchronous concurrent systems by Timed Petri Nets / C. Ramchandani // Project MAC-TR 120, MIT. - 1974.

74 Shields, M.W. Concurrent machines / M.W. Shields // Computer Journal. -1985.-V. 28.-P. 449-465.

75 Wegener, J. Petri Nets with Time Windows: a comparison to Classical Petri Nets / J. Wegener, L. Popova-Zeugmann // Fundamenta Informaticae. - 2009. - № 93. - P. 337-352.

76 Winskel, G. Events in Computation: PhD thesis / G. Winskel. - University of Edinburgh, 1980.

77 Winskel, G. Models of concurrency / G. Winskel, M. Nielsen // Handbook of Logic in Computer Science. - Oxford University Press, 1995. - V. 4. - P. 1-148.