Математические модели параллельных вычислительных процессов и их применение для построения многопоточных приложений на системах с SMP-архитектурой тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Трещев, Иван Андреевич

• Трещев, Иван Андреевич
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Трещев, Иван Андреевич

Введение

ГЛАВА 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 Фрактальная геометрия, метод адаптивного динамического распараллеливания, распараллеливание на основе волновых систем

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

Введение диссертации (часть автореферата) на тему «Математические модели параллельных вычислительных процессов и их применение для построения многопоточных приложений на системах с SMP-архитектурой»

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

Теория математического моделирования вычислительных процессов восходит к построению математических моделей, разработанных с целью формализации понятия алгоритма [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. Построены волновые системы для некоторых алгоритмов вычислительной математики и компьютерной графики.

Список литературы диссертационного исследования кандидат технических наук Трещев, Иван Андреевич, 2008 год

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.