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

Г / • О 0 - /,

04 ' ^ ^ ° // -

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

На правах рукописи УДК 681.3

ВЕРЕТЕННИКОВ АЛЕКСАНДР АНАТОЛЬЕВИЧ

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

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

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

Научные руководители: доктор технических наук Титов B.C.

кандидат технических наук Довгаль В.М.

Курск 1999

2.6.3адача корректности растровой продукционной системы..... 62

Выводы........................................................................ 76

Глава 3.Способ структурно-функциональной организации базовго специализированного процессора для реализации растровой системы продукций............................................................. 77

3.1.Общие положения....................................................... 77

3.2.Структура клетки решающего массива и алгоритм ее функционирования............................................................ 77

3.3.Структура устройства предварительной обработки данных и алгоритм его функционирования.................................... 87

3.4.Алгоритм работы базового специализированного процессора для реализации растровой системы продукций............... 91

Выводы........................................................................ 97

Глава 4.Теоретический анализ характеристик базового специализированного процессора для реализации растровой системы продукций и оценка способов разложения в растр графических объектов...................................................................... 99

4.1.Методика оценки качества аппроксимации графических объектов при их разложении в растр с помощью системы продукционных правил................................................ 99

4.2.Результаты оценки качества аппроксимации символьно -ориентированных способов разложения в растр графических объектов............................................................ 102

4.3.Анализ СБИС базового специализированного процессора для реализации растровых систем продукций и рекомендации по основным направлениям его модернизации......................................................................... 109

Выводы........................................................................ 114

Заключение.............................................................................. 116

Список литературы.................................................................... 119

СОДЕРЖАНИЕ

Введение................................................................................ 5

Глава 1 .Современное состояние вопроса представления и обработки

графических данных........................................................ 16

1.1 .Эволюция систем обработки графических данных............. 16

1.2 .Методы представления графических данных.................... 21

1.3.Особенности организации специализированных процессорных устройств синтеза и обработки графических данных........................................................................ 26

1 АУстройства отображения графической информации............ 29

Выводы........................................................................ 33

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

2.1.Концептуальный базис и понятийный аппарат исследования.......................................................................... 34

--2.2.Разработка символьно - ориентированного способа представления графической информации............................... 39

2.3.Разработка способа, математической модели и алгоритма разложения в растр отрезка, основанных на анализе пространственного размещения "штрих - клетки".................. 46

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

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

ПРИЛОЖЕНИЕ 1.Алгоритмы работы отдельных блоков базового специализированного процессора для реализации растровой системы продукций.

ПРИЛОЖЕНИЕ 2.Программа анализа способа разложения в растр отрезка по методу цифрового дифференциального анализатора.

ПРИЛОЖЕНИЕ 3.Программа анализа способа разложения в растр отрезка по методу Брезенхема.

ПРИЛОЖЕНИЕ 4.Программа анализа способа разложения в растр окружности по методу Брезенхема.

ПРИЛОЖЕНИЕ 5.Программная модель устройства, реализующего метод разложения в растр отрезка, основанный на анализе пространственного размещения "штрих - клетки".

ПРИЛОЖЕНИЕ б.Программная модель устройства, реализующего метод разложения в растр отрезка, основанный на анализе пространственного размещения "штрих - клетки" с учетом величины ее отклонения от активной клетки.

ПРИЛОЖЕНИЕ 7.Программная модель устройства, реализующего метод разложения в растр окружности, основанный на анализе пространственного размещения "штрих -клетки" с учетом величины ее отклонения от активной клетки.

ПРИЛОЖЕНИЕ 8.Анализ базового специализированного процессора

для реализации растровой системы продукций

ВВЕДЕНИЕ.

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

В настоящее время признанными лидерами в производстве видеоподсистем персональных компьютеров являются такие фирмы, как S3, Cirrus Logic, Trident, ATI, Matrox, Tsend Labs, Weitek, Western Digital и некоторые другие [1]. Спектр выпускаемого ими оборудования весьма разнообразен. Так, например, компанией Western Digital выпущен мультимедиа-акселератор WD9710, который объединяет в себе стандартные графические компоненты, а также устройство для масштабирования и интерполяции видео, фильтр и преобразователь цветов. Микросхема Vision868 фирмы S3 выполняет ускорение обычных графических операций и, кроме этого, поддерживает преобразование форматов потока видеоданных. Микросхема GD5470 фирмы Cirrus Logic ориентирована на ускорение операций двух- и трехмерной графики. Графические акселераторы Viper Pro Video фирмы Diamond Multimedia Systems оснащены одновременно двумя процессорами и используют микросхемы Power9100 и Power9130 компании Weitek [2]. Для обеспечения высокой скорости вывода и высокого качества изображения в этих устройствах аппаратно реализованы алгоритмы интерполяции и экстраполяции видеосигналов. Графический акселератор Diamond Stealth II S220 представляет собой высокопроизводительный ускоритель двухмерной и трехмерной графики [3]. В нем, в частности, аппаратно реализованы наложение двух изображений разной прозрачности, хранение карты текстур на нескольких уровнях детализации и ряд других функций трехмерной графики. Видеоадаптер Viper V330 выполняет несколько быстрее функции, реализованные в ак-

селераторе Diamond Stealth II S220 и, кроме этого, в нем реализованы такие функции как подбор комбинации цветов вместо цвета, не поддерживаемого данным видеорежимом; масштабирование с интерполяцией; коррекция перспективы и другие.

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

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

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

Графическая информация является информативным способом представления и визуализации данных. При этом, в некоторых случаях ее вообще не представляется возможным чем-либо заменить, например, при коллективном выполнении исследований в таких областях науки как астрономия, биология, медицина, физика, криминалистика и др. - объем такой информации интенсивно нарастает. Задача её своевременной обработки и распространения усложняется вследствие лавинообразного роста объемов данных [5]. На этот процесс большое влияние оказало стремительное развитие сетевых технологий. По данным информационного отдела сети LMSNET [6] в 1994 г. в глобальной сети Internet работало около 15 млн. пользователей, а по всему миру было объединено около 20 тысяч сетей. На тот момент темпы роста се-

ти были такие, что каждый год количество ее пользователей удваивалось. А по сведениям специалистов компании WebCrawler [7] к началу 1997 г. число Web- серверов достигло 145166, при этом в расчет принимались только постоянно работающие единицы и не учитывались те, которые работали нерегулярно. Указанная цифра показывает, что 1996 г. был отмечен почти шестикратным приростом числа серверов в основном за счет создания новых. Подобное развитие вычислительных сетей приводит к росту объемов передаваемых данных (подавляющая часть которых - графического типа), к превышению допустимой информационной нагрузки коммуникационных каналов, а это, в свою очередь, - к увеличению времени ожидания ответа информационной системы на запрос пользователя.

Не только большие объемы передаваемых данных определяют время отклика системы. Существуют задачи, решение которых также определяет и скорость обмена и качество обработки информации. К ним, в частности, относится задача устранения искажений информационного сигнала вследствие его прохождения через разнородные среды передачи данных [8, 9]. Основываясь на теории цифровой обработки сигналов [10] и, учитывая специфику передачи дискретной информации [11], создаются специальные адаптивные системы передачи информации [12]. В этой области проводится достаточно большое количество исследований и предлагаются различные способы корректной передачи данных [8, 9, 13]. В частности, предлагаются специальные решения устранения межсимвольной интерференции и эффективной интерполяции модемных сигналов [14-16]. Данные решения имеют большее отношение к оконечному оборудованию систем передачи данных (например, модемам) и постановка задачи сводится к созданию специальных средств кодирования любых данных с целью их корректной передачи между абонентами телекоммуникационной системы связи. В данной же работе внимание сосредоточено на решение важной народнохозяйственной задачи синтеза данных графического типа с помощью специализированного процессора.

Проблемам представления и обработки графической информации посвятили свои работы такие исследователи как: В.В. Александров, Н.Д. Горский,

Дж.Т. Джол (John Т. Johl), С.Т. Кунг (Hsiang Т. Kung), Ф.С. Ли (Philip S. Liu), Г.Р. Надд (Graham R. Nudd), Р.Л. Пикард (Ray L. Picard), К. Престон (Kendall Preston), К. Фу (King-sun Fu), Ю.П. Чанг (Yetung P. Chiang), Т. Янг (Tzay Y. Young) и многие другие.

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

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

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

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

Данная работа выполнена в соответствии с программой П.Т.614 "Микропроцессорные ЭВМ с параллельной структурой и системы виртуальной реальности" (приказ министерства общего и профессионального образования РФ №572 от 02.03.98 г.) и в рамках международного проекта "Технические

системы обработки символьной информации и изображений" (распоряжение Госкомвуза РФ №10 от 19.02.93 г.).

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

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

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

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

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

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

5. Разработать рекомендации для модернизации базового специализированного процессора с целью порождения семейства устройств данного класса.

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

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

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

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

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

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

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

На защиту выносятся:

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

2. Способ и алгоритм разложения в растр отрезка, основанные на анализе пространственного размещения "штрих - клетки".

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

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

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

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

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