автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Исследование математических моделей параллельных вычислительных систем методами алгебраической топологии

004611663

На правах рукописи

ЛОПАТКИН Виктор Евгеньевич

ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ МЕТОДАМИ АЛГЕБРАИЧЕСКОЙ ТОПОЛОГИИ

Специальность 05.13.18 — математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 8 ОКТ 2010

Комсомольск-на-Амуре — 2010

004611663

Научный руководитель:

доктор физико-математических наук, профессор

Хусаинов Ахмет Аксаиович

Официальные оппоненты: доктор физико-математических наук,

Скурихин Евгений Евгеньевич

Ведущая организация:

кандидат технических наук Логинов Василий Николаевич

Институт вычислительной математики и математической геофизики СО РАН

Защита состоится «28» октября 2010 г. в 1200 часов на заседании диссертационного совета ДМ 212.092.03 при Комсомольском-на-Амуре государственном техническом университете (ГОУВПО «КнАГТУ») по адресу: 681013, г. Комсомольск-на-Амуре, пр. Ленина, 27, ГОУВПО «КнАГТУ».

С диссертацией можно ознакомиться в библиотеке ГОУВПО «КнАГТУ ». Отзывы на автореферат в двух экземплярах, заверенных печатью, просим направлять по адресу: 681013, г. Комсомольск-на-Амуре, пр. Ленина, д. 27, ГОУВПО «КнАГТУ».

Автореферат разослан сентября 2010 г.

Учёный секретарь

диссертационного совета

кандидат физико-математических наук

М. М. Зарубин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Аюуальность темы. Желание увеличить производительность вычислительной системы привело к идеи параллельной обработки информации. Параллельные вычислительные процессы можно моделировать с помощью автоматов высшей размерности (или то же самое, с помощью полукубических множеств), систем переходов, асинхронных систем переходов, сетей Петри.

В работах Пратта, фан Глабика была предложена и исследована геометрическая модель — автомат высшей размерности (Higher Dimensional Automata). Эти автоматы — обобщение недерменированного автомата. Автоматы высшей размерности имеют очень простую геометрическую интерпретацию; параллельное выполнение двух событий в таком автомате, геометрически распознаётся как квадрат. Когда параллельно выполняются п событий, то появляются п-кубы. Такая "геометричность" позволяет привлечь методы алгебраической топологии. В работах Губо, Гаше, Губо и Йенсена, изучались группы гомологий автоматов высшей размерности. Следует отметить, что в работах Губо, изучались взаимосвязи между категориями сетей Петри, систем переходов, асинхронных систем переходов и категорией автоматов высшей размерности.

Сети Петри — эта удобная и мощная модель, одно из её удобство заключается в графической представлению работы процесса. Хорошо известно, что существует пара сопряжённых функторов между категорией асинхронных систем переходов и категорией сетей Петри.

Асинхронные системы переходов были введены в работах Беднарчика, Шил-дса, где использовались теоретико-категорные методы. С другой стороны, согласно работам A.A. Хусаинова, асинхронную систему переходов можно рассматривать как пунктированное множество, над которым справа действует свободный частично коммутативный моноид. Также A.A. Хусаиновым, было показано, что любой асинхронной системе переходов соответствует автомат высшей размерности. Гомологии асинхронных систем переходов были введены A.A. Хусаиновым, им же была поставлена проблема вычисления групп гомологий асинхронных систем переходов, в диссертации эта проблема решена.

Актуальность таких исследований обусловлена наличием проблемы топологической классификации математических моделей параллельных вычислительных процессов.

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

цели решались следующие задачи:

• изучение полукубических групп гомологий асинхронных систем переходов.

• изучение гомологий параллельного произведения асинхронных систем переходов и получение условий разложимости асинхронной системы переходов в параллельное произведение.

• изучение подгрупп кручения групп гомологии асинхронных систем переходов.

• исследование других топологических инвариантов асинхронных систем переходов и автоматов высшей размерности.

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

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

Предмет исследования: математические модели параллельных вычислительных систем.

Научная новизна работы:

- разработан и теоретически обоснован алгоритм вычисления целочисленных групп гомологий асинхронных систем переходов;

- получены достаточные условия разложимости асинхронной системы переходов в параллельное произведение;

- введено в рассмотрение градуированное кольцо когомологий асинхронных систем переходов и автоматов высшей размерности;

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

Научная и практическая значимость работы.

Основные результаты диссертационной работы были получены автором при проведении исследований, выполненных в 2007 - 2010 гг.

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

Апробация работы

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

• 37-й научно-технической конференции аспирантов и студентов г. Комсомольск - на - Амуре;

• XXXII Дальневосточная школа-семинар имени академика Е.В.Золотова г. Владивосток;

• школа-семинар "Синтаксис и семантика логических систем" посвящённая памяти профессора Ю.Е. Шишмарёва, Владивосток 2008 год.

• обсуждались на научных семинарах по теории категории, КнАГТУ.

Публикации

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава диссертации посвящена обзору некоторых математических моделей вычислительных процессов; сети Петри, системы переходов, асинхронные системы переходов и автоматы высшей размерности. Мы вводим в рассмотрение категории сетей Петри PNets, систем переходов TS, асинхронных систем переходов ATS и автоматов высшей размерности Т. Также мы приводим некоторые функторы между этими категориями. В основном диссертация посвящена асинхронным систем переходов и автоматам высшей размерности.

Определение. Асинхронной системой переходов А = [S,so,E,I,Tran) называется пятёрка, состоящая из множеств S, Е, элемента sg £ S, подмножества Tran С S х Е х S и антирефлексивного симметричного отношения I С Е х Е, удовлетворяющих условиям

i) для каждого е 6 Е существуют такие s, s' £ S, что (s, е, s') € Tran;

ii) если (s, e, s') £ Tran и (s, e, s") £ Tran, то s' = s";

iii) для любой пары (б^ег) £ I и троек (s,ei,s{) £ Tran, («1,62,") £ Tran существует такой S2 £ S, что (s, ег, 6 Tran и (вг, е.\,и) G Tran.

Элементы из S называются состояниями, из Tran — переходами, из Е — событиями, / — отношение независимости.

Условие iii) иллюстрируется диаграммой

s

и

Определение. Полурегулярным автоматом высшей размерности (полукубическим множеством) называется набор множеств (<2„), где п 6 {0,1,...} и семейство отображений öJ'E : Qn-i —* Qn определённых при 1 < i < п, с € {0,1} и удовлетворяющих коммутативности диаграммы для всех а, ß G {0,1}, п > 2, 1 < i < j < п;

д"-в

Qn—^Qn-i

ег[ 1«Г-

Qn-i^zrtQn-2

Каждой асинхронной системе переходов А = (S, .so, Е, I, Tran) соответствует полукубическое множество (полурегулярный автомат высшей размерности) QS' = (QnS', где п 6 N, 1 < г < n, е € {0,1}.

Во второй главе говориться о группах гомологии асинхронных систем переходов. Гомологии автоматов высшей размерности были введены Губо и Йен-сеном, гомологии асинхронных систем переходов были введены A.A. Хусаино-вым. В диссертации (целочисленные) гомологии асинхронных систем переходов определяются через соответствующие им полукубические множества (автоматы высшей размерности). Это позволило построить алгоритм их вычисления, на основе которого было разработано программное обеспечение по вычислению групп гомологии асинхронных систем переходов.

Т е о р е м а 2.1 Группы целочисленных гомологии асинхронной системы переходов А = (S, sq, Е, I, Tran) изоморфны гомологиям комплекса

о-фгД ф гД ф хД...

sSQoS' (s,e)eQiS* (s,ei,e2)eQ2S'

0 zi 0 z«^...

(s,eb...,e„-i)eQ„-iS- (»,«,,...,mOeOnS'

здесь

QnS' = {(s, ei,..., en) : s 6 S*, ej < ... < en € E, (e,-, es) €

для всех 1 < г < j < n}, а граничные дифференциалы определяются по формуле

п

dn{s, еь ..., е„) = £>l)fc((« ' е>" еь • ■ -, Ч, ■ ■ ■, en) - (s, е1;..., ..., е„)) fc=i

Рис. 1. Неаугментированный граф состояний асинхронной системы переходов.

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

Т е о р е м а 2.5 Если многочлен Пуанкаре пространств состояний £ асинхронной системы переходов Т не разлагается в произведение многочленов, имеющих неотрицательные целые коэффициенты, то не существует асинхронных систем переходов Т\ и Т2, для которых Т = Т! || Т2.

Многочленом Пуанкаре называется производящая функция последовательно-

оо

сти рангов групп гомологии Ре(^) = ^ пространства состояний Е,

здесь т>(Х!) = гапк .#&(£) ранг к-й группы гомологии.

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

(а) х:=а(х,у,г),(Ь) у := ¡3(х,у,г), (с) г ч{х,у,г)\

(с!) I := <р((,т,п), (е) т := х(',гп,п), (/) тп :=-ф(1,тп,п).

Вычислительные процессы будут состоять из последовательности выполнения инструкций, например: а; 6; е; с; /; Такая последовательность записывается как слово ¿аЬес}/1 и называется трассой. Замечаем теперь, что все пары инструкций, за исключением пар (а, Ь), (Ъ, с), (а, с), (с1, е), (е, /), (¡¿, /), могут выполняться параллельно. Этот факт записывается в виде равенств аЪ = Ъа, Ьс = сЬ, ас = са, йе = ее?, е/ = /е, й/ = /<£ Используя эти равенства, рассматриваемый процесс молено привести к нормальной форме Фоаты (ad)(be){cf)d, состоящей из четырёх ярусов. В результате получаем метод автоматического распараллеливания последовательностей инструкций. Применение этого метода на практике показывает, что кроме независимости инструкций от данных, необходимо учитывать действие инструкций на пространстве состояний. В нашем примере, если действия а, Ь, с приводят к одинаковым значениям переменных х, у, г, а с!, е, / — к одинаковым значениям переменных I, т, п, причём каждое из шести действий захватывает некоторый объём памяти, то при ограниченном объёме свободной памяти мы получаем асинхронную систему переходов, неаугментированный граф которой показан ниже.

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

образующими а, Ь, с, d, e, / и соотношениями ab = Ъа, be = cb, ас = са, de = ed, е/ = /е, df = fd, допускает разложение в прямое произведение.

Группы гомологии этой асинхронной системы переходов изоморфны группам гомологий следующего цепного комплекса

О Д z4 Д Z24 ¿Z36^0

Тензорно умножив этот комплекс на Q мы получим комплекс векторных пространств и линейных отображений, выписывая матрицы линейных отображений, находим их ранги с помощью метода Гаусса: rank dj ® Q = 3, rank d2 ® Q = 15. Тогда получим г0(Е) = 4-3 = 1,п(£) = 24-15-3 = 6,r2(E) = 3G-0-15 = 21, значит Pe(v) = 1 + буз + 21 ip2. Нетрудно видеть, что данный многочлен неразложим в произведение многочленов с целыми коэффициентами. Это значит, что _ данная асинхронная система переходов неразложима в параллельное произведение.

Этот пример приведён в диссертации для демонстрации методов исследования с помощью топологических инвариантов асинхронных систем переходов — их групп гомологий.

В третьей главе отражены дальнейшие результаты исследований автора гомологий асинхронных систем переходов. В основе мотивации этих исследований лежали следующие вопросы:

1. Ранее было замечено, что если гомологии асинхронной системы переходов А = (S, so, Е, I, Tran) изоморфны гомологиям точки, что частично коммутативный моноид М(Е, I) состоит из одного элемента, а пунктированное множество S' — из единственной точки. Возникает вопрос, будут ли изоморфны асинхронные системы переходов, имеющие одинаковые группы гомологий?

2. Можно ли построить (и если да, то как) асинхронную систему переходов с заданными группами гомологий?

На первый вопрос в диссертации даётся отрицательный ответ, а на второй мы отвечаем следующим образом: для любой последовательности конечных абеле-вых групп Gi, Gi-, ■ ■ ■, Gk,.. ■, можно построить такую асинхронную систему переходов А, что для каждого т > 2 подгруппа кручения её группы гомологий Нт(А) будет изоморфна Gm.

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

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

Определение. Пусть si — категория, когомологической системой объектов на полукубическом множестве X е D^Eiis называется произвольный функтор F : U+/X л/.

Рассмотрим когомологические системы колец и групп. Пусть Sf : D+/X —► Ab — когомологическая система абелевых групп на полукубическом множестве X. Рассмотрим абелевы группы nD+[X,£?] = if(1?). Определим дифференциа-

i9exn

лы : Sf] —> п+1П+[Х, if], как гомоморфизмы, делающие коммутатив-

ные диаграммы

п т__v п

PIi»V."+1'*j pr,

У Uo -тт-r^(tf)

Определение. Пусть X — полукубическое множество, & : D+/ X —» АЬ — когомологическая система абелевых групп. Группами когомологий НП(Х;ЧУ) полукубического множества X с коэффициентами в ^ называются п-е группы когомологий комплекса состоящего из абелевых групп

"□+[X,Sf]= П^)

и дифференциалов

п+1 i=1

Пусть : П+/Х —» Ring — когомологическая система колец на полукубическом множестве X, принимающая постоянное значение, равное некоторому кольцу R. Рассматривая аддитивную составляющую кольца R мы можем говорить о группах когомологий Я*(A'; R) полукубического множества с коэффициентами в кольце R. Пусть *П+[Х; Л] — коцепной комплекс. Введём в рассмотрение гомоморфизм

тг: *П+\Х-, Л] *П+[Х] -R] -> *П+[Х ® X; R],

который определяется следующей формулой

(ir(u ® у')) (с ® с') ~ jj (и(с) ®R u'(c')),

здесь с, с' е □+[А'], и, и' € *П+[Х; R] a jj : R R -» R — изоморфизм колец, который задаётся формулой

7) (и (с) ® и'(с')) = и (с) • и'(с').

где умножение понимается в смысле умножения кольца R. Рассмотрим теперь отображение

«-= Д*тг: *С]+[Х; R] *□+[*; R] -»*D+[X; Л]

показано, что оно является коцепным, значит, ^ индуцирует некоторое умножение в Н*(Х\ R) и превращает её в кольцо.

Опишем как будет выглядеть это умножение на коцепях. Пусть (/> G PD+[X;Л],!/" € ?0+[Х;Л] — две коцепи со значениями в кольце R. Пусть и 6 Ар+, — куб размерности р + q, тогда будем иметь:

(tp ^ ф) (и) = 8ак<Р (и о hxaQ) "ф{ис, hxiK) ,

g

здесь G = {зь ■ •., др} пробегает множество всех подмножеств множества {1,2,---,р + д}, состоящее изр элементов, К есть дополнение множества G, а Qgk — сигнатура (чётность) перестановки GK.

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

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

Определение. Группами целочисленных когомологий асинхронной системы переходов А = (S,s0>E,I}Tran) называются группы когомологий Нп (Ж,{А)\ Z) коцепного комплекса

о- п П П

iSQoS' (s.ejJSQjS* (s,eb<!2)sQ2S'

П П

(sA.-.en-OeQn-lS' (i,e1,...,c„)eQ„S*

где кограничный дифференциал, для n-мерной коцепи

y(s,e ь..., е„)€ JJ

(e.ei.....e»)eQ.S'

определяется следующей формулой

п+1

еь..., еп+0 = ■ еь еь..., ек,..., еп+1)-

Ь=1

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

Пусть [</>] и [гр] — классы р-мерных и д-мерных когомологий НР(А\2;) и НЯ{А\Ъ) соответственно, а ср и ф — их представители. Тогда, ^-умножение будет определятся следующим образом (¡р — еи..., ер+9) =

= Е внк'Р -Ф^-е^ ,ек1,...,ек) ,

я

где Я = {/н,..., Ь.р} — подмножество множества {1,2,..., п), К — его дополнение, днк — сигнатура (чётность) перестановки НК, а суммирование распространяется по всем Я.

Так, например, пусть р = д = 1, тогда получим

{(р ^ ф)^, еь е2) = ¥>(5, еО ■ ■¡/■(я ■ еь е2) - е2) • ^(в ■ е2, е^

Пусть нам дана следующая асинхронная система переходов '.Л; = (£ь Еи 1и Тгащ), где ^ = {х, *}, ^ =х,Ех = {а, Ь, с, 1Х = {(а, Ь)(с, <!)}, Тгащ = {г А от, а: Л х, х —> х, х Л ж}. Она имеет следующий аугментирован-ный граф состояний

Рис. 2. Аугментированный граф асинхронной системы переходов Аг = {Зъв1,Е1,1ъТгап1).

Она имеет следующие гомологии

Н2{А1->1) = Ке1{(12)^Х\ Н^АцХ) = Кег(^) = г8;

Яо(Л1;2) = Кег(ао)=й2.

Далее, рассмотрим следующую асинхронную систему переходов Л2 = (52, Е2, /2, Тгап2), где 52 = {х, *}> = х, Е2 = {а, Ь, с, 12 = {(а, £>)(!>, с)},

Рис. 3. Аугментированный граф асинхронной системы переходов

Тгап2 — {х х, х Д х, х А х, х х}. Она имеет такой же, как и в предыдущем примере аугментированный граф состояний Вычисляя её гомологии мы получим такие же как и у предыдущей системы

Л2(А1;%)^ Кег(сг2)^Ж4;

H1(A1■,Z)^Ker(d1)^¿Zs■1

Итак, мы привели две разные асинхронные системы переходов, у которых изоморфны гомологии. Рассмотрим теперь умножение в их кольцах когомоло-гий. Будем принимать следующие обозначения; (в, е\,..., е„)* — коцепь, которая принимает значение 1 на элементе (в, еа,..., еп), а на остальных принимает 0.

Рассмотрим кольцо Н*(А1;Щ. Ненулевыми равенствами в этом кольце будут следующие;

((х,а)* ^ (х,Ь)")(х,а,Ь) = (ж,а)*(ж,а) ■ (х,Ь)*(х,Ь) - 1;

((х, с)* ^ (х, с?)*) (х, с, (¿) = (х, с)*(х, с) • (х, dy(x, в) = 1; ((*)а)* - {*,ЬУ)(*,а,Ь) = (*, а)*(*,а) ■ (*,Ь)*(*,Ь) = 1;

((*, с)* - (*, ¿У) (*, С, <0 = (*, С)*(*, С) • (*, = 1.

Далее, в кольце Я*(Л2;2) будут ненулевыми следующие равенства

((ж, а)* ^ (х, Ь)*) (ж, а, ¿) = (ж, а) • (х, Ь)*(х, Ь) = 1;

((х, ЬУ - (а-, с)*) 6, с) = (ж, ЬУ(х, 6) ■ (*, с)*(*, с) = 1;

((*,а)* - (*,ЪУ)(*,а,Ъ) = (*, а)*(*, а) ■ (*,Ь)*(*,Ь) = 1;

((*, Ь)* - (*, с)*) (*, 6, с) = (*, Ь)*(», 6) - (*, с)*(*, с) = 1.

Покажем теперь, что между этими кольцами нет кольцевого изоморфизма. Рассуждать будем от противного. Для начала заметим, что системы переходов А] и Л2 представляются в виде несвязной суммы (см. их аугментированные графы), поэтому их коцепные комплексы изоморфны произведению комплексов,

а это значит, что имеют место изоморфизмы

Н*{Аг,1) = Кх х А",, Я*(Л2; Ъ) = Л* х Л„.

Образующими, например колец Я*(А'1; 2) являются элементы вида ((1, е)*, 0), (О, (*, е)*), где е £ {а, 6, с, Предположим, что существует кольцевой изоморфизм

Я*(Л1; 2) * х АГ, Я*(Л»; 2) = Ах х Л,.

Так как в кольце Н*{Аг\Ъ) справедливы равенства

(*,<*)* ~ (я, е)* = 0;

МГ-(*,еГ = 0,

для каждого е 6 {а,Ъ,с, <1}, то, в кольце Н*{А\\Ъ) должны иметь место равенства

/>((МГ)-/.((*.еГ) = 0.

Ясно, что здесь ((г, е)*), /»((*, е)*) — произвольные элементы кольца Л*(Аг;Ж) и мы, без ограничения общности, можем принять их за элементы (г, а)* и (*, а)* соответственно, здесь а £ {а, 6, с, '

Пусть

((1, с2)*) = £1(1, а)* + к2{х,Ьу + кз{х,с)* + ¿с4(МГ;

/. ((*, с£>*) = а У + к{*,ьу + 1г(*,су + Ц(*,с1у.

Тогда для каждого а £ {а, Ь, с, ¿} будем иметь равенства (кф, а)\0) + к2((х, Ь)*, 0) + * ((х, с)*, 0) + Ь((х, <*)•, 0)) - ((яг, а)', 0) = 0;

Ш (*, аУ) + /2(0, (*, Ъ)*) + г3(0, (*, с)*) + /4(0, (*, ¿Л) - (0, (*, а)*) = 0, и подставляя вместо а каждый элемент из {а, Ь, с, немедленно получаем что

к\ = = ^з = = 0;

Ь — Ь = 'з = Ь — 0.

Таким образом, этот кольцевой изоморфизм переводит ненулевой элемент в нулевой. Получили противоречие. Следовательно, кольца Н*(А\-, Щ и Н*(А2',Ъ) — неизоморфны.

Таким образом, мы видим, что хотя гомологии асинхронных систем переходов Ai и Ai изоморфны, их кольца когомолошй — неизоморфны.

В заключении приводятся основные результаты диссертационной работы:

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

2. Получены достаточные условия разложения асинхронной системы переходов в параллельное произведение.

3. Введено градуированное кольцо когомологий автоматов высшей размерности.

4. Доказано, что умножение в градуированном кольце когомологий автоматов высшей размерности косокоммутативно.

5. Доказано, что кольцо когомологий автоматов высшей размерности изоморфно фактор кольцу кольцо коциклов по двустороннему идеалу кограниц.

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

Опубликованные работы по теме диссертации

1. Лопаткин В.Е. Кольца когомологий полукубических множеств // Изв. Са-рат. ун-та. Нов. сер. — 2010. - Т. 10. - Сер. Математика. Механика. Информатика, вып. 2.-С. 3-10.

2. Лопаткин В.Е. Кольца когомологий асинхронных систем переходов (в печати Сибирского Математического Журнала).

3. Лопаткин В.Е. О полукубических группах гомологий асинхронных систем переходов // XXXII Дальневосточная школа-семинар имени академика Е.В. Золотова: Тезисы докладов. Владивосток: Дальнаука. - 2007. - С.26.

4. Лопаткин В.Е. Подгруппы кручения групп гомологий М(Е, /)-множеств. Российская школа-семинар "Синтаксис и семантика логических систем". Тезисы докладов. Владивосток: Изд-во Дальнаука, 2008. - С. 49 - 50.

5. Лопаткин В.Е. Кольца когомологий М(Е, I)-множеств. Актуальные проблемы математики, физики и информатики в вузе и школе: материалы IV региональной научно-практической конференции. 24 марта 2009г. Комсомольск-на-Амуре: Изд-воАмГПГУ, 2009. С. 88 - 89.

6. Лопаткин В.Е., Хусаинов A.A. О полукубических группах гомологий асинхронных систем переходов. Научно-техническое творчество аспирантов и студентов: материалы 37-й научно-технической конференции аспирантов и студентов (Комсомольск-на-Амуре, 3-17 апреля 2007г.) В трх частях. 41 - Комсомольск-на-Амуре: ГОУВПО "КнАГТУ", 2007. С. 151 - 152.

7. Хусаинов A.A., Лопаткин В.Е., Трещёв И.А. Исследование математической модели параллельных вычислительных процессов методами алгебраической топологии. // Сиб. журн. индустр. матем. - 2008. №1(33). С. 141 -152. http://mi.mathnet.ru/sjim495

8. Lopatkin V. Cohomology Ring of Precubical Sets //New York: Cornell Univ, Preprint, 2009. 12 pp. http://aixiv.org/abs/math.CT.0909.1415vl

9. Lopatkin V. The Homology Groups of right pointed Sets over a partially commutative Monoid IINew York: Cornell Univ, Preprint, 2009. 10 pp. http://arxiv.org/abs/math.CT.0902.041 lvl

10. Lopatkin V. The Torsion of Homology Groups of M(E,I)-sets //New York: Cornell Univ, Preprint, 2008. 5pp. http://arxiv.org/pdf70811.3722vl

Лопаткнн Виктор Евгеньевич

ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ МЕТОДАМИ АЛГЕБРАИЧЕСКОЙ ТОПОЛОГИИ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Подписано в печать 22.09.2010 Формат 60x841/16. Бумага писчая. Ризограф БК3950ЕР-а Усл. печ. л. 0,93. Уч-изд. л. 0,90. Тираж 100 экз. Заказ 23560

Полиграфическая лаборатория Государственного образовательного

учреждения высшего профессионального образования «Комсомольский-на-Амуре государственный технический университет» 681013, г. Комсомольск-на-Амуре, пр. Ленина, 27

Введение

Глава 1. Категории математических моделей вычислительных систем

1.1. Системы переходов.

1.2. Сети Петри.

1.3. Асинхронные системы переходов.

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

1.5. Функторы между категориями моделей.

Глава 2. Гомологии асинхронных систем переходов и признаки распараллеливания

2.1. Группы гомологий асинхронных систем

2.2. Вычисление групп гомологий

2.3. Параллельное произведение асинхронных систем переходов

2.4. Многочлен Пуанкаре и признак неразложимости.

Глава 3. Исследование гомологий асинхронных систем переходов

3.1. Подгруппы кручения в гомологиях асинхронных систем переходов

3.2. Гомологии М(Е, I)-множеств с коэффициентами в функторе Z[xQ,.,xn].

Глава 4. Кольца когомологий асинхронных систем переходов

4.1. Диагональное вложение.

4.2. Когомологические системы на полукубических множествах.

4.3. Свойства полу кубического кольца когомологий.

4.4. Введение когомологий асинхронных систем переходов.

Актуальность работы

Желание увеличить производительность вычислительной системы привело -к идее параллельной" обработки информации. Параллельные вычислительные процессы можно моделировать с помощью автоматов высшей размерности (или то же самое, с помощью полукубических множеств), систем переходов, асинхронных систем переходов, сетей Петри.

В работах Пратта [27], фан Глабика [28] была предложена и исследована геометрическая модель — автомат высшей размерности (Higher Dimensional Automata). Эти автоматы — обобщение недерменированного автомата. Автоматы высшей размерности имеют очень простую геометрическую интерпретацию; параллельное выполнение двух событий в таком автомате, геометрически распознаётся как квадрат. Когда параллельно выполняются п событий, то появляются /7-кубы. Такая "геометричность" позволяет привлечь методы алгебраической топологии. В работах Губо [17], Гаше [20], Губо и Йенсена [19], изучались группы гомологий автоматов высшей размерности. Следует отметить, что в работе [17], изучались взаимосвязи между категориями сетей Петри, систем переходов, асинхронных систем переходов и категорией автоматов высшей размерности.

Сети Петри — эта удобная и мощная модель, одно из её удобство заключается в графической представлению работы процесса. Согласно работе [32], существует пара сопряжённых функторов между категорией асинхронных систем переходов и категорией сетей Петри.

Асинхронные системы переходов-были введены в работах [15], [34], где использовались теоретико-категорные методы. С другой стороны, согласно работе [24], асинхронную систему переходов можно рассматривать как пунктированное множество, над которым справа действует свободный частично коммутативный моноид [16]. В работе [25], было показано, что любой асинхронной системе переходов соответствует автомат высшей размерности. Гомологии асинхронных систем переходов были введены в работе [24], где была поставлена проблема вычисления групп гомологии асинхронных систем переходов, в этой диссертации эта проблема решается теоремой 2.1.

Актуальность таких исследований обусловлена наличием проблемы топологической классификации математических моделей параллельных вычислительных процессов.

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

Цель работы

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

• изучение полукубических групп гомологий асинхронных систем переходов.

• изучение гомологий параллельного произведения асинхронных. систем переходов и получение условий разложимости асинхронной системы переходов в параллельное произведение.

• изучение подгрупп кручения групп гомологий асинхронных систем переходов.

• исследование других топологических инвариантов асинхронных систем переходов и автоматов высшей размерности.

Научная новизна

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

• разработан и теоретически обоснован алгоритм вычисления целочисленных групп гомологий асинхронных систем переходов;

• получены достаточные условия разложимости асинхронной системы переходов в параллельное произведение;

• введено в рассмотрение градуированное кольцо когомологий асинхронных систем переходов и автоматов высшей размерности;

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

Практическая значимость

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

Апробация работы

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

• 37-й научно-технической конференции аспирантов и студентов г. Комсомольск - на - Амуре;

ХХХ1Г Дальневосточная школа-семинар имени академика Е.В.Золотова г. Владивосток;

• школа-семинар "Синтаксис и семантика логических систем" посвященная памяти профессора IO.E. Шишмарёва, Владивосток 2008 год.'

• обсуждались на научных семинарах по теории категории, КнАГТУ.

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

Краткое содержание работы

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

Первая глава диссертации посвящена обзору некоторых математических моделей вычислительных процессов; сети Петри, системы переходов, асинхронные системы, переходов и автоматы высшей размерности; Мы вводим в рассмотрение категории сетей Петри PNets, систем переходов TS, асинхронных систем переходов ATS и автоматов высшей размерности Т. Также мы приводим некоторые функторы между этими категориями [17], [25], [32].- В конце главы мы показываем, какие полукубические множества (полурегулярные автоматы) соответствуют асинхронным системам переходов.

Во второй главе мы вводим гомологии асинхронных систем переходов. Группы гомологии асинхронных, систем переходов были введены в работе [11]. В ^работе [24] было показано, что гомологии асинхронной; системы переходов А = (S, SQrE,"I: Tran) можно определить как - гомологии частично коммутативного моноида М(Е, I) с коэффициентами в некотором правом М{Е, /)модуле. С другой стороны, в работах [25], [14] было показано, что гомологии асинхронной системы переходов изоморфны гомологиям некоторого полукубического комплекса. Основной результат второй главы можно сформулировать следующим образом [14, Теорема 1].

ТЕОРЕМА 2.1 Группы целочисленных гомологии асинхронной системы переходов А = (S, so, Е, I, Tran) изоморфны гомологиям комплекса о< 0 zA 0 йД 0 zi. seQoS• (s,e)eQiS9 (s,e1,e2)€Q2S'*

0 0 здесь

QnS' = {(s, eb ., en) : s <E S', ei < . < en e E, {eh ej) € J, для всех 1 < i < j < n}, а граничные дифференциалы определяются по формуле п dn(s, еь ., еп) = )k{(s ■ ek, еъ ., ek,., en) - (s, еь ., ek,., en)) k=l

Одно из приложений гомологий асинхронных систем переходов было проиллюстрировано в работе [14], где был получен признак неразложимости асинхронной системы переходов в параллельное произведение. Параллельное произведение асинхронных систем переходов было введено в работе [12]. Несложно показать, что существует функтор из категории асинхронных систем переходов в категорию полукубических множеств, и он переводит параллельное произведение в тензорное [21]. Согласно [17], если вычислительные процессы моделировать с помощью полукубических множеств, , то одновременному : выполнению независимых процессов будет: соответствовать тензорное произведение автоматов высшей размерности. Таким образом, при моделировании процессов с помощью асинхронных систем переходов одновременному выполнению независимых процессов будет соответствовать не произведение;, а параллельное произведение асинхронных систем: переходов.

В конце главы мы приводим условие неразложимости асинхронной системы переходов в параллельное произведение (Теорема 2.5).

В третьей главе отражены дальнейшие результаты исследований автора гомологий асинхронных систем переходов. В основе мотивации этих исследований лежали следующие вопросы:

1. Ранее было замечено, что если гомологии асинхронной системы переходов А — (S, sо, Е, /, Tran) изоморфны гомологиям точки, что частично коммутативный моноид М(Е,1) состоит из одного элемента, а пунктированное множество S* — из единственной точки. Возникает вопрос, будут ли изоморфны асинхронные системы переходов, имеющие одинаковые группы гомологий?

2. Можно ли построить (и если да, то как) асинхронную систему переходов с заданными группами гомологий?

На первый вопрос в диссертации даётся отрицательный ответ, а на второй мы отвечаем следующим образом: для любой последовательности конечных абелевых групп G\r G2,— , Gk, • • •, можно построить такую асинхронную систему переходов А,, что для каждого т > 2 подгруппа кручения её группы гомологий Нт(А) будет изоморфна Gm.

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

Этому: посвящена четвёртая глава диссертации, в которой сначала определяется градуированная группа когомологий полукубических множества (автоматов высшей размерности) с коэффициентами в когомологической системе колец, принимающей постоянное значение. Затем на этой группе определяется мультипликативная операция по классической алгебро-топологической схеме. Далее, доказывается, что в результате получается кольцо, изоморфное фак-торкольцу кольца коциклов по двустороннему идеалу кограниц. Доказывается также аналог известного классического результата о косой коммутативности-; кольца когомологий с коэффициентами в коммутативном кольце.

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

Сформулируем теперь о сновные результаты четвёртой главы:

1) Кольцо когомологий полукубических множеств (автоматов высшей размерности) изоморфно факторколъцу кольца коциклов по двустороннему идеалу кограниц.

2) Введено кольцо когомологий асинхронных систем переходов и показано, что этот инвариант более тонок чем рассмотренные ранее.

Структура диссертации; Диссертация состоит из введения, четьфёх глав, заключения и списка литературы. Текст диссертации изложен на 90 страницах, включает в себя две таблицы и 16 иллюстраций.

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

1. Введено кольцо когомологий автоматов высшей размерности.

2. Кольцо когомологий полукубических множеств (автоматов высшей размерности) изоморфно фактор - кольцу кольца коциклов по двустороннему идеалу кограниц.

3. Кольцо когомологий автоматов высшей размерности с коэффициентами в коммутативном кольце, обладает косой коммутативностью.

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

ЗАКЛЮЧЕНИЕ

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

1. Получены условия разложимости асинхронной системы переходов в параллельное произведение.

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

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

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

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

6. Введены группы когомологий автоматов высшей размерности.

7. Введены группы когомологий асинхронных систем переходов.

8. Введно кольцо когомологий автоматов высшей размерности.

9. Кольцо когомологий полукубических множеств (автоматов высшей размерности) изоморфно фактор - кольцу кольца коциклов по двустороннему идеалу кограниц.

10. Кольцо когомологий автоматов высшей размерности с коэффициентами в коммутативном кольце, обладает косой коммутативностью.

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

1. Габриель П.,Цисман М. Категория частных и теория гомотопий-М.:Едиториал УРСС, 2004.

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

3. Лопаткин В.Е. Кольца когомологий полукубических множеств // Изв. Сарат. ун-та. Нов. сер. — 2010. Т. 10. - Сер. Математика. Механика. Информатика, вып. 2.-С. 3-10.

4. Лопаткин В.Е. Кольца когомологий асинхронных систем переходов (в печати Сибирского Математического Журнала).

5. Лопаткин В.Е. О полукубических группах гомологий асинхронных систем переходов // XXXII Дальневосточная школа-семинар имени академика Е.В. Золотова: Тезисы докладов. Владивосток: Дальнаука. 2007. - С.26.

6. Лопаткин В.Е. Подгруппы кручения групп гомологий М(Е1 /)-множеств. Российская школа-семинар "Синтаксис и семантика логических систем". Тезисы докладов. Владивосток: Изд-во Дальнаука, 2008. С. 49 - 50.

7. Лопаткин В.Е. Кольца когомологий М(Е, I)-множеств. Актуальные проблемы математики, физики и информатики в вузе и школе: материалы IV региональной научно-практической конференции. 24 марта 2009г. Комсомольск-на-Амуре: Изд-воАмГПГУ, 2009. С. 88 89.

8. Маклейн С. Гомология. М.: Мир, 1966. 544 с.

9. Полякова Л.Ю. Резольвенты свободных частично коммутативных моноидов // Сиб. мат. журн. 2007. Т. 48, №6. С. 1259 1304.

10. Хилтон П., Уайли С. Теория гомологий. М.: Мир, 1966. 452 с.

11. Хусаинов Ai А., Ткаченко В. В. Группы гомологий асинхронных сим-стем переходов // Математическое модлерирование ихмежные вопросы математики. Хабаровск: изд. ХГПУ, 2003. С. 23-33.

12. Хусаинов А. А., Ткаченко В. В. О группах гомологий-асинхронных систем переходов // Дальневост.мат.журн. 2005. Т.6 е 1 2. С. 23 - 38.

13. Хусаинов А.А. О группах гомологий полукубических множеств // Сиб. мат. журн. 2008. т. 49, №1. с. 224-237 http://www.emis.de/journals/SMZ/2008/01/224.html

14. Хусаинов А.А., Лопаткин В.Е., Трещёв И.А. Исследование математической модели параллельных вычислительных процессов методами алгбе-раической топологии. // Сиб. журн. индустр. матем. 2008. №1(33). С. 141 - 152. http://mi.mathnet.ru/sjim495

15. Bednarczyk M. A. Categories of Asynchronous Systems Ph. D. Thesis, Unicersity of Syssex, report 1/88, 1988, 222p.

16. Diekert V., Métivier Y. Partial Commutation and Traces. II Handbook of formal languages. V. 3. Springer-Verlag, 1997. P. 457-533.

17. E. Goubault. The Geometry of Concurrency. PhD thesis, Ecole Normale Supérieure. Available at http://www.dmi.ens.ir/goubault.

18. E. Goubault. Labelled cubical sets and asynchronous transition systems: an adjunction

19. E. Goubault, T.P. Jensen. Homology of Higer-Dimensional Automata. Lecture Notes in Computer Science 630 (1992) 254-268.

20. Gaucher P. About the globular homology of higher dimensional automata: // Cahiers Topologies Geom. Differentiele Categ. 2002. V. 43, N.2 P. 107 156.

21. Fahrenberg U. A category of higher dimensional automata: Technical Report R-2005-01. Aalborg Univer. Press, 1995. P. 1-148

22. Hilton P.J;, Stambach U. A Course, in Homological Algebra. Betlin etc.: Springer, 1971.

23. T. Hune, M. Nielsen. Timed Bisimulation and Open Maps. Lecture Notes in Computer Science 1*450 (1998) 378-387.

24. Husainov A. On the Homology of small Categories and asynchronous transition system. // Homology Homotopy Appl., 2004. V. 6, N.l.P. 439 -471. http: //www.rmi.acnet.ge/hha

25. Husainov A. On the Cubical Homology Groups of Free Partially Commutative Monoids // New- York: Cornell Univ, Preprint, 2006. 47 pp. http://arxiv.org/abs/math.CT/0611011

26. Kazinski T., Mischaikov K., Mrozek M. Algebraic Topology: A Computationak Approach. Jegellonian University, 2000.

27. V. Pratt. Modeling Concurrency with Geometry. Proceedings of 18th ACM Symposium of Principles of Programming Languages. ACM Press (1991)

28. R. van Glabbek. Bisimulation Semantics for Higher Dimentional Automata. Manuscript available on the web as http://theory.stanford.edu/rvg/hda

29. Lopatkin V. Cohomology Ring of Precubical Sets //New York: Cornell'Univ, Preprint, 2009. 12 pp. http://arxiv.org/abs/math.CT.0909.1415vl

30. Lopatkin V. The Homology Groups of right pointed Sets over a partially commutative Monoid //New York: Cornell Univ, Preprint, 2009. 10 pp. http://amv.org/abs/math.CT.0902.0411vl

31. Lopatkin V. The Torsion of Homology Groups of M(E, /)-sets //New York: Cornell Univ, Preprint, 2008. 5pp. http://arxiv.org/pdf/0811.3722v 1

32. Nielsen M., Wkinskel G., Petri Nets and Bisimulations. Aarhus, 1995. 36 p. (Preprint / Aarhus Univ; BRICS Report Series RS-95-4.)

33. Peterson J.L. Petri net theory and modelling of systems. Prentice Hall, 1981.

34. Shields M.W. Concurrent machines // Computer Journal. 1985.-Vol. 28. -P. 449-465.

35. Winskel G., Nielsen M. Models for Concurrency./ZHandbook of Logic in Computer Science, Vol. IV, ed. Abramsky, Gabbay and Maibaum. Oxford University Press, 1995. P. 1 148.