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

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

ТРЕЩЕВ Иван Андреевич

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

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

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

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

003463288

Работа выполнена в государственном образовательном учреждении высшего профессионального образования «Комсомольский-на-Амуре государственный технический университет» (ГОУВПО «КнАГТУ») на кафедре «Математическое обеспечение и применение ЭВМ».

Научный руководитель: доктор физико-математических наук,

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

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

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

Автореферат разослан «2Ь> февраля 2009 г

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

профессор

Чехонин Константин Александрович

доктор технических наук, профессор Кравец Олег Яковлевич

Ведущая организация: Институт вычислительной математики н

математической геофизики СО РАН

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

М.М. Зарубин

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

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

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

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

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

К основным результатам по созданию формальных моделей для описания «реактивных систем», параллельных и распределенных вычислений относятся работы зарубежных ученых Я. Фостера, В. Пратта, Ч. Хоара, Р. Мил-нера, М Хеннесси, К. Петри Г.Винскеля, М. Нильсена, Э. Гобо, М. Беднарчи-ка, а также отечественных исследователей В.Воеводина, Вл. Воеводина, Г. Ппоткина, В. Котова, И. Вирбицкайте, Б. Головкина, А. Барского, В. Бочарова, В. Корнеева, В. Топоркова, Н. Миренкова и др.

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

В ходе достижения цели решались следующие задачи:

- разработка и исследование математических моделей для описания взаимодействующих процессов исполняющихся параллельно на системах с SMP-архитектурой.;

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

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

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

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

задач.

Основные методы исследования базируются на математическом аппарате теории множеств, дискретной математики, математического анализа, методах вычислительной математики и математического программирования. Для практических исследований и алгоритмической обработки использованы среды программирования «Borland С++ 5.02», «Borland С++ Builder v 6.0», «Microsoft Visual Studio 6.0», «Microsoft Visual Studio 2005», «Microsoft Visual Studio 2008».

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

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

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

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

- волновые системы;

- временные волновые системы;

- гибридные временные волновые системы.

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

- введен ряд эквивалентностей на множестве волновых систем;

- на множестве волновых систем введены операции позволяющие по-

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

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

- построены волновые системы для ряда алгоритмов вычислительной математики и компьютерной графики.

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

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

Практическая ценность данных исследований состоит в возможности их использования в различных областях прикладной математики, компьютерной графики, при создании систем автоматического распараллеливания. Показано, что применение, предложенной в диссертационной работе математической модели гибридных временных волновых систем, позволяет прогнозировать время функционирования взаимодействующих параллельно исполняющихся процессов. В частности, результаты диссертационной работы, использовались в ФГУЗ ЦГиЭ №99 ФМБА России при создании модуля формирования списка цехов ОАО «АСЗ» для дератизации по датам.

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

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

1. Формальные математические модели параллельных вычислительных процессов, применяемые на системах с SMP-архитектурой, а так же конструкции для множества волновых систем и оценки времени функционирования временных волновых систем, полученных в результате параллельной композиции, склеивания, последовательной композиции и замены.

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

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

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

г. Комсомольск-на-Амуре, XXXI Дальневосточной школе-семинаре имени академика Е.В. Золотова г. Владивосток, XXXII Дальневосточной школе-семинаре имени академика Е.В. Золотова г. Владивосток, VIII Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям г. Новосибирск, работы автора принимали участие и заняли призовые места в конкурсе «Программист года 2008» г. Владивосток, обсуждались на научно-технических семинарах факультета компьютерных технологий КнАГТУ.

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

Публикации. Содержание диссертации отражено в 21 публикациях, приведенных в конце автореферата. В числе основных - 13 статьей, из них 3 опубликовано в ведущих рецензируемых журналах, 4 авторских свидетельства о регистрации программ для ЭВМ.

В работах, опубликованных в соавторстве, автору принадлежат следующие научные и практические результаты: в [6] - построение алгоритма; в [15] - постановка задачи, создание математической модели, текст программы; в [10] - постановка задачи, построение алгоритма, проектирование гибридных временных волновых систем, частичная разработка текста программы; в [22] — исследование вопросов разложимости асинхронных систем переходов в параллельную композицию.

Основные результаты работы, полученные автором самостоятельно и опубликованные без соавторства - [1-5,7-9, 11-14, 16-21].

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка цитируемой литературы. Работа изложена на 120 страницах основного текста, содержит 59 рисунков и 1 таблицу, 136 наименований библиографических источников.

Автор выражает искреннюю благодарность своему руководителю доктору физико-математических наук, профессору Хусаинову A.A. и Михайловой H.H. за внимание к работе.

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

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

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

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

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

Определение. Частичным орграфом называется четверка

G = (А, V, dom, cod) состоящая из пары множеств и пары частичных функций dom, cod: A->V. Частичная функция dom ставит в соответствие каждой дуге «начальную вершину», a cod - «конечную». Определения конечности и ацикличности очевидным образом переносятся на частичные орграфы.

Определение. Моделью волновой системы или просто волновой системой будем называть простой ацикличный частичный орграф G = (А, V, dorn, cod) у которого, для каждой вершины v, её прообразы dom'(v) и если

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

Определение. Волновая система G = (А, V, dom, cod) называется вре- . менной, если для нее определены пара вещественных чисел и функция t:V~>R+ - функция времени выполнения каждой вершины, принимающая неотрицательные значения, а, ß - пара чисел, интерпретируемых как время записи и чтения из канала соответственно.

Определение, под гибридной временной волновой AWS мы будем понимать девятку:

AWS=(A, V, L, dom, cod, w, t, a, ß) где (A, V, dom, cod, t, a, ß) - временная волновая система, w:A —>L -

инъективная функция, размечающая ребра, L - множество меток.

10.0 20.0 30.0 10.0

О-МЭ-ЧЭ-^-©

а=1,Р=2

Рис. 1. Гибридная временная волновая система для вычисления значений функции g(x)=fi(f2(x))

Определение. Ориентированным путем, или просто путем, в гибридной временной волновой системе назовем последовательность / = v0,v,,...,v„, такую, что выполнено:

voe^v.e^e^.li/fsn-l,

Y/(0 < j < п -1), За € A, dom(a) = v;, cod (а) = v((1

Под It будем понимать путь, полученный отсечением от пути / первых к элементов и содержащий всю оставшуюся часть исходного пути. Множество всевозможных путей гибридной временной волновой системы A WS обозначим Tracers- Если произвольная вершина v входит в путь / будем писать vel. Для любого пути / под его длиной |/| будем понимать количество входящих в него вершин. Временем прохождения пути / назовем величину:

и

»-о

где суммирование ведется по всем вершинам, входящим в путь I. Два пути / и т будем называть эквивалентными, тогда и только тогда, когда |/|=|т| и d(l)=d(m). Пара путей называется равной, если они состоят из одних и тех же вершин, с сохранением порядка следования. Определим рефлексивное, транзитивное и антисимметричное отношение, являющееся отношением порядка на множестве Tracers следующим образом: /,Л1Е Trace AWS,l < т о d(!) < d(m)

Предложение 1

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

Z'(v)+ \A\(z + r)> Тлт > d(max(/))

veH /еГике|ЛХ

Величину £f(v)+M|(r + r) назовем верхней оценкой времени работы данной гибридной временной волновой системы и обозначим а ¿(тах(/))

/йТгосеj щУ

- нижней оценкой и обозначим .

Рассмотрим волновую систему, реализующую конвейерные вычисления AWS = yi(/2(.../„(x))...). Пусть количество вершин такой волновой системы равно т. Так же пусть VveF,f(v) = A,r = 0,r = 0, где h - константа и волновая система функционирует на ЭВМ с одним процессором. Тогда время об-

работки и последовательно подаваемых входных данных такой волновой системы равно Tv = nmh. В случае, когда у нас имеется р>т процессоров, время обработки потока из п входных данных будет равно Tr =(п + m)h. Тогда справедливо следующее Предложение 2

limS^ =m. То есть максимально достижимое ускорение вычислений на

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

Пусть величина s = (т - 1)(г + г) - время, затрачиваемое на обмен данными в конвейерной временной волновой системе для обработки одного экземпляра входных данных, тогда справедлива следующая Теорема 1

,. „ mh + s

IimS„ =-.

' h+s

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

Определим А WS* - множество всевозможных волновых систем. Определим отношение равенства на множестве А WS* следующим образом:

V А WS,, AWS2 е А WS* AWS,=AWS2 тогда и только тогда, когда А,=А2, Vi=V2, domi=dom2, codi=cod2.

Определим операцию + (параллельной композиции) для двух волновых систем следующим образом:

тогда AWS+AWS'=AWS„ в случае, если АпА'=0 VnV'= 0. AWS+ = (AuA' VuV, domudom', coducod).

Пусть заданы две гибридные временные волновые системы А WS = (У, А, dorn, cod, г, г,/, L, w), AWS'=(V\A\dom\cod\T\T\t\L\w) Предложение 3

2>) + !''(>') + |м|(г + ?)+|/Г|(г' + ?)]> т^ > min d(max(!)),d(max(/)) veC J L /еГп**)Ит 1сТкхеЛШ s'

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

Пусть А WS, =J]A fVS,> тогДа справедливо £ 7" ™ > > min(r^)

Пусть AWS = (A, V, dorn, cod), AWS'=(A\V',dom\cod),AnA'= VnV'= domndom' = codncod' = 0, V = Vin и Vf и V0,„, V'= v;„ и v; и и пусть задана f: Vou, —> V'm - биекция.

Тогда определим операцию последовательной композиции на множестве волновых систем -» следующим образом:

AWS AWS'= AWS0, A WS0 = (А0, К dorn", cocf), Vo = К uV',A° = Au А' и A a, cocf = cod и cod' и coda dorn" = dorn и dorn' и dorn a \Aa\ = j Vou\ и для V veV0U, 3 а eA a такая, что dom°(a)=v и эти стрелки образуют doma, Va еАа cocf (а) =f(dorn0 (а))

Пусть заданы две гибридные временные волновые системы. Тогда AWS ->AWS' = A WS", а для Аа время посылки данных равно а, приема b тогда справедливо следующее Предложение 4

Í2»

Lof

I*'(v)

+ |м | (г + г)+1 А' I (г' + r')]+ I VtM I (a + ft) > 7^.. >

> d( max(/)) + d( max(/)) + (a + b)

teTm*„s Mbmtjunt

Предложение 4 допускает обобщение для семейства гибридных временных волновых систем. Теорема 3

Пусть AIVS" = AWS, -> AWS2 ->...-> AWS„, для A/a время посылки данных равно а/, приема b¡, для А2а время посылки данных равно а2, приема Ь2 и так далее, тогда справедливо ¿ (| V^ | (а, + Ь,) + ) > TAWS<¡ > £ (Г™^, + а, +Ь,).

Пусть A WS = (А, V, dom, cod), AWS' = (А\ V\ dorn', cod% V=V,„u Vfu Vmb V'= v;„ uVf и V^.f: Vou, -> Vi - биекция. Тогда определим операцию склеивания -/для волновых систем следующим образом:

AWS jAWS' = AWS¿ AWS i = (Ai Vj, domj, codj), Vj. = Vm и Vou, uVfu V'f uV'm, Aj. = А и A' dorn j. = dorn и dom a codi = cod ucoda

и выполняется Vae Ai если dom'(a) eV¡„, w doma(a) ef''(dom'(a)) и для Vae Ai если dom'(a) e V'fuV'M то doma(a)=dom'(a). Причём порядок сохраняется, то есть dom'a1 (v) - конечное линейно упорядоченное множество й из того, что (dom'(а))'1 < (dom'(d))'1 следует, что (doma(a))'] <(doma(d))~'.

Пусть заданы две гибридные временные волновые системы и У — V¡„ и VfU Vou„ Г= Vi u f; u Fl, AWS j. AWS' = A WSj, тогда справедливо следующее

Предложение 5

2>)+2>'(v)

¿d(max(l)) + d(

кТпссАКх

+ |л|(г + г)+|Л' í(r' + г')]- 2>'(v) > тлт1 >

ve^

max(/)

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

Пусть А ТО 4-= А ТО, IА ТО2 4... I А ТО„, тогда справедливо

шах(/)

ItTrtHev.

Пусть /i (KS, = (А,, К/, aW;, cod,,) , A¡VS2 = dom2, codi) ,А,пА2

= 0, V,= V,,„ и V,r и V,ou„ V2 = V2m и V2f и V2ou„ также Эие V, такая, что \(codi(u))'!\ = 1 V2tn\, \(domi(u))~'\ = \V2ou,\ и 3f,g- изоморфизмы линейно упорядоченных множеств, такие, что если v,e е (codi(a))' и v <е, то отсюда следует, что f(v) <f(e) и если m,z е (domi(a))'' и m <z, то g(n) <g(z).

Определим операцию замены <— для волновых систем следующим образом: AIVS/ <-(u,f,g)AWS2 = AWS',причем AWS' = (А', V, dom', cod), V'= (V,\{u}) сjV2,A' = Ai uA2,dorn' = dom, udom2, cod'= cod, ucod2, Ve e (domi(u))'1 dorn '=(dom \(e, dornte))) u(e, g(e)) , cod'=(cod\(e, cod¡(e))) u(e,f(e)).

Пусть заданы две гибридные временные волновые системы и V = Vin и VfU Vou„ V = к: U к; и KL, A WS if- (и, f, g)A WS2 = A WS',

Vi n V2 = {и}, t(u) = t'(u) = а, так же зададим предикат P(u,AWS) принимающий значение равное единице, если ие шах(/), и ноль в противном случае, тогда справедливо следующее Предложение 6

+ f АI (г + г)+1 А11 (г' + Г')]- /(«) > TAWS. >

>d(max(l)) + d(

lüTractA i^f,

max(/)

1еТгасеА

)-Р(и,АФ81)1(и)

" и ......ЯЯ-Л * _!)

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

AWS^=ЛWSi<-(щJi,gi)AWS1^^u,J2,g1)AWS}^...^{u„.lJn_l,g„A)AWS„, тогда справедливо - £ ф,)> Тлт^ -§/>(«,.ЛМШ»,)-

I ¡-I I ы

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

Пусть заданы конечные множества А\, Лг.....А„. Для произвольного целого п>() под п-местным предикатом мы будем понимать функцию: хЛ2х...хЛ„->{0,1}, принимающую значения 1 (истина) или 0 (ложь). Предикатом мы будем называть произвольную функцию:

Q: \jAi x A2 x---x {0,1}.

П>1

Формулировка задачи. Даны конечные множества А\, А2,..., А„ и для каждого целого i задан /'-местный предикат Р,(хь х2,..., х,). Предполагается, что для всех i>J справедливы импликации:

Pi(xux2,...,xi) = \=>Pi_l(xl,x2,...,xi_l) = l.

Требуется построить последовательности х = (хьх2,...,х„), где х, е А„ при 1 < I < п, для которых верны соотношения:

1) ^(*1>*2--"*я) = 1,2) Q{x\,x2,...,xn) = 1.

Алгоритм перебора заключается в том, что за последней полученной последовательностью (xi, х2,..., хы) генерируется расширяющаяся её последовательность (xi, x2,...,xk.|,xk), а если таких расширений больше нет, то рассматривается следующий элемент Хы е Ац. Если же такие элементы хц е Ац исчерпаны, то производится возврат к последовательности (Х|, Хг,..., х^.г). Идея реализации алгоритма перебора последовательностей для систем с SMP-архитектурой заключается в том, чтобы подпрограмма перебора сама определяет, следует ли ей запуститься как потоку, если количество незанятых процессоров отлично от нуля, или как последовательной рекурсивной подпрограмме.

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

• перебор возрастающих последовательностей;

• задача Гаусса о ферзях;

• перебор разложений числа в сумму;

• перебор гамильтоновых циклов в графе;

• генерация разбиений заданного множества;

Тестирование разработанных многопотоковых приложений производилось на системе под управлением Microsoft Windows Server 2003, оснащенной двумя четырехядерным микропроцессорами Intel Pentium 4 Xeon 5320 (1,86 Гц на ядро), объем оперативной памяти 8Gb.

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

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

В пятой главе приводятся сети Петри, построенные на основе гибридных временных волновых систем, для конструирования поверхностей при помощи поверхностей Цао Ена, кривых Безье, для получения центральной и параллельной проекции некоторой точки, задания базиса углами Эйлера, преобразование вращения, алгоритмы отсечения Сазерленда-Коэна плоским и трехмерным окном, для алгоритма Варнока удаления невидимых линий, для построения кусочно-линейного сплайна, сплайна Эрмита, В-сплайна той степени, интерполяционного многочлена Лагранжа. Приводиться описание класса-канала построенного на основе семафоров для организации обмена сообщениями между параллельно функционирующими вычислительными процессами. Рассматриваются вопросы построения параллельных алгоритмов для визуализации фрактальных множеств.

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

где [7] - целая часть среднего времени выполнения приложения, - кое измерение времени выполнения приложения.

___■ _ ~_Таблица 1

Алгоритм Снежинка Коха Губка Менге- ра Дракон Хартера- Хетуэйя Множество Ньютона

Последовательный 756 1423 13789 3609

Адаптивный 693 1380 11023 3027

Распараллеливание рекурсии 904 1620 15121 6324

Расслоение 403 1212 9671 2437

На основе волновых систем 601 1320 11024 2213

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

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

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

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

3. Получены верхняя и нижняя оценки времени функционирования гибридных временных волновых систем.

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

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

6. Введен ряд эквивалентностей на множестве волновых систем.

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

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

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

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

1. Трещев И.А. Математическое моделирование волновых систем / И.А. Трещев // Моделирование. Теория, методы и средства: Материалы VII Международной научно-практической конференции, г. Новочеркасск, 6.04.2007.: В Зч. / Юж.-Рос. гос. техн. ун-т (НПИ).- Новочеркасск: ЮРГТУ. - 2007. -43. - С. 3841.

2. Трещёв И.А. Математическое моделирование волновых систем / И.А. Трещев // XXXII Дальневосточная математическая школа-семинар имени академика Е.В. Золотова: Тезисы докладов, Владивосток: Изд-во Дальнаука. - 2007. - С. 101-102.

3. Трещёв И.А. Применение волновых систем для моделирования параллельных алгоритмов машинной графики / И. А. Трещев//Информационно-вычислительные технологии и их приложения: сборник статей VI Международной научно-технической конференции. - Пенза: РИО ПГСХА. - 2007. - С. 167-175.

4. Трещёв И.А. Асинхронные волновые системы для моделирования трехмерных поверхностей при помощи бикубических поверхностей Безье и В-сплайн поверхностей / И.А. Трещев // Информационно вычислительные технологии и их приложения: сборник статей V международной научно-технической конференции,- Пенза: РИО ПГСХА. - 2006. - С. 309-312.

5. Трещёв И.А. Параллельные алгоритмы визуализации фрактальных множеств на основе асинхронных волновых систем / И.А. Трещев // Информационно вычислительные технологии и их приложения: сборник статей IV российско-украинского научно-технического и методического симпозиума. - Пенза: РИО ПГСХА. - 2006 - С. 227-230.

6. Трещёв И.А., Хусаинов А.А. Разработка асинхронных систем для визуализа-

ции трехмерных объектов / И.А. Трещев, A.A. Хусаинов // Научно-техническое творчество аспирантов и студентов: материалы 35-й научно-технической конференции аспирантов и студентов (г. Комсомольск-на-Амуре, 1-15 апреля 2005г.): Ч. 2/Редкол.: А.И. Евстигнеев (отв. ред.) и др. - Комсомольск-на-Амуре: ГОУВПО «КнАГТУ». - 2005. - С. 12-13.

7. Трещёв И.А. Разработка асинхронных систем переходов для визуализации трехмерных объектов / И.А. Трещев // Труды третьей международной конференции "Параллельные вычисления и задачи управления" Москва, 2-4 октября.

- 2006. - С. 1417-1431.

8. Трещёв И.А. Применение асинхронных волновых систем при построении параллельных алгоритмов для решения задач интерполяции / И.А. Трещев // Интеллектуальные технологии в образовании, экономики и упралении - 2006: Сборник материалов III Международной научно-практической конференции. -Воронеж: Воронежская областная типография - Изд-во им. Е.А. Болховитино-ва. - 2006. - С. 293-299.

9. Асинхронные волновые системы переходов для моделирования и визуализации трехмерных объектов: Св. 2006612000 Российская федерация, / Трещев И.А. -№2006611209 ; заявл. 13.04.2006; опубл. 29.06.2006, Бюл. №4(57).

- С. 28.

10. Асинхронные волновые системы переходов, метод адаптивного динамического программирования и метод расслоения для визуализации фрактальных множеств: Св. 2007610389 Российская федерация, / Трещев И.А., Лозовская О.М. -№2006614051 ; заявл. 28.11.2006; опубл. 23.01.2007, Бюл. №2(59). -С. 21.

11. Моделирование волновых систем при помощи сетей Петри: Св. 2007613267 Российская федерация, / Трещев И.А. - №2007612266 ; заявл. 06.07.2007; опубл. 02.08.2007, Бюл. №2(59). - С. 38-39.

12. Перебор последовательностей как раскраска вершин графа при обходе в ширину с использованием многопотоковых приложений на компьютерах с SMP архитектурой: Св. 2006613475 Российская федерация, / Трещев И.А. -№2006611646 ; заявл. 22.05.2006; опубл. 06.10.2006, Бюл. №4(57). - С. 4950.

13. Трещёв И.А. Программное обеспечение для перебора последовательностей на компьютерах с SMP архитектурой / И.А. Трещев // XXXI Дальневосточная школа-семинар имени академика Е.В. Золотова: Тезисы докладов. Владивосток: Дальнаука. - 2006. - С. 183.

14. Трещёв И.А., Хусаинов A.A. Метод перебора последовательностей как раскраска вершин графа при обходе в ширину на компьютерах с SMP архитектурой / И.А. Трещев, A.A. Хусаинов // Научно-техническое творчество аспирантов и студентов: материалы 36-й научно-технической конференции аспирантов и студентов (г. Комсомольск-на-Амуре, 3-17 апреля 2006.): Ч. 1/Редкол.: А.И. Евстигнеев (отв. ред.) и др. - Комсомольск-на-Амуре: ГОУВПО «КнАГТУ». - 2006. - С. 70-71.

15. Трещев И.А. Применение Асинхронных волновых систем типа «каскадный ливень» для моделирования параллельных вычислений на примере ряда алго-

ритмов машинной графики / И.А. Трещев // Вестник Комсомольского-на-Амуре государственного технического университета: Вып. X. Управление на-ноструктурированием металлических материалов и динамическими системами: сборник научных трудов/ редкол.: Ю.Г. Кабалдин (отв. Ред.) и др. - Комсомольск-на-Амуре: ГОУВПО «КнАГТУ». - 2008. - С. 128-133.

16. Трещев И.А. Программное обеспечение для визуализации трехмерных объектов при помощи гибридных волновых систем / И.А. Трещев // Открытый дальневосточный конкурс программных средств студентов, аспирантов и молодых специалистов «Программист 2008», Сборник докладов. Владивосток: ИАПУ ДВО РАН. - 2008. -С. 46-48.

17. Трещев И.А. Программное обеспечение для построения двухмерных и трехмерных фрактальных множеств с использованием многопоточных приложений / И.А. Трещев // Открытый дальневосточный конкурс программных средств студентов, аспирантов и молодых специалистов «Программист 2008», Сборник докладов. Владивосток: ИАПУ ДВО РАН. - 2008. - С. 49-52.

18. Трещев И.А. Программное обеспечение дня распараллеливания алгоритма перебора с возвратом с использованием многопоточных приложений / И.А. Трещев // Открытый дальневосточный конкурс программных средств студентов, аспирантов и молодых специалистов «Программист 2008», Сборник докладов. Владивосток: ИАПУ ДВО РАН. - 2008. - С. 52-55.

19. Трещев И.А. Построение многопоточных приложений для распараллеливания алгоритмов перебора / И.А. Трещев // Информатика и системы управления. -2008.-№1(15).-С. 151-159.

20. Трещев И.А. Математическая модель гибридной временной волновой системы / И.А. Трещев // Системы управления и информационные технологии. - 2007. -N4(30).-С. 19-21.

21. Хусаинов А. А., Лопаткин В. Е., Трещев И. А. Исследование математической модели параллельных вычислительных процессов методами алгебраической топологии / A.A. Хусаинов, В.Е. Лопаткин, И.А. Трещев // Сиб. журн. индустр. матем.-2008.-том 11.-номер 1.-С. 141-151.

ТРЕЩЕВ Иван Андреевич

Математические модели параллельных вычислительных процессов и их применение для построения многопоточных приложений на системах с вМР-архитектурой

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

Подписано в печать 17.02.2009. Формат 60x84/16. Бумага писчая. Печать офсетная. Усл. печ. л. 1,06. Уч.-изд л. 0,94. Тираж 100. Заказ 22188.

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

Введение

ГЛАВА 1 Обзор существующих математических моделей взаимодействующих параллельных вычислительных процессов

1.1 Граф алгоритма, информационный граф алгоритма

1.2 Граф зависимости и граф процесса

1.3 Сети Петри и СЕ-сети Петри, раскрашенные сети Петри

1.4 Размеченные системы переходов и асинхронные системы переходов

1.5 Структуры событий и размеченные структуры событий

1.6 Автоматы высокой размерности и деревья синхронизации 23 1.7Акторная модель SDF, модель Кана, маркированные потоковые графы, М-сети

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

ГЛАВА 2 Волновые системы, временные волновые системы и гибридные временные волновые системы

2.1 Формальное описание математической модели волновых систем

2.2 Эквивалентность и двойственная природа волновых систем

2.3 Конвейерные вычисления и волновые системы 34 Выводы по второй главе

Глава 3 Конструкции на множестве волновых систем, алгоритм вычисления нижней оценки времени функционирования

3.1 Параллельная композиция волновых систем

3.2 Временные оценки параллельной композиции гибридных временных волновых систем

3.3 Последовательная композиция волновых систем

3.4 Временные оценки последовательной композиции гибридных временных волновых систем

3.5 Операция «склеивания» волновых систем

3.6 Временные оценки для операции «склеивания» гибридных временных волновых систем

3.7 Операция «замены» для множества волновых систем

3.8 Временные оценки для операции «замены» гибридных временных волновых систем

3.9 Операции п, -,Л

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

Глава 4 Параллельный алгоритм перебора последовательностей для вычислительных систем с БМР-архитектурой

4.1 Описание алгоритма

4.2 Распараллеливание рекурсивных подпрограмм

4.3 Параллельная реализация с помощью обхода в ширину

4.4 Параллельная реализация для систем с БМР-архитектурой

4.5 Условия проведения эксперимента и результаты тестирования

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

Глава 5 Применение гибридных временных волновых систем при моделировании параллельных алгоритмов машинной графики и вычислительной математики на системах с 8МР-архитектурой

5.1 Реализация каналов волновой системы

5.2 Поверхности Цао Ена и кривые Безье

5.3 Бикубические поверхности Безье и В-сплайн поверхности

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

5.5 Преобразование поворота, алгоритм отсечения Сазерленда-Коэна

5.6 Кусочно-линейная интерполяция, интерполяционный сплайн Эрмита, интерполяционный многочлен Лагранжа.

5.7 Фрактальная геометрия, метод адаптивного динамического распараллеливания, распараллеливание на основе волновых систем

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

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

Теория математического моделирования вычислительных процессов восходит к построению математических моделей, разработанных с целью формализации понятия алгоритма [25, 56, 60, 93, 99]:

• Машины Тьюринга

• Конечные автоматы

• Автоматы с магазинной памятью

• Системы Маркова

• Машины с произвольным доступом

К сожалению, эти математические модели не пригодны для исследования параллельных процессов. В реальном мире лишь природа небольшого количества вычислительных систем является последовательной [12], и они могут быть описаны при помощи соответствующих моделей. Большинство систем являются распределенными, в том смысле, что их можно представить как раздельно функционирующие и взаимодействующие блоки, представляющие собой составные части (возможно, функционирующие последовательно), некоторого общего процесса, решающего поставленную задачу. Такие системы называют «реактивными» [123].

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

За последние 30 лет — зарубежными исследователями Я. Фостером [116], Ч. Хоаром [98, 119], Р. Милнером [124], К. Петри [129], Г.Винскелем [135, 136], М. Нильсеном [125, 126], Э. Гобо [118], М. Беднарчиком [115] были предложены и изучены многие формальные модели «реактивных» систем:

• CSP (Communicating sequential processes (взаимодействующие последовательные процессы)) [119, 133];

• LTS (Labeled Transition Systems (размеченые системы переходов)) . [125];

• ATS (Asynchronous Transition Systems (Асинхронные системы переходов)) [115];

• РЕ (Prime Events (Структуры событий)) [135];

• PN (Petri Network (Сети Петри)) [129];

• CE-PN (Condition Event Petri Network(YcflOBHO событийные сети Петри)) [125];

• SyncTrees (Synchronization Trees (Деревья синхронизации)) [136];

• HAD(Higher dimensional automata(ABTOMaTbi высокой размерности) [113, 118];

• SDF-графы, маркированные потоковые графы и М-сети [122, 134]. Так же стоит отметить исследования в области построения формальных моделей распределенных вычислений отечественных ученых В.Воеводина и Вл. Воеводина [19, 20], О. Омарова [57, 58], В. Котова [40, 41], И. Вирбицкайте [17, 114], А. Барского [8], В. Бочарова [13], В. Корнеева [38, 39], В. Топоркова [70, 71], Н. Миренкова [50] и др.

Реактивные» системы используются для описания поведения операционных систем и коммуникационных протоколов [94], управляющего программного обеспечения и других схожих систем, а так же для моделирования параллельных вычислений [125].

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

Многие классические модели: сети Петри, размеченные системы переходов, асинхронные системы переходов, автоматы высокой размерности, графы зависимости, графы процесса, графы алгоритма и информационные графы алгоритма позволяют исследовать проблемы связанные с достижимостью некоторого состояния вычислительного процесса [26], его нетупиковостью [40], решать классические проблемы синхронизации [14]: сериализации [72], взаимной блокировки [24], бесконфликтности [67]. Выявлять взаимосвязь моделей между собой. Анализировать состояния таких систем различными методами.

Лишь немногие модели позволяют анализировать время функционирования таких систем - временные сети Петри [114], временные структуры событий [125], временные системы переходов [125]. Из них наиболее часто используемыми на практике являются временные раскрашенные сети Петри [121]. Стоит отметить малоизученность и сложность реализации на основе этой модели, а так же сложность теоретического анализа ввиду асинхронной природы самих сетей Петри.

Автор предлагает новые математические модели параллельных вычислений — волновые системы, временные волновые системы и гибридные временные волновые системы, для систем с SMP архитектурой [128], которые позволяют моделировать, изучать, разрабатывать и анализировать сложные вычислительные процессы, использующие параллелизм задачи и позволяющие провести априорный анализ времени функционирования таких систем. Гибридная временная волновая система [76] состоит из взаимодействующих последовательных процессов и является обобщением конвейерной системы. Для данной математической модели автором получена априорные нижняя и верхняя оценки времени их функционирования. Рассмотрены различные типы эквивалентностей [117] для гибридных временных волновых систем. Построены параллельные алгоритмы различных задач вычислительной математики и компьютерной графики, приводятся алгоритмы построения гибридных временных волновых систем для произвольных арифметических выражений и алгоритм вычисления нижней оценки времени функционирования таких систем.

Цель работы.

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

Для достижения поставленной цели планируется решение ряда задач.

Задачи работы.

• Разработать и исследовать математическую модель для описания взаимодействующих процессов исполняющихся параллельно на системах с 8МР-архитектурой.

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

• Разработать комплекс программ для моделирования гибридных временных волновых систем. '

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

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

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

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

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

• введен ряд эквивалентностей на множестве волновых систем;

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

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

• построены волновые системы для ряда алгоритмов вычислительной математики и компьютерной графики.

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

Практическая ценность данных исследований состоит в возможности их использования в различных областях прикладной математики, компьютерной графики, при создании систем автоматического распараллеливания. Показано, что применение, предложенной в диссертационной работе математической модели гибридных временных волновых систем, позволяет прогнозировать время функционирования взаимодействующих параллельно исполняющихся процессов. В частности, результаты диссертационной работы, использовались в ФГУЗ «ЦГиЭ №99 ФМБА России» при создании модуля формирования списка цехов ОАО АСЗ для дератизации по датам.

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

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

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

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

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

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

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

• VIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям г. Новосибирск;

• работы автора принимали участие и заняли призовые места в конкурсе «Программист года 2008» г. Владивосток;

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

Автором опубликовано 16 научных статей [73-74, 76-88, 92], в центральной печати 3(в соавторстве одна), получены 4 авторских свидетельства о регистрации программ для ЭВМ [75, 89-91](в соавторстве одно).

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

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

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

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

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

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

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

В пятой главе приводятся сети Петри, построенные на основе гибридных временных волновых систем, для конструирования поверхностей при помощи поверхностей Цао Ена, кривых Безье, для получения центральной и параллельной проекции некоторой точки, задания базиса углами Эйлера, преобразование вращения, алгоритмы отсечения Сазерленда-Коэна плоским и трехмерным окном, для алгоритма Варнока удаления невидимых линий, для построения кусочно-линейного сплайна, сплайна Эрмита, В-сплайна m-ой степени, интерполяционного многочлена Лагранжа. Приводиться описание класса-канала построенного на основе семафоров для организации обмена сообщениями между параллельно функционирующими вычислительными процессами. Рассматриваются вопросы построения параллельных алгоритмов для визуализации фрактальных множеств.

Структура диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Текст диссертации изложен на 120 страницах, включает одну таблицу и 59 рисунков.

Выводы по пятой главе

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

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

3. Использование волновых систем упрощает задачу построения параллельных алгоритмов и выявления внутреннего параллелизма присущего задаче.

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

5. Волновые системы и параллельные алгоритмы, построенные на их основе, можно широко применять на практике.

ЗАКЛЮЧЕНИЕ

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

1. Разработана и исследована математическая модель для описания функционирования взаимодействующих процессов исполняющихся параллельно на системах с БМР-архитектурой.

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

3. Получены верхняя и нижняя оценки времени функционирования гибридных временных волновых систем.

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

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

6. Введен ряд эквивалентностей на множестве волновых систем;

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

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

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

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

1. Акимов O.E. Дискретная математика: логика, группы, графы. — М.: Лаборатория базовых знаний, 2001. — 286с.

2. Аммерал Л. Интерактивная трехмерная машинная графика. М.: «Сол Систем», 1992. - 317 с.

3. Аммерал Л. Машинная графика на персональных компьютерах. — М.: «Сол Систем», 1992. 232 с.

4. Аммерал Л. Принципы программирования в машинной графике. — М.: «Сол Систем», 1992. 224 с.

5. Архангельский А.Я. Программирование в С++ Builder 6/ А.Я. Архангельский. — М.: ЗАО «Издательство Бином», 2002. — 1152 с.

6. Ахо A.B. Структуры данных и алгоритмы / A.B. Ахо, Дж. Хопкрофт, Д.Д. Ульман. — М.: Издательский дом «Вильяме», 2000. 384 с.

7. Байцер Б. Микроанализ производительности вычислительных систем. М.: Радио и связь. 1983. - 350с.

8. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. — М.: Радио и связь. 1990. - 256с.

9. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. -М.: Наука, 2987.-600 с.

10. Боглаев Ю.П. Вычислительная математика и программирование. М.: Высшая школа, 1990. - 544с.

11. Боев В.Д. Моделирование систем. Инструментальные средства GPSS World: Учебное пособие. СПБ.: БХВ - Петербург, 2004. - 368с.

12. Бочаров H.B. Технологии и техника параллельного программирования // Программирование. 2003. - №1. - С. 5-23.

13. Бэбб Р. Программирование на параллельных вычислительных системах / Под ред. Р. Бэбба II. М.: Мир, 1991, - 376 с.

14. Вайвил Д., Цао Ен, Тротмен А. Поверхность Цао Ена: новый подход к геометрическим моделям произвольных форм // Программирование. 1992. №4. С. 4-16.

15. Васильков Ю.В. Компьютерные технологии вычислений в математическом моделировании: Учеб. пособие. /Ю.В. Васильков, H.H. Василькова. -М.: ФиС, 2001. 256 с.

16. Вирбицкайте И.Б. Семантические модели в теории параллелизма. -Новосибирск: ИСИ СО РАН, 2000. 196 с.

17. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. - 360 с.

18. Воеводин В.В. Математические модели и методы в параллельных процессах. -М.: Наука, 1986. 296 с.

19. Воеводин В.В. Параллельные вычисления / В.В. Воеводин , Вл. В. Воеводин . СПб.: БХВ-Петербург, 2004. - 608 с.

20. Волков Е.А. Численные методы М.: Наука, 1987.-412с.

21. Голованов H.H. Геометрическое моделирование. -М: Издательство Физико-математической литературы, 2002.-472с.

22. Горбатов, В.А. Фундаментальные основы дискретной математики. Информационная математика. Текст. // Учебник для втузов. — М.: Наука. Физматлит. 2000. — 544 с.

23. Гордеев A.B. Операционные системы; Питер Серия/Выпуск, 2004, Учебник для вузов ISBN: 5-94723-632-Х с. 416

24. Грин Д., Кнут Д. Математические методы анализа алгоритмов. — М.: Мир, 1987. 120 с.

25. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978. — 275 с.

26. Демидович Б.П., Марон И.А. Основы вычислительной математики. -М.: Наука, 1970. 664с.

27. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. Новосибирск: ВО «Наука», 1994. - 360 с.

28. Завьялов Ю.С. Методы сплайн функций / Ю.С. Завьялов, Б.И. Квасов, B.JI. Мирошниченко - М.: Наука, 1980. - 352 е.

29. Зельковиц М. Принципы разработки программного обеспечения. / М. Зельковиц, А. Шоу, Дж. Гэннон. М.: Мир, 1982. - 368 с.

30. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М.: Лаборатория Базовых Знаний, 2001. - 288 с.

31. Иванов В.П., Батраков A.C. Трехмерная компьютерная графика. —М.: Радио и связь, 1995. 224с.

32. Клейнрок JI. Вычислительные системы с очередями. М.: Мир. 1979. -600с.

33. Кнут Д. Искусство программирования для ЭВМ. Т. 1: Основные алгоритмы. М.: Издательский дом «Вильяме», 2000. - 720 е.

34. Кнут Д. Искусство программирования для ЭВМ. Т. 2: Структуры данных. — М.: Издательский дом «Вильяме», 2000. 832 е.

35. Кнут Д. Искусство программирования для ЭВМ. Т. 3: Поиск и сортировка. М.: Издательский дом «Вильяме», 2000. — 832 с.

36. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ Серия: "Классические учебники". М.: МЦНМО, 1999. - 960 с.

37. Корнеев В.В. Архитектуры с распределенной разделяемой памятью // Открытые системы. — 2003. №5. — С 15-23.

38. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж. — 1999.-320с.

39. Котов В.Е. Сети Петри. М.: Наука, 1984. 160с.

40. Котов В.Е. Элементы параллельного программирования. М.: Радио и связь, 1983.-192 с.

41. Крылов В.И., Бобков В.В., Монастырный П.И. Вычислительные методы. Т.1., Т.2 - М.: Наука, 1976. - 304с., 1977. - 400с.

42. Крылов, В.И. Вычислительные методы / В.И. Крылов , В.В.Бобков , •П.И. Монастырный Т.1./Г.2 - М.: Наука, 1976. - 304с., 1977. - 400с.

43. Лацис А. О. Как построить и использовать суперкомпьютер. М.: Бестселлер 2003. - 274 с.

44. Левин И.И., Омаров О.М. Расширение сетей Петри для моделирования распределенных вычислений // Информационные технологии моделирования и управления. Воронеж: Изд-во «Научная книга», 2005. - № 4(22). - С.555-562.

45. Левин И.И., Омаров О.М. Управляющие функциональные сети Петри для моделирования распределенных вычислительных сетей // Вестник Дагестанского научного центра РАН. Махачкала: Изд-во ДНЦ РАН, 2005. -Т.21. - С. 44-49.

46. Липский В. Комбинаторика для программистов. М.: Мир, 1988. -213 с.

47. Маклейн С. Категории для работающего математика / Пер. с англ.подред. В.А. Артамонова. -М.: ФИЗМАТЛИТ, 2004. 352с.

48. Мандельброт Б. Фрактальная геометрия природы. М.: Институт комп. иссл., 2002. - 656 с.

49. Миренков H.H. Параллельное программирование для мультимодульных компьютерных систем. — М.: Радио и связь. 1989. -320с.

50. Михайлова H.H. Вычислительная математика: Учеб. пособие. -Комсомольск-на-Амуре: Комсомольский-на-Амуре гос. техн. ун-т, 2002-105 с.

51. Михайлова H.H. Обработка экспериментальных данных на ЭВМ : Учеб. пособие. Комсомольск-на-Амуре: ГОУВПО «КнАГТУ», 2006 - 56с.

52. Морозов А.Д. Введение в теорию фракталов. Москва — Ижевск: Институт комп. иссл., 2002. — 160 с.

53. Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: Изд-во МАИ, 1992.

54. Нивергельт Ю. Машинный подход к решению математических задач / Ю. Нивергельт, Дж. Фаррар, Э. Рейнгольд. -М.: Мир, 1977. 352 с.

55. Новиков Ф.А. Дискретная математика для программистов. СПб: Питер, 2000. - 304 с.

56. Омаров О.М. Моделирование параллельных алгоритмов с использованием сетей Петри // Искусственный интеллект. Донецк: Наука i освгга, 2005. - Т 4. - С. 240-244.

57. Омаров О.М. Теория вычислительных процессов и структур. Учебное пособие. Махачкала: РИО ДГТУ, 2005. - 268 с.

58. Павлидис Т. Алгоритмы машинной графики и обработки изображений. -М.: Мир, 1986.-396с.

59. Петрова А.Н. Теория языков программирования и методы трансляции. 4 1- Теория: Учеб. пособие. Комсомольск-на-Амуре: ГОУВПО «КнАГТУ», 2004- 110с.

60. Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. М.: Мир, 1984.- 284с., ил.

61. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. -М.: Мир, 1989. 478 с.

62. Роджерс Д.Ф. Алгоритмические основы машинной графики: Пер. с англ. М.: Мир, 1989. 512с.

63. Роджерс Д.Ф., Адаме Дж. А. Математические основы машинной графики: Пер. с англ. М: Мир, 2001. 604с.

64. Самарский A.A. Введение в численные методы. М.: Наука,1987, -288с.

65. Стенли Р. Перечислительная комбинаторика. — М.: Мир, 1990. — 440 с.

66. Таненбаум Э., Вудхалл А.Операционные системы : разработка и реализация. Классика Computer Science: Перевод с англ. СПб : Питер, 2006 г. - 576 с.

67. Тихомиров Ю.В. Программирование трехмерной графики. СПб.: БХВ - Петербург, 2001. - 256с.

68. Топорков В.В. Модели распределенных вычислений. М.: ФИЗМАТЛИТ, 2004. 320с.

69. Топорков В.В. Реализуемость потоковых моделей распределенных программ // Программирование. — 2001. №18. — С. 18-25

70. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции / Э.А. Трахтенгерц . М.: Наука, 1981.-256 с.

71. Трещев И.А. Математическая модель гибридной временной волновой системы / И.А. Трещев // Системы управления и информационные технологии. 2007. - N4(30). - С. 19-21.

72. Трещёв И.А. Математическое моделирование волновых систем / И.А. Трещев // ХХХП Дальневосточная математическая школа-семинар имени академика Е.В. Золотова Владивосток: Изд-во Дальнаука. 2007. - С. 101102.

73. Трещев И.А. Построение многопоточных приложений для распараллеливания алгоритмов перебора / И.А. Трещев // Информатика и системы управления. — 2008. № 1 (15). - С. 151 -159.

74. Трещев И.А. Применение Асинхронных волновых систем типа «каскадный ливень» для моделирования параллельных вычислений на примере ряда алгоритмов машинной графики / И.А. Трещев // Вестник

75. Трещёв И. А. Программное обеспечение для перебора последовательностей на компьютерах с SMP архитектурой / И.А. Трещев // XXXI Дальневосточная школа-семинар имени академика Е.В. Золотова Владивосток: Дальнаука. 2006. - С. 183.

76. Трещёв И.А. Разработка асинхронных систем переходов для визуализации трехмерных объектов / И.А. Трещев // Труды третьей международной конференции "Параллельные вычисления и задачи управления" Москва, 24 октября.-2006.-С. 1417-1431.

77. Трещёв И.А. Свидетельство об официальной регистрации программы для ЭВМ №2006612000 Асинхронные волновые системы переходов для моделирования и визуализации трехмерных объектов 9.06.2006

78. Трещёв И.А. Свидетельство об официальной регистрации программы для ЭВМ №2007613267 Моделирование волновых систем при помощи сетей Петри 2.08.2007

79. Трещёв И.А. Свидетельство об официальной регистрации программы для ЭВМ №2006613475 Перебор последовательностей как раскраска вершин графа при обходе в ширину с использованием многопотоковых приложений на компьютерах с SMP архитектурой 6.10.2006

80. Трудоношина В.А., Пивоварова Н.В. Математические модели технических объектов Минск : Высшая школа, 1988 г. - 352с.

81. Фейт С. TCP/IP: Архитектура, протоколы и реализация 2-е Изд. "Лори" 2003. 448 стр.

82. Фокс, А. Вычислительная геометрия. Применение в проектировании и на производстве / А. Фокс А., М. Пратт М.: Мир, 1982. - 304 е.

83. Хаусдорф Ф. Теория множеств. Едиториал УРСС, 2004. - 304 с.

84. Хилл Ф. OpenGL. Программирование компьютерной графики. Для профессионалов. СПб.: Питер, 2002. 1088с.

85. Хоар Ч. Взаимодействующие последовательные процессы: Пер. с англ. — М.: Мир, 1989,-264 е., ил.

86. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений — М.: «Вильяме», 2002. — С. 528.

87. Хусаинов A.A. Структуры и алгоритмы обработки данных. Часть 1: Учеб. пособие/А.А. Хусаинов, H.H. Михайлова. -Комсомольск-на-Амуре: ГОУВПО «КнАГТУ», 2007. 86с.

88. Хусаинов А А., Михайлова H.H. Алгоритмы машинной графики и их реализация на языке Си: Учеб. пособие. Комсомольск-на-Амуре: Комсомольский-на-Амуре гос. техн. ун-т., 1999. - 65 с.

89. Хусаинов A.A., Михайлова H.H. Интерактивные графические системы. Теория: Учеб. пособие. Комсомольск-на-Амуре: ГОУВПО «КнАГТУ», 2007 - 132с.

90. Хусаинов A.A., Михайлова H.H. Интерактивные графические системы. Практика Учеб. пособие. Комсомольск-на-Амуре: ГОУВПО «КнАГТУ», 2007 - 52с.

91. Шамис В. Borland С++ Builder 6. Для профессионалов. СПб.: Питер, 2004.-798 с.

92. Шикин Е.В. Плис Л.И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. —М.: «ДИАЛОГ-МИФИ», 1996. 240с.

93. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. М.: «ДИАЛОГ-МИФИ», 1995. - 288 с.

94. Шикин Е.В., Боресков А.В. Компьютерная графика. Полигональные модели. М.: «ДИАЛОГ-МИФИ», 2000. - 464 с.

95. Шилдт Г. Программирование на С и С++ для Windows 95/ Г. Шилдт .Киев: Торг. изд. бюро BHV, 1996. - 400 с.

96. Яблонский С.В. Введение в дискретную математику. — М.: Высшая школа, 2001. — 312с.

97. Alur R., Dill D. The theory of timed automata // Lect. Notes Comput. Sci. — 1991.—Vol. 600. —P. 45-73.

98. Andreeva M. V., Bozhenkova E. N., Virbitskaite I. B. Analysis of Timed Concurrent Models Based on Testing Equivalence // Fundamenta Informaticae. — 2000. — Vol. 34. — P. 1-19.

99. Bednarczyk M.A., Categories of asynchronous systems, PhD thesis in Computer Science, University of Sussex, rep ort no. 1/88,1988.

100. Dongarra J. Foster Y. Sourcebook of parallel computing Elsevier Science ISBN: 1-55860-871-0 2003 852p

101. Glabbeek R., Goltz U. Equivalence Notions for Concurrent Systems and Refinement of Actions// Lect. Notes Comput. Sci. — 1989.— Vol. 379.— p.23 7-248.

102. Goubault, E. and Jensen T.P. A homology of higher dimensional automata, in leaveland, W.R. (ed.), Concur 92, Springer LNCS 630. 1992. - pp. 254-268

103. Hoare С., Communicating sequential processes, Comm. ACM, 21 (1978), pp. 666-677.

104. Husainov A.A. The study of distributed computing algorithms by multithread applications. // Preprint Department of Computer Technologies Komsomolsk-on-Amur State technical University, 2004. 17p. http://arxiv.Org/abs//cs.DC/0404015

105. Jensen, K. Colored Petri Nets: Basic Concepts, Analysis Methods and Practical Use. Текст. Berlin: Springier. - Vol.1 - 1996, Vol.2 - 1997, Vol.3 -1997.

106. Keller R., Formal verification of parallel programs, Comm. ACM, 19 (1976), pp. 371-384.

107. Luca A. Kim G. An Introduction to Milner's CCS // Preprint BRICS, Department of Computer Science Aalborg University, 2005. 97p. http://www.cs.auc.dk/luca/SV/intro2ccs.pdf.

108. Milner R. A Calculus of Communicating Systems// Lect. Notes Comput. Sei. —1980.—Vol. 92.

109. Nielsen M., Winskel G. Models for concurrency // Preprint DAIMI PB-429, Department of Computer Science University of Aarhus, 1993. 187 p.

110. Nielsen M., Winskel G. Petri Nets and Bisimulations. // Preprint BRICS RS-95-4, Department of Computer Science University of Aarhus, 1995. 36 P

111. Niemann T. Sorting and Searching Algorithms: A Cookbook. — Preprint, 1999. 36 p. - http://members.xoom.com/thomasn/sman.htm

112. Parhami B. Introduction to parallel processing. Algorithms and architectures. Kluwer, 2002. -557 c.

113. Petri C. A., Non-sequential processes, GMD-ISF Report ISF-77-05, 1977.

114. Ranadae A. Optimal speedup for backtrack search on butterfly network. Mathematical Systems Theory, 1994. pages 85-101.

115. Rao V.N., Kumar V. On the efficiency of parallel backtracking. IEEE Transactions on Parallel and Distributed Systems, 4(4): 427-437, April

116. Sarfraz M. Advances in Geometric Modeling. John Wiley &. Sons, Ltd, 2003 -320p.

117. Schneider S., Davies J., Jackson D.M., Reed G.M., Reed J.M., Roscoe A.W. Timed CSP: theory and practice // Lect. Notes Comput. Sci. — 1991. — Vol. 600. — P. 640-675.

118. Skyum S. Introduction to Parallel Algorithms. Preprint BRICS LS-95-2, Department of Computer Science University of Aarhus, 1995. - 17 pp.;

119. Winskel, G., Events in Computation. PhD thesis, University of Edinburgh, available as a Camp. Sc. report, 1980.

120. Winskel, G., Synchronization trees, Theoretical Computer Science, 34, pp. 33-82,1985.1994.