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

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

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

МОДЕЛИ ПАРАЛЛЕЛЬНЫХ СИСТЕМ И ИХ ПРИМЕНЕНИЕ ДЛЯ ТРАССИРОВКИ И РАСЧЕТА ВРЕМЕНИ ВЫПОЛНЕНИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

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

АВТОРЕФЕРАТ

15 АПР 2015

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

005567209

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

005567209

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

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

Официальные оппоненты:

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

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

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

Намм Роберт Викторович,

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

Эйсымонт Леонид Константинович,

кандидат физико-математических наук, научный сотрудник Федерального государственного унитарного предприятия «Научно-исследовательский институт «Квант», г. Москва

Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Дальневосточный федеральный университет», г. Владивосток

Защита состоится 22 мая 2015 года в 09 часов 00 мин. на заседании диссертационного совета Д 212.092.03 в ФГБОУ ВПО «Комсомольский-на-Амуре государственный технический университет» по адресу: 681013, г. Комсомольск-на-Амуре, пр. Ленина, 27, ауд. 201/3, email: cvmi@knastu.ru

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Комсомольский-на-Амуре государственный технический университет» и на сайте http://sovet.knastu.ru/

Автореферат разослан «£?3» апреля 2015 г. Ученый секретарь ^

диссертационного совета '^^¿L^) Бормотин Константин Сергеевич

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

Актуальность темы. В последние годы параллельное программирование все больше проникает во все сферы человеческой деятельности. Дня реализации параллелизма современные компьютеры снабжены многоядерными процессорами. Для решения задач, связашгак с параллельными вычислительными процессами, применяются различные математические модели: сети Петри, структуры событий, асинхронные системы и т.д. Несмотря на их широкое применение существуют задачи, для решения которых нужны более общие модели. Различные обобщения моделей с отношением независимости рассматривались в работах М. Droste, R. М. Shortt, D. Kuske, Е. Goubault.

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

• Временные сети Петри (P. A. Merlin/L. Popova-Zeugmann).

• Сети Петри с задержками (С. Ramchandani/L. Popova-Zeugmann).

• Автоматы с отношением параллельности (М. Droste, R. М. Shortt).

• Временные системы переходов (Т. A. Henzinger, Z. Manna, A. Pnueli).

• Временные структуры событий (И. Б. Вирбицкайте, Р. С. Дубцов).

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

В последнее время большое внимание уделяется конвейерному параллелизму (J. L. Hennessy, D. A. Patterson). В литературе широко изучены синхронные линейные конвейеры. Менее изученным является класс асинхронных линейных конвейеров (J. Ebergen, R. Berks). При этом они очень широко применяются, начиная с уровня обработки запросов в параллельных системах упранления базами дашшх (JI. Б. Соколинский) и кончая уровнем вентильной реализащш (А. А. Герасимов, П. В. Кустарев). Остаются открытыми вопросы об оценке ускорения таких систем. В работе К. В. Герценбергера и Е. В. Четша рассматривается соответствующая формула, но она охватывает лишь такие асинхронные конвейеры, для которых предполагается, что скорость обмена данными между каналами и

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

Цель работы. Разработать методы трассировки и расчета времени выполнения асинхронных параллельных вычислительных процессов.

Объектом исследования являются параллельные вычислительные системы и процессы.

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

Задачи исследования. Для достижения поставленной цели необходимо решить ряд задач:

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

2. Рассмотреть для асинхронных систем и расширить на обобщенную модель метод трассировки и расчета времени выполнения параллельного процесса с помощью нормальной формы Фоаты.

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

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

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

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

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

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

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

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

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

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

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

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

Положения, выносимые на защиту:

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

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

• Формулы для нахождения времени обработки входных данных объема п конвейером и волновой системой.

• Результаты компьютерных экспериментов по вычислению времени выполнения конвейеров и волновых систем.

Соответствие диссертации паспорту специальности.

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

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

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

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

3. Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий. - Разработаны, обоснованы и проверены эффективные методы нахождения минимального времени выполнения для конвейеров и волновых систем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Автором введены дистрибутивные асинхронные автоматы. Дистрибутивным асинхронным автоматом называется пятерка А = (,S, s0, Е, J, Tran), состоящая из множеств S и Е, элемента s0 £ S, отношения Tran £ S х Е х S и семейства антирефлексивных симметричных отношений 3 = (/s)ses, /s £ Е X Е. Элементы s £ S называются состояниями, е 6 Е -инструкциями (действиями, событиями), s0 - начальным состоянием.

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

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

ii. Для любых s 6 S, (a1,a2) 6 Is, (s,allsl) E Tran и (s^ a2,s') 6 Tran существует такое s2 6 S, что (s, a2, s2) £ Tran и (s2, a1, s') £ Tran (рисунок 1).

ч /

Рисунок 1 - Условие (ü) для дистрибутивных асинхронных автоматов

В частности, асинхронная система1 удовлетворяет этим условиям. Доказано, что дистрибутивный асинхронный автомат обобщает автоматы с отношением параллельности в смысле Droste2:

Теорема 1.1. Всякий автомат (S,s0,E,l ,Trari) с отношением параллельности удовлетворяет аксиомам (i) — (ii) и, значит, является дистрибутивным асинхронным автоматом.

Пусть (Р,Т,pre,post,М0) - сеть Петри3. Обозначим mt-{p 6 P:pre(t)(p) * 0}, t ■= {р б P\post(t)(p') Ф 0}.

Каждой сети Петри соответствует дистрибутивный асинхронный автомат:

Теорема 1.2. Сеть Петри (Р, Т, pre, post, Mg) определяет дистрибутивный асинхронный автомат (S,s0,E,I,Tran), S - Ир, Е-Т, s0 - М0, Тгап-

{(М, t, М') е Мр х Г х : существует М->М'}, для которого /м определяется по формуле:

¡м = {(ti, УеГхГ:М> pre(tx) & М > pre(t2) & ■ ^ п ■ i2 = 0} (1.2)

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

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

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

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

2 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.

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

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

Рассматриваются пути в дистрибутивных асинхронных автоматах.

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

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

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

Рассмотрим асинхронную систему А. Будем интерпретировать события а £ Е как выполняющиеся во времени машинные команды, инструкции. Пусть для каждой инструкции задано время выполнения в тактах т(а) £ М+ = {1,2,3,...}. Наша задача — найти алгоритм вычисления минимального времени, необходимого для выполнения конечной последовательности инструкций.

В случае т(а) = 1 для всех а 6 Е ответ дал У^екегТ1 — минимальное время выполнения равно высоте нормальной формы Фоаты.

В общем случае при т(а) £ М+ мы разлагаем каждую операцшо асинхронной системы в композицию операций, имеющих зависимые инструкции сг, е2, —, ек, где к — т(а). Каждая из инструкций e¡ выполняется за один такт. Для того чтобы это разложение стало возможным, добавим к множеству 5 «промежуточные» состояния и обозначим их через уе15 яе1е2, Бе1е2е3, ■■■ ,$ехе2 ■•■ ек_1. Положим хеге2 ■■■ ек = где к = т(а). Получим

разложение перехода 5->5в композицию 5 -> -» -> ••• -» -> 5 , где = ... е1 для всех 1 < I < к — 1. Обозначим операцию а через а. Будет иметь место = а для всех 1 < I < /с - 1.

Определим новую асинхронную систему Аг. Отношение независимости /т будет состоять из пар (а, Ь), для которых (а, Ь) £ I. Введем множество состояний 5Х = {(х, а[х ■•■ 5 £ 5 &5 • % ■■■ат £ 5 & а1 < а2 < ••■ <

Оп & а;) £ I для всех 1<£<;< т&1<11< т (аг), 1 < ¿2 < т(а2),-Д < ¿т <т(ат)}.

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

Предложение 2.3. Минимальное время выполнения трассы аг ••■ ап, для которой существуют такие 5, з' 6 что з • а1-~ап = з', равно высоте нормальной формы Фоаты трассы а^0'2'1 ■■■ й^ап\

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

Псевдо-конвейер состоит из конечной последовательности действий а1а2 ... ап, в которой события и аг+1 зависимы для всех 1 < / < п — 1, а все остальные события независимы.

Псевдо-конвейер можно представить с помощью трассы (а1а2 ... ап)т, для некоторого т > 1. Для нахождения минимального времени выполнения трассы ах — Оп, нужно разложить каждую операцию в композицию инструкций, выполняющихся за единичное время, выписать трассу

ат(а1)йг(а2)...йг(ап)

и затем построить ее нормальную форму Фоаты. Количество блоков этой нормальной формы будет равно искомому минимальному' времени.

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

Рассмотрим псевдо-конвейер, состоящий из трех операций, применяемых к очереди, содержащей т элементов (рисунок 2). Каждая из операций считается неделимой. Она читает данные из области памяти, соответствующей входному месту, вычисляет значение некоторой функции и записывает в область памяти выходного места. Таким образом, соседние операции зависимы.

у

<1-2

Рисунок 2 - Сеть Петри нсевдо-конвейера

Трасса выполнения процесса будет равна С = [(а1а2а3)т]. Пусть т(аг) = 2, т(а2) = 1, т(а3) = 2. Тогда временная трасса, соответствующая трассе [{алага3)т] будет равна [(а1а2а^)т]. После приведения к нормальной форме Фоаты получаем [(а?а2а|)т] = [а1][аг]([а2][а1а3][а1а3])Тп~1[а2] [а3][а3]. Отсюда 0(0 = 1 + 1 + 3(гтг - 1) + 1 + 1 + 1 = Зт + 2. Если выполнять действия последовательно, то время выполнения будет равно 5т.

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

Рассмотрим конвейер, состоящий из р > 1 функциональных устройств и р + 1 каналов с0, ■••, ср. Пусть щ - последовательность действий, выполняемых за один шаг, 0 < I < р — 1. Она состоит из чтения из канала вычислительной операции а1 и записи в канал с1+1. Время выполнения щ равно г(с() + т(а^) + \у(с1+1), где г(сг) обозначает время чтения из канала си ю(с{) - время записи в канал С;, т(а£) - время выполнения операции а£, 0 < £ < р — 1.

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

5 („) = __"Со*^)_

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

/ • \ и

'■< • I

Рисунок 3 - Конвейер из четырех функциональных устройств

Для каждого функционального устройства щ, 0 < I < р — 1, задано время выполнения т(и£). Имеет место равенство т(и£) = г(с£) + т(а() + и'(с!+1). Для сетей Петри вводится отношение независимости, при котором два перехода независимы, если они не имеют общих входных и выходных мест. В сети Петри

на рисунке 3 переходы щ и щ зависимы, поскольку во время записи устройство щ должно захватить канал, из которого читает устройство щ. Для того, чтобы учесть это правило, мы измельчаем переходы сети Петри на переходы, время работы которых равно 1. Для того чтобы переходы, полученные после измельчения перехода щ, выполнялись как последовательная подпрограмма, мы добавляем сверху место с фишкой, соединенное с первым и последним переходами. В результате для всех 0 < I < р - 1 переход щ будет заменен частью сети Петри, показанной на рисунке 4. Стрелка, входившая раньше в переход щ, будет теперь входить в аго, а выходившая из щ будет выходить из сц1Т(щ)-1-

Рисунок 4 — Измельчение г-ого перехода

Обработка п элементов данных конвейером и0... ир_1 описывается трассой, состоящей из операций а^, 0 < I < р — 1, 0 < < т (щ) — 1, со временем выполнения 1:

(ао.0^0.1 ■■■ а0,т(и1)-1ар-1,0ар-1д ••■ «р-ЬтСИр-О-!) ' в которой для каждого I попарно зависимы операции и10,а1л, ■•■,аг1Т(и.)_1, принадлежащие иь а также для каждого I из диапазона 0 < I < р — 2 зависимы операции и а;+10.

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

Обозначим через Ь{ первый символ из слова щ, а через - последний символ из щ. Введем ограничение т(иг) > 2.

Следствие 2.2. Время обработки п входных элементов данных конвейером и0щ •••и{р_1} равно высоте нормальной формы Фоаты трассы,

определенной словом (ь0 а0Ыо)~2 е0 — ^ а^ид~2е1 ■■■ Ьр^ а^'1^'2, в которой попарно зависимы элементы Ьь аг и еь для каждого 0 < I < р — 1, а также зависимы элементы в; и Ь1+1 для всех 0 < ( < р-2. Здесь Ь2ег обозначает композшцпо операций Ьь а^"1-1-2, е1 в случае, когда т(щ) > 2.

Рассмотрим, например, конвейер, состоящий из трех функциональных устройств щщи2. Пусть т(щ) = 2, т(щ) = 4, т(и2) = 3. Тогда время обработки п элементов данных будет равно высоте нормальной формы трассы (b0e0b1aie1b2a2e2)n. Нормальная форма равна

[b0][eo][b0b1][e0a1][b0a1][e0e1]([b1b2][a1a2][a1e2][e1])n-1[b2][a2][e2]. Отсюда

9 TL

время выполнения равно (9 + 4(п — 1)), а ускорение равно ——.

Для дальнейшего исследования вопроса вычисления времени выполнения различных процессов была разработана компьютерная модель, имитирующая работу асинхронных конвейеров и волновых систем. Она состоит из р потоков (нитей). Потоки взаимодействуют с помощью операторов чтения из канала и записи в канал. В частности, для конвейера, перед началом работы в канал с[0] записывается п элементов входных данных. Затем загружаются потоки 0 < i < р- 1:

Thr(i)

{

int х;

for (int з=0; j<nj j++)

Í

c[i]»x; Sleep(tau[i]); c[l+l]<<x;

}

}

Здесь tau[i] равно T(a¿). Пусть r[i] -число, равное времени чтения r(c¿) из канала c¡, а w[i+l] - время записи w(c¡+1) в канал c¡+1, 0 < i < р — 1.

Потоки будут работать параллельно. Синхронизация достигается с помощью класса канала.

Наша компьютерная модель имитирует многопроцессорную систему. Это становится возможным благодаря использованию подпрограммы Sleep(t), которую могут выполнять параллельно несколько потоков.

Выполнение оператора c[i]>>x начинается с ожидания события «канал не пуст». Затем поток захватывает канал с [i], извлекает из него элемент и освобождает канал. Перед освобождением мы добавили оператор Sleep(r[i]).

Запись c[i+l]<<x состоит из ожидания «свободного места» в очереди канала c[i+l]. Затем поток захватывает канал c[i+l], записывает в него элемент, выполняет задержку Sleep(w[i+1]) и освобождает канал.

На экран выводятся графики ускорений, изображешше на рисунке 5. Каждый график соответствует конвейеру, состоящему из десяти функциональных устройств с различными временами выполнения. Объем

входных данных изменяется от 1 до 100. Графики, состоящие из отрезков, получены с помощью формулы (2.2). Графики ускорений, полученных опытным путем, выводятся точками. Полученные графики почти не отличаются. Это, во-первых, дает подтверждение формулы (2.2) опытным путем. Во-вторых, мы получаем адекватную модель асинхронного конвейера с буферной памятью.

4

I 5

Рисунок 5 — Графики зависимости ускорений от объема входных данных

Теорема 2.2. Время обработки л элементов данных конвейером вычисляется по формуле:

Тр(п) = З*"1 г (и,) + (п - 1) тах0Й5р_1{т(и£)} (2.3)

Из этой теоремы вытекает формула, полученная экспериментально Герценбергером и Чепиным5.

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

Пусть щ — операция /-го устройства волновой системы. Разложим ее в композицию операции еь выполняющихся за один такт. Будем называть выполнение е^ частичны м срабатыванием

Пусть е1,е2,—,е1 - последовательность частичных срабатываний волновой системы. Определим блок наибольших частичных срабатываний как наибольшее множество частичных операций, которые можно одновременно применить к состоянию волновой системы в данный момент времени. Максимальная нормальная форма будет состоять из блоков наибольших

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

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

Теорема 2.3. Количество блоков максимальной нормальной формы равно минимальному времени выполнения волновой системы.

Теорема 2.4. Время обработки входных данных объема п с помощью волновой системы, состоящей из р функциональных устройств, имеющих времена выполнения т(щ) при 0 < i < р — 1, равно

Тр(п) = Гр( 1) + (п - 1) maxo^p^irCUi)}.

В третьей главе рассматриваются временные сети Петри6. Автором введено понятие временных дистрибутивных асинхронных автоматов. Временным дистрибутивным асинхронным автоматом называется дистрибутивный асинхронный автомат А = (S,s0,E,],Tran), вместе с парой функций eft: Е -> Е>0, lftm-E-> 1Й>0 U {со}, удовлетворяющих для всех а Е Е неравенству eft(a) < lft(a). Здесь Кг0 обозначает множество неотрицательных вещественных чисел.

Показана связь между временными дистрибутивными автоматами и временными сетями Петри:

Теорема 3.1. Временная сеть Петри (P,T,F,M0,eft,lft) определяет временной дистрибутивный асинхронный автомат (S, s0, Е, I, Tran, eft, Ift), S = UP, E —T, Sq — M0, Tran = {{M, t, M') E Np xTxNp: существует

M-»M'} для которого /д, определяется по формуле (1.2).

Установлена связь между волновыми системами с функцией времени и временными дистрибутивными аашхронными автоматами:

Замечание. Волновая система (Р, Т, pre, post, п) с функцией времени т: Т -»N+ определяет временной дистрибутивный асинхронный автомат (5, s0, Е, I, Tran, eft, Ift), S — Np, E — T, Tran = {(M, t, M') £ИрхГх

Mp : существует M -» M'}, начальному состоянию s0 соответствует «-данных в каждом начальном месте, eft{t) = т(£), lft(t) = со, V t 6 Т, а отношение 1М определяется по формуле (1.2).

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Построена компьютерная модель, имитирующая работу многопроцессорной системы с помопц>ю приложения, работающего на двухъядерном компьютере. Модель основана на возможности одновременного выполнения функции Sleep() различными потоками. Передача данных в этой модели выполняется с помощью каналов, которые могут работать одновременно благодаря этой функции.

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ИССЛЕДОВАНИЯ

Статьи в журналах из перечня ВАК:

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

2. Кудряшова, Е. С. Моделирование конвейерных и волновых вычислений / Е. С. Кудряшова, Н. Н. Михайлова, А. А. Хусаинов // Интернет-журнал «Науковедение». - 2014.-№1 (20). http://naukovedenie.ru/PDF/56TVN 114.pdf

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

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

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

Свидетельства о регистрации программ для ЭВМ:

1. Программное обеспечение «QNX Real Time Monitoring System», свидетельство № 2012660639, 26.11.2012.

2. Программное обеспечение «Программное обеспечение для вычислешш времени работы сети Петри», свидетельство №2013618071, 29.08.2013.

Прочие наиболее значимые публикации:

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

2. Кудряшова, Е. С. Математические модели параллельных систем / Е. С. Кудряшова // Параллельные вычисления и задачи управления РАСО 2012: материалы шестой Международной конференщга 24-26 октября 2012. — Труды в 3 т. - М: ИПУ РАН, 2012. - Том 2. - С. 388-393.

3. Кудряшова, Е. С. Временные дистрибутивные асинхронные автоматы / Е. С. Кудряшова // XXXVI дальневосточная математическая школа-семинар

им. академика Е.В. Золотова, 4-10 сентября 2012 г.: сб. материалов [Электронный ресурс]. - Владивосток: ИАПУ ДВО РАН, 2012. - С. 371-375.

4. Хусаинов, А. А. Обобщенные асинхронные системы / А. А. Хусагагов, Е. С. Кудряшова // Актуальные проблемы математики, физики, информатики в вузе и школе: материалы Международной научно-пракшческой конференции 23 марта 2012. -Комсомольск-на-Амуре: Изд-во АмГПГУ, 2012. - С. 31-36.

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

6. Кудряшова, Е. С. Математическая модель для временных оценок параллельных систем / Е. С. Кудряшова // Наука молодых - основа будущего России: материалы докладов конкурса научно-исследовательских работ аспирантов и молодых ученых «КнАГТУ». — Комсомольск-на-Амуре: ФГБОУ ВПО «КнАГТУ», 2013. - С. 21-26.

7. Кудряшова, Е. С. Моделирование волновых вычислений / Е. С. Кудряшова // Наука молодых - основа будущего России: материалы докладов конкурса научно-исследовательских работ аспирантов и молодых ученых «КнАГТУ». - Комсомольск-на-Амуре: ФГБОУ ВПО «КнАГТУ», 2014. - С. 3944.

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

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

10. Кудряшова, Е. С. Математическая модель для волновых вычислений / Е. С. Кудряшова, А. А. Хусаинов // Интернет-журнал «Мир науки». - 2014. - № 3. http://mir-nauki.com/PDF/05KMN314.pdf

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

МОДЕЛИ ПАРАЛЛЕЛЬНЫХ СИСТЕМ И ИХ ПРИМЕНЕНИЕ ДЛЯ ТРАССИРОВКИ И РАСЧЕТА ВРЕМЕНИ ВЫПОЛНЕНИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 19.03.2015. Формат 60x84/16. Бумага писчая. Ризограф RIZO EZ 570Е. Усл. печ. л. 1,16. Уч.-изд. л. 1,10. Тираж 100. Заказ 26899. Полиграфическая лаборатория Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Комсомольский-на-Амуре государственный технический университет» 681013, Комсомольск-на-Амуре, пр. Ленина, 27