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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

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

Введем необходимые определения.

Волновая система задается с помощью числа n > 0 и ацикличной сети Петри (P, T, pre, post, Mo) такой, что каждому переходу сети соответствует как минимум одно входное и выходное место, а для каждого места сети выполняется одно из условий:

• существует одна входящая стрелка и одна выходящая;

• существует только одна выходящая стрелка - такое место называется начальным;

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

При этом число n характеризует количество фишек в каждом начальном месте сети на момент начальной маркировки Mo.

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

Под начальной маркировкой будем понимать такое состояние волновой системы, при котором все фишки (данные) находятся в местах, не имеющих входящих стрелок (рисунок 1, а). Напротив, конечная маркировка - состояние волновой системы, при котором все фишки находятся в местах, не имеющих выходящих стрелок (рисунок 1, б). a)

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Рис. 1. Маркировка волновой системы: а - начальная; б - конечная

Тупики в волновых системах.

Напомним, что синхрографом (или маркированным графом [5]) называется такая сеть Петри, в каждое место которой входит ровно одна дуга и из каждого места выходит ровно одна дуга [1].

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

Лемма 1. В любом пути, ведущем из начального места к конечному, число фишек постоянно и равно n.

Доказательство. Для доказательства этой леммы воспользуемся теоремой [1, теорема 4.4] для синхронизационного графа. Рассмотрим произвольную волновую систему (например, рисунок 1). Дополним её до синхрографа добавлением перехода t: конечные места волновой системы будут его входными местами, а начальные - выходными. Любой путь волновой системы, ведущий из начального места к конечному, теперь будет являться циклом синхрографа. По [1, теорема 4.4] число фишек в цикле не меняется при функционировании синхрографа. Соответственно, число фишек в пути волновой системы будет постоянно.

Пусть тупиком называется достижимая маркировка M, при которой не существует M?, допускающей срабатывание M > M?. Напомним, что маркировка M называется достижимой из M??, если существует переход, переводящий M?? в M [5].

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

Предложение 1. Волновая система не имеет тупиков, за исключением конечной маркировки.

Доказательство. Предположим, что волновая система имеет тупик M и этот тупик не является конечной маркировкой. Из леммы 1 следует, что если M(p) = n, для всех конечных мест, то M является конечной маркировкой. Отсюда существует некоторое конечное место p? такое, что M(p?) < n. Из определения волновой системы следует, что для любого места существует путь в него из некоторого начального места, и существует путь в некоторое конечное место. Для места p? обязательно существует единственный переход со стрелкой t > p?. Поскольку M - тупик, то переход t не может сработать и, значит, какое-нибудь из его входных мест не содержит фишек. Обозначим это входное место p1. Если p1 не является начальным, то существует переход t1 и стрелка t1 > p1. Переход t1 также имеет входное место, не содержащее фишек. Продолжив процесс движения по волновой системе, мы получим путь из некоторого начального места в искомое место p?. Число фишек в этом пути равно M(p?) < n, что противоречит утверждению леммы 1. Значит, предположение неверно и M - не тупик.

Волновая система с минимальным количеством блоков

Пусть M и M? - достижимые маркировки. Множество достижимых маркировок частично упорядочено отношением M ? M? , если существует последовательность срабатываний переходов .

Предложение 2. Пусть M - множество достижимых маркировок. Частичноупорядоченное множество (M, ?) имеет наибольшие и наименьшие элементы.

Доказательство. Поскольку число p ? P мест волновой системы конечно и маркировки M(p) ограничены значением n, число достижимых маркировок будет конечно. Известно, что каждое срабатывание перехода переводит маркировку , такую что M1 ? M. Рассмотрев последовательность срабатываний переходов M1 > M2 > …?> Mk, мы достигнем конечной маркировки M? , которая и будет являться наименьшим элементом множества (M ?) . Напротив, наибольшим элементом множества (M ?) будет являться начальная маркировка волновой системы.

Лемма 2. Для каждого состояния волновой системы существует наибольшее множество переходов, которые можно одновременно применить к этому состоянию. Будем называть это множество блоком наибольших срабатываний.

Доказательство. Представим, что в некоторой маркировке ?? могут сработать три перехода: t1, t2, t3. Поскольку переходы разрешены, для каждого из них существует одно или несколько мест, в которых содержится n > 0 фишек. По определению волновой системы, каждое место может содержать только одну выходящую стрелку и, следовательно, соответствующие переходы не могут иметь общих мест и являются независимыми. Таким образом, эти переходы могут сработать одновременно.

Для примера рассмотрим волновую систему, представленную на рисунке 2.

Рис. 2. Пример волновой системы

В данном состоянии переходы t1, t2 и t3 могут сработать одновременно. Отсюда, эти переходы принадлежат к наибольшему множеству.

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

Лемма 3. Любые два маршрута, соединяющие заданные маркировки, состоят из одинаковых букв.

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

Теорема. Маршрут волновой системы, состоящий из блоков наибольших срабатываний, будет иметь наименьшее количество блоков.

Доказательство. Рассмотрим маршрут от некоторой начальной маркировки Mo к конечной Ms. Предположим, что этот маршрут имеет наименьшее количество блоков.

Рис. 3. Срабатывание

Существует маркировка M1, к которой ведет блок b1 вместе с переходом t. Эта маркировка получается при последовательном срабатывании сначала блока b1, а затем перехода t, или при срабатывании сначала t, а затем блока b1.

Таким образом, мы получаем диаграмму, изображенную на рисунке 4.

волновой арифметический граф

Рис. 4. Диаграмма маршрута

Рассматривая альтернативный маршрут от Mo к Ms , состоящий из блоков b1, b2, …?, необходимо учесть, что согласно лемме 3 в нём обязательно должен содержаться переход t. Пусть s - наименьший индекс, при котором t ? bs. Тогда будет иметь место последовательность переходов bs\{t} = bs: Ms-1 > Ms. В результате получим маршрут, состоящий из последовательности блоков b1, b2, …, bs-1, bs, в которой первый элемент полностью укомплектован и содержит на один переход больше. При этом общее количество блоков маршрута осталось прежним.

Эта теорема дает метод построения маршрута, состоящего из минимального количества блоков. Рассмотрим, например, сеть, изображенную на рисунке 1 (а). На момент начальной маркировки сети n = 3, то есть в каждом начальном месте находится по 3 фишки. Построим маршрут Mo > M? из начальной маркировки сети в конечную (рисунок 1 (б)). Последовательность блоков наибольших срабатываний будет иметь вид

m = [t1t2][t1t2t3t4]n-1[t3t4] = [t1t2][t1t2t3t4][t1t2t3t4][t3t4].

В статье [2] для нахождения маршрута, состоящего из минимального числа блоков и содержащегося в асинхронной системе, использовалось приведение трассы к нормальной формы Фоаты. Это позволило разработать метод вычисления минимального времени обработки входных данных для конвейера и псевдо-конвейера. Волновая система не является асинхронной системой, поэтому для расчета маршрута, состоящего из минимального числа блоков, мы разработали другие методы. Легко доказать, что волновая система будет дистрибутивным асинхронным автоматом в смысле [4], если определить состояния как маркировки, а переходы, допускающие срабатывания из одной маркировки, как независимые. Это дает шанс получить результаты для ацикличных дистрибутивных асинхронных автоматов, аналогичные результатам, полученных для волновых систем.

Данная работа была выполнена в рамках программы стратегического развития государственных образовательных учреждений высшего профессионального образования, грант № 2011-ПР-054.

Литература

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

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

3. Кудряшова, Е.С. Моделирование конвейерных и волновых вычислений / Е.С. Кудряшова, Н.Н. Михайлова, А.А. Хусаинов // Интернет-журнал «Науковедение», 2014 №1 (20) [Электронный ресурс] - М.: Науковедение, 2014.

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

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

Размещено на Allbest.ru