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

п

и 1

1 3 Г * Г''¿7 На правах рукописи

Тимофеев Александр Викторович

РАЗРАБОТКА И ПОВЫШЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ ПАРАЛЛЕЛЬНОЙ СИСТЕМЫ ВИЗУАЛИЗАЦИИ ТРЕХМЕРНЫХ СЦЕН

Специальность: 05.13.13 • Вычислительные машины, системы,

комплексы и сети

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

Санкт-Петербург -1997

Работа выполнена е Санкт-Петербургском Гссударственном Электротехническом Университета имени В.И. Ульянова (Ленина).

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

кандидат технических наук, профессор Шмидт В. К.

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

доктор технических наук, профессор Новиков Г.И.

кандидат технических наук, доцэнт Кирьянчиков В.А.

Ведущая организация - ВНЦ ГОИ им. С.И. Вавилова.

Защита состоится 1997 г. в /У- часов на

заседании диссертационного совета К 063.36.12 Санкт-Петербургского Государственного Электротехнического Университета имени В.И. Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5,

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан к/"/ »

Ученый ее*Ср-зт«рь диссертационного совета

Маркин А.С

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

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

Одной из наиболее динамичных отраслей информатики, ставшей необходимым инструментом в работе ученых и инженеров, является машинная графика. Методы растровой графики позволяют создавать цветные изображения высокого качества. Однако для решения задачи визуализации сложных трехмерных сцен, содержащих десятки и сотни тысяч графических примитивов, требуются огромные вычислительные затраты. В настоящее время существует достаточное количество высокопроизводительных графических станций и суперкомпьютеров фирм SGI, HP, Sun. Эти системы характеризуются следующим образом: использование конвейерной и параллельной обработки; очень широкий спектр областей применения; ориентация на сверхвысокий уровень качества изображений; наличие развитых, Стандартных средств разработки программного обеспечения (ПО) (OpenGL, РЕХ); очень высокая стоимость аппаратных средств. Таким образом, графические станции ориентированы на решение задачи визуализации вообще и нэ учитывают конкретные требования в узких областях применения. Поэтому для некоторых узких областей применения Зй-графики, например, в тренажеростроение, имеет смысл отказаться от применения дорогостоящих графических систем широкого назначения и сделать выбор в пользу разработки параллельных систем визуализации с заданными характеристиками.

В последние 2-3 года на рынке вычислительной техники появилось около полутора десятков «деи><?вых» процессоров трехмерной графики, которые ориентированы на применение в персональных компьютерах и рабочих станциях средней производительности. Некоторые из 3D-npoqecccpoa сочетают умеренную стоимость с достаточно высокой производительностью и качественной графикой, например, процессоры 3Dfx фирмы Voodoo Graphics и Permedia фирмн 3Dlabs Эти процессоры обеспечивают на тесто 3Dtex-Triangles (вывод текстурированных треугольников площадью 50 пикселей) производительность 700-1000 тысяч треуг./с. Графические суперкомпьютеры последней серии Опух2 фирмы SGI на этом тесте показывают производительность 5.5-80 млн. треуг,/с. Кроме того, для 30-процессороа производители предлагают свои собственные средства разработки ПО (Voodoo Graphics - Glide, 3D¡abs - CGL). Таким образом, no сравнению с коммерческими графическими суперкомпьютерами 30-процессоры имеют: меньшую производительность (в 5-100 раз); меньшую точность (упрощенные модели освещения, меньшая разрядность данных); нестандартные средства разра-

ботки ПО, возможность реализации оригинальных идей по повышению производительности; существенно более низкую стоимость (до 1000 раз),

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

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

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

-- разработка, рёализация и анализ параллельной системы. визуализации на базе многопроцессорной станции обработки изображений Т1Р-Бе1;

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

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

Научная новизна исследования заключается в следующем:

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

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

Практическими результатами являются:

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

2. Разработана параллельная ВС визуализации на базе многопроцессорной станции "ПР-Бе^ использующая параллельную обработку в пространстве изображения.

3. Реализован и экспериментально исследован ряд методов распределения потоков данных в системе визуализации на базе станции ИР-Бе!. Предложены рекомендации по их использованию.

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

Основные положения диссертационной работы представлялись и обсуждались на 5-ой и 6-ой Международных Конференциях ГРАФИКОМ (С.Петербург, 1995, 1996), 2-ой Международной конференции по применению компьютерных систем (Щецин, Польша, 1995), 10-ом Международном симпозиуме по вопросам высокопроизводительных компьютерных систем НРСБ (Оттава, Канада, 1996), а также на отчетных семинарах Центра Транспьютерных Технологий СПбГЭТ/(С.-Петербург, 1995 - 1997).

Публикации

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

Структура работы

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

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

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

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

Представителом ВС данного класса является многопроцессорная станция обработки изображений ИР-Бе! фирмы Раг8у1сс, которая была выбрана для реализации прототипного варианта параллельной системы визуализации.

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

Второй раздел диссертации посвящен исследованию параллельной обработки □ задаче визуализации на примере реализации параллельной системы визуализации на базе многопроцессорной станции "ПР-Бе!.

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

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

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

Для решения этой проблемы в диссертации предложен "параллельный бинарный алгоритм слияния. Процесс слияния состоит из N параллельных подпроцессов слияния, каждый процессор обменивается информацией лишь с ] (од-Г^ Г процессоров. Идеальной архитектурой ВС для бинарного ал-

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

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

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

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

Далее был разработан алгоритм визуализации для использования в разрабатываемой системе визуализации. Этот алгоритм основан на удалении невидимых поверхностей с помощью буфера глубин. Достоинством алгоритма является то, что его производительность с ростом сложности сцены остается приблизительно постоянной. Исходными данными для алгоритма визуализации являются: описание рельефа в виде совокупности плоских пространственных треугольников; описание объектов (деревья, дома, подвижные объекты); параметры наблюдения сцены.

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

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

Для сравнения альтернативных вариантов параллельной системы ви: зуализацим был выбран коэффициент ускорения представляющий собой отношение времени решения задачи на однопроцессорной ВС ко времени решения зтой задачи и-з N-процессорной системе - Ку = Ti/Tn-

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

Ку s N((a + 1 )/(а + N)), где N - число параллельных вычислительных модулей; а - коэффициент равный отношению трудоемкости стадии растрирования и тонирования/РТ) Трт(1) к трудоемкости стадии геометрических преобразований (ГП) Тгп(1);

Tm(N) - время выполнения стадии ГП на N вычислительных модулях; Tpr(N) - время выполнения стадии РТ на N вычислительных модулях. В случае параллельной обработки в пространстве сцены коэффициент ускорения равен

Ку s Nb(N) / (b(N) + N), где TOT (N) - трудоемкость слияния N изображений объектов; b(N) - коэффициент равный отношению трудоемкости алгоритма визуализации (Трп(1) + Трг(1)) к трудоемкости слияния То, (N).

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

ТеяМ < tcn(M), где ^ (М) - время, затрачиваемое на слияние двух массивов из М пикселей на основе информации буфера глубин; Поэтому будем считать, что b(N) = tc„(M) = const.

Расчеты дали следующие значения коэффициентов а и b (при М = 800*600 = 480000 пикселей):

- для TIP-VPU - а = 7,6 и b = 0,8;

- для TIP-MPC - а = 4,8 и b = 1,1.

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

ложности, или посла решении проблемы быстрого слияния изображений бъектов.

В ходе диссертационной работы на базе многопроцессорной станции бработки изображений TiP-Set была реализована параллельная система изуализации трехмерных сцен. Система визуализации выполняет задачу интеза последовательности изображений трехмерных сцен, имитирующей ,вижение наблюдателя по рельефу местности с шестью степенями свободы три линейные и три угловые). В основу системы визуализации было поло-сена параллельная обработка в пространстве изображения. Автором было азработано два варианта реализации ВС визуализации на базе станции 'IP-Set (с различным типом вычислительных модулей). В распоряжении ав~ ора находилось три модуля T1P-VPU (транспьютер Т805-30МГц) и два модуля TIP-MPC (RISC-процессор PowerPC 601-66МГц). Варианты совместно-о использования вычислительных модулей TIP-VPU и TIP-MPC не рассмат-мвались из-за значительного различия в их производительности.

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

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

2. Стадии растрирования и тонирования алгоритма визуализации (па-яллельный этап). На этом этапе выполнялся параллельная отрисовка отельных частей изображения сцены.

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

Статистические измерения проводились с помощью высокочастотного ппаратного таймера с периодом 1 мкс. Все варианты тестировались на од-1их и тех же последовательностях наборов исходных данных.

После анализа полученных статистических данных был сделан ряд вы-юдов:

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

TN=k(T1/N), где кмрс = 1,02 и кдаи = 1,06+1,12.

2. Время, затрачиваемое на выполнение стадии геометрических пре-(бразований, с увеличением числа модулей почти не изменяется.

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

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

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

В результате проведенных испытаний параллельной системы визуализации была подтверждена необходимость равномерной загрузки вычислительных модулей. Данные для системы визуализации с числом процессоров 2-3 были получены непосредственно в результате экспериментов. Данные для системы с большим числом процессоров (до 16) были получены в результате моделирования многопроцессорной системы на однопроцессорной. Достоверность результатов моделирования подтверждается как аналитически, так и экспериментально (для двух- и трехпроцеосорных ВС). Для решения проблемы простоев было решено использовать распределение рабочей нагрузки в виде потоков данных.

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

1. тип распределяемого потока данных в ВС;

2. стадия решения задачи, на которой производится распределение.

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

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

1. синхронные:

- замкнутые методы (методы на основе обратной связи);

- разомкнутые методы (методы без обратной связи);

2. асинхронные:

- методы распределения по запросу.

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

Достоинства замкнутых динамических методов:

1. нет необходимости в апририорных знаниях о закономерностях изменения значений параметров потоков данных;

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

Недостаток - со снижением межитерационной зависимости эффективность замкнутых методов падает.

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

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

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

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

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

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

Статическое распределение потоков данных в пространстве изображения

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

1. Для большинства спроецированных полигонов длина их строк (или столбцов) развертки на этапе растрирования плавно изменяется.

2. Существованием однородности строк (столбцов) развертки по наблюдаемости. Это свойство предполагает, что сегменты, которые видны в одной строке (столбце), вероятно, также видны и в следующей строке (столбце) развертки.

В работе предложен метод статического распределения потоков данных в пространстве изображения, названный "чересстрочным". Это* метод последовательно распределяет строки изображения среди вычислительных модулей ВС. Основное достоинство метода - простота. К недостаткам можно отнести необходимость изменения алгоритма растрирования. Недостатком является также то, что свойство внутрикадровой зависимости будет с разной эффективностью выполняться для различных типов трехмерных сцен.

Разомкнутый метод "Циклического чередования"

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

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

Замкнутые следящие методы распределения потоков данных в пространстве изображения

Замкнутые следящие методы основаны на межкадровой зависимости значений параметров потоков данных. В рамках диссертации рассматриваются 2 класса следящих методов:

1. Следящие методы с экстраполяцией. Эти методы прогнозирую параметры потоков данных на следующей итерации исходя из динамики процесса.

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

В работе приведены оценки вычислительной сложности рассмотренных методов распределения потоков данных.

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

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

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

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

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

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

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

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

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

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

Правило алгоритмической эквивалентности: Две объектно-функциональные схемы организации вычислений ОФС1 и ОФС2 называются эквивалентными относительно алфавита I, если они имеют одну и ту же область определения и результаты их действий при поступлении одинаковых значений входных слов 'X совпадают.

ОФС задачи удобно отображать в виде интерпретации иерархической помеченной сети Петри, в которой: 1 Переходы.

- Переходы соответствуют методам объектов.

- Составные переходы соответствуют сложным методам, а простые переходы - элементарным методам.

- Каждому переходу поставлена в соответствие временная функция срабатывания

- Каждому перэходу (методу) ставится в соответствие набор правил декомпозиции по всем входным и выходным дугам (потокам данных).

2. Позиции. Позиции соответствуют элементам данных объектов.

3. Дуги.

- Дуги соответствуют потокам дачных между объектами.

- Кратность или вес дуги обозначает ширину потока данных.

- В общем случае вес дуги может быть переменным.

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

Для всех методов ОФС задачи визуализации предложены две пары правил декомпозиции по данным:

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

2. Правила декомпозиции в пространстве изображения. ПерЕое правило (П2.1) относится к методам, для которых входными и выходными данными являются' элементы изображения. Второе правило (П2.2) относится к методам, для которых входными данными являются элементы сцены, а выходными - элементы изображения. При использовании правил декомпозиции П2.1 и П2.2 добавление новых переходов не производится.

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

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

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

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

- 3. Построение ОФС задачи визуализации'с учетом алгоритма визуализации и базового набора функций.

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

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

6. Разработка коммутационной среды.

Распределение ОФС задачи визуализации носит поярусный характер, т.е. производится поочередное, независимое распределение всех ярусов ОФС. Алгоритм распределение для ¡-го яруса ОФС задачи визуализации:

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

2. Распределение переходов ¡-го яруса среди виртуальных процессоров по одному из универсальных минимаксных алгоритмов.

3. Осуществление оптимизации распределения за счет проведения процедуры сглаживаний и выравнивания времен работы отдельных виртуальных процессоров на ¡-ом ярусе. Это достигается путем применения правил декомпозиции по данным к распределенным переходам. Для декомпозиции по данным предлагается использовать итерационный алгоритм:

- Выбор пары процессоров: один с максимальной, другой с минимальной загрузкой.

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

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

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

- Переход к началу.

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

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

- Если переход работает только в одном пространстве, то декомпозиция осуществляется в этом пространстве;

- Если переход работает и в пространстве сцены, И в пространстве изображения, то декомпозиция осуществляется в пространстве изображения. .

5. Если при распределении ¡-го яруса применялась декомпозиция по данным с использованием правила П1.2, то в этом случае добавляется дополнительный ярус между 1-ым и (¡+1)-ым ярусами, содержащий переходы типа РЗ.

Таким oбpaзoмi при лоярусном распределении ОФС задачи визуализации за счет использования распределения вычислений в пространстве данных реализация возможностей параллельной обработки в системе визуализации будет близкой к максимальной.

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

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

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

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

3. Разработан параллельный бинарный алгоритм слияния изображений объектов в единое изображение сцены с 1од2Ы-связным графом потоков данных. Использование этого алгоритма позволяет ускорить процесс слияния и упростить разработку коммутационной среды.

4. Разработана параллельная ВС визуализации на базе многопроцессорной станции TIP-Set, использующая' параллельную обработку в пространстве изображения.

5. Реализован и экспериментально исследован ряд методов распределения потоков данных в системе визуализации на базе станции TIP-Set. Предложены рекомендации по их использованию.

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

1. Шмидт В.К., Татаринов Ю.С., Тимофеев А.В. Параллельная обработка в задаче синтеза изображений пространственных сцен. //Материалы 5-ой Международной Конференции ГРАФИКОН'95. Конкурсные доклады, специализированные семинары, С.-Петербург, 1995.-Том2, с.178.

2. Schmidt V., Shah V., Timofeev A., Perkov A., Burenev N. Research and development of parallel system for image synthesis of 3D-dynamic scenes. //Projects in Massively Parallel Computing. Annual Report, Center for Parallel Computer Technologies, Electrotechnical University, St-Petersburg, 1995.-p.14-24.

3. Шмидт В,К., Шах В.В., Лерков А.Н., Буренев Н.А., Тимофеев А.В. Система визуализации при движении по рельефу. //Материалы 5-ой Международной Конференции ГРАФИКОН'95. Конкурсные доклады, специализированные семинары, С.-Петербург, 1995.-Том2, с.182.

A. Schmidt V.K., Shah V.V., Timofeev A.V., Perkov A.N., Burenev N.A. The disributed interactive system for synthesis of image space scene. //Applications of Computer Systems. Proceedings of the Second International Conference, Szczecirv-Poland, December 8-9, 1995.-p.215-223.

5 Schmidt V.K., Tatarinov Y.S., Shah V.V., Timofeiev A.V., Burenev N.A., Perkov A.N. Parallel processing in a problem of 3D scene visualization. ffThe 10th Annual International Symposium on High Performance Computers, IEEE Canada Electronic Services HPCS'96 Conference Proceedings, Ottawa, Canada, July 5-7, 1996.

6 Шмидт В.К., Тимофеев А.В., Шах В.В., Перков А.Н. Система параллельного синтеза изображений динамических пространственных сцен. //Материалы 6-ой Международной Конференции ГРАФИКОН'96. Конкурсные доклады, специализированные семинары, С.-Петербург, 1996.-Том 2, с.200.

i j