BC/NW 2006, №2, (9) :7.2

ПОСТАНОВКА И РЕШЕНИЕ ОТКРЫТОЙ ЗАДАЧИ ПОИСКОВОГО ПРОЕКТИРОВАНИЯ ВИДЕОАКСЕЛЕРАТОРА

Д.А. Орлов, В.Ю. Харитонов

(Москва, Московский энергетический институт (ТУ), Россия)

Общеизвестный фактом является то, что львиную долю информации об окружающем мире человек получает с помощью зрения. Неудивительно, что компьютерная индустрия, выйдя в массы, стала интенсивно развиваться в сторону эффективной, а затем и эффектной визуализации процессов. Графике в современном компьютере уделяется самое пристальное внимание — от разработки красивых и ресурсоемких оболочек операционных систем до потрясающих воображение эффектов в новейших компьютерных играх и других задачах динамической 3D-визуализации, например, таких как организация виртуального группового полета над местностью [1,2].

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

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

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

Задачи динамической 3D-визуализации являются чрезвычайно сложными в вычислительном плане. Основная сложность заключается в том, что, в отличие от задач статической визуализации, где процесс построения изображения может идти днями, а то и месяцами, в рассматриваемых задачах изображение должно строиться в реальном времени, да еще и с частотой не менее 60 кадров в секунду (frames per second — FPS).

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

Рассмотрим теперь подробнее, как устроен современный видеоакселератор (рисунок 1).

В состав видеоакселератора входят следующие блоки: графический процессор (Graphics Processing Unit, GPU), видеопамять, внутренние (для подключения к системным шинам ЭВМ) и внешние (для подключения внешних устройств графического вывода) интерфейсы.

Основой графического процессора является один или несколько так называемых пиксельных конвейеров (pipelines), которые отвечают за операцию закраски пикселей на экране. Значительная часть вычислений пиксельного конвейера всегда связана с использованием одной или нескольких текстур, поэтому в состав GPU входят специальные текстурные блоки (Texture Module Unit, TMU), единственная задача которых — осуществлять выборку отдельных пикселей из текстур. Чтобы вовремя обеспечить графический процессор необходимыми данными, используется видеопамять с очень малым временем выборки, работающая на высокой частоте (600–1500 МГц) и имеющая шину данных высокой разрядности (до 256 бит). Для работы с ней в GPU интегрирован специальный высокопроизводительный контроллер памяти.

Характеристики видеоакселератора существенно влияют на производительность ЭВМ в задачах динамической 3D-визуализации. Однако, с увеличением производительности, цена видеоакселератора резко возрастает. Поэтому задача выбора и проектирования видеоакселераторов стоит очень остро. Для её решения предлагается использовать методы поискового проектирования.

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

Прежде чем решать задачу поискового проектирования, необходимо: определить поисковое пространство решаемой задачи (т. е. набор внутренних переменных, отображающих архитектурные особенности исследуемой области), задать параметры среды (определяющих параметры решаемой задачи с позиции исследователя), а также выбрать внешние показатели качества (отражающие цель проектирования). Следует отметить, что некоторые сочетания значений внутренних параметров принципиально не реализуются. Такие комбинации называются запрещёнными. Их также необходимо знать перед началом работы алгоритма. Затем экспертом задается начальная база фактов, включающая в себя как удачные комбинации значений внутренних параметров, так и заведомо неудачные. На основе базы фактов генерируется функция выбора, которая используется для оценки гипотез и фактов. После чего с помощью алгоритма поискового проектирования производится генерация гипотез, которые затем оцениваются экспертом как удачные или неудачные. Для облегчения оценки гипотез эксперт может использоваться дополнительный алгоритм. Оценка эксперта может противоречить оценке, которую даёт функция выбора, это означает, что необходимо расширить базу фактов. Все оценённые гипотезы добавляются в исходную базу фактов, и производится генерация следующего набора гипотез.

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

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

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

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

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

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

Также при оценке производительности учитывался такой показатель как сбалансированность видеоакселератора, т. е. соответствие значений его одних внутренних параметров значениям других параметров. Например, не имеет смысл ставить очень быстрый графический процессор при медленной видеопамяти, так как она будет являться «слабым звеном», и графический процессор не будет полностью загружен. С другой стороны, в данном случае установка более медленного графического процессора не повлияет на производительность, снизив при этом цену. Ограничения по сбалансированности позволят нам отсекать абсурдные гипотезы, а также избегать появления запрещённых комбинаций. Обычно для анализа сбалансированности принимают во внимание два соотношения: соотношение пропускной способности видеопамяти и частоты работы графического процессора и соотношение пропускной способности видеопамяти и её ёмкости. Последнее представляет собой оценку максимальной частоты кадров при условии, что будет использована вся видеопамять. Если это значение мало, тогда данный видеоакселератор не будет обеспечивать необходимую производительность в приложениях, работающих с большими объёмами текстур. Целесообразно ограничить его снизу 30 кадрами/сек, т.к. это минимальная частота кадров, которая позволяет работать относительно комфортно.

Для учета цены видеоакселератора были введены ценовые категории: Low-end (начальный уровень – самые дешёвые видеоакселераторы, обладающие относительно низкой производительностью), Middle-end (средний уровень) и High-end (высший уровень – самые дорогие и высокопроизводительные видеоакселераторы).

В данном исследовании были сформулированы две открытые задачи: а) подобрать видеоакселератор ценового класса High-end, которая обеспечивает производительность в среднем 60 кадров/с при высоком качестве изображения; б) выбрать видеоакселератор ценового класса Low-end, которая обеспечивает производительность около 30 кадров/с при низком качестве изображения.

Для решения рассматриваемых задач поискового проектирования применялся созданный на кафедре ВМСиС программный продукт Решатель Открытых Задач, который позволяет на основе существующей базы фактов выявить новые, возможно, ранее неизвестные, комбинации значений внутренних параметров, отвечающие поставленным условиям (гипотезы). Для анализа гипотез, выдвигаемых Решателем, разработан алгоритм оценки видеоакселераторов, основанный на предложенных выше методах оценки внешних показателей качества и реализованный в виде подключаемой библиотеки (блока качественной оценки). В данном алгоритме гипотеза считается удачной, если выполняются следующие 5 условий:

1) теоретическая оценка производительности должна быть не меньше заданной;

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

3) выполнение ограничения по сбалансированности ёмкости видеопамяти и её пропускной способности;

4) ёмкость видеопамяти должна быть не меньше необходимой;

5) ценовая категория должна быть не выше заданной.

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

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

Для первой задачи коэффициент ранговой корреляции по Кэнделлу составил 0,9, для второй задачи — 0,64, что говорит о достаточно хорошей настройке Решателя на проблемную среду.

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

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

ЛИТЕРАТУРА

1. Харитонов В.Ю. «Сетевая модель воспроизведения группового полета над местностью», Труды международной технической конференции «Информационные средства и технологии». Москва, МЭИ, 18-20 октября 2005г., в 3-х т.т. Т3. — М.: Янус-К, 2005. — с. 138 – 141.

2. Орлов Д.А. «Распараллеливание процесса динамической визуализации трёхмерных сцен», Труды международной технической конференции «Информационные средства и технологии». Москва, МЭИ, 18-20 октября 2005г., в 3-х т.т. Т3. – М.: Янус-К, 2005. – с. 116 – 119.

3. Дзегеленок И.И. Учебное пособие по курсу «Теоретические основы машинного проектирования»: Логика поиска проектных решений / И. И. Дзегеленок, Ред. А. К. Поляков, Московский энергетический институт (МЭИ). — М.: Изд-во МЭИ, 1984.