Введение к работе
Актуальность темы.
Современный этап развития вычислительной техники характеризуется созданием и использованием высокопроизводительных параллельных вычислительных систем. Разработкапрограммногообеспс-чения для параллельных вычислительных систем требует решения ряда проблем, связанных с нетрадиционными методами организации вычислений. Проблемы возникают при разработке прикладных программ, хотя также возможно их общее решение на уровне операционной системы и компилятора. Поэтому очень актуальным направлением развития в данной области является создание парал-лельных алгоритмов для решения новых трудоемких задач в разных областях применения компьютеров. _
Одна из таких областей - геометрическое моделирование тел. Оно играет ключевую роль в системах автоматизированного проектирования (САПР), машинной графике, роботостроении и в других областях и видах деятельности, связанной с пространственными изображениями. Любая система геометрического моделирования тел предоставляет возможности создания, визз'плизации и модификации тел. В частности, все современные системы поддерживают конструктивные операции над телами, т.е. операции объединения, пересечения, дополнения и т.п..
В любой системе геометрического моделирования тел, по сути, две задачи, от скорости решения которых сушсственно зависит функционирование системы, это:
-
визуализация объектов; , -
-
конструктивные операции.
В диссертации предлагается конкретный подход к решению второй из них на многопроцессорных вычислительных системах транспьютерного типа.
Дель работы.
Представленная работа является исследованием в области геометрического моделирования тел. Ее целью является:
1. Изучение возможностей разработки параллельных алгоритмов выполнения конструктивных операций над многогранными телами, предназначенных для многопроцессорных вычислительных систем транспьютерного типа.
-
Программная реализация одного из возможных параллельных алгоритмов на транспьютерной сети.
-
Получение математической и экспериментальной оценки эффективности алгоритма.
Научная новизна.
Научная новизна работы заключается в том, что:
-
Разработан параллельный алгоритм выполнения конструктивных операций над многогранными телами, предназначенный для многопроцессорных вычислительных систем транспьютерного типа.
-
Разработана инструментальная среда, предназначенная для написания и отладки программ на Параллельном C(3L), работающих с геометрическими структурами, на транспьютерной сети. С ее помощью осуществлена программная реализация алгоритма на транспьютерной сети кольцевой и древовидной конфигураций.
-
Получено экспериментальное сравнение эффективности алгоритма на разных типах входных данных.
-
Построены две вероятностных модели алгоритма для разных случаев входных данных, на их основе получены математические оценки эффективности алгоритма, а также перспективная характеристика сложности полиэдрального тела. -
Практическая значимость.
Проведенные исследования позволили сделать ряд практических рекомендаций ло разработке и созданию параллельных алгоритмов для регдения некоторых задач геометрического моделирования с использованием граничного представления тел, предназначенных для многопроцессорных вычислительных систем транспьютерного типа.
Программные реализации базовых процедур, таких как разделение поверхности многогранного тела на примерно равные связные части, "система диагностических сообщений" для отладки программ на C3L на транспьютерной сети, функции для передачи геометрических структур между разными параллельно выполняющимися процессами и т.п., представляют самостолтельяыг '*нтсрес.
Полученные результаты могут быть использованы при создании системы геометрического моделирования тел для работы на многопроцессорной'вычислительной системе транспьютер .ic-i'o паи в МГУ, НИИСИ РАН, НПЦ "Сапсан", ИПМ РАН, ИСП 1'АН.
Реализация результатов исследований.
Разработанный автором параллельный алгоритм для выполнения конструктивных операций над многогранными телами реализован в виде файлов макроопределений и программ на языке C(3L) общим объемом около 600 Кбайт.,
, Апробация работы.
Основные результаты диссертации докладывались и обсуждались на на Г/ конференции Российской Транспьютерной Ассоциации "Транспьютерные системы и их применение", 1994г., на II международной конференции "Software for multiprocessors and supercomputers: Theory, practice, experience", 1994 г., на научных семинарах в Научно-исследовательском институте Системных Исследований РАН, в Институте Программных Систем РАН и на научно-исследовательском семинаре по автоматизации программирования под руководством проф. М.Шура-Бура на факультете ВМК МГУ.
ПуТі лик адии .-
По результатам диссертации опубликованы 3 печатных работы.
Структура и объем работы.
Диссертация состоит из введения, пяти глав, заключения и списка литературы (69 наименований). Работа содержит 148 страшщ, 37 рисунков и 14 таблиц.
