Синтез изображений рельефов и ландшафтов методом ROAM
на кластерной и CUDA- архитектурах
вычислительных систем

Введение

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

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

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

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

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

Основные алгоритмы синтеза изображений рельефов и ландшафтов

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

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

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

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

- методы, использующие иррегулярные сети треугольников (Shroeder, Rossignac, Borrel и др. [1, 2]);

- методы с ограниченной адаптивностью (Willem H. de Boer, Lossaso и Hoppe [3, 4]);

- методы иерархической триангуляции на основе квадродеревьев и бинарных деревьев треугольников (Duchaineau и Ulrich, [5, 6]).

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

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

Синтез изображений рельефов и ландшафтов методом ROAM на базовой вычислительной системе

Авторами была проведена программная реализация и исследования характеристик метода ROAM (время загрузки карты, производительность от количества выводимых треугольников) на ПК с четырех ядерным процессором (рис. 3, 4).

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

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

Синтез изображений рельефов и ландшафтов методом ROAM на архитектуре GPGPU (CUDA)

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

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

Например, время выполнения реализованных функций на видеокарте в 4-5 раз меньше времени выполнения на процессоре базовой системы, но загрузка данных в память видеокарты повышает общее время выполнения в 24 раза! (частая загрузка-выгрузка данных из оперативной памяти процессора в память видеокарты, на что уходит порядка 90-98% общего времени) (рис. 6).

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

Синтез изображений рельефов методом ROAM на параллельной кластерной вычислительной системе NeClus

Была создана программная параллельная реализация основных частей метода ROAM с использованием технологии MPI на кластере NeClus ДонНТУ (рис. 7).

Алгоритм синтеза ROAM переносится на параллельную архитектуру вычислительного кластера NeClus путем (рис. 8):

а) разбиения карты высот на части (патчи);

б) параллельной обработки патчей на вычислительных узлах кластера:

Реализованные основные функции выполняют инициализацию патчей (Init), построение точной аппроксимированной модели (Tessellate) и ее рендеринг (Render) (рис. 9). Используемая для исследований карта высот имеет размер 1024х1024, при размере патча 32х32, для распараллеливания требуется 2^k узлов вычислительного кластера. Так как кластер ограничивает количество используемых узлов для одной задачи, то каждый узел будет обрабатывать 32х32/k патчей, где k – количество используемых узлов.

Исследования показали, что использование MPI для организации параллельных вычислений на вычислительном кластере является эффективным. Так, использование 4-х узлов кластера позволяет увеличить производительность алгоритма в 2 раза при рендеринге 125000 треугольников (время выполнения алгоритма - 21мс, время реализации на базовой архитектуре – 40 мс, время реализации с использованием технологии CUDA - 750мс).

Увеличение количества используемых узлов кластера приводит к увеличению производительности алгоритма и уменьшению времени выполнения основных его частей (рис. 10) - время синтеза уменьшается на 85-90% с каждым двукратным увеличением числа узлов, и возможен синтез в реальном времени.

Выводы

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

Показано, что одним из эффективных методов решения поставленной задачи является метод ROAM. Проведено исследование эффективности реализации метода на базовой системе (ПК) и параллельных архитектурах вычислительных систем – параллельного GPU-мультипроцессора в составе современных видеокарт ПК (технология CUDA) и кластерной архитектуре NeClus (технология MPI), получены показатели процесса синтеза.

Показано, что ввиду отсутствия поддержки технологией CUDA рекурсивных вычислений и динамических древовидных структур в памяти GPU, использование CUDA является неэффективным (сами вычисления выполняются в 4-5 раз быстрее, чем вычисления на базовой системе, однако на частую загрузку-выгрузку данных из оперативной памяти процессора в память видеокарты уходит порядка 90-98% общего времени).

Показано, что использование MPI для организации параллельных вычислений на вычислительном кластере является эффективным, увеличение количества используемых узлов кластера приводит к увеличению производительности алгоритма и уменьшению времени выполнения основных его частей (время синтеза уменьшается на 85-90% с каждым двукратным увеличением числа узлов), и возможен синтез в реальном времени.