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

Р Г Б ОД

ИНСТИТУТ ТОЧНОЙ МЕХАНИКИ и оптики САНКТ-ПЕТЕРБУРГ

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

ПАЛТАШЕВ Тимур Турсунович

МУЛЬТИПРОЦЕССОРНЫЕ АКСЕЛЕРАТОРЫ В СИСТЕМАХ ВИЗУАЛИЗАЦИИ ГРАФИЧЕСКИХ СТАНЦИЙ.

05.13.05 - "Элементы и устройства вычислительной техники и

систем управления" 05.13.13 - "Вычислительные машины, комплексы, системы и сети"

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

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

- г -

Работа выполнена на кафедре Вычислительной Техники Санкт-Петербургского Института Точной Механики и Оптики

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

профессор Новиков Г.И.

Ведущая организация - Институт Прикладной Математики

им. М.В. Келдыша РАН.

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

Доктор технических наук, профессор Байков В.Д.

Доктор физико-математических наук, профессор Клименко C.B.

Доктор технических наук, профессор Очин Е.Ф.

Защита состоится "18" октября 1994 года в 15 ч. 20 мин. на за седании специализированного совета Д 053.26.02 Санкт-Петербургског института точной механики и оптики по адресу:

197101, Санкт-Петербург, ул. Саблинская, 14, ИТМО. Факс: (812) 238-87-65

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

Автореферат разослан "_" _ 1994 г.

Ученый секретарь специализированного совета Д 053.26.02, д.т.н., профессор A.B. Ушаков

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

Актуальность проблемы. Тема диссертационной работы связана с исследованием и разработкой систем визуализации, обеспечивающих синтез изображений в реальном масштабе времени (РМВ). Интенсивное развитие алгоритмической базы компьютерной графики, развитие технологии СБИС и появление высокопроизводительных графических рабочих станций создали возможность широкого применения систем визуализации, работающих в РМВ, что подразумевает генерацию кадров с частотой 5-30 кадров в секунду. Это позволяет осуществлять плавное изменение реалистичного изображения сцены в соответствии с изменениями параметров обзора и динамикой объектов.

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

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

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

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

Учитывая огромный объем необходимых вычислений, который нужно выполнять для генерации каждого кадра изображения, в ГА необходимо использование высокопроизводительных мультипроцессорных вычислительных структур, построенных на основе специализированных процессорных элементов (ПЭ), реализованных в виде СБИС.

Специфика обработки позволяет выделить в графическом акселераторе две основные подсистемы - геометрическую и растрирующую, для которых характерны различные требования к макроархитектуре подсистем и микроархитектуре ПЭ. Развитие международного процесса стандартизации графических систем поставило проблему соответствия функций ГА требованиям недавно принятых стандартов PHIGS+, РЕХ и OpenGL.

Малое число отечественных публикаций по этой тематике, ограничивающихся вопросами аппаратной поддержки отдельных этапов визуализации, реализация только двух систем визуализации в РМВ ("Аксай" и "Альбатрос" в ИАЭ СО РАН), обладающих ограниченными возможностями, делает актуальным задачу исследования и разработки основных подсис-

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

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

В соответствии с этим сформулированы следующие основные направления исследований:

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

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

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

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

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

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

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

- Разработана общая методика проектирования подсистем графического акселератора, основой которой является разработка концептуально-логической и вычислительной модели подсистемы с учетом функциональных спецификаций международных графических стандартов PHIGS+/PE> и OpenGL с последующим отображением логических модулей на архитектуру устройств обработки;

- В рамках детализации методики проектирования выполнена разработка и исследование конвейерных и параллельных мультипроцессорны> структур для геометрических подсистем, соответствующих спецификация», графических стандартов PHIGS+/PEX и OpenGL;

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

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

процессорных элементов.

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

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

- Разработаны и исследованы способы аппаратной реализации функциональных спецификаций международных графических стандартов PHIGS+/PEX и OpenGL в процессе проектирования графического акселератора:

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

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

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

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

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

- Разработан программный моделирующий пакет "GRAFO Render-ing Project", обеспечивающий возможность моделирования работы подсистем графического акселератора при учете глобальной и локальной освещенности.

Реализация результатов работы. Результаты исследований и разработок использованы при проектировании СБИС графического процессора К1809 ВГ4 в КТБ АО "СВЕТЛАНА" и семейства графических контроллеров GLX на основе этой СБИС, специальной графической системы для КБ завода "РОССИЯ", специальных графических контроллеров для НИИ Авиационного Оборудования, графического сопроцессора "Галета 1,2" в КТБ АО "СВЕТЛАНА". Кроме того, результаты работы в настоящее время используются в работах по проекту "KAMELEON", выполняемого по программе "COPERNICUS" Европейского Сообщества, и связанного с разработкой методов совместного проектирования аппаратно-программного обеспечения систем генерации реалистичных изображений.

В рамках внедрения в учебный процесс результаты работы использованы в совместном проекте с Университетом Брауна (США) по модификации программных пакетов SRGP и SPHIGS для создания курса лабораторных и практических работ по курсу компьютерной графики в Институ-

те Точной Механики и Оптики.

Апробация результатов работы. Основные результаты диссертацион ной работы докладывались и обсуждались на Всесоюзной конференци "Микропроцессорные системы" (Челябинск, 16-19 мая 1984); I Республи канской научно-технической конференции "Применение микропроцессоре в народном хозяйстве" (Фрунзе, 1965); II, III, IV Всесоюзных конфе ренциях "Методы и средства обработки сложной графической информации (Горький, 1985, 1988, 1991); семинаре "Программное обеспечение применение микропроцессорных систем и устройств" (Москва, 1986); I Всесоюзной конференции по проблемам машинной графики (Протвино, 9-1 сентября 1987); зональном семинаре "Применение машинной графики моделировании и обучающих системах" (Пенза, 18-19 октября 1989); II IV Международных Конференциях по Компьютерной Графике и Визуализации ГРАФИКОН (Москва - сентябрь 1992, Н.Новгород - сентябрь 1994) на российско-германском семинаре по Информатике и Прикладной Матема тике (Москва, сентябрь 1993); 9-ом Семинаре по Графической Аппарату ре Международной конференции EUROGRAPHICS (Осло, Норвегия, 12-1 сентября 1994).

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

Структура и объем работы. Диссертационная работа состоит и введения, шести глав, заключения, списка литературы из 287 наимено ваний и трех приложений. Общий объем работы составляет 516 страниц основной текст работы изложен на 374 страницах, иллюстрируемых 16 рисунками и 54 таблицами.

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

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

Разд.1.1 посвящен введению в проблему синтеза реалистичнь изображений в РМВ. В случае повышения сложности сцены (появления до полнительных объектов и источников света) или увеличения частоты мс дификации кадров происходит соответствующий рост вычислительных зат рат. Это делает абсолютно необходимым использование ГА, построение на основе специализированных СБИС и мультипроцессорных архитектур.

Процесс реалистичной визуализации объектов и сцен включает:

1) Извлечение моделей объектов из базы данных, формирование обработка дисплейного файла;

2) Преобразование моделей объектов и сцен, включая геометричес кие преобразования (поворот, масштабирование, проецирование отсечение и видовые преобразования);

3) Расчет параметров освещенности и затенения поверхностей зависимости от их типов и характеристик, числа и расположе ния источников света;

4) Сканирующее преобразование объектов сцены в растровый вид

5) Определение видимых поверхностей;

6) Тоновая закраска поверхностей в соответствии с заданной моделью и текстурой;

7) Занесение кодов пикселей в кадровый или строчный буфер, либо непосредственный вывод на видеомонитор.

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

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

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

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

- алгоритмы, использующие Z-буфер; - алгоритмы трассирования лучей

- приоритетные алгоритмы; - алгоритмы излучательности;

- алгоритмы построчного - смешанные алгоритмы, сканирования (АПС).

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

Рассмотрена группа локальных моделей освещенности (ЛМО), включающие простую модель Фонга, модель Варна и модель Торренса-Сперроу. По модели Фонга, уравнение освещенности имеет вид:

" / IiJ Ея \

1=1» *k« + £<------* (kd»(N*L) + k.«(R«S) ) / (1)

¡=1 v г + k '

где Ia - интенсивность рассеянного света; Iij - интенсивность j-ro источника света; к - коэффициент ослабления; г - удаленность от наблюдателя (глубина); ш - количество источников света; k», kd , ка -

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

Выполненный обзор показал, что вычислительная сложность этих моделей вполне приемлема для аппаратной реализации в подсистемах ГА, и эти ЛМО приняты в качестве базовых.

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

Внешним циклом алгоритма Z-буфера является перебор всех ГПВ описания сцены, внутренним циклом - перебор всех пикселей внутри ГПВ. ГПВ растрируются в произвольном порядке, ядром алгоритма является растрирование отдельного полигона, которое обеспечивается процессом билинейной интерполяции координат и ассоциированных параметров. Здесь выделены три этапа: 1) Расчет параметров интерполяции для растрирования полигона; 2) Интерполяция границ (вертикальная интерполяция); 3) Интерполяция линейного сегмента (ЛС) (горизонтальная).

Используются три основных алгоритма тонирования: 1) Однородная закраска; 2) Линейная интерполяция интенсивности (Гуро); 3) Линейная интерполяция нормали с последующим расчетом интенсивности (Фонг). Наибольшую вычислительную сложность имеет алгоритм Фонга.

Кратко рассмотрены алгоритмы визуализации на основе глобальной модели освещенности. Алгоритм трассирования лучей при внешней простоте требует огромных вычислительных затрат, за счет необходимое^ расчета пересечений луча со всеми поверхностями объектов сцены, которое выполняется в пространстве объектов.

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

В разд.1.3 выполнен краткий обзор стандартов на графическое программное обеспечение, где выделены: «Программные интерфейсы GKS, GKS-3D, PHIGS(+), РЕХ, OpenGL, CGI, X-1ib>, «Графические метафайлы и языки - GKSM, CGM, Postscript*, <Растровые графические файль - TIFF, GIFF, РСХ>, «Прикладные протоколы - IGES, STEP, VDAFS, MAP, EDIF, DXF>.

Основное внимание уделено программным интерфейсам PHIGS+, OpenGL, обеспечивающим режим визуализации. Рассмотрены структурь стандартов и основные функции. Отмечено, что наиболее перспективной

реализацией графических стандартов является модель "клиент-сервер", которая реализована в стандартах РЕХ (развитие PHIGS+) и OpenGL.

В разд.1.3 рассмотрена эволюция графических станций (ГС), разработана классификация существующих ГС, в которой выделены графические суперстанции и суперкомпьютеры, использующие мультипроцессорные акселераторы. В ГС можно выделить 5 основных ступеней обработки, рис.1. ГА обеспечивает поддержку от одной до четырех основных ступеней обработки в ГС, снимая с системного процессора вычислительную нагрузку. На этой основе выделены 4 класса архитектур ГА. Определены факторы, влияющие на параметры архитектурной платформы, приведены табличные методы оценки параметров ГС. На основе анализа архитектурных платформ выделены следующие основные подсистемы ГА: - ГЕОМЕТРИЧЕСКАЯ ПОДСИСТЕМА (ГПС); - РАСТРИРУЮЩАЯ ПОДСИСТЕМА (РПС);

- ДИСПЛЕЙНАЯ ПОДСИСТЕМА (ДПС). Каждая из них характеризуется специфичными алгоритмами обработки, выбор которых определяется непосредственно в процессе проектирования ГА. При этом наиболее эффективная их реализация обеспечивается специализированными СБИС в составе мультипроцессорных структур(МПС). Основными направлениями разработок алгоритмов и МПС являются: - Разработка процессоров трэвврсэ графических баз данных (ГБД);

п

п

< й > # Создание, прием, модификация

данных, создание структур данных;

< Т > # Просмотр структур данных с выбор-

кой ГПВ для визуализации

< X > # Стандартный набор геометрических

преобразований по отображению в экранное пространство и расчет освещенности;

< 3 > # Растрирование и тонирование объ-

ектов с записью в кадровый буфер (КБ);

< О > # Простые растровые операции в КБ,

сканирование и вывод содержимого кадрового буфера на видеомонитор.

Классы архитектур графических акселераторов по росту сложности:

— ГА = G.T.X.S. * D. (Простые растровые операции и отображение)

— ГА = G.T.X. » S.D. (Растрирование/тонирование + < D >)

- ГА = G.T. * X.S.D. (Геом. преобразования +<S>+<D>)

- ГА = G. * T.X.S.D. (Траверс данных +<X>+<S>+<D>)

Рис.1. Пять основных этапов обработки и типы архитектур ГА.

- Разработка специализированных МПС и СБИС процессорных элементов (ПЭ) для геометрических преобразований и расчета освещенности;

- Разработка СБИС ПЭ и МПС 30-растрирования;

- Разработка СБИС ПЭ и МПС для тонирования и текстурирования;

- Разработка СБИС ЗУ и подсистем памяти изображений.

Первые ГПС ГА имели конвейерную архитектуру, развитие уровня технологии СБИС сделало экономически оправданным использование в ГПС параллельных архитектур типа MIMD и SIMD.

РПС в наибольшей степени нуждается в использовании специальных ПЭ и структур, которые наряду с общими признаками (SIMD, MIMD, MISD) классифицируются по реализуемым базовым алгоритмам растрирования/тонирования и режиму взаимодействия с ДПС.

Разработки архитектур РПС велись в следующих направлениях:

- Разработка СБИС ПЭ и МПС асинхронных РПС с полным кадровым буфером

- Разработка СБИС ПЭ и МПС синхронно-асинхронных РПС на основе АПС.

Информация в имеющихся источниках характеризует в основном параметры разработанных систем. Процесс проектирования подсистем ГА описывается только во внутренних технических отчетах и информация остается недоступной, так как относится к категории "Know-how". В связи с этим особую актуальность приобретает анализ, исследование и разработка методов проектирования подсистем ГА. Необходима также разработка аппаратно-ориентированных версий алгоритмов растрирования и тонирования.

В разд. 1.5 формулируются ЦЕЛИ и ЗАДАЧИ диссертационной работы.

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

Рассмотрены основные принципы реализации процесса генерации реалистичных изображений и основные ступени последовательности обработки графических данных при их визуализации. Для ЛМО возможны три основных варианта построения конвейера, определяемых комбинацией методов тонирования и алгоритмов удаления скрытых поверхностей:

#1 - Конвейер визуализации с алгоритмом Z-буфера (или построчного сканирования) и методом тонирования по Гуро;

#2 - Конвейер визуализации с алгоритмом Z-буфера (или построчного сканирования) и методом тонирования по Фонгу;

#3 - Конвейер визуализации с приоритетным алгоритмом и методом тонирования по Фонгу (или по Гуро).

Рассмотренные модели генерации изображений в ГС показывают глобально последовательный характер обработки при визуализации на основе ЛМО. Очевидна возможность реализации распределенной обработки на базе макроконвейера специализированных ПЭ, обеспечивающих поддержку отдельных ступеней. Однако малое число ступеней алгоритмов визуализации не позволяет использовать большое число ПЭ (не более 8-9).

Учитывая технологические ограничения в скорости работы СБИС и передаче данных между ступенями конвейера, общая производительность не может превышать 500 М операций/сек. Повышение степени реалистичности требует значительно большего уровня производительности, который может быть достигнут за счет использования параллельной обработки. Показано, что модели генерации реалистичных изображений с использованием ЛМО допускают как глобальное, так и локальное распараллеливание вычислений при сохранении общей последовательности ступеней обработки. Для геометрических преобразований всех моделей характерен единый порядок арифметической обработки, которая может быть реализована с помощью ПЭ, обеспечивающих быстрые арифметические вычисления с плавающей запятой (ПЗ).

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

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

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

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

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

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

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

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

Раздел 2.3. посвящен функциональному анализу процесса визуализации в ГС. Рассмотрены основные спецификации графических стандартов PHIGS+/PEX и OpenGL, отражающиеся на аппаратные структуры ГА. Выделены основные ресурсы, требующие аппаратной поддержки в подсистемах ГА, рассмотрены спецификации обработки вершин и параметров ГПВ.

Определены фундаментальные различия между PHIGS+/PEX и OpenGL.

Используя аналогию с процессорными архитектурами, систему PHIGS+/PEX можно отнести к классу CISC, a OpenGL - к классу RISC.

Анализ уровня сложности функциональных спецификаций РЕХ и уровня описания ГПВ показал, что локальная реализация полного набора функций PHIGS+/PEX в рамках ГА достаточно сложна и в любом случае значительная часть ресурсов PHIGS+/PEX реализуется системным процессором ГС. Специфика аппаратной ориентации OpenGL позволяет разрабатывать ГА, ориентированные на прямую интерпретацию полного набора команд ГПВ и управления этой системы. Рассмотрены ресурсы OpenGL, регламентирующие работу ГПС, РПС и структуру кадрового буфера. На рис.2 приведена структура стандарта OpenGL.

В разд.2.4 выполнен анализ вычислительных моделей визуализации с учетом требований стандартов PHIGS+/PEX и OpenGL. Разработаны операторные модели и составлены таблицы формуляров для всех ступеней геометрических преобразований. На основе моделей определены требуемые вычислительные ресурсы ГПС для алгоритмов, удовлетворяющих спецификациям стандартов. Разработаны операторные модели расчета освещенности для различных моделей освещения и тонирования, регламентированных стандартами PHIGS+/PEX и OpenGL. В частности, исследована вычислительная модель расчета освещенности, включающей рассеянный, направленный, позиционированный и прожекторные источники света в комбинациях с диффузной и зеркальной составляющей. Разработаны алгоритмы и операторные модели расчета параметров растрирования. Данные операторные модели и таблицы формуляров использованы как основа для детализации требований к макроархитектуре МПС и микроархитектур ПЭ в

Табл.1. Мультипроцессорные структуры растрирования.

NN СТРУКТУРНАЯ ОРГАНИЗАЦИЯ СИСТЕМЫ РАСТРИРОВАНИЯ ТИП ВИРТУАЛЬНОГО БУФЕРА

Полный кадровый буфер Буфер на 1 строку Буфер на полосу (N строк) Буфер на прямоуг-ый фрагмент

1 . 2. 3. 4. 5. 6. 7. ô. Одиночный процессор Конвейер процессоров Линейный массив процессоров (SIMD)* (MIMD)» Процессор/пиксел (SIMD)* Прямоугольный массив процессоров (SIMD)« (MIMO)* Строчный массив процессоров/пиксел (SIMD)* Массив процессоров/пиксел на полосу (SIMD)* Прямоугольный массив процессоров/пиксел (SIMD)« шя шш Шй

*- Требуется использование процессоров для предобработки.

Данные вершин.

г#1-

Дисплейный список

г» 2-

Обраб-ка входных полин-оа

1

Пиксельные данные

газ-

Операции над вершинами

ГПВ Сборка примитивов

г#5-

г#4-

Пиксельные операции

Растрирование

г# 7-

Текстурная память

Рис.2. Диаграмма работы и основные ресурсы стандарта OpenGL.

процессе разработки подсистем ГА, рассмотренных в следующих главах.

Третья глава посвящена анализу и проектированию геометрических подсистем ГА. В разд.3.1 в качестве основы для разработки подсистем ГА предложена общая методика проектирования, использующая в своей основе системный подход и принцип "нисходящего проектирования". В целом методика включает этапы анализа технических требований, системотехнического, структурно-функционального и технического проектирования. Ключевой проблемой системо-технического проектирования является формирование концептуально-логической модели (КЛМ), отражающей основные детали функционирования подсистем ГА. На рис.3 проиллюстрирована разработка и использование КЛМ в проектировании подсистем ГА.

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

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

С использованием введенной в разд. 2.2 структурной нотации, определено общее описание мультипроцессорных архитектур ГПС и РПС.

ГПС: DC Vert ex with Data)fP Ch(E,M,Mff) —> Cvi(Dfp-Dfp) —> K*I[Pfp]. —> Cvz(Dfp-Dbp)—> РПС

D(Vertex,Lighting)bp

РПС: D(Vertex,Lighting)bp Ch(E.Mff) —> L* I [P1b p ] --> М»1[Р2ьр]|р —> N*I[P3r9b]iP ~> ДПС

□(Pixels,rgba)bp

где К - число ПЭ обработки с ПЗ в ГПС; L - число ПЭ обработки с ФЗ е РПС; M - число ПЭ интерполяции сегментов ГПВ; N - число ПЭ обработкк пикселей ГПВ.

Исследована упрощенная КЛМ ГПС и показано формирование макромодели вычислений и передачи данных для спецификаций стандартоЕ PHIGS+/PEX и OpenGL.

Условие баланса работы ГПС описывается выражением:

Pgp*Pt г *qt г »Fdout *( 1-Кс I I р )

T| d йТс«|с ^Tsnd, где Tend= -

Wo bue

V

PSp*(Q9P*F9P+Vgp*QV*FdV) РвР*У9Р* bHi *Qî v

Tid= - ; Te11 с = - »Top

Wi bus К

здесь Pgp - число входных комплексных ГПВ в секунду; Q9P - число обрабатываемых параметров ГПВ; Fd9P - число байт в формате представления с ПЗ данных параметров ГПВ; Vgp - число вершин в комплексно!» ГПВ; Qv - число параметров вершин в ГПВ; Fav - число байт в формат« представления параметров вершин; Wibua и Wobue - полоса пропускания

Рис.3. Разработка и использование концептуально-логической модели в проектировании подсистем ГА.

входной и выходной шины ГПС (байт/с); Н, - число операций над вершинами ГПВ i-ой ступени логического конвейера; Qiv - число параметров вершины, обрабатываемых на i-ой ступени; К - число ПЭ в ГПС; Тор -цикл выполнения одной операции; Ptr - число параметров в комплексном ГПВ; qtr - число параметров треугольника (с учетом двойной точности для некоторых); Fdout - число байт в формате представления с ФЗ.

В разд.3.2 рассматривается разработка конвейерных ГПС с учетом спецификаций стандартов PHIGS+/PEX и OpenGL, и исследуются варианты реализации конвейера арифметических процессоров (АрП). Набор необходимых операций определяется разделением требований геометрической обработки PHIGS+/PEX на следующие три задачи:

1) Управление структурами: включает обеспечение интерфейса с прикладной программой и управление центральной памятью структур.

2) Управление траверсом: поддерживает механизм системы имен и передает элементы структуры в геометрический конвейер.

3) Геометрический конвейер: включает геометрические преобразования (такие как преобразования моделирования и обзора),расует освещенности, клиплирование и детектирование при идентификации ГПВ.

Это возможно реализовать на различных типах ПЭ, при этом (1) и (2) требуют манипуляций с неарифметическими данными, а геометрический конвейер (3) требует арифметической обработки с ПЗ. Разделение (1) и (2) на различный аппаратный базис осуществляется благодаря концептуальному разделению в PHIGS манипулирования структурами и визуализации структур. В общую структуру конвейерной PHIGS-ГПС, включаются: траверс-процессор с локальной памятью; процессор управления структурами; процессор интерфейса; группа АрП, объединенных в конвейер .

Множество АрП в геометрическом конвейере может быть сформировано либо из копий одного ПЭ с загружаемым микрокодом или отдельных ПЭ с нестандартной микроархитектурой. Прямое отображение операторной модели, с одновременным выполнением большого числа операций может привести к несбалансированности с внешним и межпроцессорным интерфейсом. Необходим поиск компромисса при разработке микроархитектуры АрП. Верхний предел внутреннего распараллеливания обработки в АрП конвейерной i ЛС (для одной вершины ГПВ) определяется: 0*R / SMP У SA lu л

Tbue*- <Tdp + Tfp* I- + - l+ Tpc (3)

Rbue Qmpy Qalu

где: О и R - число и разрядность операндов во входном пакете данных; Тьив и Rbus - время цикла и ширина (в битах) межпроцессорной магистрали конвейера; Tdp и Трс - временные затраты на распаковку и упаковку входного и выходных пакетов данных; TfP - время цикла выполнения операции с ПЗ; S - число одновременно выполняемых операций; Q -число параллельно работающих операционных блоков. Более важные преимущества дает использование множества идентичных АрП, что позволяет упростить разработку аппаратных средств. При этом микроархитектура АрП должна быть тщательно выбранным компромиссом, между требованиями различных ступеней обработки логического конвейера.

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

El »top + Oi/Wb «Ei + i*toe + 0|н/№

N

< max[(Ei *top + Оi/Wb)] <1/N* £(Ei*toP + Oi/Wb) (4)

N 1=1

Ее. *ki =E*

i ■ 1

где Ei - число последовательных циклов обработки ГПВ в i-ом АрП; top - среднее время цикла обработки АрП; Oi - объем данных, порождаемый в результате Е циклов обработки в АрП| и подлежащий передаче в Ар-П1+1; Wo - скорость передачи данных (в байт/секунду) по межпроцессорным магистралям; Ех - общее число арифметических операций по преобразованию одного ГПВ; Ki - коэффициент внутреннего распараллеливания выполнения операций (сложения и умножения) в i-ом АрП; N - число АрП в конвейере.

Используя набор данных из операторных моделей и общее число операций с учетом микроархитектуры АрП, итеративным путем находится распределение операций между АрП в конвейере. Конвейерная ГПС/OpenGL должна включать в себя отдельный командный процессор преобразований (КПП) с FIFO модулем, за которым следует линейка из N идентичных СБИС АрП. Рассмотрены вопросы проектирования ПЭ КПП, преобразователей форматов ГПВ и микроархитектуры АрП. Показано, что в случае использования сложных моделей освещенности и дополнительной триангуляции поверхностей по результатам обработки возникают проблемы локальной перегрузки отдельных АрП. Вследствие этого, конвейерные ГПС теряют свою эффективность для сложных режимов рекурсивной обработки ГПВ, локально увеличивающих поток данных между отдельными АрП.

Для оценки производительности конвейерной РПС предложены аналитические выражения, определяющие коэффициент ускорения К» и коэффициент загрузки АрП К| :

N«U U

К» = - , Ki = - (5)

N*( )+U+N-1 N*( tf*l+1)+U+N-1

N - число АрП в конвейере (число ступеней); U - число ГПВ в группе с единым контекстом; 1 - емкость буфера FIFO АрП; К- средний коэффициент загруженности буфера FIFO.

Анализ показывает, что наиболее оптимальными режимами работы для конвейерных ГПС являются обработка длинных последовательностей ГПВ с относительно редким переключением контекста обработки. При числе элементов в группе ГПВ с одним контекстом, сопоставимой с глубиной конвейера, эффективность обработки резко падает. Показано, что производительность реальных конвейерных структур, как правило, ограничивается пределом 150-200 MFIops.

В разд.3.3. рассмотрено проектирование параллельных геометри-

ческих ГПС класса MIMO. Сформулированы исходные принципы построения параллельных ГПС, выполнен структурный анализ потока входных команд, в котором выделены 2 основных класса команд: независящие от порядка следования и последовательные команды. Обработка первого класса команд обеспечивается их произвольным распределением на АрП, для второго класса команд необходимо соблюдение порядка следования в обработке, аналогичному входному потоку. Определено, что ключевым моментом в эффективности ГПС-MIMD является независимость от порядка следования большинства команд ГПВ.

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

1) Траверс-Процессор (ТрП) для работы с высокоструктурированными входными данными (структуры в PHIGS+/PEX), который содержит систему двухпортовой памяти и процессор управления памятью (ПрУП). В этой системе памяти графические команды хранятся, как иерархическая структура связных блоков, соответствующая стандарту PHIGS+.

2) Обычный КПП, обеспечивающий выборку дисплейного списка низ-ко-уровневых ГПВ из системной памяти.

3) Сложный Командный Процессор, обеспечивающий интерпретацию команд графического языка (OpenGL) или запросов протокола РЕХ.

Входные графические команды распределяются между АрП следующими способами: 1) Команда не посылается ни в один из АрП, используется для вставки меток и другой неграфической информации s дисплейный список; 2) Команда посылается во все АрП, используется для команд загрузки контекста обработки; 3) Команда пересылается в АрП, наиболее готовый для принятия команды, согласно механизма арбитража команд, который используется для всех ГПВ и всех других команд, которые далее следуют в РПС.

Рассматривается проектирование ГПС-MIMD в базисе PHIGS+/PEX. Определены форматы, классификация входных команд ГПС-MIMD, которые включают 6 основных классов: 1) Команды нетонируемых ГПВ; 2) Команды тонируемых ГПВ; 3) Последовательные команды управления РПС; 4) Команды опроса РПС; 5) Команды опроса состояния АрП; 6) Команды управления РПС, независящие от порядка следования.

Разработаны сетевые модели арбитража и распределения входного потока команд, использующие двухуровневый приоритет и циклическое распределение. Определены требования к микро-архитектуре АрП, который должен включать: контроллер приема входных графических команд; FIFO тегов; Процессорное Ядро (ПЯ) и контроллер выдачи команд в РПС. Определены структурные требования к микроархитектуре процессорного ядра (ПЯ) АрП, которое может быть реализовано: 1) на основе RISC-процессора (i860), что обеспечивает гибкость, расширяемость для использования сложных ГПВ во входном потоке команд; 2) на основе микропрограммируемого ПЭ обработки с ПЗ, удовлетворяющего следующим требованиям: - Использование асинхронных двухбуферных регистровых файлов ввода/вывода; - Число внутренних регистров >250; - Параллель-

ная работа внутренних блоков; - Параллельное управление функциональными блоками; - Аппаратная поддержка теста клиппирования; - Аппаратная поддержка сортировки вершин по У(Х); - Аппаратная поддержка функций повышения общесистемной производительности.

Рассмотрена специфика работы АрП в ГПС-MIMD, способы синхронизации ГПС-MIMD при обработке последовательных команд, с использованием FIFO тегов, исследована реализация режимов предварительной выборки входных команд, упорядочивания ответных данных функций опроса PHI6S, идентификации ГПВ в структуре с аппаратной поддержкой механизма подсчета ГПВ.

Проектирование ГПС-MIMD в базисе OpenGL проиллюстрировано на реализации параллельной геометрической машины Reality Engine фирмы Silicon Graphics. Рассмотрены функции командного процессора в режиме интерпретации команд OpenGL и микроархитектура RISC-АрП.

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

N ! *Gi ( N) - ТхN N!*G2 (N) - TtrN

Wo 1 = - ; Wo z = - ( б )

(Tcp+Td)»N!«Gi(N) Trs*N!*G2(N)

» (Тср+Та £ ТЧг""' *Тгя>

где -; С2(Ю=Е -

(N-3)! (N-3)!

где Тер - среднее время диспетчеризации входного ГПВ командным процессором; Та - среднее время загрузки ГПВ из КП в АрП через интерфейс Кп-АрП; Тх - среднее время выполнения геометрических преобразований ГПВ типа треугольник; Т»г - среднее время расчета параметров интерполяции треугольника; Тг» - среднее время передачи формуляра треугольника в РПС; N - число АрП в ГПС-МШР.

Учитывая, что обе подсистемы составляют единую ГПС-М1М0, уравнение баланса работы ГПС-М1М0 описывается равенством: №01= Wa2.

В разд.3.4. исследуются вопросы проектирования ГПС класса ЭШС». Главными условиями использования МПС класса 51М0 в ГПС являются: - ограничение типов обрабатываемых ГПВ (вектор, треугольник, четырехугольник); - использование простых моделей освещенности; - предварительное группирование входных ГПВ в однородный поток. Основными задачами в проектировании ГПС-81М0 является разработка микроархитектуры ПЭ АрП с учетом операторных моделей и синтез эффективной схемы общего микропрограммного управления.

В ГПС-вШО все АрП в один момент времени должны выполнять одну команду, но только каждый для своего ГПВ. Преимуществом является минимальный уровень затрат на обеспечение мультипроцессорной работы. Все ПЭ используют один и тот же блок МПУ (БМПУ), общую память микропрограмм и одну память для глобальных данных, что обеспечивает серьезную экономию аппаратных ресурсов по сравнению с архитектурами типа М1Мй. Рассмотрена специфика реализации входного КПП и предложе-

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

1) При получении команды запуска выполнения из КП в момент, когда не все АрП загружены. Незагруженые АрП приостанавливаются в течении цикла обработки загруженной группы ГПВ;

2) В другом случае приостановка используется для выполнения условных вызовов подпрограмм отдельными АрП в SIMD-массиве, Если подгруппа ПЭ не выдала условия, эта подгруппа приостанавливается, пока остающиеся АрП не выполнят подпрограмму.

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

Производительность ГПС-SIMD может быть оценена через коэффициент ускорения обработки:

U»(E« + ß * Еа ' )

К«= --(7)

1и/ы[*(Еа+ ß*Ea ' )+и*(Тр+Ть ) где: U - число ГПВ в обрабатываемой группе; N - число АрП в структуре SIMD; Е» - среднее время полной обработки одного ГПВ в АрП; Еа'~ среднее дополнительное время обработки в случае ветвления по условию в одном или нескольких АрП; ß- вероятность локального ветвления для группы из N ГПВ (например, при клиппировании составляет примерно 0,1); ТР - среднее время группирования одного ГПВ; Ть - среднее время на загрузку одного ГПВ из командного процессора в соответствующий блок АрП; [U/NJ - частное от U/N, округленное в большую сторону.

В разд.3.5 рассмотрена реализация алгоритма излучательности для мультипроцессорной ГС с аппаратным ГА. В качестве основы взят алгоритм с последовательными улучшениями, где производится выбор SP-пат-ча, создание и заполнение I-буферов полукуба, преобразование содержимого в форм-факторы, распределение световой энергии. Выполнена декомпозиция алгоритма для МПС с общей памятью и локальными модулями КЭШ-памяти, объединенной с ГА. В системе реализуется два типа процессоров: "Генератор I-буферов", который создает 1-6уферы полукуба, используя ГА, имеющий в составе РПС и ГПС; "Расчетный процессор" -РП выполняет оставшиеся операции, включающие пересчет элементов буфера а форм-факторы, расчет распределения световой энергии, выбор следующего SP-патча. Рассмотрено описание задачи "Генератора 1-буфе-ров" и "Расчетного процессора", возможности перекрытия по времени вычислений ГА и процесса расчета 1-буферов.

Разработана аналитическая модель оценки производительности МПС

в расчете излучательности, учитывающая число РП, число полигонов в сцене, разрешение полукуба и параметры оборудования. Для создания и проверки правильности модели использовался специально разработанный пакет GRAFO RendProject. Определено, что использование высокопроизводительного ГА для создания и заполнения I-буферов полукуба должно быть уравновешено соответствующим числом РП, обеспечивающих основной объем вычислений.

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

1) Набор входных ГПВ сокращается до минимума, в котором присутствуют только ГПВ, для которых существуют эффективные аппарат-но-ориентированные алгоритмы растрирования и тонирования. Соответственно все ГПВ более высокого уровня, регламентируемые PHIGS+/PEX и OpenGL должны быть преобразованы в указанные типы. Как следствие этого, при проектировании РПС общий набор ГПВ, определяемый стандартами, не оказывает никакого влияния на набор входных данных.

2) Набор обрабатываемых атрибутов ГПВ также сокращается до набора атрибутов минимального набора ГПВ . Исключение представляют РПС, ориентированные на стандарт OpenGL, которые используют дополнительные глобальные атрибуты типа "туман" и текстурные образы. В набор атрибутов, ассоциированных с ГПВ и поступающих в РПС могут входить: 1) Цвет вершин ГПВ для тонирования по модели Гуро; 2) Цвет поверхности ГПВ для однородного тонирования; 3) Значения произведений векторов нормали, векторов источника света и наблюдения; 4) Значения векторов нормали для тонирования по модели Фонга; 5) Коэффициенты разложения в ряд Тейлора для тонирования "Фаст-Фонг"; 6) Индексы материала для тонирования поверхностей; 7) Координаты текстуры; 8) Атрибуты прозрачности и затенения. Эти атрибуты ассоциируются с ГПВ в зависимости от модели тонирования, реализуемой РПС. PHIGS+/PEX определены 4 основных модели тонирования, проиллюстрированные на рис.4 и включающих однородное тонирование, тонирование по цвету (метод Гуро), тонирование по произведениям векторов, тонирование по вектору нормали (метод Фонга). Реализация этих моделей в РПС должна обеспечивать соответствующую интерпретацию ассоциированных с ГПВ атрибутов и данных. В набор базовых функций РПС включены: #1 Расчет исходных параметров для растрирования ГПВ; #2 Растрирование ГПВ с заданным числом дискрет на пиксел; #3 Удаление скрытых поверхностей; #4 Тонирование ГПВ согласно заданной модели тонирования.

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

—Метод тонирования по вектору нормали (тонирование Фонга)

Г Метод тонирования по произведениям векторов.

. . Метод тонирования, использующий интерполяцию значений цвета (тонирование Гуро)

Ы-нормаль вершин

Интерпол. нормали N

Вычислен

NL, RS вершин

Вычислен цвета С

Интерпол. NL, RS

Цвет С вершин

Интерпол, цвета С

N Вычислен NL, RS Вычислен Цвет С

пиксела N»1.^*8 пиксела цвета С пиксела

Код пиксела Я,б,В Рис.4. Диаграмма методов тонирования.

Входные данные ГПВ

_4_

Блок FIFO Входные данные формуляра

« назначенной строки

БЛОК МПУ

Внешняя синхронизация

1_

Регистровый файл >70 слов

МРУ Умножитель

п

AL.ll

Инвертор 1/Х

Блок линейной интерполяции

параметров ЛС

А R G В X г

G

Умножители смешения цвета

АШ

Вывод в кадровый -в буфер НвВ

В

Z-блок

X

Контроллер буфера

АсЫ

Сдвоенный строчный буфер R,G,B,A,Z

Рис.5.

Микроархитектура СБИС РПЭ со строчным Z-буфером.

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

В разд.4.2. рассмотрено проектирование РПС на основе интервального АПС. В качестве основы параллельной обработки используется пространственная декомпозиция, разделяющая изображение на пучки раздельно обрабатываемых строк, которые в свою очередь разделены на интервалы. Этот подход порождает двухступенчатую иерархическую структуру, на первом уровне которой использованы процессоры строк в1.Р, каждый из которых обрабатывает свою группу строк, а на втором процессоры пикселей РХР, каждый из которых обрабатывает свой интервал. 81-Р реализует строчную часть стандартного интервального АПС в группе выделенных строк. РХР обрабатывает список активных ЛС для каждой строки, удаляя невидимые и тонируя видимые ЛС, реализуя пиксельную часть. С учетом операторной модели расчета параметров интерполяции определены основные структурно-функциональные требования к 51.Р, которые обеспечиваются: быстродействующим АЛУ; целочисленным умножителем; полным сумматором, подключенным к умножителю для вычисления порядков при расчетах с ПЗ; преобразователем форматов данных; внутренним регистровым файлом объемом не менее 5000 слов; высокоскоростной шиной. Модификация списка активных ЛС требует быстрого доступа к формулярам и быстрой сортировки, и ускорение возможно за счет перекрытия операций чтения/модификации/записи. Этот процесс обеспечивает быстрая одно- или двухуровневая система памяти, Для работы со списком необходимо использование дополнительных регистров адреса памяти. Аналогично определены требования и структуре процессора РХР, спецификой которого является наличие блока интерполяторов и строчного буфера. Разработаны функциональные схемы и форматы микрокоманд.

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

В разд.4.3.рассмотрено проектирование РПС на основе АПС с строчным Л-буфером. На основе анализа АПС с строчным г-буфером определено, что основным условием эффективной реализации является размещение строчного I- и яаВА-буфера на одной СБИС с растрирующим ПЭ (РПЭ). Строка из 1280 пикселей требует 102 К бит памяти, и не представляет технологических проблем для объединения с РПЭ. При этом возможно использование группы параллельных РПЭ, обеспечивающих растрирование для сопредельных строк. Разработана модификация АПС для параллельного исполнения. При наличии в составе РПЭ параллельного умножителя, сблокированного с АЛУ, выгодно использовать лобовой способ вычисления пересечений со строкой сканирования, что позволяет упростить расчет параметров растрирования, уменьшить объем памяти для списка

активных ГПВ и снизить уровень входного потока данных за счет использования общих данных описания ГПВ группой РПЭ при параллельной обработке строк. Разработаны требования к микроархитектуре РПЭ, которая должна обеспечивать прямой расчет параметров правой и левой границ ЛС с последующей интерполяцией вдоль ЛС. Функциональная схема РПЭ с строчным ¿-буфером приведена на рис.5. Число параллельно формируемых строк ГПВ соответствует числу РПЭ. Однонаправленность канала данных загрузки ГПВ из списка активных полигонов в РПЭ обеспечивает простоту управления работой РПС и естественную балансировку нагрузки, обусловленную когерентностью изображения. Разработана упрощенная аналитическая модель оценки производительности параллельной РПС со строчным ¿-буфером, учитывающая скорость обработки входных ГПВ и формирования кодов пикселей.

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

где Тсус - время цикла тактирования систолического конвейера, Р -число ГПВ в сцене, Э - сложность сцены по глубине; Ор1х - число пикселей экрана, А - среднее число пикселей в ГПВ.

Базовой входной командой для СКП является токен линейного сегмента (ТЛС), который описывается параметрами горизонтальной интерполяции. Для каждой строки сканирования должна быть сформирована цепочка ТЛС для всех активных ГПВ. ТЛС формируются путем вертикальной интерполяции ГПВ, основанной на когерентности строк изображения. Таким образом, растрирование может быть разделено на 2 основных процесса: 1) Для каждой строки должны быть сформированы ТЛС, которые вычисляются из данных ГПВ (процесс ТЛС); 2) Для каждой строки должны быть определены все активные ГПВ (процесс активных ГПВ). При этом процесс активных ГПВ является управляющим по отношению к процессу ТЛС. Исходя из требований алгоритма сформулирован общий архитектурный подход к аппаратной реализации РПС с использованием СКП и требования к микроархитектуре ПЭ ТЛС и ПЭ активных ГПВ. На рис.6 представлена архитектура РПС с СКП.

Особенностью СКП является параллельная обработка определенного числа ЛС в массиве процессоров пикселей (ПП). Каждый следующий цикл интерполяции ЛС выполняется в следующем по порядку ПП. При этом сам процесс интерполяции конкретного ЛС начинается только в том ПП, позиция которого соответствует левой Х-координате (XI) ЛС и занимает число циклов, соответствующее длине ЛС. В СКП, вводятся команды трех типов: 1) ТЛС с формуляром ЛС; 2) Пустые токены; 3) Регенерация изображения. Сформулированы требования к микроархитектуре ПП СКП и приведены расчеты по числу коммуникационных выводов СБИС СКП для

а) Для малоразмерных ГПЗ: 7гг1

б) Для крупноразмерных

(9)

Поток формуляров ГПВ с расчитанными параметрами интерполяции

АИ ~ сигнал переключения ребра на промежуточной вершине треугольника.

Адр АП - адрес формуляра ГПВ, активного на текущей строке.

Рис.б. Архитектура РПС с систолическим конвейером процессоров.

Шина Данных

Рис.7. Функциональная схема одного координатного модуля Ы-блока ПЭ Треугольника.

различных форматов формуляра ЛС.

Рассмотрены требования к вычислению в СКП интенсивности Я, в, В для усложненных моделей тонирования и рассмотрена реализация алгоритма "Фаст-ФОНГ". На первой ступени используется РПС с СКП, выполняющая вертикальную и горизонтальную интерполяцию ГПВ с удалением скрытых поверхностей, но без расчета значений интенсивности. Вместо расчета интенсивности линейно интерполируются значения атрибутов пикселей (вектор нормали или произведение векторов). Кроме этого должны быть рассчитаны соответствующие коэффициенты разложения формулы освещенности Фонга в ряд Тейлора. Сформированные таким образом "неосвещенные" ЛС подаются на вторую ступень - конвейер тонирования, состоящий из ПЭ, выполняющих только функции расчета интенсивности. Этот способ обработки определен как пост-тонирование.

Сочетая интерполяцию и уравнение отражения, диффузная составляющая из уравнения Фонга (1) переписывается:

I Ах+Ву+С

1аи» . (х, у )= - * --(10)

|Ц |Ц* | Ах+Ву+С | Вычислением векторных произведений и расширением области векторных величин получено:

ах+Ьу+с

1ди».(х,у)= — — (11)

/ах* +exy+fy2 +дх+11у+1 С использованием предварительно вычисленных значений коэффициентов формула (11) может быть реализована для последовательных значений X и У, что существенно упрощает формулу Фонга, но, однако, деление и извлечение квадратного корня не желательны для использования в системах реального времени. Поэтому используется разложение функции отражения в ряд Тейлора относительно центра треугольника:

1*И*.(х,у)=Т5х2 + Т4ху + Т3уг + Т2Х + Т1у +Т0 (12)

где Т0-Т5 - коэффициенты ряда Тейлора. Аналогичным способом раскладывается зеркальная составляющая. Разработана структура систолического ПЭ для тонирования методом "Фаст-Фонг", обеспечивающего обработку пиксела за 12 циклов тактирования.

В разд.4.5. выполнена разработка двухконвейерной структуры РПС с объектным параллелизмом, включающей конвейер растрирования треугольников и конвейер тонирования. Разработан общий алгоритм функционирования РПС этого типа и этапы предобработки для поддержки конвейерных вычислений. Определен формат входных данных ПЭ Треугольника и разработана его микроархитектура, включающая Х-блок, ¿-блок, Ы-блок, и М-блок. Предложен алгоритм интерполяции, обеспечивающий параллельное растрирование множества треугольников в конвейере ПЭ. Разработаны функциональные схемы блоков ПЭ треугольника. Как пример, на рис.7 приведена схема одного координатного модуля И-блока, обеспечивающего генерацию атрибута нормали. Три таких модуля (Nx.Ny.Nz) используются для интерполяции значений векторов нормалей N в каждом пикселе треугольника. До того, как треугольник становится активным, исходный Ы-вектор, а также Дх и Ду загружаются в блок. По Дх обновляется

Ы-вектор вдоль строки сканирования (С1), тогда как У~инкремент обновляет вектор нормали при переходе на новую строку сканирования (СО). Выходной мультиплексор выбирает локально интерполированный вектор нормали поверхности, если пиксел, поступающий из предшествующего процессора, перекрывается локально-вычисленным пикселом (СЗ) и, следовательно, должен быть заменен; в противном случае входное значение нормали из предшествующего видимого треугольника сохраняется без изменения и проходит к следующему ПЭ треугольников. Таким способом в И-блоке формируются атрибуты только видимых пикселов, необходимые впоследствии для тонирования треугольника. Исследованы режимы работы конвейера ПЭ треугольников, включая случаи переполнения..

Далее рассматривается алгоритмический базис конвейера расчета освещенности (КРО). С учетом предварительных расчетов в конвейере ПЭ треугольников уравнение (1) может быть переписано следующим образом:

К1 *11 *(С1 *ка+Сг*к» ) II *(ка*(М*П+кв*(Р*5)Е"

Ci , Сг - константы, аппроксимирующие произведения векторов (N*L), (R*S), соответственно; kd, ke - предварительно вычисляемые коэффициенты (определяются материалом отражающей поверхности); СГ - константа, аппроксимирующая значение глубины r=Z; коэффициенты Ki и Кг используются для установления соответствия между составляющими и лучшей аппроксимации полной интенсивности отраженного света.

С учетом этого выражения предложена микроархитектура ПЭ тонирования (ПЭТ), приведенная на рис.8. Рассмотрен возможный вариант реализации ПЭТ на основе упрощенного решения уравнения освещенности.

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

Пятая глава посвящена проектированию асинхронных растрирующих подсистем с кадровым буфером. Спецификой их разработки является то, что архитектуру и модификации алгоритма растрирования здесь в первую очередь определяют способы организации параллельного доступа в кадровый буфер (КБ). В разд.5.1. рассматривается модификация общей методики проектирования подсистем ГА для РПС с кадровым буфером с учетом спецификаций стандарта OpenGL. В РПС с КБ в качества базового используется принцип управления входной последовательностью ГПВ, что подразумевает растрирование ГПВ по мере их поступления без какой-либо сортировки. Это должно быть обеспечено возможностью произвольного доступа РПЭ к любой части КБ, соответствующей фрагменту пространства изображения. В РПС этого типа область экранного пространства координат полностью отображается на систему памяти КБ, обеспечивающей хранение и отображение отдельных "окон" из пространства изображения.

Спецификой интерпретации общей схемы проектирования РПС являет-

r + к

Сг

ДАННЫЕ ИЗ КОНВЕЙЕРА ПЭ ТРЕУГОЛЬНИКОВ

N,1.

Регистры данных текущего пиксела Х.У.Г.Н.и.Я.в.М

Л

т

Блок вычисления

произведения

векторов

N1.

Г

Блок вычисления произведения векторов (1=1*8)

Р"

Ив

¥

ИЕ (Х,У)

г-г

БЛОК 1

Ел

Хп

и

БЛОК 2

1Г

я г

БЛОК

3

ТАБ- ТАБ- —1- ТАБ- 1 1 ТАБ- ТАБ- 1 ТАБ- и 1 ТАБ- ТАБ- ТАБ-

ЛИЦА ЛИЦА ЛИЦА И ЛИЦА ЛИЦА ЛИЦА II ЛИЦА ЛИЦА ЛИЦА

1«о 1.8 1*Ы) 1аЬ0 Хюе 1гЯ 1гО 1г В

Ег

Ез

1в

1о

УУЕ

ВЫХОДНОЙ БУФЕР ЛвВ

2-БУФЕР (дополнит)

ДИСПЛЕЙНАЯ ПОДСИСТЕМА

Рис.8. Структурная схема ПЭ тонирования.

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

1) Технология полного кадрового буфера, которая предполагает растрирование/тонирование всех ГПВ и одновременное размещение в память произвольного доступа всех пикселей кадра.

2) Технология виртуального или частичного кадрового буфера, предполагающая растрирование/тонирование ГПВ фрагмента пространства кадра и повторяющая эти операции для полного конструирования кадра.

Рассмотрены общие спецификации и функции КБ, регламентируемые стандартом OpenGL как ресурсы "Кадровый Буфер" и "Обработка фрагментов". Согласно этих спецификаций КБ подразделяется на следующие логические буферы: - буфер цвета R, G, В, А или индексный (в стереова-риантах); - буфер глубины 2; - буфер шаблонов; - буфер-аккумулятор; - дополнительный буфер, рассмотрена регламентация доступа в КБ стандартом OpenGL. Рассмотрены также другие команды OpenGL, регламентирующие работу РПС с КБ. Важной особенностью архитектур с кадровым буфером является возможность смешивания цветов для моделирования прозрачности и генерации сглаженных изображений с использованием значения А (Альфа)-буфера. Это функция реализуется непосредственно при доступе в КБ и требует использования в канале доступа к кадровому буферу в РПС специальных быстродействующих умножителей. Буфер шаблонов обеспечивает простой автомат состояний в каждом пикселе. Варианты использования включают: - рисование по шаблону; - визуализацию силуэтов; - визуализацию плоскостей пересечения полигональных объемных объектов; - интерференция бликов света полигональных объектов; - визуализация конструктивной геометрии сплошных тел для полигональных объектов.

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

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

В разд.5.2. рассмотрено проектирование РПС, использующих рассло-

ение полного КБ. Рассмотрены предельные значения определяемые через минимальное время модификации различных форматов доступа к КБ: для сцен с мелкой детализацией для сцен с крупной детализацией

производительности, полного кадра для

для сцен с мелкой детализацией

Tfг=0*0*Трв, Тгг =Р*А*Тр«,

0*0«Тсуе

Тг г =

Доступ к пикселу

одному (14)

для сцен с крупной детализацией Тгг =

для сцен с мелкой детализацией

Tf г-

вм пг Р*А*Тс у с

в! I п^ 0*0*Тсус веч г

Р*А*Тс у с

(15)

Доступ к линейному фрагменту пикселей

(16)

(17)

Доступ к прямоуг. фрагменту пикселей

(18)

для сцен с крупной детализацией Тгг= -

Бед!

Для расчетов коэффициентов ускорения Бмпг, была разработана

специальная программа моделирования доступа в КБ.

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

Вариант доступа Один пиксел Линейный Квадратный

Слово Пиксел Слово Пиксел

Формат доступа 1 X 1 16 х 1 16 х 1 4x4 4x4

Время цикла Тсус 250нс 250 не 250 не 250нс 250 НС

Число полиг./с Больших (32x32) Малых (8x8) 4 К 62 К 43 К 390 К 62 К 500 К 52 К 562 К 62 К 1000 К

Общая эффек-ть

записи

Размер Пиксел/

блока цикл

1 х 1 0.69

2 х 1 1.04

2x2 1.57

4 х 1 1.41

4x2 2.22

4x4 3.10

8X4 4.04

8x8 5.27

Таблица 26. Эффективность различных параллельных архитектур записи.

С учетом расслоенной структуры КБ, обеспечивающей параллельный линейный доступ, растрирование ГПВ разделяется на четыре этапа:

1. Полигоны должны быть раздроблены на трапеции с вертикальными правыми и левыми границами (процесс обработки полигона).

2. Трапеции разделяются на вертикальные линейные сегменты единичной ширины (ЛС) (процесс обработки ребер или границ).

3. Отдельные ЛС растрируются (процесс обработки ЛС).

4. Вычисленные значения пикселей передаются на пиксельные процессоры (ПП) для записи в кадровый буфер с учетом значений г и Альфа (процесс доступа в КБ).

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

расслоением памяти:

Ttot=P«T.u + Tfr

(13)

В случае временного перекрытия всех трех ступеней, что реализовано в аналогичных системах:

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

Трехуровневая структура РПС с расслоением КБ, представлена на рис.9. Особенностью структуры является использование мультипроцессора КБ, содержащего 20 ПЭ КБ, каждый из которых имеет доступ к 1/20 части памяти кадрового буфера.

Каждый из 20 ПКБ должен включать в свою структуру АЛУ и умножитель для й(А) -смешивания. Каждый из ПКБ реализует следующее уравнение:

Командами OpenGL задаются компоненты для смешивания из следующего списка:

Fere:= О, 1, й«ге , 1- Йягс , 0L<S»\ , 1- C(d»t, Cd»t, 1-Cd«t Fa » t : = 0, 1, Йягс, 1-йшгс, Oicje t , 1-Cld»t, C»rc, 1 -Cire Понятия источник (src) и приемник (dst) относятся к входящему и текущему значению кода пиксела.

Исследована возможность реализации однокристальной СБИС РПС. Учитывая необходимость упрощения функциональной структуры, необходимо вывести из состава РПС ПЭ полигонов, обеспечивающий вычисления параметров наклона. Эти расчеты, учитывая их вычислительную сложность, можно выполнять на последнем этапе обработки в ГПС. Параллельные ГПС классов SIMD и MIMD без особых проблем обеспечивают решение этих задач с максимальной точностью, обеспечивая балансировку загрузки. Кроме того, учитывая сложность реализации моделей тонирования по произведениям векторов и Фонгу в одной СБИС с РПС, необходимо ограничиться простой моделью Гуро с Z-буфером.

Микроконвейеризация обработки в РПС выбрана в качестве наиболее эффективного решения. Выбор общего числа ступеней микроконвейера и числа шин памяти для СБИС РПС является рекурсивным процессом и зависит от технологических ограничений СБИС. Для достижения максимального темпа закраски пикселей, конвейер растрирования должен поддерживать темп генерации пикселей в к раз больший, чем пропускная способность VRAM в страничном режиме, где к - число используемых шин памяти (банков памяти). С учетом пятислойного буфера RGB, тактовая частота работы микроконвейера должна быть в 5 раз выше частоты страничного доступа в VRAM, при допущении, что каждый цикл генерируется код пиксела. Наиболее медленным элементом микроконвейера РПС являются блоки линейных интерполяторов. Общий цикл конвейера для пятислойного кадрового буфера определяет число ступеней конвейера в РПС. Разработана структурная схема микроконвейерной СБИС РПС, имеющей 2в ступе-

(20)

Cdst:= Fare"Cere + Fd»t*Cdst

(21)

Преобразованные ГПВ из ГПС

Рис. 9. Макроархитектура трехуровневой РПС с расслоением КБ.

ней конвейера, в котором вычисляются параметры интерполяции треугольника до момента записи в кадровый буфер. Предусматривается использование двух контроллеров памяти на два раздельных порта памяти. Это вызвано различным условием расслоения, RGB-буфер использует 5 слоев, а Z-буфер использует 10 слоев. Такой подход необходим для уравнивания скорости работы RGB-буфера и Z-буфера. Так как Z-буфер требует двух доступов (чтение и запись), он должен иметь скорость работы вдвое выше. При использовании одного и того же типа VRAM это может быть обеспечено только вдвое большим расслоением. Возможно использование двух СБИС РПС, растрирующих четные и нечетные строки одного ГПВ. РПС с расслоением КБ позволяют наиболее эффективно решить проблему использования серийных VRAM для поддержки параллельного доступа процессоров ЛС в кадровый буфер. Учитывая технологические ограничения в быстродействии VRAM и технически приемлемый уровень расслоения (5-10), предельная производительность может достигать 80 млн. пикселей/сек и примерно 0,6 *0,8 млн. треугольников/сек.

В разд.5.3. рассматривается проектирование РПС с использованием КЭШ-ЗУ пикселей. Высокая степень локальности обращений к КБ в процессе растрирования и порождает идею использования КЭШ-ЗУ пикселей для разработки быстродействующих РПС, использующих мультипроцессор для обработки кодов пикселей в КЭШ-ЗУ. Если для архитектур с расслоением памяти в формуле (17) используется длительность цикла динамической памяти VRAM, то для случая использования быстродействующей КЭШ-памяти длительность цикла на порядок меньше и составляет около 15-25 не. В РПС с КЭШ-ЗУ пикселей (КЗП) растрирующий процессор (РП) выполняет все вычисления, связанные с обработкой пикселей, непосредственно в КЗП и размещает их в виртуальном кадровом буфере, который может являться также частью основной памяти ГС.

Команды, поступающие из ГПС, интерпретируются трехуровневой РПС. Общая архитектура мультипроцессора включает в себя 3 независимых процессора, работающих в конвейерном режиме: - Процессор расчета параметров (ПРП); - Адресный процессор (АП); - Блочный SIMD-процес-сор пикселей - SIMD-ПП (16 процессоров пикселей).

ПРП выполняет инициализацию и предварительный расчет параметров для растрируемых ГПВ и посылает команды и данные в другие процессоры. АП определяет покрытие ГПВ блоками 4x4 пикселей и последовательно загружает в КЗП все эти блоки, обеспечивая расчет кодов пикселей в КЗП соответствующими SIMD-ПП, и последующую запись в виртуальный кадровый буфер. SIMD-ПП решает уравнения границ для ГПВ, вычисляет значение интенсивности пикселей по принятой модели тонирования, Z-координаты и выполняет сравнение по глубине. Разработаны требования к микроархитектуре процессорного ядра, ПРП, АП, SIMD-ПП.

Для моделирования работы трехуровневой РПС рассмотренного типа была разработана специальная программа, включающая: Блок "Setup Engine" (моделирует работу ПРП); Блок "Address Engine" (моделирует работу АП); Блок "Pixel Engine" (моделирует работу SIMD-ПП).

Спецификой работы мультипроцессорной РПС с КЗП является необходимость прохода по растрируемому треугольнику блоками (например

4x4). При этом, часть пикселей не будет обрабатываться, а соответствующие ПП будут простаивать. Для 100-пиксельных треугольников такого рода холостой ход будет составлять 40-50Х.

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

/Q*D*Tcyc»Wpi* Q*D«Tca«h*Wpi* Q«D»Tpp*Vpp \

Trг =max <- ; - ; - > (22)

4 S.qt»Wvbuf Wc.eh'N'p Np(1+ P) '

где Wpix - число бит в коде пиксела; Wvbuf - ширина доступа из КЗП в виртуальный КБ; Тс»«ь - цикл доступа к КЗП; Wс«.м - ширина доступа в КЗП для блочного ПП; Трр - цикл работы блочного ПП; Vрр - число циклов ПП, необходимых для обработки одного пиксела (5 +50 циклов в зависимости от алгоритма тонирования); Np - число SIMD-процессоров в блоке ПП; N'P - число SIMD-процессоров, имеющих параллельный доступ в КЗП; р- коэффициент холостого хода (0,4 *0,5).

В случае генерации ГПВ большой площади (более 32x32 пикселей) выражение для минимального времени генерации кадра принимает вид: /Р*А*Тсус*Wpiх P*A»Tc«.h»Wpi* P*A*Tpp*Vpp \

Tf г =max <- ; - ; - > (23)

V S.q**Wvbuf Wcaeh*N'p Np(1+ p) '

где P - число ГПВ в сцене; А - среднее число пикселей в ГПВ, р- коэффициент холостого хода (0,1 +0,15).

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

В разд.5.4.1. выполнен анализ и разработаны рекомендации к проектированию РПС, использующих пространственный параллелизм. Базовой структурой, обеспечивающей этот вид параллелизма является структуры типа Pixel Planes, первичной идеей которых было создание большой вычислительной поверхности из SIMO процессоров, обрабатывающих все экранное пространство одновременно. Учитывая размер изображения 1280x1024 необходимо иметь 1 миллион 310720 таких процессоров, что не является приемлемым со стоимостной и технологической точки зрения. Выходом является использование одной или более SIMD-структур, обрабатывающих отдельные небольшие (128x128) фрагменты в виртуальном пространстве экрана. Виртуальные фрагменты могут быть соотнесены с любым из реальных фрагментов кадра в ходе обработки. Основной проблемой, возникающей с разделением экранного пространства, является необходимость сортировки ГПВ по групповым спискам. Таким образом сцена может растрироваться путем назначения и передачи региональных списков на один или более РПЭ типа SIMD (РП-SIMD). При этом производится диспетчеризация доступа РП-SIMD к групповым спискам с целью последовательного формирования полного кадра. Экран форматом 4280x1024 разделяется на 80 регионов форматом 128x128 пикселей каж-

дый. Такой подход позволяет использовать разное число РП-SIMD и дает возможность линейно варьировать соотношение стоимость/производительность. Как образец для анализа выбрана система Pixel Planes 5, в состав которой входят: - группа геометрических процессоров. (ГП), обеспечивающих обработку с ПЗ и имеющие значительный внутренний объем кода и памяти данных (МПС типа MIMO); - Растрирующие ПЭ типа SIMD (РПЭ-SIMD), каждый имеет небольшой 128x128 массив SIMD процессоров пикселей; - Сдвоенный кадровый буфер на СБИС VRAM; - Интерфейс к базовой UNIX станции; - Кольцевая сеть для межсоединений.

Главной спецификой данной архитектуры РПС является использование в РПЭ специализированной СБИС памяти с дополнительной логикой. В дополнение к 256 ПЭ пикселей (с памятью на 208 бит), СБИС содержит устройство решения квадратичного уравнения (QEE), которое рассчитывает значение выражения Ахг+Bx+C+Dx2+Exy+Fy2 одновременно для каждого пиксела с позицией [х,у]. Квадратичные выражения, хотя не вполне соответствуют растрированию полигонов, удобны для растрирования криволинейных поверхностей и вычисления сферической модели излучатель-ности. Структура РПЭ-SIMD приведена на рис.10.

Рассмотрены основные шаги процесса визуализации в РПС с пространственным параллелизмом и способы управления всеми типами ПЭ в РПС.

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

T=max{Ti,Т2}; (24)

/■300*Р*Трр«(1+р' ) N9*P»Vpr*(1+p')+M**Vpix*Nr Nr Wn«

f300*P*Tpp«(1+p') N9*P*Vpr*(1+p )+M**VpIx *Nr 4

где: Ti = - + --J

x Nr '

P*(Teort+p'*Tclip)

Тг =

Ne

где Трр - цикл работы процессора РП-SIMD; р' - коэффициент клиппиро-вания ГПВ по границе региона; Nr - число РП-SIMD в системе; МхМ -размерность региона экрана, обрабатываемого РП-SIMD; Ng - число ГП в системе; Vpr - число бит в формуляра ГПВ; Vpix - число бит в пикселе; Те о г t - время на сортировку ГПВ; Тсмр - время на клиппирова-ние ГПВ ( определяется по операторным моделям). При пост-тонировании добавляется время обработки кадра по модели Фонга.

В разд.5.4.2. выполнен анализ построения композитных архитектур РПС, реализующих пространственный и структурный параллелизм.

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

QBE

Массив 128 АЛУ

Первичная видеопамять 128 пикселей на 208 бит

Контроллер управления растрированием

#57

Узел сети

* 1 I» 2

ЕЗ

* 8

SIMO массив ПП

8x8 СБИС

»64

Вторичная видеопамять VRAM

8М байт 4К бит/пиксель

Узел сети

Рис.10. Структура растрирукмцего процессора pn-SIMD в системе Pixel Planes 5.

КБ от основной ЭВМ

Рис.11. Реализация композитной архитектуры в системе Pixel Flow.

Wco«p=m«n*S.»p*(Vpxi+Z.)*Fd (25)

где m*n - формат кадра, Se«P- число дискрет на пиксел, Vpxi и Z. -число бит в пикселе на RGB (или атрибуты) и Z-координату.

Генерация тонированного по Гуро супердискретного изображения с высоким разрешением и частотой 30 Гц требует полосы пропускания шириной по крайней мере:

Wco«p=1280x1024*5 дискр/пиксел*48 бит/дискр*30 кадр/с = 9,4 Гбит/с

Использование алгоритмов пост-тонирования требует в 2 или 3 раза большей полосы пропускания, из-за необходимости объединения в коде пиксела атрибутов nX, nY, nZ, RGBi, атрибутов затенения и прозрачности.

Конструктивное размещение модулей РПС определяет реализацию конвейерной сети композиции изображений. Эта сеть может быть распределена путем включения блока композиции на каждую плату с последующим соединением по иерархической цепи. В качестве РПЭ здесь используется Рендер-Процессор (РнП) на основе СБИС ЗУ типа EMC Pixel Flow. РнП может растрировать 1 миллион треугольников/с и обеспечивает композицию изображения с полосой до 30 Гбит/с. При этом используется 64 заказных СБИС памяти и один заказной СБИС-контроллер. На рис.11 приведена архитектура композитной РПС. Каждый РнП содержит только 128x128 ПЭ пикселей и может генерировать полный кадр 1024x1280 за 80 шагов. Проблемы балансировки загрузки при подразделении экрана на регионы решаются за счет обеспечения буферирования некоторого числа регионов внутри СБИС PixelFlow EMC.

Алгоритмы пост-тонирования (Фонг, произведения векторов, процедурное и табличное текстурирование) выполняются на специальных ПЭ тонирования (ПЭТ), размещенных непосредственно перед общим кадровым буфером. Регионы пикселей, содержащих атрибуты (такие как присущий цвет, нормали к поверхности и координаты текстуры), растрируются на РнП, объединяются сетью композиции изображения и загружаются в ПЭТ. ПЭТ обрабатывают регионы параллельно, преобразуя коды атрибутов пикселей в конечное значение RGB, смешивают множество дискрет вместе для сглаживания и пересылают конечное значение цвета в кадровый буфер. Регионы связываются с ПЭТ по циклическому принципу. Число требуемых ПЭТ зависит только от алгоритма тонирования, но не от числа ГПВ, так как число обрабатываемых пикселей определяется форматом изображения. SIMD-реализация ПЭТ позволяет выполнять тонирование для всех пикселей региона одновременно. Таким образом, ПЭТ могут быть просто разработаны на основе РнП с небольшой доработкой блоков композиции на ЕМС для двунаправленных передач данных между сетью композиции изображений и ЕМС-памятью. ПЭТ могут быть оснащены дополнительным аппаратным блоком для вычисления табличных текстур в дополнение к процедурным.

Рассматривается архитектура РнП, главными его компонентами являются: - Арифметический процессор (АрП) на базе RISC-процессора i860ХР обработки с ПЗ в состав которого включено 8 MB VRAM, используемой как основная память, и как большой буфер FIFO для подачи команд в РПЭ с последовательного порта. РПЭ использует массив 128x128

SIMD-процессоров, реализованных в 64 Pixel Flow EMC СБИС. Каждая СБИС EMC построена на принципе аналогичных разработок Pixel Planes и использует линейное или квадратичное выражение для каждого ЛЗ пикселей. Управляющий алгоритм визуализации включает 4 основных шага:

1) АрП в каждом РнП преобразует свою долю ГПВ сцены и сортирует их на регионы экрана 128x128 пикселей;

2) Растрирующий блок РнП вычисляет значения пикселей для всех ГПВ и для одной дискреты аппертуры сглаживания;

3) Когда все РнП завершат шаг (2), для региона производится композиция изображения на сети и размещается в одном из ПЭТ;

4) Шаги (2) и (3) повторяются для каждой дискреты и для каждого региона экрана. При этом возможна их конвейеризация.

Производительность композитных РПС определяется 4-мя базовыми параметрами:

- Полоса сети композиции Тсоир(тах_33,8 Сбит/с, геа!_30 вбит/с);

- Производительность АрП Tgeo» (150 тысяч треуг/с);

- Производительность РПЭ Tr««t ( 64*EMC - 1,4 млн. треуг/с по Гуро, и 0,8 млн треуг/с по Фонгу или твкстурируемых, масштабируется числом дискрет/пиксел);

- Производительность тонирования Tehads (Один ПЭТ - 10,000 регионов/с размером 128x128 пикселей, Mip-map текстуры для 3700 регионов/с

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

Q г • 9

Tfг =£ max(Trndi , Тсоир, Teh/ N»h) (26)

i а 1

где Trndi = max(Tg.o«I,Тг»«tI) - время растрирования для региона i может быть определено по формуле (26); Тсояр - время композиции для региона, определяемое как: Тсошр= М2 * (Ppxi+Z*)/ Wco»P,

где М - размер фрагмента; T»h - время тонирования региона (примерно 270 мкс для модели Фонга и текстурирования); N»h - число процессоров тонирования; Qr»s - число регионов изображения в полном кадре.

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

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

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

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

В разд.6.1. рассматривается новый класс кривых порождаемых регулярными вычислительными структурами, состоящими из блоков интерполяции. В качестве отправного пункта выполнено обобщение алгоритма Брезенхема для генерации векторов в многомерном пространстве. Генератор одномерных векторов определен как линейный интерполятор (1D ЛИ). Начальная инициализация 1D ЛИ выполняется известными соотношениями для алгоритма Брезенхема. Аналитически работу 1D ЛИ можно описать следующей формулой:

А(t )=Ао +Ао11; t [0,1], (27)

где Aoi=Ai-Ao - приращение координат вектора AoAi .

Коническая дуга, вписанная в произвольный треугольник Ао Ai Аг, может быть задана параметрической формулой:

Х( X) , Y( t) х

А( X )=Ао +Ао 1 *- + Alz* 1--I (28)

R 4 R 7

где Х( t), Y( X) - выпуклая симметричная кривая, вписанная в квадрат со стороной R и удовлетворяющая следующим граничным условиям:

Х( tB)=Y( X, )=Х'( tr)=Y'( t,)=0; Y( X. )=Х( tf )=R, (29) где tf te, Xf] - параметр, изменяющийся от начального Хя до конечного tf значения. Если в качестве Х( X), Y( X) взять кривую второго порядка, то принимая во внимание граничные условия (29), получаем уравнение, описывающее коническую кривую Х( X), Y( X):

n(X2+Y2)-2mXY+2mR(X+Y)-(2m+n)R2 =0 (30)

Отношение m/n имеет смысл эксцентриситета конической кривой (30). Предложен алгоритм, ориентированный на его реализацию в регулярной структуре из кругового и линейного интерполяторов. Этот алгоритм определяет работу конического интерполятора (КИ). Для начальной инициализации КИ, его параметры должны получить следующие значения: U=4n=2m; V=U-4R(n+m); D=(n+m)(1-2R); K1=4r>; K2=4m. KU выполняет генерацию дуги (30) за 2R итераций, независимо от вида дуги (эллиптической при d<1/2, параболической при 0=1/2 или гиперболической при Й>1/2). Предложенный алгоритм КИ является устойчивым в отличив от известного алгоритма Питтвея. Параметрические функции Х( X), Y( t) могут быть выражены в явном виде. Однако параметр X в процессе ее генерации неизвестен, а известно количество

выполненных интерполятором итераций 1. Показано, что положение текущих координат кривой (30) можно выразить через число выполненных КИ итераций. Обозначим:

Х( Т) у( ■€) Х( •£) + У( X)

х( -С)= - ; у( Т)=1--: и "С)=- . (31)

Я Я 2

Для кривых второго порядка возможно получить аналитическое выражение х(г),у(1), причем 1=т/2В линейно зависит от числа итераций 1, Принимая во внимание, что на каждой итерации КИ вырабатывает единичные управляющие посылки Е*, €у :

£х!П ЕХН1 с!А(=Ао1- + Аи- , (32)

гн 2н

где йА| - приращение кривой (28), получаемое при выполнении т-той итерации КИ.

Генератор конических дуг можно представить в виде двухуровневой вычислительной структуры, верхний уровень которой состоит из управляющего КИ, а нижний уровень из двух многомерных линейных интерполяторов, выполняющих генерацию векторов А0А1 и А1Аг, рис.12а. Работа вычислительной структуры из КИ и двух ЛИ аналитически описывается формулой:

А(и=Ао+Ао1Х(1:)+А1гу(0 (33)

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

А(и=Ао+Ао1 Ф1 (г )+А1 г фгШ+Агг ФзШ+Аз4 Ф<(0, (34) где ЧЧ т=хг(х, (1:)), Фг(г)=уг(х1 И)), <Рэ(-0=ха(у1 (П)

<р«т=уэ(у1т), ФИО, ч>гт, Фз(1), ф^т, 1 [0,1] Такие кривые не имеют общепринятого названия и названы лекальными кривыми. Предлагается единая методика синтеза алгоритмов и вычислительных структур геометрически заданных кривых. Предлагаемый подход состоит в том, создав некоторую структуру, составленную из КИ и ЛИ, исследовать класс кривых, которые будет порождать данная структура. Этот подход отличается от традиционного, когда вычислительная структура рализовывалась исходя из аналитического описания кривой. Генератор конических дуг в ЗР пространстве состоит из одного КИ и шести ЛИ , а генератор лекальных кривых (рисунок 126) состоит из трех КИ и 12 ЛИ и так далее. Регулярный характер вычислительных структур, построенных из ЛИ и КИ делает удобным реализацию предлагаемых структур в виде СБИС. Форма лекальной кривой определяется положением вершин управляющего многоугольника и тремя эксцентриситетами (или коэффициентами С(), задающими режим работы КИ. Лекальные кривые могут использоваться для геометрического проектирования непосредственно, в интерактивном режиме, аналогично использованию, например, кривых Безье. При этом, с точки зрения гибкости управления формой кривой, они превосходят кривые Безье.

(а)

Summer

(б)

Рис.12, а) Функциональная схема генератора конических дуг.

б) Функциональная схема генератора лекальных кривых. Показано использование генератора лекальных кривых для генерации кривых Безье и параметрических сплайнов. Если все КИ генератора лекальных кривых настроить на параболический режим, то, согласно (34), параболическая лекальная кривая будет представлять собой степенной полином четвертой степени. Однако кривая Безье также может быть представлена в виде степенного полинома:

4 * к

РШ= Е(-1 )кС4*Рк(1--(:)-,-''1:,'= Е(-1 )*С4|Ч,< £(-1)'Ск'Р| (35) к=о к=о ¡«о

где Р| - управляющие точки кривой Безье (т=0,...,4), к!

Ск----биномиальный коэффициент, 4 - степень рассматриваете к- т ) ! мого полинома. Пересчет управляющих точек кривой Безье в набор точек эквивалентной ей лекальной кривой выполняется матричным преобразованием.

(Ао1,А12,Агз,Аз4)т=бз4(Ро1,Р1г,Ргз)т; (36)

(Ао 1 , А1 г , Аг з , Аз 4 )т =в4 4 (Ро 1 , Р1 г , Рг з , Рз 4 )т ; (37)

где Аи - сторона управляющего многоугольника лекальной кривой, Р! j сторона управляющего многоугольника кривой Безье, "т" - операция

транспонирования вектора-строки в вектор-столбец. Gs4, G*< - матрицы соответствующие полиномам Безье 3-й и 4-й степеней.

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

В разд 6.2 рассматриваются алгоритмы визуализации криволинейных фрагментов поверхности, использующие в своей основе разработанную технологию генерации лекальных кривых. Предложен новый метод тонирования поверхности с использованием нелинейной интерполяции интенсив-ностей R, G, В для тонировании крупных криволинейных кусков поверхности без их предварительного разбиения на полигоны. Получаемые с помощью различных методов куски Кунса, Безье и В-сплайны соответствуют различным формам задания кусочнополиномиальной функции, а управляющие точки и векторы этих форм могут быть пересчитаны друг в друга посредством матричного преобразования. Используя аппаратно-ре-ализованный генератор лекальных кривых в 6D пространстве (X,Y,Z,R,G,B), можно обеспечить прямое тонирования кусков Безье.

Аналитически кусок Безье задается формулой:

■ п

P»,n(u,V)=£ EpiJ С«1CnJ (1-U)"-1U1 (1-v)"-i vi (38)

I ж о J a о

где Pi j - координаты управляющих вершин куска Безье в 6D пространстве (X,Y,Z,R,G,B); u,v [0,1]. Преобразуем (38) б вид:

п

p(u,v)= Eai(V)C.'(1~u)"-'u' (39)

i в 0

где

п

Ai (v)= EPtjCnJ(1-v)"-JvJ; i = (0...m) (40)

i =o

Для каждого значения параметра v [0,1] формула (40) позволяет рассчитать положение т+1 управляющих точек семейства кривых Безье (39). Из (38) и (39) видно, что проблема тонирования куска Безье (38) может быть сведена к генерации семейства кривых Безье (39).

Формула (40) задает m-И кривых Безье, текущие точки которых являются управляющими вершинами кривой Безье (39). Для расчета этих точек также можно использовать алгоритм растрирования лекальных кривых. Разработаны моделирующие программы тонирования куска Безье.

Более сложно обеспечивается растрирование трехсторонних кусков Безье. Для задания трехсторонних кусков можно предложить аналитическую формулу аналогичную (38), а для расчета произвольной точки трехстороннего куска Безье можно использовать следующий алгоритм: for (1 = 1 ; K=m; 1++) { for (j=0; j<=m-4; j++) {

for (i =0; i<= m-l-j; i++) {

к = m—1 — 1—j;

} > >

где m - степень куска Беэье ; Р - управляющие точки куска Беэье ; u,v,w е [0,1] (u+v+w=1) - параметры, задающие бариоцентрические координаты точки. Этот алгоритм реализует вычисление степенного полинома вида:

i + j s ■

Рк (u,v) = Е ECÍJU'vJ (41)

i . j =o

где набор коэффициентов <Ci j> можно получить из набора <Рij k t о j > пользуясь приведенным выше алгоритмом. Например для куска второй степени имеют место следующие соотношения (т=2):

Соо=Роог; Со i=2(Ро 11-Роо г);

Ci о =2 (Pi о 1 -Ро о г ); Ct i =2 (Pi 1 о -Ро 11 -Pi о i +Ро о г );

Со 2 =Ро г о -2Ро 11 +Ро о г ; Сго =Рг о о -2Р» о t +Ро о г .

Четырехсторонний кусок (38) также можно представить в виде степенного полинома:

я я

P»,n(u,v)=E Ec'nu'vJ, (42)

i а О J = О

где коэффициенты <C'tj> могут быть найдены непосредственно из формулы (38). Приравнивая коэффициенты при одинаковых степенях u'vJ, из условия P«,n(u,v) sP«(u,v) находятся соотношения между управляющими точками <Pijk> трехстороннего куска Безье и управляющими точками <Ai|>, эквивалентного ему в области u+v [0,1], четырехстороннего куска Беэье (42). В матричной форме соотношениее выглядит:

<A>=G£«l<Р>, (43)

где <Р> - вектор столбец управляющих вершин трехстороннего куска Безье; <А> - вектор столбец управляющих вершин четырехстороннего куска Безье , эквивалентного исходному трехстороннему куску в области их совмещения (u+v [0,1]).

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

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

ХН = ~Хн + Хн * 2"»; YH = ~Yh + Yh * 2""; (44)

Хк = ~Хк + Хк * 2"»; Yk = ~Yk + Yk * 2'"; (45)

где: (Xh,Yh) - координаты начала вектора; (Xk,Yk) - координаты конца вектора; значком помечены целые значения координат; значком "-" помечены дробные значения координат сдвинутые на ш разрядов влево; m - разрядность дробной части.

Уравнение прямой проходящей через две точки с координатами (Хн,Ун) и (Xk,Yk) преобразовывается в следующий вид:

V

Y(X) = YO + - * X, (46)

U

где: X - [0,~Хк - ~Хн]; Y - [0,~Yk - ~Yh];

и = ^(Хк - Хн)*2^; V = ^(Ук - Yн)*2■j; 1

УО = - ( Ун * и - Хн » V )*2'«

и

Наличие ненулевого члена УО в уравнении линии (46) составляет отличие предлагаемой расчетной модели от классической.

В качестве целевой функции берется разность расстояний от прямой до смежных пикселов 0т=81-"П:

01 = 2 * УШ + 1) - 2»У1 - 1. (47)

С учетом (46) оно приводится к виду:

01 = 00 + 2*У»Х1 - 2*и*У1, (48)

где 00 = 2*У - и + 2*и*У0. Значение целевой функции От меняется при переходе к каждому следующему пикселу. Внутренний цикл алгоритма полностью идентичен классическому алгоритму Бреэенхема. Введение субпиксельного представления координат обеспечивает коррекцию начального значения целевой функции.

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

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОНОЙ РАБОТЫ.

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

2. Разработаны и исследованы способы аппаратной реализации функциональных спецификаций международных графических стандартов PHIGS+/PEX и OpenGL. Выделены и классифицированы группы функций стандартов, определяющих аппаратную реализацию подсистем акселератора и разработаны базовые операторные модели, являющиеся основой для отображения стандартизованных функций обработки и управления на отдельные процессорные элементы и мультипроцессорные структуры в целом.

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

4. В рамках детализации методики проектирования выполнена разработка и исследование конвейерных и параллельных геометрических подсистем, соответствующих спецификациям графических стандартов PHIGS+/PEX и OpenGL. Разработаны методы оценки производительности, балансировки загрузки и определены требования к микроархитектуре процессорных злементов.

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

6. Разработаны основные концепции проектирования РПС, базирующихся на использовании кадрового буфера. В рамках детализации концепций исследованы проблемы проектирования мультипроцессорных РПС, использующих расслоение памяти, КЭШ-ЗУ пикселей и виртуальные раст-рирующие процессоры, интегрированные в СБИС ЗУ кадрового буфера. Разработаны рекомендации по разработке РПС с заданными набором функций и параметрами производительностии и предложены аналитические методы предварительной оценки параметров РПС.

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

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

9. Результаты исследований и разработок использованы при проектировании СБИС графического процессора К1809 ВГ4 в КТБ АО "СВЕТЛАНА" и семейства графических контроллеров GLX на основе этой СБИС, специальной графической системы для КБ завода "РОССИЯ", специальных графических контроллеров для НИИ Авиационного оборудования, графического сопроцессора "Галета 1,2" в КТБ АО "СВЕТЛАНА".

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

1. Палташев Т.Т., Платунов А.Е., Скорубский В.И. Мультисистема с графическими возможностями. //Материалы Всесоюзной конференции "Микропроцессорные системы". - Челябинск, 16-19 мая 1984, стр.28-29.

2. Палташев Т.Т. Микропроцессорная система управления растровым графическим терминалом. //Тезисы докладов I Республиканской науч^® но~технической конференции "Применение микропроцессоров в народном хозяйстве". - Фрунзе, 1985, стр.27-29.

3. Палташев Т.Т., Стародубцев Э.В. Распараллеливание процесса генерации графических примитивов в растровых видеотерминалах. //Тезисы докладов II Всесоюзной конференции "Методы и средства обработки сложной графической информации". - Горький, 1985, стр.66-67.

4. Палташев Т.Т. Система представления и генерации графических образов. //Тезисы докладов II Всесоюзной конференции "Методы и средства обработки сложной графической информации". - Горький, 1985, стр.127-129.

5. Палташев Т.Т., Стародубцев Э.В. Управление формированием изображений в растровых графических терминалах. //Зарубежная радиоэлектроника. - 1985, N10, стр.56-80.

6. Палташев Т.Т., Скорубский В.И., Шендриков И.А. Структура аппаратных и программных средств интерактивной САПР для персональных микро-ЭВМ. //Материалы семинара "Программное обеспечение и применение микропроцессорных систем и устройств". - МДНТП, Москва, 1986, стр.102-106.

7. Палташев Т.Т. Генерация изображений в растровом графическом терминале. //"Известия ВУЗов СССР - Приборостроение", т.XXIX, 1986, N7, стр.33-38.

8. Палташев Т.Т., Смирнов И.Б., Стародубцев Э.В., Шендриков И.А. Графический контроллер на основе специализированной БИС. //Тезисы докладов IV Всесоюзной конференции по проблемам машинной графики. - Протвино, 9-11 сентября, 1987. - Серпухов, 1987, стр.47.

9. Палташев Т.Т., Смирнов И.Б., Стародубцев Э.В. Алгоритмы формирования простых фигур в растровых графических видеотерминалах. //"Известия ВУЗов СССР - Приборостроение", т.XXX, 1987, N9, стр.45-50.

10. Палташев Т.Т. Анализ производительности канала интерактивного графического вывода. //Тезисы докладов Всесоюзной конференции "Методы и средства обработки сложной графической информации". Горький, 1988, стр.168-169.

11. Палташев Т.Т., Лях A.C. Реализация графического контроллера на основе специализированной БИС. //Тезисы докладов Всесоюзной конференции "Методы и средства обработки сложной графической информации". - Горький, 1988, стр.169-170.

12. Палташев Т.Т., Гафуров Н.Т., Рахматулин O.A., Федоренко А.К. Развитие графических контроллеров на основе БИС К 1809 ВГ4. //Тезисы докладов к зональному семинару "Применение машинной графики в моделировании и обучающих системах". - Пенза, 18-19 октября 1989, стр.25-27.

13. Палташев Т.Т., Лях A.C. Эволюция специализированных СБИС для управления растровыми графическими видеотерминалами. //Тезисы докладов к зональному семинару "Применение машинной графики в моделировании и обучающих системах". - Пенза, 18-19 октября 1989, стр.67-69.

14. Палташев Т.Т., Смирнов И.Б., Стародубцев Э.В. Оценка производительности канала вывода в проектируемых графических видеотерминалах. //"Известия ВУЗов СССР - Приборостроение", т.XXXII, 1989, N12, стр.39-44.

15. Палташев Т.т., Рахматулин O.A. Графический сопроцессор для рабочих станций и ПЭВМ.//Микропроцессорные средства и системы. 1990.- N3-4, стр.10-14.

16

17

1в

19

20

21

22

23

24

25

26

27

28

29

30

Палташев Т.Т., Гафуров Н.Т., Рахматулин O.A., Ю Вл.К. Развитие специализированной элементной базы для управления растровыми графическими видеотерминалами // Зарубежная радиоэлектроника. 1990.- N5, стр.31-38.

Палташев Т.Т., Шляхтин В.В. Стандартизация графических средств высокого разрешения для ПЭВМ. //Урал-Информатика. - 1991. - N1, стр.31-33.

Палташев Т.Т., Гафуров Н.Т., Рахматулин O.A., Ю Вл.К. Графические процессоры фирмы TEXAS INSTRUMENTS. //Зарубежная. Радиоэлектроника. - 1991, - N3, стр.73-81.

Палташев Т.Т., Смирнов И.Б., Стародубцев Э.В. Круговой интерполятор. //Авторское свидетельство N1665341, 22 марта 1991, G05B 19/18. //Б.И. N27 от 23.07.91 года.

Палташев Т.Т., Климина С.И., Ю Вл.К. Технология визуализации в компьютерном синтезе реалистичных изображений.//Зарубежная радиоэлектроника - 1991. - N6, стр.96-108.

Палташев Т.Т., Климина С.И., Шендриков И.А. Инструментальная Форт-система программирования графического процессора.// Методы и средства обработки сложной графической информации: Тезисы докладов IV Всесоюзной конференции. - Н.Новгород, сентябрь 1991, стр.86-87.

Палташев Т.Т., Климина С,И. Растрирование и распределенная обработка в системах генерации реалистичных изображений. // Зарубежная радиоэлектроника. - 1992, - N11, стр.3-22.

Палташев Т.Т., Чириков C.B. Генерация лекальных кривых в растровых графических видеотерминалах. //Тезисы докладов 2-ой Международной Конференции по Компьютерной Графике и Визуализации ГРАФИ-КОН'92. - Москва, сентябрь 1992, стр.48-50.

Палташев Т.Т., Шляхтин В.В. Основные тенденции в стандартизации средств графического интерфейса для ПЭВМ. // Зарубежная радиоэлектроника. - 1993. - N1, стр.68-73.

Палташев Т.Т., Смирнов И.Б., Стародубцев Э.В. Метод оценки параметров видеопамяти в растровых графических видеотерминалах. //"Известия ВУЗов СССР - Приборостроение", т.XXXIII, 1993, N4, стр.33-38.

Палташев Т.Т., Климина С.И. Анализ конвейера растрирования, реализующего объектный параллелизм,// Компьютерная графика - 1993. - Ы2, стр.35-42.

T.T. Paltashev, S.I. Klimina. Analysis of Rasterization Pipeline Using Object Paral lei ism.//Informat ion Technology and Applied Mathematics: First Russian-German Workshop. - Moscow, September 29, 1993, pp.6.

Палташев Т.Т., Чириков C.B. Генерация лекальных кривых в растровых графических видеотерминалах. //Компьютерная Графика. - Москва. 1994, N1.- Статья находится в печати.

Палташев Т.Т., Чириков C.B. Нелинейный метод тонирования триангулированных поверхностей. //Компьютерная Графика. - Москва. 1994, N1. - Статья находится в печати.

Paltashev T.Т., Chirikov S.V. Curve Rasterization Algorithm Desing: An Unifying Approach. // ACM Transactions on Graphics, 1994, (submitted, Paper 93-58).

31. Paltashev Т.Т., Chirikov S.v. The Fast Hardware-Oriented Method of Bezier Patch Shading. // Proceedings of 4-th International Conference on Computer Graphics and Vizualization GRAPHICON'94. - Nizhniy Novgorod, September 19-25, 1994.

32. Paltashev T.T., Chirikov S.V. An Unifying Approach in Fast Hardware-Oriented Rasterization of Curves and Shaded Surfaces. //Proceedings of 9-th EUROGRAPHICS Workshop on Graphics Hardware. - Oslo, Norway, September 12-13, 1994, (accepted for publishing).

33. Палташев Т.Т., Чириков С.В. Генерация линий с субпиксельной точностью в растровых графических видеотерминалах. // Труды 4-й Международной конференции по компьютерной графике и визуализации ГРАФИКОН-94. - Нижний Новгород, 19-25 сентября 1994 года.

Подписано к печати 20.06.94

Отпечатано в Центре распределенных издательских систем. 197101, Санкт-Петербург, Саблинская 14. Тел (812) 238-85-38

Заказ 218

ЦЕНТР РАСПРЕДЕЛЕННЫХ ИЗДАТЕЛЬСКИХ СИСТЕМ /97Ю/, САНКТ-ПЕТЕРБУРГ, САБЛИНСКАЯ /4 ТЕЛЕФОН: /2) 233-35-33 ФАКС: (8t2)232-76-22