Введение к работе
Актуальность темы. В условиях быстрого роста парка компьютеров, одной из основных проблем взаимодействия между человеком и компьютером стала сложность программного обеспечения. Человек оказался не в состоянии быстро переключаться с одной задачи на другую и ориентироваться в море предоставляемой информации. Для того, чтобы сделать компьютер доступным каждому человеку и облегчить труд как специалиста, так и неспециалиста, стал необходим прозрачный, интуитивно понятный графический интерфейс с пользователем, в котором информация представляется в легко воспринимаемой форме, а управление программой осуществляется простыми и привычными способами, не требующими лишних действий и знаний. Да и с эргономической точки зрения, графический интерфейс, обладающий наибольшей гибкостью в формах и цветовой гамме отображаемых на экране объектов, явился оптимальным.
Однако, подобный интерфейс, особенно если применяется графика высокого разрешения и цветности, сопряжен с манипулированием большими объемами данных необходимых только для поддержания самого интерфейса и не имеющих никакого отношения к основным задачам программы. Подобные затраты на поддержание интерфейса оказались способны свести на нет эффективность использования выбранного типа интерфейса, замедляя вывод на экран монитора.
Решить эту проблему можно только совершенствованием методов программирования прикладных задач с использованием максимально гибких системных графических библиотек умело сочетающих аппаратные и программные ресурсы компьютера.
Помимо вновь появившихся задач графического интерфейса пользователя, всегда существовали и остаются актуальными задачи для систем с графическим ядром. К этому классу относятся системы построенные на графическом аппарате, являющемся ядром системы, а не всего лишь подсистемой отображения результатов их работы. Например, системы автоматизированного проектирования и моделирования объектов, системы визуализации в реальном времени промышленных процессов, цифровое телевидение, видеоигры и т.п..
Скорость вывода графической информации, как в системах с графическим ядром, так и с графическим интерфейсом пользователя, является важным фактором, влияющим на эффективность работы этих систем. Она определяется полнотой реализации различных графических функций аппаратными средствами и эффективностью реализации программных алгоритмов обработки информации при организации графического вывода.
Как известно, наибольшего эффекта в повышении производительности можно добиться модернизацией аппаратных средств. Но это ведет к значительному удорожанию устройств (в нашем случае - графических карт) и, как правило, к потере совместимости с существующими аппаратными и программными средствами.
В подобных условиях, эффективным подходом к решению проблемы увеличения производительности графической подсистемы ПК, является совокупность модернизации аппаратуры существующих графических карт, с оптимальным программным использованием аппаратных возможностей.
Правильная программная реализация процедур обработки и вывода графической информации открывает дополнительные возможности по ускорению и повышению эффективности работы графических систем.
Цель и задачи диссертации. Целью данной работы, было отыскание программных способов увеличения скорости графического вывода для карт SVGA на компьютерах класса IBM PC.
Эта цель достигалась путем исследования существующих алгоритмов вывода графической информации, особенностей аппаратуры указанных карт и компьютеров и последующего отыскания на основе полученной информации направлений оптимизации по скорости алгоритмов графического вывода.
Для достижения поставленной цели решались следующие задачи:
-
Исследование и классификация существующих графических систем, типов графической информации, принципов образования высокоуровневых графических объектов и примитивов из низкоуровневых.
-
Исследование влияния привязки программных алгоритмов к специфике центрального процессора и системы ввода/вывода на скорость графического вывода. В частности:
-
влияние общей алгоритмической оптимизации с целью использования новых команд старших моделей процессоров на производительность алгоритмов графического вывода;
-
влияние используемой разрядности регистров процессора и портов ввода/вывода на производительность алгоритмов графического вывода;
-
влияние применения специально отобранного по критерию минимума времени исполнения стандартных графических операций набора команд на производительность алгоритмов графического вывода.
3. Исследование возможности использования в алгоритмах вывода графиче
ской информации аппаратных средств повышения производительности,
реализованных в графических картах SVGA.
4. Исследование возможности разделения множества алгоритмов вывода
графической информации на уровни по степени их универсальности, и
_. влияние этого разделения на скорость графического вывода.
-
Исследование возможности перенесения реализации некоторых прикладных задач с уровня прикладного программирования на уровень системных графических библиотек, и влияние этого на скорость графического вывода.
-
Построение математической модели классической реализации универсального алгоритма отображения прямой линии с целью получения способа расчета времени исполнения как различных его частей, так и всего алгоритма в целом.
-
Разработка конкретных методов оптимизации алгоритмов графического вывода по какому-либо из исследованных направлений.
-
Оптимизация с помощью полученных методов какого-либо из базовых графических примитивов с целью подтверждения их эффективности.
Методы исследования. При работе над диссертацией использовались общие методы классификации информации; методы математического моделирования программных алгоритмов с помощью аппарата линейной алгебры; эвристические методы поиска оптимумов в таблично заданных зависимостях; методы итерационного преобразование алгоритмов с опорой на результаты математического моделирования; а также построение и анализ графических зависимостей.
Научная новизна.
-
Проанализированы графические системы двух основных видов - GKS и GUI, различные типы графической информации, принципы иерархического образования высокоуровневых графических объектов из низкоуровневых в GKS-системах, и высокоуровневых графических примитивов из низкоуровневых в GUI-системах. Составлены соответствующие классификации проиллюстрированные примерами объектов.
-
Предложен ряд общих направлений программной оптимизации алгоритмов графического вывода, пригодных для любых графических примитивов.
-
Построена математическая модель классической реализации универсального алгоритма отображения прямой линии, позволяющая рассчитывать время его исполнения при различных углах наклона и длине линии. В качестве результатов работы этой модели приведены таблицы и графики, иллюстрирующие зависимости времени исполнения всех блоков классического алгоритма прямой относительно угла наклона или длины отображаемой им линии.
-
Произведен детальный анализ некоторых из предложенных направлений оптимизации, и предложены конкретные методы оптимизации алгоритмов графического вывода по направлению "Привязка программных алгоритмов к специфике центрального процессора и системы ввода/вывода".
-
Произведена оптимизация универсального алгоритма прямой линии. Расчеты с помощью построенной модели показали, что в некоторых случаях удалось достичь 150%-го прироста производительности алгоритма (то есть в 2.5 раза). Полученный код на языке ассемблера представлен в приложениях к диссертации.
-
На основании материалов и результатов диссертации, построена графическая библиотека функций, предназначенная для отображения на экране компьютера базовых графических примитивов.
-
Выявлены зависимости, свидетельствующие о том, что для более современных моделей процессоров, в результате программной оптимизации алгоритмов графического вывода, удается получить больший прирост производительности, так как в этих процессорах имеется больше всевозможных технических усовершенствований, которые можно использовать при оптимизации.
Практическая ценность. С помощью идей и материалов, лежащих в основе данной диссертации, в 1993 году автором была реализована графическая библиотека VideoSupport. К моменту защиты диссертации данная библиотека в переработанном виде внедрена на четырех предприятиях города Москвы. Об этом свидетельствуют акты о внедрении, представленные в приложении к диссертации.
С помощью библиотеки VideoSupport в 1993 году в МКБ "ЭКАбанк" специалистами отдела сетей и отдела прикладного программного обеспечения были разработаны следующие программные продукты с графическим интерфейсом пользователя:
-
Инструментальное средство "VSOEdit", предназначенное для создания и редактирования специализированных графических объектов;
-
Программа статистической обработки информации о движении средств по лицевым и балансовым счетам банка;
-
Универсальная программа расчета начисления процентов по различным типам процентных ставок.
В течение 1994-1995 годов, была разработана вторая версия библиотеки VideoSupport, учитывающая появившиеся новые аппаратные средства и другие аспекты, влияющие на производительность алгоритмов графического вывода.
С ее помощью в 1996 году отделом автоматизации московского универмага "Вешняки" были разработаны следующие программные продукты с графическим интерфейсом пользователя:
-
Программное обеспечение аппаратно-программного комплекса "Cash-Desk", предназначенного для автоматизации рабочего места кассира торгового зала магазина;
-
Программа "Счета и главная бухгалтерская книга", предназначенная для автоматизации работы бухгалтерии предприятия;
-
Информационная система "Shops".
В этом же году отделом автоматизации универсама "Вешняковский" с помощью новой версии библиотеки VideoSupport был разработан пакет прикладных программ с графическим интерфейсом пользователя - "Payment", предназначенный для подготовки платежных поручений и автоматизации учета расчетов с поставщиками и подрядчиками универсама.
В 1998 году графическая библиотека VideoSupport была переработана автором с учетом конечных результатов данной диссертации.
Тогда же в "НИИ Экономики авиационной промышленности" его сотрудниками с помощыо переработанной версии библиотеки VideoSupport были разработаны следующие программные продукты с графическим интерфейсом пользователя:
-
Автоматизированная система проходной института с отображением фотографий сотрудников при считывании пропусков специально созданным устройством;
-
Автоматизированная система прогноза и анализа финансового состояния института.
В общем случае, результаты диссертации могут быть применены при по-
строетгаи графических библиотек для приложений, критичных к скорости вывода на экран векторных графических примитивов или графического интерфейса пользователя.
В список таких приложений могут быть включены текстовые и графические редакторы, обучающие системы, системы моделирования объектов и процессов, системы автоматизированного проектирования, разнообразные системные приложения, вплоть до интерфейсного ядра какой-либо операционной системы.
Кроме того, существует возможность применения материалов данной работы для увеличения скорости графического вывода и уже существующих приложений. Это становится возможно в том случае, если рассматриваемые продукты полностью открыты или имеют интерфейсы прикладного программирования достаточно низкого уровня.
Апробация результатов работы. Работа докладывалась на семинарах кафедры №242 МГИРЭА и лаборатории №15 ИГГИРАН и получила положительную оценку. Апробация работы произведена в процессе внедрения ее результатов, в частности - библиотеки графических функций VideoSupport, в организациях МКБ ЭКАбанк, московском универмаге "Вешняки", в универсаме "Вешняковский" и НИИ Экономики авиационной промышленности. Акты о внедрении приложены к диссертации.
Публикации. По материалам диссертации опубликовано пять статей в различных научно-технических журналах и сборниках статей, и издано одно учебное пособие МГИРЭА (80 стр.).
Результаты, выносимые на защиту.
-
Математическая модель для расчета времени исполнения универсального алгоритма отображения прямой линии при различных углах наклона и длине линии.
-
Методы ускорения графического вывода, связанные с оптимизацией программных алгоритмов в результате привязки к специфике центрального процессора и системы ввода/вывода.
-
Усовершенствованные для различных процессоров семейства х86 реализации универсального алгоритма отображения прямой линии.
Структура и объем работы. Диссертация состоит из введения, шести глав, основных результатов, выводов и шести приложений. В приложения входят: справочные таблицы, листинги программ, список сокращений и условных обозначений, список публикаций из 6-й наименований, 4 акта о внедрении, список использованной литературы из 60-и наименований.
Общий объем работы составляет 207 страниц, в них присутствуют 125 страницы текста, 176 иллюстраций (86 схем, диаграмм и рисунков, и 90 фрагментов листингов), 112 таблиц, 7 листингов программ.