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

Московский Государсгвеппьш Университет им. М.В.Ломопосова Факультет вычислительной математики и кибернетики

РГБ ОД

- В О ИТ 1395

ЧЯПАЙТЕ Юрате

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ДЛЯ

КОНСТРУКТИВНЫХ ОПЕРАЦИЙ НАД МНОГОГРАННЫМИ ТЕЛАМИ

05.13.13 - математическое и программное оГюспечеяие . вычислительных машин, комплексов, сетей и систем

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

На правах рукописи УДК 681.3:519.8

Москва 1995

Работа выполнена ва кафедре общих проблем упргллмпш механико-математического факультета Московского Государствея-ного Университета ии. М.В.Ломоносова -

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

кандидат физико-математических наук, доцент Кушниренко Анатолий Георгиевич

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

доктор технических наук, профессор Дадаев Юрий Георгиевич

кандидат физико-математических наук, профессор Шмелев Георгий Сергеевич

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

Научный совет по комплексной-проблеме "Кибернетика" РАН

Запита состоится ^ О^Г^РХ 1995 года ъ-// на заседании Специализированного Совета Д.053.05.38 по математике по адресу: 119899, Москва, Воробьевы горы, МГУ, факультет вычислительной математики и кибернетики, аудитория

оо

часов

С диссертааией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат разослан " " 1995 года.

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

у г

Спепиализированного Совета

профессор Н.П.Трифонов

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

Актуальность темы.

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

Одна из таких областей - геометрическое моделирование тел. Оно играет ключевую роль в системах автоматизированного проектирования (САПР), машинной графике, роботостроении и в других областях и видах деятельности, связанной с пространственными изображениям-!. Любая система геометрического моделирования тел предоставляет возможности создания, визуализации и модификации тел. В частности, все современные системы поддерживают конструктивные операции над телами, т.е. операции объединения, пересечения, дополнения и т.п..

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

1) визуализация объектов; , -

2) конструктивные операции.

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

Цель работы.

Представленная работа является исследованием в области геометрического моделирования тел. Ее целью является:

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

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

3. Получение математической и экспериментальной опенки эффективности алгоритма.

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

Научная новизна работы заключается в том, что;

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

2. Разработана инструментальная среда, предназначенная для написания и отладки программ на Параллельном С(ЗЬ), работающих с геометрическими структурами, на транспьютерной сети. С ее помощью осуществлена программная реализация алгоритма на транспьютерной сети кольцевой и древовидной конфигураций.

3. Получено экспериментальное сравнение эффективности алгоритма на разных типах входных данных.

4. Построены две вероятностных модели алгоритма для разных случаев входных данных, на их основе получены математические оценки эффективности алгоритма, а также перспективная характеристика сложности полиэдрального тела. - ■ -

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

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

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

Полученные результаты могут быть использованы при создают системы геометрического моделирования тел для работы на многопроцессорной вычислительной системе транспьютера о паи. в МГУ, НИИСИ РАН, НПЦ "Сапсан", ИПМ РАН, ИСП ГАН

Реализацил результатов исследований.

Разработанный автором параллельный алгоритм для выполнения конструктивных операций над многогранными телами реализован в виде файлов макроопределений и программ на языке C(3L) общим объемом около 600 Кбайт.

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

Основные результаты диссертации докладывались и обсуждались на на IV конференции Российской Транспьютерной Ассоциации "Транспьютерные системы и их применение", 1994г., на II международной конференции "Software for multiprocessors and supercomputers: Theory, practice, experience", 1994 г., на научных семинарах в Научно-исследовательском институте Системных Исследований РАН, в Институте Программных Систем РАН и на научно-исследовательском семинаре по автоматизации программирования под руководством проф. М.Шура-Бура на факультете ВМК МГУ.

Публикации.

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

Структура и объем работы.

Диссертация состоит из введения, пяти глав, заключения и списка литературы (69 наименований). Работа содержит 148 страниц, 37 рисунков и 14 таблиц.

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

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

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

Базовый алгоритм предложен В.И.Вьюковым (НИИСИ РАН). Его строгое обоснование осуществлено автором диссертации.

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

каждьм полигоном связано направление внешней нормали к телу: {р°1л}, {ро*в}.

Надо найти граничное представление для тела S, где S — А о В\ о - регуляризованная конструктивная операция.

Базовый алгоритм состоит из трех этапов.

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

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

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

Второй этап алгоритма - подразбиение на части полигонов каждого из тел А, В, пересекшихся с другим телом (соответственно В или А). Каждый полигон, для которого найдены какие-либо отрезки пересечения, должен быть подразбит ка части так, чтобы все вычисленные отрезки пересечения стали ребрами новых полигонов. Полученные после этой процедуры полигоны не будут пересекаться с полигонами другого тела (т.е. не будут иметь общих внутренних точек, а только общие вершины и ребра), и каждый из них будет находиться в однозначно определенном положении по отношению к другому телу. Полигон будет занимать одно из следующих положений: "вне тела", "внутри тела", "награнице тела, с одинаковой ориентацией", "награнице тела, с противоположной ориентацией". Полученные в результате подразбиения полигоны будут в общем случае невыпуклыми.

Третий этап алгоритма - разметка всех полигонов обоих тел по их положению относительно другого тела (polл относительно тела В и рЫв относительно тела А) и сборка-резуса гата соответствующей конструктивной операции по известным Формулам. Пси сборке некоторые полигоны надо, возможно, иызертироват!, а г лигоны, полученные в результате подразбиения на втором этапе невыпуклые, - разбить на выпуклые.

Предположим, что полиэдральные тела А, В являются прибли-

жениями каких-то реальных тел 5', 5", полученными следующим образом: на поверхности тела выбрано множество точек {V, } и через эти точки проведена полигональная поверхность, так, чтобы все точки стали вершинами полигонов.

Пусть у нас есть два приближения - полиэдральные тела АI, Л2. Они получены на основании множеств точек V1 = V/, V2 = V2. Будем говорить, что приближение является уточнением приближения А\ , если V1 С V2. Определим масштаб уточнения приближения Л.2 по отношению к А1 ц:

\

где означает количество полигонов в представлении тела

А;, ¿ = 1,2.

Проведена оценка времени работы алгоритма и изменения этого времени в случае, когда вместо приближений А я В используются уточнененные приближения А\ В', с масштабом уточнения /¿. Количество полигонов в телах увеличится в ц раз.

Получены следующие результаты для изменения времени выполнения алгоритма:

.. на первом этапе с .ростам числа полигонов вклад пррверок в общее время выполнения растет с коэффициентом /г2 , а непосредственно проведение вычислений отрезка пересечения - с коэффициентом Л//Г, и хотя одна проверка занимает во много раз меньше времени, чем вычисление отрезка, с ростом объема данных проверки будут занимать время, сравнимое (а потом и превосходящее) время вычислений;

на втором этапе, время выполнения растет с коэффициентом на третьем этапе - с коэффициентом ц.

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

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

Первые два этапа базового алгоритма выполняются параллельно по схеме:

Разделение данных

Рассылка данных по сети Счет —>

—► Сборка результатов и восстановление единства структуры данных, в которой отражена смежность полигонов

Третий этап выполняется последовательно, в силу того, что он непродолжительный и здесь алгоритм существенно использует отношение смежности граней.

Эффективность параллельного алгоритма сильно зависит от способа разделения данных. От него зависит равномерность нагрузки транспьютеров на этапе выполнения вычислений ("Счет"), а также удачное разделение данных может сильно сократить затраты времени на последнем этапе при объединении результатов вычислений.

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

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

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

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

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

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

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

Используются три принятых способа оценки эффективности. Обозначим

¿сч - "чистое" время счета при реализации параллельного алгоритма;

¿об ~ время обмена данными между процессами; . <пр - время простоев, причем

1 ' 1 ' 1 ' ¿сч = у гоб = У 'пр = уХ

1=1 1=1 ¡=1

где ¿'б, ¿'1р - время "чистого'' счета, обменов и простоя ¿-ого процессора системы, а процессоров всего I.

В этих обозначениях эффективность параллельного алгоритма можно оценивать величиной

^_ _ ¿сч_

(*сч + *об + *пр) :

а также

5 — (^об + *пр) ~ + '

*-сч

' т,

а=гг~' •

>

где - время счета задачи на одном процессоре системы.

Первая модель. Пусть - случайная величина с функцией распределения причем пусть

г

¿=г

где Лг/ - число полигонов тела А, N8 - число полигонов тела В.

Соотношение 9 = N л! N я будем считать постоянным, ввиду того, что рассматриваемые нами тела А, В - полигональные приближения некоторых реальных тел и допускать только случаи уточнения приближений А, В с одинаковым масштабом утрчнения.

Вышеприведенные допущения отражают тот факт, что фиксированное число полигонов тела Л делится между процессорами: £¡=1°' = -^А, и каждый процессор должен обработать все пары полигонов (ро1л,ро1в) Для тех полигонов тела А, которые он получил, и всех полигонов тела В, поэтому время счета 4СЧ пропорционально количеству таких пар Функция Р является функцией распределения некоторой случайной величины зависящей от геометрии тел и их расположения относительно друг друга и относительно используемой ортогональной системы координат и может быть определена серией измерений. Пусть "

а структуры тела достаточно сложна, чтобы считать г = 1,... , I независимыми, тогда

ШЪ, = а^вМ и 1>г'ч =

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

=_~~М_.

+ А\/Ъ) + (? * /Ув + * (°б + (Лгв + А^л/О * ■

^ ^ + {Шв + ^ + ^ Нлщ „ ^ ^

1

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

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

Как и выше, считаем Тсч случайной величиной с функцией распределения но полагаем

Г (

«=1 ¿=1

где ИА - число полигонов тела Л, Ид - число полигонов тела В. При равномерном распределении данных С (г) ~

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

М = Ь = тогда

Оценки эффективности лля данной модели на этапе подразбиения полигонов:

1 =

2*(уШ*Ро6 + ^ * +4 * \jZf-D М

8 = 2

М

На этапе вычисления отрезков пересечения полигонов, с учетом только времени на вычисление самих отрезков: •

М

7= ~

5 =

' М

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

Как контрольный вариант рассмотрим следующий геометрический алгоритм разбиения. Пусть Б (¿1, ¿2, ёз) - некоторая ортогональная система координат, С - бокситгг тела (минимальный параллелепипед с ребрами, параллельными координатным осям и вмещающий тело). Разбиваем боксинг С на I равных слоев, параллельных

плоскости (ёьег). Через тц, для 1 < г < I, обозначим количество полигонов, входящих в слой с номером г (или частично входящих и некоторым образом отнесенных к этому слою). Пусть к - случайная величина, с равной вероятностью принимающая значения из ;.птожества {1,... ,/}. Пусть система координат Е также является случайным событием. Нас будет интересовать поведение случайной величины V = цк (Е), то есть количество полигонов в случайном слое при случайном выборе системы координат (ступенчатая функция).

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

Критерий 4.3.1 (о применимости топологического алгоритма разбиения поверхности). Топологический алгоритм разбиения лучше геометрического тогда, и только тогда, когда характеристика тела Пу удовлетворяет неравенству

а?92

где в = N/±[N¡3, постоянное для разных приближений, а характеризует затраты топологического алгорит-ма разбив-нгиг ^¿разб = а^А ),

'а К = 2 (2М + *Ц = Л'(М,/,^,релячи/А"в) - за-

'висит от тела А (от М), количества транспьютеров в сети I и скорости передачи структур данных, деленной на N¡3:

Мы определили понятие "сложности тела", позволяющее установить, что для полиэдрального тела предпочтителен топологический алгоритм разбиения, а также, возможно, имеющее и другие применения. Характеристикой сложности тела служит Юи (см. выше). При выборе распределения вероятностей систем координат логично заложить "равновероятность" вест возможных систем. При введении вероятностной меры используется мера Хаара

на SO3. Считая вероятность того, что случайная система координат Е G G С 50з, равной di(G), получим характеристику сложности полиэдрального тела:

. , ¿(^(E)-Af,)2 H{A) = Dv = / 1=1 l-d,(E), Mv = ~y-

sof

При таком подходе сложность полиэдрального тела H {А) не зависит от выбора исходной системы координат, по причине левоиввариантности используемой меры.

В случае приближения реального тела полиэдральным по некоторому правилу, получено выражение для Н{А).

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

В работе использовалась транспьютерная плата VMTM фирмы Parsy teç GmbH, инсталлированная на рабочей станции БЕСТА-88 и содержащая 4 транспьютера T80D-20, каждый с 1 Мбайт орератив-ной памяти. Доступное физическое обеспечение позволило провести оценку времени работы параллельного алгоритма для транспью-. . терной сети из двух, трех и четырех транспьютеров, и для ограниченных объемов данных, примерно до 600 полигонов на каждое тело.

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

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

1) при увеличении числа обрабатываемых пар полигонов N л * Nr ;

2) при увеличении числа транспьютеров, а также

.3) большую зависимость показателей эффективности алгоритма от .,

входных данных.

На достаточно больших, около 600 полигонов на каждое тело, объемах данных, и на 4-х транспьютерах, достигается ускорение до

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

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

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

2. Разработана инструментальная среда, предназначенная для шисания и отладки программ на Параллельном C(3L), рабоця-ших с геометрическими структурами, на транспьютерной сети. С : помощью осуществлена программнал реализация алгоритма на эанспьютерной сети кольцевой и древовидной конфигураций.

3. Получено экспериментальное сравнение эффективности алго--ггма на разных типах входных данных.

4. Построены две вероятностных модели алгоритма для разных [учаев входных данных, на их основе получены математические генки эффективности алгоритма. ■

Автор выражает "глубокую благодарность Кушнирснко Анато-«о Георгиевичу и Грюнталю Андрею Игоревичу за ценные сове-1, помощь и поддержку.

ПИСОК ПУБЛИКАЦИЙ НА ТЕМУ ДИССЕРТАЦИИ

1. Чяпайте Ю.Р., Алгоритм разделения множества граней по-рхности многогранного тела на примерно разные связные части, Ж, препринт, 1994, стр. 1-31.

2. J.Chepaite, Transputer Network Implementation of Boolean Op-ations on Polyhedral Objects, in Proceedings of the Second Interzonal conference "Software for multiprocessors and supercomputer Theory, practice, experience", Moscow, September 19-23, 1994,

3. 189-197.

3. Чяпайте Ю.Р., Методы разделения геометрических данных: еимущества топологического подхода. МГУ. Москва, 1995,11 стр. ш. в ВИНИТИ 13.01.1995г. No 112:В95.