Содержание к диссертации
Введение
1 Математические модели параллельных вычислительных систем 10
1.1 Предварительные сведения 10
1.2 Дистрибутивные асинхронные автоматы 17
1.3 Сети Петри как дистрибутивные асинхронные автоматы 20
1.4 Волновые системы 24
1.5 Максимальная нормальная форма 31
2 Расчет времени выполнения параллельного процесса 37
2.1 Основные определения 37
2.2 Асинхронная система с функцией времени 41
2.3 Псевдо-конвейер. Вычисление минимального времени выполнения 48
2.4 Асинхронный конвейер. Вычисление времени выполнения 55
2.5 Волновая система. Вычисление времени выполнения 70
3 Временные дистрибутивные асинхронные автоматы и сети Петри 84
3.1 Временные сети Петри 84
3.2 Временные дистрибутивные асинхронные автоматы 86
3.3 Временные сети Петри как временные дистрибутивные асинхронные автоматы 88
3.4 Волновые системы как временные дистрибутивные асинхронные автоматы 91
3.5 Дистрибутивные асинхронные автоматы с задержками 94
3.6 Применение временных сетей Петри 95
Заключение 103
Список использованных источников
- Сети Петри как дистрибутивные асинхронные автоматы
- Максимальная нормальная форма
- Псевдо-конвейер. Вычисление минимального времени выполнения
- Временные сети Петри как временные дистрибутивные асинхронные автоматы
Сети Петри как дистрибутивные асинхронные автоматы
Асинхронные системы. Асинхронные системы были введены в диссертации Беднарчука [39] и работе Шилдса [74] независимо друг от друга. Они основываются на идее расширения систем переходов с указанием переходов, независимых между собой.
Асинхронная система - это пятерка (S,і,Е,Тгап,/), где (S,i,E,Tran) -система переходов, I Q Е2 - антирефлексивное симметричное отношение независимости на множестве Е событий, такое что:
Отношение независимости е11е2 Если в асинхронной системе не выделять начальное состояние, то мы приходим к пространству состояний. Таким образом, пространством состояний называется четверка (S,E,I,Tran), такая что S,E - множества, / - отношение независимости на Е, Tran Q S х Е х S - подмножество, удовлетворяющее аксиомам (1 )-(2).
Автоматы высших размерностей. Автоматы высших размерностей являются обобщением конечных автоматов. Недетерминированным конечным автоматом называется пятерка А = ((?,, 8, q0,F), состоящая из конечного множества состояний Q, конечного множества входных символов Z, начального состояния q0 Є Q, множества допустимых финальных или заключительных состояний F Q Q, функции действия S:QxT,- 2Q [29]. Конечный автомат является автоматом размерности 1.
Автоматом высшей размерности называется набор множеств Мп (п Є М) вместе с функциями Мп = "i Mn_i, где п Є N и 0 i,j п — 1, такими что df о dj = dj_1 о df (і j,k,l = 0,1) и\/п,тпФ т, МпГ\Мт = 0. Элемент х из Мп называется «-переходом (или состоянием, если п = 0) [52]. Автоматы с отношением параллельности. Недетерминированным автоматом с отношением параллельности называется четверка Л = {Q, , Т, ), где Q и 2 - счетные непересекающиеся непустые множества состояний (или ситуаций) и действий соответственно, Т Q Q хТ,х Q - множество переходов, и = (д) - семейство антирефлексивных симметричных бинарных отношений параллельности iL на Т..
Отношение a \\q Ъ означает, что действия а и Ъ могут выполняться независимо друг от друга в состоянии или ситуации q. Если a \\q Ъ, имеются состояния q,q ,r Є Q и переходы (р, a, q),(p,b,q ), (q, b, г), (q t а, г) в Т [41].
Недетерминированный автомат с отношением параллельности Л = (Q#I,T, ) называется детерминированным если из (p,a,q)t(ptatr) Є Г следует q = г, В этом случае мы называем Л детерминированным автоматом с отношением параллельности или просто автоматом с отношением параллельности [42],
Сети Петри. Сеть Петри определяется как пятерка (Р,Т,pre,post, MQ), состоящая из конечных множеств Р и Т , функций М0:Р -» N,pre:T -» Np,post:T -» Мр, Здесь Мр обозначает множество всех функций Р - N. Элементы р Є Р называются местами, t Є Т — переходами, М Є Np — маркировками, а М0 — начальной маркировкой. Исходя из структуры сети, граф сети Петри обладает двумя типами вершин: место обозначается кружком, а переход — прямоугольником. Ориентированные дуги (стрелки) соединяют места и переходы. При этом некоторые дуги направлены от мест к переходам, а другие - от переходов к местам. Дуга, направленная от места pi к переходу tj, определяет место перехода, которое является входным. Напротив, дуга от перехода tj к месту Pt+1 определяет выходное место перехода [22],
Маркировка — это функция M:P— N, которая ставит в соответствие каждому месту сети неотрицательное натуральное число (рисунок 1,5), Значение маркировки обозначается с помощью М(р) точек, которые называются фишками. Графически фишки обозначаются в виде точек внутри места либо записываются числом, если их количество велико. Фишки используются для определения выполнения сети Петри, При этом их количество и положение может изменяться. Это происходит посредством срабатываний переходов сети,
Срабатывание перехода означает удаление фишек из его входных мест и появлением фишек в выходных местах. Срабатывание перехода возможно, если каждое входное место перехода имеет число фишек, по крайней мере, равное числу стрелок из места в переход, т.е. М pre(t). Такой переход называется разрешенным.
На рисунке 1.4 переход t2 разрешен в маркировке М0 = (2,0,1,1). При срабатывании перехода t2 произойдет удаление фишек из мест р3,р4и появление фишки в месте р2. Маркировка сети примет вид М± = (2,1,0,0) (рисунок 1.6). Дальнейшее выполнение сети происходит аналогичным образом.
Максимальная нормальная форма
Два пути между s Є S и s Є S называются эквивалентными, если один из них может быть получен из другого с помощью некоторой конечной последовательности элементарных преобразований.
Поскольку элементарные преобразования лишь переставляют, но не добавляют и не удаляют события, то эквивалентные пути имеют одинаковые наборы событий.
Одновременное выполнение конечной последовательности переходов введем с помощью независимых блоков. Напомним, что размещением (ilt i2, ...fife) во множестве {1,2, ...,п} называется набор элементов этого множества, для которого функция j »- ц определяет инъекцию {1, ...,&}-
Независимым блоком (s,{%, ...,ап}) называется состояние s GS вместе с множеством событий таких, что (ait а;) Є /s для всех 1 і j п. Кроме того, для каждого размещения (ilt i2, —fife) во множестве и для каждого двухэлементного подмножества {i,j} Q [1, ...,n}\{ilt ...,ik} имеет место (dj, а,) Є Isa. a. . Состояние s называется началом независимого блока.
Независимый блок можно рассматривать как «-мерный куб с вершинами satl ...aik. Каждому і Є {1, ...,n} \ {i±l..., ik] будет соответствовать направленное ребро этого куба. Оно соединяет вершину sai±... aik с вершиной sa ... CLika.
Пусть (5, а1; ...,ап) - путь между sES и s ES. Независимый блок (5,{blt ...,bm}) называется блоком этого пути с началом s, если существуют такие, что этот путь эквивалентен пути (5,bv В этом случае существует такое размещение (ilti2 — Лт) в {1,2, ,п}, что Ьі = а-іг b2 = аІ2,...,Ьт = аіт.
Максимальная форма не является единственной. Если максимальная форма единственна, то мы будем называть ее максимальной нормальной формой. Для использования максимальной нормальной формы в программировании задают отношение линейного порядка на множестве событий, и независимые блоки определяют как возрастающие конечные последовательности попарно независимых событий.
Пусть 7Г = (s, alt —,CLn) - ПУТЬ в дистрибутивном асинхронном автомате. Его окружением П(7г) называется множество вершин всех путей, эквивалентных пути я. Окружение П(7г) можно рассматривать как дистрибутивный асинхронный автомат, событиями которого служат элементы а Є {alt ...,ап), а переходами -тройки (у, a, v а), такие, что v Є П(7г) и v а Є П(л:). Начальное состояние равно s. События независимы в П(7г) тогда и только тогда, когда они независимы во всем дистрибутивном асинхронном автомате.
Теорема 1.4. Пусть л = (s,av ...,an) - путь в дистрибутивном асинхронном автомате между s Є S и s Є S. Если для всякого состояния v Є П(7г) существует наибольшее подмножество о попарно независимых событий окружения с началом в V, причем (у, а) для него будет независимым блоком, то максимальная форма пути будет иметь наименьшее число независимых блоков.
Доказательство. Ясно, что в условиях этой теоремы максимальная форма будет единственной, каждый ее блок будет состоять из наибольшего множества событий из П(7г), исходящих из текущего состояния.
Рассмотрим некоторый маршрут (s, аг) о (slt а2) (sm-i, 0Vn) пути п, число блоков которого т минимально. Предположим, что этот маршрут, не является максимальной формой. В этом случае какой-нибудь из блоков этого маршрута не будет максимальным. Будем доказывать, что число блоков максимальной формы пути п будет не больше, чем т. С этой целью рассмотрим сначала случай, при котором первый блок (s, аЛ) не является максимальным. В этом случае существует событие t Є П(тт), которым можно дополнить первый блок. Согласно условиям теоремы, множество ог U {t} будет определять независимый блок (s, 0"i U {t}). Получаем диаграмму, составленную из событий и состояний дистрибутивного асинхронного автомата П(л") (рисунок 1.23). - -Sl
Элемент t может не принадлежать о2. Тогда, поскольку все маршруты пути имеют одинаковые наборы событий, существует наименьший номер к, для которого t Є ок, a t & 0fc_i. Диаграмма, показанная на рисунке 1.23, продолжается до диаграммы, изображенной на рисунке 1.25.
В результате приходим к маршруту пути тг: (s,01 U {t}) о (5l t,о2) о о (Sk ,ak\{t}) о (Sk ak+1) о -.о (sm_1#o"m). Поскольку множество ak \ [t] может быть пустым, то этот маршрут имеет не более т непустых блоков. Итерируя это построение, можно построить разложение, в котором первый блок будет максимальным независимым блоком с началом в s.
Обозначим в построенном разложении начало второго блока через s[. Полученное разложение с началом s[ можно привести к разложению с максимальным независимым первым блоком с началом s{. Затем перейти к следующему блоку и т.д. В результате приходим к разложению, все блоки которого максимальны, и число этих блоков не больше т. Поскольку маршрут будет состоять из максимальных независимых блоков, то он будет максимальной формой пути 7Г. Согласно построению, число блоков максимальной формы не больше т. По предположению, исходный маршрут имел минимальное число блоков т. Значит, число блоков максимальной формы равно т. Максимальные независимые блоки являются наибольшими и, значит, строятся канонически. Приходим к выводу, что максимальная форма будет единственной и будет иметь минимальное число независимых блоков. Теорема доказана.
Псевдо-конвейер. Вычисление минимального времени выполнения
В данном пункте описан алгоритм вычисления минимального времени выполнения псевдо-конвейера и эксперимент, частично подтверждающий этот алгоритм [14]. Приведены графики зависимости времени работы псевдоконвейера от объема входных данных, полученные с помощью эксперимента. Средствами численных методов получена аппроксимирующая прямая для экспериментальных данных. Предложена общая формула вычисления времени выполнения псевдо-конвейера, состоящего из трех функциональных устройств.
Псевдо-конвейером называется цикл, состоящий из конечной последовательности действий ага2 ...ап, в которой события щ и ai+1 зависимы для всех 1 і п — 1, а все остальные события независимы. Этот цикл выполняется некоторое конечное число раз.
Псевдо-конвейер можно представить с помощью трассы (а а-г ... an)m, для некоторого т 1. Например, этому определению удовлетворяет конечная последовательность, состоящая из п неделимых операций присваивания xt = fi(xi-i) 1 і тг, составляющих цикл, выполняющийся т Мы видим, что в данном случае соседние операции зависимы, они должны выполняться последовательно. Устранить зависимость между последовательными операциями цикла невозможно. При этом заметим, что время выполнения каждой операции различно. Такой цикл наилучшим образом иллюстрирует особенности псевдо-конвейера.
Согласно положениям предыдущего пункта, для нахождения минимального времени выполнения трассы аг- -ап, нужно разложить каждую операцию в композицию инструкций, выполняющихся за единичное время, выписать трассу а1 аТ2ш-аТпы и затем построить ее нормальную форму Фоаты. Количество блоков этой нормальной формы будет равно искомому минимальному времени.
Рассматривая различные примеры псевдо-конвейеров, мы будем задавать их как последовательности срабатываний переходов сети Петри. Пусть (Р, Т, pre, post, MQ) - сеть Петри. Обозначим t = {р Є Р pre(t)(p) 0},t "= {P Є P post(t)(p) Ф 0}. Определим отношение / = {(ti,t2) Є T x T: С tx П tx ) П С t2 П t2 О = 0}. Легко видеть, что / будет отношением независимости на множестве Т. Пусть Np - множество всех маркировок, а Тгап состоит из троек ( M1,t,M2), t для которых М -» М . Тогда пятерка (Мг, М0, Г, /, Тгап) будет асинхронной системой.
Предположим, что каждому переходу а Є Г сопоставлено положительное целое число т(а) - время выполнения перехода. Покажем, как находить минимальное время выполнения трассы, состоящей из переходов, связывающих маркировки.
Рассмотрим псевдо-конвейер, состоящий из трех операций, применяемых к очереди, содержащей m элементов (рисунок 2.1). Каждая из операций считается неделимой. Она читает данные из области памяти, соответствующей входному месту, вычисляет значение некоторой функции и записывает в область памяти выходного места. Таким образом, соседние операции зависимы.
Трасса выполнения процесса будет равна t = [{сг1а2а3)т]. Пусть т(ах) = 2, т(а2) = 1, т(а3) = 2. Тогда временная трасса, соответствующая трассе [(сііСІ2аз)т] будет равна [(afa2a)m]. После приведения к нормальной форме Фоаты получаем [(afa2a)m] = [а С З азЗ аз])171-1 ] ] ]. Отсюда 6(t) = 1 + 1 + 3(m — 1)+ 1 + 1 + 1 = 3m + 2. Если выполнять действия последовательно, то время выполнения будет равно 5тп.
Для постановки эксперимента с целью подтверждения или опровержения полученных результатов мы разработали программное обеспечение, вычисляющее время работы сети Петри псевдо-конвейера. Опишем алгоритм работы программы.
Программа организована таким образом, что в процессе работы для каждого перехода сети создается отдельный поток. Взаимодействие между потоками обеспечивает выполнение условия зависимости соседних операций.
Для того чтобы потоки выполнялись одновременно, за операцию в данной программе будем принимать задержку выполнения на заданное пользователем время. В этом заключается основная идея, делающая возможными эксперименты по измерению времени работы параллельно работающих процессов.
Работа программы начинается с создания глобального таймера, который заканчивает отсчет времени после выполнения последней операции. С помощью него мы получаем на выходе результирующее время работы псевдо-конвейера.
В качестве объекта синхронизации работы потоков в данной программе выступает событие (event). Объект событие может находиться в двух состояниях: занят (есть событие) и свободен (нет события). Состояние, при котором объект событие занят, называется сигнальным, в противном случае -невыделенным. Функция потока представляет собой ожидание сигналов о завершении смежных потоков, выполнение операции и последующую установку события, сигнализирующего об окончании работы.
Временные сети Петри как временные дистрибутивные асинхронные автоматы
В пункте 2.2 мы моделировали разложение операций процесса, заданного с помощью трассы, в композицию операций единичной длины. Напомним, что при и , этом переход s -»s представлялся как композиция переходов, имеющих зависимые инструкции elt е2, —,ек, где к = т(и) - время выполнения инструкции. Каждая из инструкций et выполнялась за один такт. Мы будем использовать эту идею для нахождения минимального времени выполнения волновой системы с помощью построения максимальной нормальной формы. Пусть щ - инструкция волновой системы. Разложим ее в композицию операций Єї, выполняющихся за один такт. Будем называть выполнение е частичным срабатыванием щ.
Пусть ег, е2,..., et - последовательность частичных срабатываний волновой системы. Определим блок наибольших частичных срабатываний как наибольшее множество частичных операций, которые можно одновременно применить к состоянию волновой системы в данный момент времени. Максимальная нормальная форма будет состоять из блоков наибольших частичных срабатываний, упорядоченных во времени. При этом порядок букв в каждом блоке будет возрастающим.
Таким образом, в каждый блок мы выписываем все частичные операции, которые могут сработать в данный момент времени. Каждый блок максимальной формы выполняется за одну единицу времени.
Волновая система представляется с помощью сети Петри. Функция времени определена на множестве ее переходов и принимает положительные целые значения r(t). Измельчением волновой системы мы будем называть сеть Петри, полученную из волновой системы, с
Доказательство. Докажем, что отношение антисимметрично. С этой целью рассмотрим произвольный переход сети Петри измельчения, соединяющий достижимые маркировки. Существует путь, содержащий этот переход и соединяющий некоторое начальное место с некоторым конечным местом. Этот путь содержит постоянное число фишек. Отсюда срабатывание перехода приводит к продвижению фишки вдоль этого пути от начального места к конечному. И никакой другой переход не может вернуть эту фишку назад. Следовательно, отношение антисимметрично и превращает множество достижимых маркировок измельчений в частично-упорядоченное множество. Предложение 2.6. Пусть Ж — множество достижимых маркировок измельчения. Частично-упорядоченное множество (М, ) имеет наибольший и наименьший элементы.
Доказательство. Это утверждение аналогично предложению 1.2 и повторяет его доказательство. Лемма 2.4. Для каждого состояния измельчения волновой системы существует наибольшее множество переходов, которые можно одновременно применить к этому состоянию. Доказательство. Аналогично доказательству леммы 1.2. Лемма 2.5. Любые два маршрута в измельчении волновой системы, соединяющие заданные маркировки, состоят из одинаковых букв. Доказательство. Аналогично доказательству леммы 1.3.
Теорема 2.3. Для любого пути в волновой системе существует максимальная нормальная форма измельчения этого пути. Количество блоков этой максимальной нормальной формы равно минимальному времени выполнения волновой системы.
Доказательство. Рассмотрим дистрибутивный асинхронный автомат, соответствующий сети Петри измельчения волновой системы. Из леммы 2.4 следует, что для пути в этом дистрибутивном асинхронном автомате выполнены условия теоремы 1.4. Отсюда вытекает, максимальная нормальная форма существует, и она имеет наименьшее число блоков. Поскольку каждый блок маршрута имеет время выполнения 1, то время выполнения маршрута равного максимальной нормальной форме будет наименьшим.
Входные данные размещаются в местах, имеющих один выходной переход. На рисунке 2.11 входные данные размещаются в каналах с0 и сх. Результаты вычислений записываются в каналы, соответствующие местам, имеющим по одному входному переходу. Для данного примера этими каналами будут с6 и с7.
Компьютерная модель этой волновой системы состоит из потоков, соответствующих переходам ее сети Петри и каналов, соответствующим ее местам. Программная реализация использует класс канала, описанный в пункте 2.4. Всякий поток, соответствующий переходу, состоит из цикла. В теле цикла сначала принимаются данные из входных каналов. Затем имитируется выполнение операции с помощью подпрограммы Sleep(). После этого передаются данные в выходные каналы.
