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

Г г'<

О 3 ФЕЙ Ш7

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

Головкова Елена Юрьевна

РАЗРАБОТКА ПАРАЛЛЕЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ СИНТЕЗА РЕАЛИСТИЧЕСКИХ ИЗОБРАЖЕНИЙ

специальность: 05.13.13 . - Вычислительные машины, системы, ' комплексы и сети

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

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

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

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

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

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

доктор технических наук. проф. Советов Б.Я.

кандидат физико-математических наук, вед. научн. сотр. Попов А.П.

Ведущая организация - ОКБ "Электроавтоматика"

Защита диссертации состоится " " 1997 г.

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

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

Автореферат разослан " " ^¡СёСл^Щ^ 1997 г.

Ученый секрётарь диссертационного совета

Маркин А. С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы

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

Поиск решения проблемы повышения производительности средств вычислительной техники ведется в основном в двух направлениях: разработка суперЭВМ с внутренним параллелизмом и систем с массовым (внешним) параллелизмом. Системы с массовым параллелизмом позволяют сочетать высокую производительность и универсальность отдельных йроцессоров и возможность построения параллельной структуры, причем регулярная структура и упорядоченность связей обеспечивают простоту программирования и эксплуатации. К ним относятся система Paradox фирмы Intel, системы на базе транспьютеров западноевропейских фирм Inmos, Transtech. Parsytec, Meiko.

• Транспьютеры имеют ряд преимуществ перед другими процессорами при построении параллельных архитектур: наличие программно настраиваемых линий связи; минимальное количество дополнительных микросхем при соединении транспьютеров; небольшое энергопотребление транспьютерной микросхемы. Недостатком систем на базе транспьютеров является ограничение роста производительности из-за ограниченной пропускной способности последовательных соединений. Однако, в направлении увеличения скорости обмена по линиям связи ведутся разработки. Предполагается, что при значении пропускной способности линий связи 500 Мбит/с. для изображения средней сложности размером 1024 на 1280 точек возможно получить скорость 24 кадра в секунду.

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

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

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

Цель диссертационной работы состоит в

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

Для достижения поставленной цели необходимо:

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

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

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

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

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

- исследование характеристик параллельного алгоритма при реализации на транспьютерной сети;

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

Разработка структуры системы включает решение следующих задач:

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

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

- выбор, исследование .1! модификация средств моделирования,

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

- разработка оптимальной структуры параллельной вычислительной системы.

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

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

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

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

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

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

- разработан параллельный алгоритм синтеза реалистических изображений;

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

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

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

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

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

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

Основные положения диссертационной работы докладывались и обсуждались на семинарах кафедры ВТ СП6ГЭТУ,. научно-технической конференции профессорско-преподавательского состава СПбГЭТУ в 1993г., на 1-ой международной конференции по применению вычислительных систем, Польша, 1994г.

Публикации

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

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

Диссертационная работа состоит из введения, четырех разде-

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

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

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

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

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

В рамках диссертационной работы для эксперимента с изображением используется рабочая станция, включающая HOST-машину OPUS (Sun-clone) и матрицу транспьютеров с жесткой конфигурацией;-производительность транспьютерного модуля'- 10 млн. оп./сек.. скорости передачи данных по линиям связи - 10 Мбит/сек.

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

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

Объект изображения аппроксимируется совокупностью опорных

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

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

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

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

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

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

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

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

В конце данного раздела сформулирована развернутая постановка задачи.

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

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

- синтез изображения Фрагментов объекта, включая все вычисления. связанные с проецированием, отсечением и закраской полигонов на изображении без учета передачи данных между модулями (характеризуется временем синтеза T3lnt);

- пересылка всех полей изображения (яркости, глубины, теней) из узлов синтеза в узлы слияния (характеризуется временем пересылки T3end);

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

. Для определения значений основных параметров параллельного алгоритма был проведен эксперимент на транспьютерной системе. Разработанная программа синтеза реалистического изображения предназначена для выполнения на транспьютерной матрице из 16 транспьютеров (4 на 4) жесткой конфигурации. Она может запускаться на любом количестве транспьютеров от 1 до 16. количество модулей указывается в командной строке. Программа работает в среде Х-VJ1ND0WS на рабочей станции OPUS (SU1J-clone), используемой в качестве HOST-машины, предназначенной для выполнения функций диалога с пользователем, загрузки исполняемого кода в транспьютеры и отображения на экране синтезируемых изображений.

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

данного ему Фрагмента объекта независимо от других модулей.

Исходным обьекто ' для синтеза изображения является рельеф местности, заданный регулярной сеткой высот, образующей совокуп--ность пространственных треугольников, аппроксимирующих объект изображения. Изображение задается тремя точками в пространстве: точкой наблюдения Р(ХР, YP, ZP), точной фиксации взгляда L(Xl, Yl, Zl) и точкой источника света S(Xs, Ys, Zs), а также фокусным расстоянием F и интенсивностью света Е. По этим основным параметрам рассчитывается матрица изображения aj...с3 и коэффициенты а и b для расчета параметра глубины. В процессе синтеза выполняется отсечение по пирамиде видимости, передняя граница которой задается величиной Smln, а задняя граница - величиной Smax. Точки рельефа, находящиеся ближе Smln и дэчьше Smax по глубине на плоскость изображения не проецируются.

На втором этапе организуется конвейер слияния изображений фрагментов (от модуля (N-1) до модуля 0).

Сначала необходимо выполнить слияние полей теней изображений. Модуль 1 принимает значения глубины t от (1-1)-го модуля и формирует значения результирующего поля теней по следующему соотношению:

tx(xt. yt) = max{ t10(xt. yt), tj.^xt. yt) ), где tj - значение в результирующем поле теней, t10 - значение в поле теней собственного изображения модуля, t± _ j - значение в поле теней, принятом от предыдущего модуля в конвейере слияния, xt, yt - координаты точки в поле теней.

Далее сливаются поле яркости и поле глубины согласно выражениям:

Мх, У) = шах { h10 (х, у), h1.1(x, у) },

vt(x, у)

v10(x, у), если ht о (х, у) > h!_t (х. у)

и t, о (xt, yt) > t..! (xt, yt) v1.1(x. у), если h10(x, y) <- hj.jtx, y)

и t10 (xt. yt) <= tj _ j (xt, yt) vt, в остальных случаях.

где - значение в результирующем поле глубины, Ь10 - значение в поле глубины собственного изображения модуля, - значение

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

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

При работе с изображением рельефа местности, заданного регулярной сеткой высот, образующей 2048 пространственных треугольников, размером 256 на 256 точек на односвязном конвейере из 4-х транспьютерных модулей при значении коэффициента деления изображения КБ = 64 были получены следующие значения:

1. Время синтеза изображения на одном транспьютере 11.2 с.

2. Значения времени синтеза изображений фрагментов рельефа в 1-м, 2-м, 3-м и 4-м модулях соответственно равнялись 2.8 с., 3.6 е., 3.0 с. и 1.8 с.

3. Время пересылки всего изображения без обработки данных между соседними модулями 0.1 с.

4. Время пересылки порции изображения без обработки 1.5 мс.

5. Значения времени слиянии всего изображения в 1-м, 2-м, 3-м и 4-м модуле с учетом времени пересылки порций изображения соответственно 2.6 е., 1.7 е., 2.2 с. и 3.4 с. Разброс времени слияния вызван разбросом времен синтеза изображений фрагментов.

6.- Время обработки порции данных при слиянии 0. 01 с.

7. Время синтеза кадра изображения на 4-х модулях параллельно 5.4 с.

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

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

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

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

как в варианте 1. На переписывание изображения из одного модуля в другой требуются дополнительные затраты времени, но общий выигрыш во времени возможен за счет параллельности процесса слияния текущего кадра изображения и синтеза изображений фрагментов ■ следующего кадра. Представителями данного типа являются "двухсвязный конвейер", включающий всего N модулей, из которых число модулей синтеза ((N+1) /2 + 1), где N .всегда нечетное, и "двухсвязное дерево", включающее всего N модулей, из которых число модулей синтеза ((N+1) /2+1), где N = 2т - 1, ш - количество уровней "дерева".

3. "Трехсвязные схемы" (по числу связей транспьютера: три связи для приема изображений и одна - для передачи), аналогичные двухсвязным, но с удвоенным числом модулей синтеза. К ним отно-., сятс5г "трехсвязный конвейер", включающий всего К модулей, из которых. синтезируют ((2 * N + 1) /3) модулей, и "трехсвязное дерево", включающее всего N модулей, из которых, синтезируют ((2 * М + 1) /3) модулей, причем необходимо соблюдать соотношение 2 * N = 3"\ где ш - количество уровней "дерева".

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

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

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

Т4 = к * Тз1п40 / N + Тгоегв0, гДе Тэтю ~ общее время, затрачиваемое на синтез всего изображения, N - общее количество модулей в схеме. ТшеГб0 - суммарное ■ время слияния, к - коэффициент.неравномерности загрузки модулей.

В "двухсвязном конвейере" (схема 2) на получение первого кадра изображения будет затрачено время, включающее три процесс са: синтез изображений фрагментов (к * Тз1п10 / N¡¡1. пересылка всего изображения без обработки (ТзеП(Ш) и слияние в конвейере (Тщетно)■ Но поскольку далее действия, связанные со слиянием текущего кадра изображчшя. и синтез изображений фрагментов следу-

ющего кадра будут выполняться параллельно, то в общем случае время выполнения синтеза кадра изображения в схеме 2 с учет™ того, что количество модулей синтеза в структуре И3 = N / 2: Т2 = Тзепао + тах{(2 * 1с * Та1пго / 11), Ттегё0>.

В "трехсвязном конвейере" (схема 3) процессы аналогичны двухсвязному конвейеру, но имеют свои времена слияния и пересылки данных: Тгаегг3 = 2 * ТтегЕ0' Тзелаз = 2 * Т,епао. При условии, что синтезом изображений Фрагментов занимается II, = 2/3 к И модулей, получаем выражение для варианта 3: Тг = 2 * Таеиао + ™ах{("з * И * Та1в10 / (2 * И)). (2 *Тиега0)}.

Для значений параметров, полученных экспериментальным путем, можно сделать вывод, что при Н,<= 4 вариант 1 более эффективен, при И > 4 и N <= 10'лучшие результаты дает схема 2. а вариант 3 лучше, если число модулей в структуре больше 10, по при N > 145 вновь "предпочтительнее вариант 1-, поскольку время синтеза будет уменьшаться, а относительная производительность будет стремиться к нулю.

. Для полноты исследований предлагается далее использовать метод имитационного моделирования.

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

В результате анализа возможностей существующих систем моделирования было определено, что наиболее подходящей и доступной является система логического моделирование - технических устройств "Аметист", разработанная в Санкт-Петербургском ГЭТУ на кафедре ВТ, которая включает в себя средства для создания электрических и функционально-логических фазовых моделей и служит для проведения экспериментов на таких моделях. Система удовлетворяет основным требованиям к системе моделирования для исследований, которым посвящается данная работа. Она доступна для дополнения и модификации средств моделирования, что является важнейшим обстоятельством при использовании системы для моделирования к изучения нестандартных объектов.

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

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

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

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

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

- способ описания формата данных типом STRUCT дает выигрыш во времени моделирования по сравнению с описанием байтовым массивом;

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

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

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

- мадель вычислительного узла должна быть единым функцио-

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

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

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

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

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

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

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

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

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

Основными исследуемыми параметрами являлись ускорение' по времени реакции и ускорение ло пропускной способности параллельной структуры. Настройка моделей соответствовала условиям физического эксперимента.

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

'Результаты моделирования подтверждаются экспериментальными данными для основных временных параметров и аналитическими вчоа-жениями.

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

Приложение. В приложении 1 предлагается описание и обосно-

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

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

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

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

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

4. Предложена аналитическая модель параллельной системы синтеза реалистических изображений. С учетом экспериментальных данных получены аналитические оценки производительности базовых схем параллельных вычислений в системе синтеза изображений.

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

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

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

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

9. Разработана структура блока синтеза изображения системы синтеза реалистических изображений.

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

1. Shmidt V., Shah V., Golovkova Е. Transputer Based Image Synthesis Parallel Algorithms of ?D Objects. / Applications of Computer Systems. //Proceedings of the First Intern. Conference, Szczecin, Poland. i994.

2. Головкова Е.Ю., Тимофеев A.0. Система "АМЕТИСТ" для моделирования электронных устройств. /Системы автоматизированного проектирования дискретных устройств. // Междунар. конф. 15-17 ноября 1995г., Минск, Республика Белорусь. - Минск - Szczecin, 1995.