Введение к работе
Актуальность.
Скорость решения задач машинной графики и обработки изображений является одной из наиболее важных характеристик качества вычислительной техники, для улучшения которой используют все доступные способы, включая аппаратурную реализацию наиболее употребительных операций, а также учет внутреннего и внешнего параллелизма обработки данных. Первые ап-паратно реализованные модули для ускорения геометрических преобразований, основанные на идеях Сазерленда И.. 'Спрулла Р., Гилоя В., Штрассена В. и др.. были созданы уже в конце 60-х годов. Современные специализированные процессоры, называемые дисплейными, графическими или геометрическими' (ГП). обычно выполняются в виде отдельных плат, встраиваемых в другие системы, и ориентированы на быструю реализацию графических алгоритмов. Так. например, производительность графических ускорителей.Freedom фирмы Hewlett Packard' составляет несколько миллионов преобразований-пространственных векторов в секунду, а процессор для компьютера Poly 300Р фирмы Poly-well Computers на базе RISC-процессора Alpha обрабатывает б секунду 360 к простых трехмерных фигур.
Тем не менее, задачи моделирования сцен реального мира требуют гораздо большей вычислительной мощности, чем сегодня имеет самый быстрый компьютер или. спецпроцессор. В этой свя-зи привлекают работы по созданию многопроцессорных графических станций. Фундаментальные основы построения подобных систем были развиты Кларком Дж., основателем компании Si Пеон Graphics. Созданный им конвейерный Геометрически;', процессе;; имеет до 12 программируемых процессорных элементов (Па) V. достигает- производительности равной сотням миллионов c:i> раций г секунду. Однако и он не может реиить ьсе-х ПрСаеаа:,: обеспечения скорости для приложений реального времени. Пег— тему во всем мире ведутся работы пс различным направления:.; сеьер^йнетьгвгч;" ГП, применяемых для решения задач ь таких с<аъ;ткх как САПР, цифровая обработка сигналов, расиеенапа-кие образов, тренажеры, индустрия компьютерных игр и фильмов.
Среди отечественных исследований отметим труды коллектива Института автоматики и электрометрии СО РАН по созданию'
геометрического процессора синтезирующей системы визуализации (ССВ). Существенный вклад внесен лабораториями образного анализа данных и машинной графики Института проблем управления РАК под руководством Прангишвили И.В. по созданию Графической синтезирующей системы реального времени (ПС ГРВ). Работа над совершенствованием математического и программного обеспечения с привязкой к современным техническим средствам машинной графики ведется в ИПМ РАН им. М.В.Келдыша под руководством Банковского Ю.М. Отечественные разработки ГП.представляют собой различные варианты параллельно-конвейерной обработки, но отставание в элементной базе не позволило добиться здесь рекордных показателей быстродействия. Современные исследования по построению спецпроцессоров,- ориентированных на решение траекторных задач в системе алгоритмов . Волдерз, выполнены в .- Санкт-Петербургском государственном электротехническом институте им. "- Ульянова (Ленина) Байковым В.Д., Сиоловым В.Б.. Вашкевичем С. Н. и Сергеевым М.Б. Однако итерационный/.; характер вычислений и сложность коррекции результата, оі'раничивают возможности использования этого-метода. Помимо конвейерной конфигурации для задач машинной графики часто используют-различные.параллельные включения многих процессоров.;:;;Эффективные системы. с массовым параллелизмом были разработаны,. ^например..:;;-'.фирмой" Motorola. Ее графические ускорители на ..основе"RISC-процессоров PowerPC подключаются к станциям Sun, или. встраиваются "в корпус, компьютера IBM ; для .вьшолнения параллельных программ. 'Наивысший эффект ускорения, достигается в систолических системах с поразрядной обработкой. '" В;: этой связи вызывает большой интерес теория разрядных вычислений,; :предложенная Пуховым Г.Е. и развитая его учениками, позволившая распараллелить ряд вычислительных процессов до .-уровня, отдельных/ разрядов, однако реализация сложных—геометрических преобразований -здесь затруднительна. Большой вклад ;,в; развитие принципов' конвейеризации и распа- раллеливания процессов, внесли- Самофалов К.Г., Луцкий Г.М., Поспелов Д. кг, Воеводин В.В.,' Карцев М.А., Трахтенгерц Э. А., Игнатущенко В. В., \Каляев-А. В;'.' .Котов В.Е.. Головкин Б.А., Вальковский В. А.'-'.-'и др.-. Создание ГП приводит, к необходимости решения задачи,' оптимальной настройки его решающего поля на
многократную реализацию графических алгоритмов. Существенный вклад в теорию периодических расписаний.. наиболее естественных для работы ГП. внесли Танаев B.C., Шкурба В. В.. Шурайц Ю.М., Гильман А.Л., Хаит Я.Г., Конвей Р.В., Максвелл В. А.. Миллер Л.В., Айзенштат B.C., Метельский А.С. и др.
Несмотря на достигнутые -успехи, проблема обеспечения высокой скорости обработки графической информации остается весьма актуальной.. Имеющиеся сегодня/процессоры в действительности, с одной стороны, обладают недостаточным параллелизмом, а с другой - мало подходят, для итеративных процессов, характерных д\пя большинства, алгоритмов машинной графики. Необходимость многократного счета по одной и той же. вычислительной схеме является наиболее.узким -местом в таких процессах как интерполяция^ проекционные и аффинные преобразования, закраска,-отсечение видовым-объемом и т.д. Это приводит к тому., что реалистическое изображение генерируется современными средствами'.непозволитель'но; долго. Для моделирования реальных процессов существующие системы следует заменить более совершенными. При этом требуется пересмотр' основных .алгоритмов 2D и ЗБ-граФики для адаптации к особенностям структур специализированных вычислителей.' Дополнительным источником ускорения может служить оптимизация представления графической информации. Таким образом актуальной является как задача совершенствования, структурной организации ГП. так и привязки к ним алгоритмов машинной трафики. «
Комплексное решение вопросов построения высокопроизводительных процессоров для эффективного решения геометрических задач представляет собой слокную научную проблему, решение которой имеет sasuoe народохозяйствекное значение.
' Пель работы заключается в развитии и применении теории проектирования разрядно-пзралпельных геометрических процессоров, обладающих ексокой скоростью обработки в сочетании с гибкой адаптацией к широкому кругу геометрических задач, з том числе задач машинной графики.. Указанная цель достигає: ся путем эффективной реализации типовых геометрических операций и планирования периодической обработки с совмещением циклов в среде из нескольких ПЭ. .
В соответствии с поставленной' целью основные этапы л
задачи работы определены следующим образом:
разработка новых способов представления и сжатия геометрической информации, обеспечивающих: ускоренное выполнение последовательности геометрических операций над полутоне -бой графической информацией; компактное хранение и восстановление геометрической информации с заданной точностью;
выбор эффективной алгоритмической и структурной организации ПЭ высокой производительности с ориентацией на геометрические операции, для чего требуется: обоснование набора операций; выбор вычислительных методов для реализации набора и их модификация; исследование и адаптация базовых алгоритмов к разрядно-параллельной вычислительной структуре;
разработка алгоритмов машинной графики, адаптированны:-; к структуре ГП " и их программирование б наборе команд ГПЭ; выявление параллелизма алгоритмов многократного выполнения:
разработка методов оперативного планирования периодической работы ГП с программируемой структурой для быстрой, реализации алгоритмов машинной графики;
разработка методов структурной оптимизации ГП. рационального представления исходных алгоритмов и применение теории для построения структур реальных устройств.
Методы исследования. . В работе используются методы теории множеств и графов, методы теоретической механики, аналитической геометрии,и алгебры: эвристические методы решения задач, математического, программирования; элементы математической статистики, теории расписаний и алгебры логики..
Научная новизна определяется развитием теории разряд-яо-параллельных вычислений и структур в направлении построения алгоритмических и структурных основ проектирования раз-рядно-параллельных геометрических процессоров с набором крупных операций/и эффективным совмещением циклов обработки информации.
Принципиальный вклад в развитие теории построения геометрических процессоров составляют следующие результаты, еы .-носимые на защиту: ;
1. Методы структурного описания объектов и подготовки данных для ГП на основе выделенных информативных параметров, обеспечивающие ускорение геометрических операций, а также
управляемое сжатие и восстановление графической информации.
-
Принципы построения геометрических процессорных элементов с набором аппаратно-реалкзованных крупных операций на основе комбинаций разрядно-параллельных представлений кодифицированных алгоритмов Волдера и.Пухова, обеспечивающие оптимальное соотношение меящу скоростью таблично-алгоритмических вычислений и аппаратурными затратам!.
-
Алгоритмические способы компенсации линейных искажений в процедурах Волдера, включая: ввод корректирующих углов, выбор дополнительных итераций., умнокение параллельного представления на компенсирующий коэффициент.
-
Алгоритмы решения итерационных задач машинной графики, адаптированные к структурам ГП, и способы их программирования в системе команд разрядно-параллельного ГПЭ..
-
Метод оперативного планирования.."периодических расписаний работы многопроцессорной. Геометрической -'машины (ГМ) с эффективным совмещением циклов,'':' включая,'формализацию задачи на основе выделенных косвенных показателей качества, алгоритм максимального совмещения циклов;. алгоритм '. псевдооптимального закрепления' ПЭ за операциями, способы совмещения параллельных комплексов алгоритмов." .
-
Метод настройки .'(оптимизации)' структуры ГМ или ГП. состоящего из набора программируемых ПЭ, . на заданный комплекс алгоритмов многократного выполнения и система программного обеспечения для автоматизации процессов проектирования.
-
Структуры разработанных и.практически реализованных геометрических процессоров , для Графической, синтезирующей системы реального времени ПС ГРВ.
Практическая ценность. Предложенный.метод проектирования разрядно-параллельных ГП с набором крупных операций, і! разработанное программное обеспечение для -оперативного плакирования периодических расписаний в системах из нескольких функционально-ориентированных ПЭ позволяет научно-обоснованно и эффективно решать геометрические задачи в областях вычислительной техники, САПР, системах машиной графики. ССВ и АСКИ. Разработанные формализованные модели и алгоритмы периодических процессоз, метод' разрезания, графовых моделей применимы'такке и для решения инженерных:задач, связанных с
многократным (циклическим) выполнением комплексов работ.
Достоверность разработанных в диссертации теоретических и прикладных основ проектирования геометрических процессоров применительно к итерационным алгоритмам машинной графики подтверждается математическими выкладками, моделированием на ЭВМ. результатами практического использования предложенных моделей, методов, программных и технических средств.
Реализация и внедрение результатов работы. Основные результаты диссертации получены автором при выполнении научно-исследовательских работ, проводимых Дагестанским политехническим институтом (Дагестанским государственным техническим университетом) совместно с Институтом проблем управления РАН в рамках: научно-технической проблемы ГКНТ при СМ СССР О.Ц.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.
Научные и практические результаты, полученные в диссертации использованы при чтении курсов "Компьютерная графика".' "Автоматизированное управление в технических системах" и "Вычислительные машины и- системы"; подготовке методических указаний и постановке лабораторных работ на кафедрах автоматики, прикладной математики и вычислительной техники Дагестанского государственного технического университета.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на: ХХУІІІ и XXIX конференциях молодых ученых Института проблем управления (г.Москва, 1982. 1983), Школе-семинаре по проблемам управления качеством продукции (Москва,1983); II Всесоюзном совещании "Автоматизация проектирования и конструирования" (Ленинград. 1983); Региональном научно-техническом семинаре Северо-Кав^ казского научного центра высшей школы "Автоматизированные системы управления технологическими комплексами на базе микропроцессоров, микро-и мини-ЭБМ" (Новочеркасск. 1983 ): IX Всесоюзном совещании по проблемам управления (Ереван. 1983); II Всесоюзной научно-технической конференции молодых ученых и специалистов приборостроительной промышленности (г.Москва. ВДНХ СССР. 1983); III. V.-VI и'VII научно-технических секи-.
нарах "Математическое обеспечение систем с машинной графикой" {Устинов, 1985; Ижевск,1988; Махачкала.1989; Тюмень, 1990); Всесоюзной конференции "Методы и микроэлектронные устройства цифрового преобразования и обработки информации" (Москва.1985): Всесоюзной научно-технической конференции "Проблемы развития аппаратных и программных средств вычислительной техники для машинного моделирования" . (Ыоск-ва. 1987): Научно-технической конференции "Образное представление данных в управлении и научных исследованиях" (Грозный, 1987;; Российской научно-технической конференции "Системны:*! анализ и принятие решений в задачах автоматизированного обеспечения качества и надежности изделий приборостроения и радиоэлектроники" (Махачкала. 1991); XX Международной конференции "САПР-93" (Крым, 1993); Российской научно-технической конференции-"Интерактивные системы" (Ульяновск.1993); ?.. 3, 5 и 6 -Международных конференциях по компьютерной графике и визуализацииУ в России "Графикой" (Москва: 1992; Санкт-Петербург: .1993,. 1995, 19S6); 1-ом Международном симпозиуме "ИНТЕЛС-94" (Махачкала.1994); 2-ой Международной научно-технической конференшш "Актуальные проблемы фундаментальных наук", (Москва, 1994);.- -Международной конференции "Автоматизация прРек.тігрс-Башія дискретных систем" ( Минск. 1995): Международной' конференцій. "Интерактивные системы: Проблеми человеко-компьютерного.';,- взаимодействия" (Ульяновск. 1995); Международном симпозиуме -. "Каспий-Балтика. 95" {Санкт-Петер-бург,1995)..- Всероссийской конференции "Информационно-управляющие системи ц специализированные вычислительные устройства для обработки и передачи-данных" (Махачкала,1996);' Международной ' КОНферЗНЩШ; "Информационные' ТеХНОЛОГІГЛ В іМОДЄЛИ-
розании и управлении"(Санкт-Петербург,1996),
Публикации.; По теке диссертации опубликовано 46 печатных работ, включая две монографии, 15 статей, 23 .тезисов докладов и .1 авторское свидетельство.
Структура и объем диссертации. -Диссертация состоит из сведения, вести разделов,- -заключения, списка литературы, иклачзющего 178 наименований, и .четырех приложений. Основная часть работы изложена на 2S6 страницах машинописного текста. Работа содержит 59 рисунков и 51 таблицу.