Исследование математических моделей параллельных вычислительных систем методами алгебраической топологии тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Лопаткин, Виктор Евгеньевич

• Лопаткин, Виктор Евгеньевич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Лопаткин, Виктор Евгеньевич

Введение

Глава 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. Введено кольцо когомологий асинхронных систем переходов и показано, что этот инвариант более тонок, чем рассмотренные ранее

Список литературы диссертационного исследования кандидат физико-математических наук Лопаткин, Виктор Евгеньевич, 2010 год

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.