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

РГБ ОД

1 8 ОКТ 1996

На пралгд рукописи

Хачумоп Вячеслав Мнхг.клосич

РАЗВИТИЕ И ПРИМЕНЕНИЕ ТЕОРИИ ПРОЕКТИРОВАНИЯ РАЗРЯДИ О-П АР АЛ Л ЕЛЪНЫХ ГЕОМЕТРИЧЕСКИХ ПРОЦЕССОРОВ (на примере задач машинной графика)

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

системы и сети; 05. 13. 05 - элементы и устройства вычислительной техника и систем уграаленя»

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

С-Петербург -1956

Работа выполнена в Дагестанском государственном техническом университете

Научный консультант:

доктор технических наук Кокаев О.Г.

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

доктор технических наук, профессор Малюгин В.Д. доктор технических наук, профессор Торгашез В. А, доктор технических наук, профессор Байкоз В.Д.

Ведущее предприятие - Научно-исследовательский институт многопроцессорных вычислительных систен при Таганрогском государственном радиотехническом университете им. В.Д.Калмыкова.

Зацита состоится Д996 Г. в час. на

заседании диссертационного созета Д 063.36.08 Саккт-Петер-бургского государственного электротехнического унизерситета им. В.И.Ульянова (Ленина). по адресу: 1973-76. Санкт-Петербург. ул. Проф. Попова. 5.

С диссертацией можно ознакомиться в библиотеке университета Автореферат разослан " ^" 19Э5 г.

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

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

Актуальность.

Скорость решения задач машинной графики и обработки изображений является одной из наиболее важных характеристик качества вычислительной техники, для улучшения которой ис-. пользуют все доступные способы, включая аппаратурную реализацию наиболее употребительных операций, а также учет внутреннего и внешнего параллелизма обработки данных. Первые ап-паратно реализованные модули для ускорения геометрических преобразований, основанные на идеях Сазерленда И., ■Спруллл Р., Гилоя В., Штрассена В. и др.. были созданы уже в конце 60-х годов. Современные специализированные процессоры, называемые дисплейными, графическими или геометрическими' (ГШ, обычно выполняются в виде отдельных плат, встраиваемых в другие системы, и ориентированы на быструю реализацию графических алгоритмов. Так. например, производительность графических ускорителей.Freedom фирмы Hewlett Packard' составляет несколько миллионов преобразований -пространственных векторов в секунду, а процессор для компьютера Poly 300Р фирмы Poly-well Computers на базе RISC-процессора Alpha обрабатывает б секунду 360 к простых трехмерных фигур.

Тем не менее, задачи моделирования сцен реального мира требуют гораздо большей вычислительной мощности, чем сегодня имеет самый быстрый компьютер или. спецпроцессор. В этой сея-зи привлекают работы по созданию многопроцессорных графических станций. Фундаментальные основы построения подобных систем Оыли развиты Кларком Дж., основателем компании Silicon Graphics. Созданный им конвейерный Геометрически;', процессор имеет до 12 программируемых процессорных элементов (¡г?} и достигает- производительности равной сотням мкллионсе ций в секунду. Однако и он не может реекть ьсе»: прс:.;>::,: обеспечения скорости для приложении реального времени. Пег— теку во Есек кпре ведутся работы пс различным напрезлення:.: ссьер^енотьсвгн;" ГП, применяемых для решения задач ¿з таких ■■.<■■ .'¡атях как САПР, цифровая обработка сигналов, p;ic;icзябкие образов, тренажеры, индустрия компьютерных игр и -{ильное..

Среди отечественных исследований отметим труды коллектива Института автоматики и электрометрии СО РАН по созданию'

— й. ~

геометрического процессора синтезирующей системы визуализации (ССВ). Существенный вклад внесен лабораториями образного анализа данных и машинной графики Института проблем управления РАК под руководством Прангишвили И.В. по созданию Графической синтезирующей системы реального времени (ПС ГРВ). Работа над совершенствованием математического и программного обеспечения с привязкой к современным техническим средствам •машинной графики ведется в ИПМ РАН им. М.В.Келдыша под руководством Банковского ü.M. Отечественные разработки ГП.представляют собой различные варианты параллельно-конвейерной обработки, но отставание в элементной базе не позволило добиться здесь рекордных показателей быстродействия. Современные исследования по построению спецпроцессоров,- ориентированных на решение траекторных задач в системе алгоритмов .Волдера, выполнены в . Санкт-Петербургском государственном электротехническом институте им. : Ульянова (Ленина) Байковым В.Д., Сиоловым В.Б.. Вашкевичем С. Н. и Сергеевым М.Б. Однако итерационный.; характер вычислений и сложность коррекции ре-' з'ультата: ограничивают возможности использования этого-метода.

.-.Помимо конвейерной конфигурации для задач машинной графики часто используют-различные.параллельные включения многих процессоров. Эффективные системы.с массовым параллелизмом были разработаны, например, фирмой Motorola. Ее графические ускорители на .основе RISC-процессоров PowerPC подключаются к станциям Sun,или.встраиваются в корпус, компьютера IBM ; для.-выполнения параллельных программ. 'Наивысший эффект ускорения, достигается в систолических системах с поразрядной обработкой. ' "В этой связи • вызывает большой интерес теория разрядных вычислений,; -чпредложенная Пуховым Г.Е. и развитая его учениками, позволившая распараллелить ряд вычислительных процессов до-- уровня, отдельных/ разрядов, однако реализация сложных—геометрических преобразований -здесь затруднительна. Большой вкладов'развитие принципов' конвейеризации и распа-■ раллеливания процессов, внесли- Самофалов К.Г., Луцкий Г.М., Поспелов Д. кг, Воеводин В.В. ,' Карцев М.А., Трахтенгерц Э. А., Игнатуценко В.В., ^Каляев-А. В:'.' -Котов В.Е.. Головкин Б.А., Вальксвский В. А.'- 'и др.-. Создание ГП приводит, к необходимости-решения задачи',' оптимальной настройки его решающего поля на

многократную реализацию графических алгоритмов. Существенный вклад в теорию периодических расписаний. - наиболее естественных для работы ГП. внесли Танаев B.C. , Шкурба В. В.. Шурайц Ю.М., . Гильман А.Л., Хаит Я.Г., Конвей Р. В., Максвелл В. А.. Миллер Л.В., Айзенштат B.C., Метельский А.С. и др.

Несмотря на достигнутые -успехи, проблема обеспечения высокой скорости обработки графической информации остается весьма актуальной.. Имеющиеся сегодня/процессоры в действительности, с одной стороны, обладают недостаточным паралле-■ лизмом, а с другой - мало подходят, для итеративных процессов. характерных Для большинства алгоритмов машинной графики. Необходимость многократного счета по одной и той же. вычислительной схеме является наиболее узким • местом в таких процессах как интерполяция, проекционные и аффинные преобразования, закраска, отсечение еидорым объемом и т.д. Это приводит к тому,, что реалистическое изображение генерируется современными средствами' непозволитель'но; долго. Для моделирования реальных процессов существующие системы следует заменить более совершенны;®. При этом требуется пересмотр' основных .алгоритмов 2D и ЗБ-граФики для адаптации к особенностям структур специализированных вычислителей. Дополнительным источником ускорения может служить оптимизация представления графической информации. Таким образом актуальной является как задача совершенствования, структурной организации ГП. так и привязки к ним алгоритмов машинной трафики. «

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

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

В соответствии с поставленной' целью основные этапы и

задачи работы определены следующим образом:

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

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

- разработка алгоритмов машинной графики, адаптированны:-; к структуре ■ ГП " и их программирование б наборе команд ГПЗ; выявление параллелизма алгоритмов многократного выполнения;

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

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

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

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

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

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

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

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

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

4. Алгоритмы решения итерационных задач машинной графики. адаптированные к структурам ГП, и способы их программирования в системе команд разрядно-параллельного ГЛЭ..

5. Метод оперативного планирования.."периодических расписаний работы многопроцессорной. Геометрической машины (ГМ) с эффективным совмещением циклов,': включая -формализацию задачи на основе выделенных косвенных показателей качества, алгоритм максимального совмещения циклов;. алгоритм . псевдооптимального закрепления' ПЭ за операциями,' способы совмещения параллельных комплексов алгоритмов. .

6. Метод настройки (оптимизации) структуры ГН или ГП, состоящего из набора программируемых ПЭ, . на заданный комплекс алгоритмов многократного выполнения и система программного обеспечения для автоматизации процессов проектирования.

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

Практическая ценность. Предложенный метод проектирования разрядно-параллельных ГП с набором крупных операций. I! разработанное программное обеспечение для .'оперативного плакирования периодических расписаний в системах из нескольких Оункциональн'о-оркентировагошх ПЭ. позволяет научно-обоснованно и эффективно решать геометрические задачи в областях вычислительной техники, САПР, системах машиной графики, сев и АСКЙ. Разработанные формализованные модели и алгоритмы периодических процессов, метод разрезания графовых моделей применимы'такке и для решения инженерных:задач, связанных с

многократным (циклическим) выполнением комплексов работ.

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

Реализация и внедрение результатов работы. Основные результаты диссертации получены автором при выполнении научно-исследовательских работ, проводимых Дагестанским политехническим институтом (Дагестанским государственным техническим университетом) совместно с Институтом проблем управления РАН в рамках: научно-технической проблемы ГКНТ при СМ СССР О.Ц.027 "Создание и развитие автоматизированных систем научных исследований (АСНИ) и систем автоматизированного проектирования (САПР) с применением стандартной аппаратуры КАМАК и'измерительно-вычислительных комплексов", вошедшей в тематический план Института проблем управления РАН (номер Гос. регистрации 2474 930120) и включенной в план важнейших работ Минприбора; программы ГКНТ при СМ СССР "Создание методов, элементов и комплексов САПР для решения задач в различных отраслях народного хозяйства в рамках многостороннего сотрудничества (КП НТО СЭВ)" по Постановлению Совмина СССР N 1322 от 26.12.85 года; Международного проекта "Разработка средств для создания интегрированных систем автоматизированного проектирования /ИСАЛР/ Министерства науки, высшей школы и технической политики, РФ; научно-технической программы "Глобальные сети САПР реального времени"; госбюджетной тематики в соответствии с приказом N 520 от 10.08.92 Госкомитета по Еысшей школе, регистрационный номер 1.7.92 "Математические и технические аспекты организации массовой обработки числовой информации в процессорных элементах с изменяемой системой счисления"(1992-1995 гг).

Автор являлся соисполнителем ряда разделов договора о научно-техническом сотрудничестве Института проблем управления РАН и Всесоюзного научно-исследовательского института организационной техники (ВНИИоргтехники) по теме- "Исследование и определение принципов построения автоматизированного

интерактивного рабочего места обработки графики (АРМграфи-ка-01) шифр 0377 229 310.

Диссертационная работа является также обобщением опыта проектирования спецвычислителей, накопленного в процессе работы: над темой "Исследование принципов построения и разработка процессора связи моделирующего комплекса", выполненной в Дагестанском политехническом институте совместно с Таганрогским радиотехническим институтом (отчет, номер Гос.регистрации 78027323 от 27 апреля 1978 г.); над темой "Разработка и. исследование быстрых функциональных преобразователей на основе многовходовых суммирующих устройств", выполняемой в рамках Программы информатизации народного хозяйства Республики Дагестан по Постановлению Совета Министров РД К 106 от 19 июля 1991 г.; над ОКР "Разработка банка методик выявления ненадежных микросхем (шифр "Нерёида-90"). выполняемой в рамках Госзаказа по хоздоговору с.Минсвязи СССР и СКБ "Искра" (МЗ "Орбита".г.Москва) от 07.02.90 N 6016-135/40.

Научные и практические результаты, полученные в диссертации использованы при чтении курсов "Компьютерная графика",' "Автоматизированное управление в технических системах" и "Вычислительные машины и- системы"; подготовке методических указаний и постановке лабораторных работ на кафедрах автоматики, прикладной математики и вычислительной техники Дагестанского государственного технического университета.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на: ХХШ1 и XXIX конференциях молодых ученых Института проблем управления (г.Москва, 1982. 1983), Школе-семинаре по проблемам управления качеством продукции (Москва,1983); II Всесоюзном совещании "Автоматизация проектирования и конструирования" (Ленинград. 1983); Региональном научно-техническом семинаре Северо-Кавказского научного центра высшей школы "Автоматизированные системы управления технологическими комплексами на базе микропроцессоров, микро- и мини-ЭВМ" (Новочеркасск.1983 ): IX Всесоюзном совещании по проблемам управления (Ереван, 1983); II Всесоюзной научно-технической конференции молодых ученых и специалистов приборостроительной промышленности (г. Москва. ВДНХ СССР, 1983); III, V.■VI и'VII научно-технических секи-.

нарах "Математическое обеспечение систем с машиной графикой" (Устинов,1985; Ижевск,1988; Махачкала.1989; Тюмень, 1990); Всесоюзной конференции "Методы и микроэлектронные устройства цифрового преобразования и обработки информации" (Москва,1985); Всесоюзной научно-технической конференции "Проблемы развития аппаратных и программных средств вычислительной техники для машинного моделирования" . (Москва. 1937); Научно-технической конференции "Образное представление данных в управлении и научных исследованиях" (Грозный, 1987;; Российской научно-технической конференции "Системный анализ и принятие решений в задачах автоматизированного обеспечения качества и надежности изделий приборостроения и радиоэлектроники" (Махачкала.1991); XX Международной конференции "САПР-93" (Крым,1993); Российской научно-технической конференции "Интерактивные системы" (Ульяновск.1993); 2. 3, 5 и 6 -Международных конференциях по компьютерной графике и визуализации. 'в России "Графиков" (Москва: 1992; Санкт-Петербург:'- .1393,. 1995, 1956); 1-ом Международном симпозиуме "ШТЕЛС-94." (Махачкала. 1994); 2-ой Международной научно-технической конференции --"Актуальные проблемы фундаментальных наук", (Москва. 1994);. -Международной конференции "Автоматизация прйектированяя 'дискретны»; систем"'- ( Минск. 1995); Международной- кокфзренцки:"Интерактивные системы: проблемы человеко-кокпыотерного ;; взаимодействия" (Ульяновск.1995); Международном сьдапозаукв "Каспий-Балтика 95" (Санкт-Петер-бург. 1995).. Всероссийской конференции "Информационно-управляющие ■системы и специализированные вычислительные устройства для обработки и передачи данных" (Махачкала,1996); международной ' конференции.;' "Информационные' технологии в моделировании и управлении" (Санкт-Петербург,1996).

Публикации.• По. -'теме - диссертации опубликовано 46 печатных работ, включая две монографии, 15 статей, 28 .тезисов докладов и Л авторское свидетельство.

Структура и объем диссертации. -Диссертация состоит ведения, вести разделов,- -заключения, списка литература, •¿клэчзздего 178 наименований, и .четырех приложений. Основная часть работы изложена на 236 страницах машинописного текста. Работа содержит 59 рисунков и 51 таблицу.

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность исследуемой в диссертации проблемы. Формулируются цель и основные задачи исследований, отмечены полученные в работе новые научные результаты и их практическая значимость, представлены структура и краткое содержание диссертации.

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

Ориентация объекта на экранной плоскости задается вектором положения, для построения которого предложено два метода. Метод получения взвешенных точек характеризуется простотой построения вектора полевения, направленного из точки центра тяжести (X.Y) в точку (х'.у*). для определения которой предложены удобные формулы, содераэдие координата всех точек объекта, однако наличие только двух, хотя и взвешенных точек, не гарантирует высокой точности закрепления вектора на изображении при выполнении кногочаслетшх геометрических преобразований. В качестве основного предлагается метод выделения взвешенной линии положения объекта. Ее использование позволяет: получать описание геометрии объекта, ускорять процедуру поворота и. на основании теоремы Шаля, унифицировать описание перемещения. Линия положения, определяемая уравнением y^ao+aj-х. на основании метода наименьших квадратов проводится таким образом, чтобы сумма S произведений квадратов расстояний s, (i=l,...IJ) от точек изображения до линия положения на их яркости (веса) была минимальной:

S= i s, 2m, .

1-1 1 x

где Sj ~|/(x"-x1 )2 + (y~-yi )г. x". у" - координаты текущей точки пересечения линии положения и прямой, проходящей перпегщяку-

лярно к ней через точку (х^, у± >.

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

к К ц

р-а,г+ч-а1-р=0. а,,-! И! + а, I ххп»! - I т1у1« 0.

1»1 1-1 , 1-1

цц К N

где: р - 1га, - 2т, х, у, - 2га! у, • Ег^ х1.

1-11-1 1-1 1-1

» * - * * „ *

q - ап1--(1т1х1г - Хи^!2) + (ЩУО - Ит,^)2.

1-1 1-1 1-1 1-1 1-1

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

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

.' Если при расширении,число точек изображения и их яркости оставлять неизменными, а при сжатии яркость точки определять суммой яркостей.совмещенных'в ней точек объекта, то величина в монет, служить характеристикой размера изображения.

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

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

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

Расширением подхода является процедура "сватая" геометрической информации путем выделения набора информативных интегральных параметров. Результат сжатия информации по принципу "изображение-код* представляется для плоского случая вектором интегральных характеристик I-! I, Is....InI. где:

î, (x)-//m(x.y)dydx. 1,-f, (х) Х.х: Гг (x)-/f, Cxjdx.

00 о

1г-гг(х) Гп(х)-Я».1 (x)dx. Ia-fa(х) ж.х .

X.Y- граничные координата изображения. ■ m(х. у)-яркость точки (х.у). Применяя для вычисления элементов вектора численные методы интегрирования, например метод трапеций, получают на- ' бор информативных параметров, интерпретируемых как некоторый, код полутонового изобрагения, Управляя размерностью вектора I, -можно подобрать число'параметров, достаточное для идентификации обьекта. Исследования над реальными, изобретениями показали, что предлоаенный метод дает интегральные параметры. отличающиеся менышм разбросом значений при выполнении преобразований поворота, по сравнению с результатами, полученными по известному методу/инвариантных моментов. ; •

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

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

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

рассмотренные методы сжатия и восстановления объектов служат дополнительным средством повышения эффективности ГП.

В Разделе 2 рассматриваются вопросы выбора эффективной системы команд ГП и закладываются теоретические основы построения разрядно-параллельных ГПЭ на основе аппаратурной реализации вычислительных процедур Волдера. ГП выполняет Функции универсальной геометрической подсистемы, реализующей основные операции аналитической геометрии СА,....АП}. Так. для плоскости имеем следующие задачи: измерение длины отрезка и ■ расстояния от точки до прямой; определение отношения, в котором точка делит отрезок; определение угла положения вектора и угла между двумя прямыми; установление связи между декартовыми и полярными координатами; поворот осей координат.

Определение 2.1. Геометрическим процессорным элементом называется специализированное вычислительное устройство, ориентированное на выполнение не менее одной операции из набора {А, А„}.

Определение 2.2. Геометрическим процессором называется совокупность алгоритмических, программных и технических средств, реализованных на основе ГПЭ. для формирования описания и преобразования геометрии графических объектов.

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

итераций обоих этапов вычислений. Для каждого фиксированного угла поворота точки (X, У) значения операторов Et, EjEitl) (1=0....п) вычисляют заранее и заносят в ПЗУ для многократного использования. Развернем ео времени итерационные процедуры второго этапа. Для п=10 соотношения для новых координат (X'.Y') принимают по Волдеру в сжатой форме следующий вид:

10 t 10-К

К Х'= В2° +1 C„AZ-k - I I ekEjB2-(KM) -k-i k-i l'k*l

г t(9-K)/2j iо-<k*i) - I I I ЕкЕ1Ез1А2"(,с*1*и);

к« 1 1«'к*1 в-1*1

10 4 10-*

К-У'= А2° - I ЕкБ2"к '- Е 1 EkEIА2"( 11 + к • 1 1с «1 1-к-и

2 [(9-к>/£) 10-(К*1> + 1 2 I Е). Е J ЕвВ2"

k»l lak+1 0*1+1

где A=Y-t0X. B=X+e0Y, K-коэффициент деформации вектора. ;■ Для организации параллельных вычислений необходимо подставить в полученные выражения значения всех операторов Бодлера, соответствующие заданному углу поворота. Операция "поворот" является наиболее валкой для системы, команд ГП. поэтому в работе исследуются вопросы ее точности я сложности. Рассмотрен способ выполнения- операции "вектор" методом последовательного поворота вектора на половинные углы до совпадения с одной из осей ординат с требуемой точностью. Исследованы способы параллельного представления кнояитель-но-делителькых операций вида 1/3, А/В, (А/В)•С и ряда элементарных функций. Предложены структурные реализации параллельных алгоритмов на основе устройства группового суммирования. К сожалению; для многих из них не удается получить одновременно операторы Волдера. Решение задачи становится возможным после перехода к разрядно-параллельным Формам.

Анализируется эффективность реализации наборов команд в системе итерационных и параллельных алгоритмов Волдера по сравнению с наиболее используемым методом полиномиальной аппроксимации в широком диапазоне разрядностей (8+54). Про-

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

- на микропрограммном уровне в системе команд АЛУ с аппаратной реализацией сдвигов увеличение быстродействия в диапазоне разрядностей т-16+32 примерно в 1.5 раза:

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

- параллельное представление алгоритмов Волдера обеспечивает в диапазоне и»16+32. по сравнению с параллельной реализацией формул полиномиальной аппроксимации, выигрыш по быстродействию примерно в 3 раза;

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

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

Конвейерный способ оказывается более выгодным при организации структуры ГП на основе q ГПЭ и к.-кратном выполнении вычислений. В частности/при реализации полиномов степени п условия предпочтения могут быть записаны следующим образом:

при ч=[п/21+1 (случай неограниченного параллелизма):

.. КХ2п-Г2п^1)/( Г1ое2 (п+1)1+1-Г2п/д|);

при ц=1Уп ] (случай ограниченного параллелизма):

К> (2п-[гп/яЬ/([(2П+2-2Г10«2 Ч1)Л}1 + Г'1оегя! - ГгпЛ}] ).

Здесь Гх1 -ближайшее целое не меньшее х.

Таким образом, перспективным направлением совершенство-

вания ГП и ГПЭ является объединение принципов параллельной и конвейерной организации, что гарантирует наивысшую производительность.

Раздел з посвящен развитию теории построения разряд-но-параллельннх ГПЭ с набором аппаратно-реализованннх процедур Еолдера и Пухова как основных узлов для построения ГП.'

Предложены эффективные методы устранения линейных искажений. внсспкьех алгоритмами Еолдера. Идея метода направленного изменения, коэффициента деформации К заключается во введении для итераций с номером 1 некоторого числа p¡ дополнительных взаикококпенсйрукда поворотов ¿^.»j, »const, таким образом, что величина К становится кратной 2. Тогда йомпен-сация в конце процесса осуществляется простыл сдвигом результата вправо на нужное число caros. Л'етод раздельного поворота на корректируйте углы закачается в раздельном применении процедуры "поворот" для каждой координаты а вваяепяя соответстзузкщх коррехтирукзаг углов. При' этом предполагается. что известен начальный угол нологения вектора- Используя процедуру Волдера. " вектор поворачивается на па заданный угол ф, а на угол <?, . такой, что X'-KRcóstfto+spj J^KRcosfipg-Hp+A^j). Для другой координаты вектор поворачивается на угол <fe-i?-Aq>2. такой что Y' -KRsin(<?о)"KRslnС<?0-Hp-Atfe). В приведенных выражениях R - длина_ исходного вектора. Получены формулы для корректирующих углов: - .

Дфч =arccos (cos (í?¡¡ -f ;р) /К) - (ф^+tp). - ■ '

Дф2 =arcsln (sin (<?з +<?) /К)+(Фо-нр), <р'«=(Ф0+<р) - угол, соответствующий новому полонению повернутого вектора. Таким образом, величины А-?, и А^ являются фактически функциями одной переменной р'. Если есть возможность отслеживать при выполнении поворотов значения углов положений, то проблема коррекции решается достаточно просто. Можно заранее просчитать значения корректирующих углов для фиксированных и заложить их в ПЗУ. Б методе прямого уклонения на коэффициент параллельные представления результатов операции "поворот" модифицируются путем умножения их элементов на величину 1/К-О.10011011012 (для разрядности и-10).

На основе параллельных записей для результирующих зела-

чин X' и У достаточно просто удается получить разрядно-па-раллельные формы относительно двоичных представлений промежуточных параметров А=(а1аг____а„) и В=(Ь1Ьг____Ьт). Они

предоставляют дополнительные возможности для ускорения некоторых операций. Так путем приравнивания нулю выражений для каждого разряда результирующего значения координаты V (с коррекцией) операции, "поворот" удается получить значения операторов ^ для операции "вектор". Для ш=8 имеем: £0=0. С1=аг. Сг-аз-цЬг, Ез^-Е^-Ег^-Е^га^ Е^ —ад —Е| Ь^ "ЕзЬз —£3 &2 »

Е5«а6-Е 1 Ь5-ЕгЬ4-Е3Ь3-Е1 Е2аЗ"£4Ьг-£1 Езаг-(£, Е4+ЕгЕ3 )а5 , Б6=а7-£1Ь6-ЕгЬ5-ЕзЬ4-Е1Ега1-Е4Ьз-£1Езаз-£5Ь2-(£1Е4+£г£з)аг

+Б1ЕгЕ3Ь1-(Е1Е5+Е2Е4)а1. Е7=аа-Е1&7-£2Ь6-ЕзЬ5-Е1Е2а5-Е4Ь4-£1Еза4-Е5Ьз-(Е1£4+£г£з )а3 + + (Е1Е2Еэ-£а)Ь2-(Е1Е5+Е2Е4)а2+£1Е2Е4Ь1-(£1£6+Ег£5+Е3Е4)а1 . После подстановки операторов в параллельное (или раз-рядно-параллельное) представление координаты X' при условии а4 =0 определяют искомое значение длины вектора. Найденные операторы £4 .(1-0,..,7) принадлежат множеству {0.1,-1}, что отличает их от операторов Волдера, принадлежащих множеству {-1,+1} и получаемых строго последовательно (итерационно). Приводятся результаты моделирования, подтверждающие корректность полученных разрядно-параллельных схем решения задачи.

Рассматривается реализация разрядно-параллельных представлений алгоритмов Волдера для операций 1/Х, /X. В результате их сопоставления с разрядными формами Г. Е. Пухова удается получить операторы ех параллельно, записав их относительно разрядов аргумента. Так для у=1/Х и разрядности гп=8 имеем разрядно-параллельную форму:

В-1

у- I , • 1-0

Кф^Ед, ^=£4, к2=£2-, кз^Ез+с^г. к^+Е^з.

кэ^Ез+Е^^+ЕгЕз, К6-Е6+Е1Е5+Е2Е4+£1Ег£з.

На основании приравнивания разрядно-параллельных форм Пухова и Волдера получено:

1д-х1 =1, е| ~ ~х2 . £2--х3+х2 , е3 х3—х4 ,

е4=-х2 х* -х5 +х3 +х2 Х5 +х3 х4 +хг, £ 5-2хг хз -хд +хг х4 +х2 х§ +х3 х5 -х2 хз х5 +х2 х3 х4 -х3 х4 , £ 6 =зх2 х3 -х2 х3 х4 +х2 х4 -х7 -х2 х5 -х3 х5 +х4 +х2 х7 +х3 х6 -х2 ха +х4 х5, £7 =4х2 х3 -х2 х5 -2х2 хв +2х2 х4 х5 -х3 :<б +х3 х5 +2х2 х3 х« +2хг х3 х4 -

-¿х2х3 х5-х1х5-х8 .

Таким образом операторы £( получают непосредственно по двоичному аргументу X. Множество {£,...,е7) в этом случае

является множеством целых чисел: е1Е{±р1), р1е{0,1.2____}.

Моделирование на ЭВМ подтверждает эквивалентность полученной системы операторов системе операторов Ёолдера еге{±1}. Следовательно операторы, полученные по Пухову. и классические операторы Волдера представляют собой фактически два возможных решения задачи. Расширением подхода служит получение разрядно-параллельных форм для составных множительно-дели-тельных операций и процедуры "вектор".

В работе предлагаются и исследуются двухэтапные и одно-этапные процедуры измерения длины пространственного вектора (X.V.2). Итерационные формулы приобретают, например, для одного из вариантов одноэтапной схемы пространственного случая следующий вид:

у1 + 1=у1-е11г12-1, 21М = (21+Е11У12"1)/К1.

21 1'

X! +1 =X^ — £2^ Ъ^ 2 ^ , + ^ Х^ 2 1.

Е11+1=31ЕП у1М, Е21м=з1ёп Х1 + 1. Начальные значения: х0=Х, у0=У, е10=е2„=1.

■ Результат: х„=0. у„=0. гп=К11/(Х2+У2+г2). Здесь К;=1/(1+2'21).

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

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

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

по Волдеру: по Пухову:

поворотах 1/1 1пХ \ 1/Х п

п N(01) ■ ш ■ ( 2га ш

Б(1П)-|оН(1).Щ1)=1+ [1/2]+ |"1/з]+. .. + [1/11 Л= [-1/2+1/21/1+81].

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

1= Г1оегп1+1, в то время как последовательное суммирование

займет (п-1) такт. Такт здесь равен времени одной операции суммирования да -разрядных операндов. Быстродействие при использовании ассоциативных многовходобых суммирующих устройств определяется, в зависимости'от .конструкции, по формулам:.

т+[1оБ2п"|+2. 1=- т/г+[^гп1+2, 1= [т/г].

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

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

В Разделе' 4' предлагается рещша раса геометрических задач машинной графики в системе ксэдакд ГПЭ. 1фккенитапъно к структурам конвейерно-параллельных процессоров. Перечень задач включает: генерацию и растровую развертку векторов, генерацию кривых линий, выполнение группы аффинных преобразований. отсечение плоских и пространственных объектов окнами.

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

Описание (программирование) -алгоритма для ГП с использованием установленного набора команд выполняется 5 виде взаимосвязанных операторных блоков. Последовательность описания функциональных операторов для алгоритмов одного гпэ соответствует последовательности их выполнения. Каждый функциональный оператор имеет идентификатор, который определяет выполняемую стандартную процедуру, существующую в наборе команд. Рассмотрены графические схемы описания структур алгоритмов. 3 описании участвуют: схемный эквивалент оператора, разделитель и переменные. В соответствии с установленным набором операций и аргументов производится назначение входов/выходов блока. Так, например, весь комплекс операций обобщенного геометрического преобразования точки {1.4.Ъ) при. условии визуализации двух результирующих координат (Х'.У) мояет быть описан с помощью схемы:

I-;а

йот (у. г, т. г,, )^от(21.х.р.х1,^2)^от(х1 л1. а. уг. хг) - в

А ->MUL (1г. Sz. *) -ADD (*. ZT. W) -

W'

•*MUL(XZ, Sx, *)"ADD(*, XT, XR )-МОУ(Хя ,W'. d)-> V

-MUL(YZ, SY', *)-*ADD(*. YT, YR )-»MDV(Ya. W', d)-* Y' Здесь: а. З.к -углы поворотов: sx.sy,sz и XT,YT.ZT -масштабирующие коэффициенты и сдвиги вдоль координатных осей; ROT. MDV.MUL -операции Волдера: "поворот","множительно-делитель-ная" и "умножение": Xj. Yt.Zt ,Х2.Y2.Z2,XR,YS,ZR,V)'. * - переменные. Получаемые при этом конструкции могут быть отнесены к одному из видов параллелизма по классификации Карцева. В частности, рассмотренный выше комплекс содержит ветви смея-

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

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

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

Определение 5.1. Алгоритм А - ал,азг...азп. б котором строго определен порядок выполнения операций,- называется локальным алгоритмом (/¡А) обработки цифровой-информации.

Определение 5.2. ЛА А* = а^ а^-.-а)" называется

отмеченным локальным алгоритмом (ОМ), если в А -помимо выполняемых операций указаны закрепленные за ниш: ПЭ.

Запись означает, что ПЭ с номером 1к из набора с^ выполняет операцию азк на К-ой фазе реализации ЛА. При многократном выполнении алгоритма в режиме совмещения вычислительны?: процессов предполагается выполнение следующих Условий: а) выполнение ЛА не может быть прервано; б) каждая операция ЛА выполняется-одновременно-не более чем. на одном ПЭ; в) каждый

такт ПЭ выполняет одновременно не более одного оператора ЛА; г) такт работы ГП является составным и равен át « taHn + t0(Sl(, где t3wn ® maxí^}. 1=1____1 - время выполнения самой длительной из 1 операций алгоритма. teíM - Бремя межпроцессорного обмена, для простоты полагаем At«i; л) ограничения на число и вид межпроцессорных связей не накладываются.

Решение задачи максимального совмещения циклов обработки ОЛА сводится к следующему. Для каждого ПЭ выписываются из заданного ОЛА порядковые номера (фазы) закрепленных за ним операций. Если <?, и <р2 ~ язе разные фазы закрепления ПЭ. то величину T«|<to1-ip2| называют сдвигом фазы. Таким образом, для всех ПЭ 1-го типа выписывается множество сдвигов фаз Ht(A"), а всему варианту ОЛА ставится з соответствие множество:

Н(А*) = U Н, (А" 1 = {t,, .., тР}. введем множество G (А*) такое.

что G(А* )=Нр\Н(А*), где Np-n.....р*1}. р=шахСх: т с Н(А')}.

Здесь и ранее t - знак принадлежности множеству.

Множество Н(А*) определяет запрещенные шаги совмещения циклов обработки периодического расписания, a G(А") - разрешенные шаги. Информация о множествах Н(А'). G(A*) и длине локального .алгоритма ш слуяит формальной моделью ОЛА и является достаточной для построения допустимых периодических расписаний. В работе предлагается итеративный быстро сходя-5ципся процесс построения периодического расписания, основанный на сформулированных принципах максимального совмещения.

Результаты статистических исследований ЛА. имеющих разную длину и структуру. ' показали, что величина |Н(А*)| может служить косвенным критерием качества расписаний, что важно для оптимизаций решения. Задача оптимального закрепления ПЭ заключается з нахождении ОЛА.. для которого tí А* }"я1п{ tí Aj*) |1<.1<г} и сводится к отысканию такого пути на ярусном орграфе, что ría. Р)-я1п|Н3 (а, [5) |. J=l,., г. Т. е. суммарное число разных сдвигов фаз в множестве Hj (a,{$). взятых без повторения, является минимальным. Такая постановка эквивалентна известной задаче минимального покрытия таблицы вариантов. Результаты моделирования показывают, что предложенные алгоритмы максимального совмещения.циклов и оптимиза-

ции закрепления ПЭ дают существенный выигрыш по сравнению с полным перебором/ который нарастает с увеличением длины алгоритма.. Так для ЛА с длиной п« 9.10,11.12.13.14,15 выигрыш составил: 1.04. 1.89, 4.01. 7.21. 9.39, 18.37. 33.54.

Полученные алгоритмы построения расписаний для простей-1шХ ЛА служат основой для,рассмотрения более сложных систем, содержащих несколько ЛА. Наряду с А рассмотрим также локальный алгоритм В: В ■■» Ь, Ьг... Ьп. 1 < п < иг., причем у алгоритмов А и. Б могут быть одинаковые операции, для выполнения которых могут использоваться общие:ПЭ. Локальные алгоритмы А и В образуют простейшую систему (комплекс) ЛА многократного выполнения. Рассмотрены системы ЛА, отвечающие требованиям одного из видов параллелизма,-' уточненные в соответствии с алгоритмами машинной графики./Предложены алгоритмы составления периодических расписаний для систем ЛА, минимизирующие среднее время однократной реализации.

Фактором, резко сшшаедкм эффективность систем с конвейерной обработкой, являются .команды. , условного перехода. • Рассмотрены две стратегии планирования периодической работы • .ГП при.наличии условных;/Операторов, - Относительная простота алгоритмов машинной графики позволяет заранее спланировать закрепление ресурсов ГЛ за оператора»« при. одновременном включении всех альтернативных информационных ветвей, по которым может- пойти процесс реаения задачи. Для этого выполняется преобразование блок-схемы алгоритма, не содержащего циклов и контуров, заключающееся в замене условных на обычные вычислительные блоки и склеивании входов альтернативных процессов, принадлежащих разным ветвям..В предположении равной вероятности выполнения.альтернативных ветвей составляется периодическое расписание.'как для системы с параллелизмом независимых ветвей или' смешанным параллелизмом. ,

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

наиболее вероятных сочетаний условных переходов.

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

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

иА'^НИ'МсА'), I (А*. ч) <-1пР0 (сА* )/(Хкч). КсКп, 1<ц<т.

. Задаваемыми величинами являются: п- число ЛА в системе; т- общее число операций в ЛА; 1- число типов операций в ЛА; к- кратность реализации системы; С0(сА*),Р0(сА*)- ограничения, соответственно, по быстродействию и надежности канала обработки; Х-интенсивность отказов ПЭ. Переменными являются: й- число каналов обработки в ГП; число ПЭ в канале:' ИА*^)- среднее время получения одного результата в канале. Задача решается методом направленного перебора.

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

Ь„ Лип-1).

Здесь Я=п(п-1)/2, а каждое слагаемое выражения представляет

собой произведение числа ребер графа на длину ребра. Легко проверить, что никакие перестановки вершин в кортеже полного графа не приводят к изменению величины !,„, что не выполняется для произвольного графа с числом ребер ш < К.

Эффективность разрезания графа, принадлежащего семейству графов с числом вершин п и числом ребер т. ■ мояно оценить. используя для этой цели специальную функцию Г(к) = (Ь11;ах-ЬтП1)/ш. Причем Г(к)=1. если подграфы вообще не связаны ребрами, в этом случае Ьюах =ю, ЬЕ1п =0 ; и Ик)=0 , если ¡э„,ах =Ьт1 „ , что характерно для разрезания полного графа. Процедура разрезания тем эффективней, чем блике к единице значе'ние функции Г (к).

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

Для автоматизации основных этапов проектирования ГП разработано .специализированное программное обеспечение (СПО), входящее в состав интерактивной системы проектирования "Графика-81". Подключение СПО к системе обеспечивает: использование имеющихся в ней библиотек типовых ПЭ различной степени интеграции, вывод графической информации на основных этапах проектирования в виде блок-схем алгоритмов, структур специализированных вычислителей и диаграмм совмещения, анализ графовых моделей алгоритмов и устройств.

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

Разработан блок предварительного отсечения (БПО), который является ГПЭ и на базе которого реализованы более сложные конвейерные и параллельные структуры. Рассмотрена организация вычислений б одном ПЭ. функционально ориентированном на реализацию клиппинга прямоугольным окном. Здесь ПЭ является специализированны].! микропрограммируемым устройством повышенного быстродействия в составе конвейерной Геонетричес-

кой машины. Часть алгоритмов его функционирования, связанных с множите;:ьно-делительными операциями реализована о прлмене-;«!6М разрядно-паралдельнкх Форм Волдера.

Рассмотрена организация многопроцессорной системы, включавшей четыре !1Э разработанного вида. На основе сравнения параллельной и конвейерной организаций показано преимущество конвейерной организации при выполнении операции отсечения многоугольников. Рассмотрены принципы программирования П!Э параллельного типа с двумя АЛУ к аппаратпо-реапвзовгнным у?.шсяителем/делктелбм. На основе данного процессора исследована программная модель двухпроцессорного -вычислителя Еолдера, ориентированного на итерационные процедуры второго зтдпа для операций "поворот", "вектор" и "множитэльно-делитель-аая". Все предложения имеют практический выход и реализованы 5 виде действующих устройств и/или программных средств.

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

- этап подготозка графических данных,

- с-тап синтеза разрядно-параллельного ГПЭ,

- этап программирования задач маишшой ■ графики.

- этап составления периодических расписаний работы ГП.

- ?тап проектирования структуры ГП.

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

- исследован метод двухэтажной идентификации, который по сравнению с методом инвариантных моментов повышает уотейч::-

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

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

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

■-.получены параллельные представления алгоритмов Волдера обеспечивающие в диапазоне разрядностей операндов га=16+32 выигрыш по быстродействию по сравнению с параллельной реализацией формул полиномиальной аппроксимации, примерно в 8 раз;

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

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

- разработаны структуры ГПЭ, в которых разрядно-параллель-ные формы Волдера и Пухова в сочетании с методом группового суммирования операндов позвспяют превзойти в 2-3' раза показатели быстродействия серийно выпускаемых процессоров.

На'этапе программирования задач машинной графики для ГП:

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

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

На этапе проектирования периодических расписаний:

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

- разработаны средства оперативного планирования работы ГП

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

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

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

На этапе проектирования структур ГП:

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

- разработаны специализированные программные средства для автоматизации процессов проектирования структур и планирования периодической работы ГП при реализации как отдельных локальных алгоритмов так и комплексов ЛА:

- рассмотрены вопросы структурной организации ряда ГП конвейерной Геометрической машины реального времени и программно-аппаратные средства для реализации параллельных форм представления алгоритмов Волдера в системе их команд. ■

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

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

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

1. Канаев М.М., Хачумов В.М. Области применения и классификация .процессоров связи: Тез. докл. научн.-практич. конф.молодых ученых Дагестана.-Махачкала:ДГУ,1979.-С.184.

2. Кондаков O.A., Матвеева Л.Н., Омаров О.М., Темирханов Т.Э.. Хачумов В.М. К вопросу построения процессора связи моделирующего комплекса, //Управляющие системы и машины. -1980.-N5.- С.25-28.

3. Хачумов В.М. Организация периодической обработки информации в многопроцессорных вычислительных системах.//Изв. вузов СССР,; Электромеханика:-1983. - N8. - С. 122.

4. Хачумов В. М., : Юмагулов М. Г. Метод анализа и синтеза оптимальных .структур вычислительных устройств для систем управления: Тез. докл. II Воессвз. совещ. "Автоматизация проектирования ;и конструирования.Часть 2. " -М.: Институт прзблем управления, .1983. ~ С. 106-109.

5. Хачумов: В. К... Автоматизация проектирования цифровых, систем реального времени: ..Тез. . докл. 'школы-семинара по проблемам управления качеством прбдукции.-М.:ЦНИИТЭИ . приборострое-

" ни.ч, 1983. -С.72-73.

6. Шабалов Д.В., Хачумов В.М. Об одной возможности организации и обработки/графической информации в системах автоматизированного проектирования:. Тез. докл. IX Всесоюз. совещ. по проблемам управления..: -К.: Институт проблем управления, 1983.- С. 279.

7. Хачумов'В.Ы. Автоматизация проектирования вычислительных устройств: Тез. докл. Второй Всесоюз. конф. молодых приборостроителей. М.': ЦНИИТЭИ. приборостроения. 1983.-С. 80.

8. Хачумов В.К.. Юмагулов М. Г. Об оптимизации метода совмещения вычислительных процессов в специализированных устройствах. : -В кн.: Управление в сложных нелинейных систе-

. мах. -М.: Наука, 1984! - С. 148-152.

.9. -Бренер В. С.,.. Шабалов Д. В.. Воротынцева И. В., Хачумов В. М. Об одном алгоритме вывода графической информации '//Приборы и системы управления.-1984.-N9. -С. 13.

10.Яабапоз Д. В.. Хачумов В. К. К вопросу о структурной организации процессора .. обработки графической информации //Приборы к системы управления.- 1984.- N3.- С.13-14.

П. Парков З.Н.. Хачумов В.М. Интерактивное разрезание графовых моделей и его эффективность: Тез.докл. 3-го научк. -техн. сем. "Математическое обеспечение систем с малинной гс-аф-иксй". -Устинов: Удм. респ. упр. статистики, 1985. -С. Р5-27.

V?.. Артамонов Е.И., Хачумов В. М., Шабалов Д. В. Автоматизация проектирования структур устройств цифрового преобразования и обработка информации: Тез. докл. научн. -гекн.г.оаФ. "Методы л чикроолектронные устройства цифрового преобразования и обработки информации". -И.: ЙЙЭТ, 1935. -С. 235-235.

13. Айдемиров И. А.. Исмаилов Ш-М.А.. Хачумов В.М. Ускорение процессов визуализации графической информации на основе быстрого преобразования "вектор-растр'': Тез. докл. Всесо-1оз. научн.-техн. конф. "Проблемы развития аппаратных и программных средств вычислительной техники для магшного моделирования". -М.: Радио и связь, 1987,- с.114-115.

14.Хачумов В.П.,Артамонов Е.И.,Айдемироз И.А. и др. Геометрический процессор для диалогового анализа изображения: Тез.докл.конф."Образное представление данных в управлении и научных исследованиях".Ч. 2.-М.: ВСНТО. 1987.-С.159-150.

15.Хачумов В.М., Магомедов X.Д. Оптимизация совмещения пик . лов работы и структуры устройства, ориентированного на параллелизм множества объектов' //Теория и ¡фактика проектирования РЭА.-Махачкала: ЛГУ, 1987. -С. 126-129.

16. Айдемиров И. А., Исмаилов Ш-.Ч. А., Хачумов В.М. Специализированный процессор для быстрых геометрических преобразований: Тез. докл. V научн.-техн. сем.'"Математическое обеспечение систем с машинной графикой. -Ижевск: Удм. респ. упр. статистики,1988.-С.12.

17. Айдемиров И. А., Хачумов В.М., Шабалоз Д.В. Применение алгоритмов Волдера для быстрого преобразования "зектор-растр" // Изз. вузов СССР.Приборостроение.-т.XXXI.-1988.-:>7. -С. 21-25.

18. Лагнееа М.М., Хачумов В.М. БесповторнкЯ алгоритм отсечения плг:ких многоугольников: Тез. докл. VI научн.-техн.сем. "Математическое "бэспечение систем с машинной графике;;". -Махачкала-Изсевск: Удм. респ. упр. статистики, 1989. -С. 8 -9.

19. Артамонов Е.И., КокаевО.Г. . Исмаилов 111-М. А., Хачумов В.М. Параллельный алгоритм Болязра для операции поворота

и его применение в машинной графике //Управляющие системы и. машины. -1990. - Iii.-С. 106-109.

20. Айдекиров И. А.. : Исмаилов Ш-К.А., Хачумов В.М.; Об одном алгоритме отсечения плоских многоугольников //Автометрия. -1990,- N 4. -С. 10-14, .

21. Айдемиров И. А., Воробьев Ю.Д.. Лагиева М. Mi . Хачумов В.М. Программно-аппаратные средства клиширования в синтезирующей конвейерной . графической системе //- Автометрия. -1990.-КЗ.-С. 20-23.

22. Лагиева М.М.., Хачумов. В.М.Шабалов Д.В. Метод построения линий положения для идентификации полутоновых изображенной .//Автометрия.-1991.-Кб. -С.7-12.

23. Хачумов В,М., Лагиева'М.М.:Метод двухэтапной идентификации. . полутоновых изображений:., Тез.докл. Российской на-

учн. -техн. ■ конф.: "Системный анализ и принятие решений в задачах обеспечения качества'й надежности:изделий приборостроения и, радиоэлектроники". -Махачкала: ДЩ АН СССР, .1991. -С. 73. ' . ' .

24. Артамонов Е.И., Хачумов В.Мч Синтез структур специализированных средств машинной, графики. -' М. Институт проблем управления АН СССР, 1991. -150 с.

25. A.c. н 1665373 СССР.' • МКИ G .06 F 7/50. 'Ассоциативное суммирующее устройство. /Исмаилоз Ш-М.А., Зурхаев A.A., Магомедов И. А., Хачумов В.М. (СССР). N 4722382/24;-заявл. 14.06.69; Опубл. 2.3.07.91, Бюл. N27.

26..Хачумов В.К., Лагиева М.М. Метод сжатия и'идентификации • полутоновых изображений: Тез. докл. 2-ой международной KOHit.no компьютерной графике "Графикон-92". -М,: ИПК РАН. 1592. ' -С. 59-60.

21. Артамонов Е: и.. Кскаилов Ш-М. А.. Кокаев О.Г., Хачумов В.М. Специализированные алгоритмы и устройства обработки массивов данных. ■ - Махачкала: Дагестанское книжное издательство, 3 993.-304 с.

28. Хачуиов В.. К. Автоматизация' проектирования циклограмм: Тез. дцкл. XX Международной конф. САПР-93:. "Новые информационные технологии в науке, образовании и бизнесе".-Крым, /Гурзуф: ДО КО Украины, 1993. - С. 88-89.

29. Исмаилов Ш-М. А.'. Хачумов B.W. Решение задач машинной гра-

Фики в системе алгоритмов Волдера: Тез. докл. 3-ей международной конф. по компьютерной графике и визуализации. Том 2. - Санкт-Петербург: НГТО "ГРАФО", 1993.- С.24.

30.Хачумов В. М. Автоматизация выбора структуры цифрового устройства: Тез. докл. Российской научн.-техн. конф. "Интерактивные системы".-Ульяновск: УПИ. 1993,- С.39-40.

31.Хачумов В.М. Планирование эффективных совмещений в итерационных алгоритмах и устройствах машинной графики: Материалы сессии АЕН "Фундаментальные и прикладные вопросы естественных наук".-Махачкала: Лаг. академ. центр АЕН. 1994. -Т. 2.- С. 37-39.

32.Хачумов В.М. Эффективное вычисление многочленов"в специализированных системах машинной графики //Информатика и вычислительная техника. Теория и приложение. -Махачкала: ЛГУ. 1994,- С.83-86.

33.Хачумов В.М. Итерационные устройства машинной графики и обработки изображений: Тез. докл. Первого международного симп. "Интеллектуальные системы 94". -М.: МГТУ им: Баумана. 1994,- С. 142-143.

34.Хачумов В.М. Планирование многократной реализации арифметических выражений в специализированных' вычислительных структурах //Актуальные проблемы информатики, управления и радиоэлектроники.-Махачкала: ДПТИ, 1995.- с. 50-55.

35.Алибеков А.Г.. ' Лагиева М.М., Хачумов В.И. Определение ориентации трехмерных графических объектов //Изв. вузов. Приборостроение.-1995.-Т. 38. -. N3-4.-С.35-37.

36.Хачумов В.М. Обобщённое геометрическое преобразование в системе алгоритмов Волдера. // Изв. вузов. Приборостроение.-1995.-Т. 38.-К5-6.-С. 31-34. '

37.Хачумов В.М. Геометрический процессор с сокращенным набором команд.. - Труды 5-ой международной конф. по компьютерной графике и визуализации, в России'"Графикон'95". -Санкт-Петербург: НТТО "Графо". 1995,- С.43-44.

ЗЗ.Хачумов В.М. Определенно ялики вектора методом полозинно-• го угла // Информатика и вычислительная техника. Теория и приложения. Часть II. - Махачкала: Даг. отд.Международной акад. информат., 1995. - С. 83-86; -

39.Хачумов В.М. Автоматизированное построение конических се-

- ъг -

чений е системах машиной графики: Тез. докл. Международной конф, "Автоматизация проектирования дискретных систем", - Минск: БГУ, 1995. С. 122.

■ 40. Хачумов Б.М. Разрядно-параллельное представление алгорит-' мов Волдера // Информатика и вычислительная техника. Теория и приложения. Часть II. - Махачкала: Даг. отд. Международной акад. информат..1995.- С. 19-28.

41.Khachumov V.M. Dlsparalleling problems In Voider algorithms.: Тез.' докл. Международной конф. ■ "Интерактивные системы: Проблемы.человеко-компьютерного взаимодействия". Часть 2,- Ульяновск: УГТУ. 1995,- С. 56-57.

42. Хачумов В.М. Специализированное устройство для моделирования процессов реального времени: Тез., докл. Всероссийской научн.-техн.. конф. "Состояние.и перспективы развития термоэлектрического приборостроения".- Махачкала; ИПЦ ДГТУ, 1995. -С.63-64. •

43. Лагиева М.М:. .Хачумов В.М. Автоматизированный синтез специализированных арифметических ускорителей: Тез. докл.

■ Всероссийской научн.-техн. конф. "Состояние и перспективы развития термоэлектрического приборостроения".- Махачкала:. КПЦ ДГТУ, 1995,- С. 67.

44. Хачумов В.М. - Геометрические процессоры-реального времени ' для систем мониторинга: Тез: докл. Международного симп.

"Проблемы рационального природопользования и обеспечения ■ экологической'!; экономической безопасности Прикаспийского региона "Каспий-Балтика 95".' -С.Петербург: КПЦ ДГТУ, 1995. -С. 71. ■ ■ '

45. Хачумов В.М. Функциональная полнота и эффективность набора команд .геометрического процессора:Тез.докл.6-ой международной конференции по компьютерной графике и визуализации к России.Часть2.-С.-Петербург: Ц?йС ИТ'Ю.i966.-С.225.

46. Хачумов В.к.. Трехмерные операции Бодлера для измерения' длины E&KTopd-:' Тез. докл. Всероссийской -конф. "КкФормацион-нэ-упракшхзке систему и специализирОЕ.акнж вычислительные устройства для обработки и передачи данных".-Махачкала:' ЙПЦ ЛГТУ. 1996. - С. 95-96.