zabika.ru 1
How to Prepare Your GraphiCon’2011 Paper


Ivan Ivanov, Petr Petrov
Department of Computational Mathematics and Cybernetics

Moscow State University, Moscow, Russia
{ivan, petr}@graphicon.ru


Abstract

This is about how to prepare your GraphiCon’2011 paper. You may either read it or use it as a template for your own paper.

Your paper should have a short (no more than 250 words) — one to several paragraphs — abstract as the first section of the paper, which may be excerpted for reference or promotional purposes.

Relevant keywords should be placed just after the Abstract:

Keywords: Ray Tracing, Acceleration Structures, BVH, GPGPU, OpenCL, Real-time rendering.

1.Введение


Это введение.

2.ОБЗОР РАБОТ


Это обзор работ по теме исследования.

3.ПОСТАНОВКА ЗАДАЧИ


Формальная постановка задачи – что решалось и для каких данных? В чем специфика нашей постановки.

4.АРХИТЕКТУРА СИСТЕМЫ


Общее описание всех модулей системы. Что и как связано, в какой последовательности работает. Блок-схема синтеза изображения.



Figure 1: Your GraphiCon’2011 paper.

5.ПОСТРОЕНИЕ ДЕРЕВА

5.1Базовый алгоритм построения


В качестве базового алгоритма был взят классический алгоритм на основе Surface Area Heuristic [3], использованный также в работах [1] и [2]. Но, в отличии от указанных работ, мы не использовали простые эвристики, такие как “Median Splits” или “LBVH”, поскольку они ведут к снижению качества генерируемого дерева и, как следствие, худшей производительности на этапе трассировки лучей.

Алгоритм можно описать следующей последовательностью действий:
  1. Добавить в очередь заданий корневой узел дерева (узел, содержащий все геометрические примитивы).


  2. Сделать текущим первый узел очереди.

  3. Разбить текущий узел на 16 бинов по всем 3 осям. При этом для каждого бина вычисляется количество геометрических примитивов и выпуклая оболочка.

  4. С использованием SAH вычисляется оптимальная плоскость разбиения.

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

  6. Для каждого нового узла число геометрических примитивов сравнивается с заданным пороговым значением (мы использовали 4). Если число примитивов превышает указанный порог, то соответствующий узел добавляется в очередь задач.

  7. Текущий узел удаляется из очереди. Если очередь не пуста – переходим к шагу 2.

5.2Адаптация для GPU


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

Наиболее простой способ – отобразить одну задачу на одну рабочую группу (по терминологии OpenCL). В этом случае мы получим результат, аналогичный работе [2]: низкая производительность на первых уровнях дерева, так так в вычислениях будет задействована только часть доступных ядер, а также падение производительности на последних уровнях дерева, связанное с ростом накладных расходов на поддержание большого количества небольших задач.

Следующим относительно простым методом является метод, предложенный в работе [4] для архитектуры Intel MIC: для больших узлов (с количеством примитивов больше заданного порога) используется ресурсы всего графического процессора, после чего остальные узлы обрабатываются как и раньше – по одному на рабочую группу. Этот подход оказался эффективным для архитектуры Intel MIC, но при отображении на архитектуру ГПУ имеет ряд недостатков: также как и предыдущий подход он ведет к падению производительности на низких уровнях, появляется “промежуточный слой” – часть уровней, на которых одна задача не способна загрузить весь графический процессор, но количество задач мало для того, чтобы спровоцировать их на рабочие группы.

5.2.1Общая схема


Основываясь на описанных выше недостатках, мы разработали улучшенный алгоритм построения дерева на ГПУ:

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

  2. Для обработки узлов, содержащих достаточно большое количество геометрических примитивов (мы использовали порог 256), используется несколько рабочих групп на узел (мы использовали n/512, где n – количество геометрических примитивов в узле). В сочетании с оптимизацией из п.1) это позволяет получить использование ресурсов, близкое к оптимальному.

  3. Построение дерева было разбито на 3 этапа: обработка больших узлов (размером более 32K), обработка средних узлов (от 256 до 32K) и обработка малых узлов (менее 256 примитивов). Это дало возможность использовать специальные модификации алгоритма на каждом уровне, в следствии чего были сокращены накладные расходы и оптимизировано использование ресурсов ГПУ.



Рис. 1 Построение уровня дерева


На рис. 1 изображена наиболее общая схема генерации уровня дерева (используется на стадии обработки больших узлов). Из представленных стадий на центральном процессоре выполняются только отправка заданий и генерация новых заданий. Эти фазы обладают наименьшей трудоемкостью и их перенесение на графический процессор не является оправданным.

5.2.2Генерация заданий для GPU

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


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

[Формулы?]

5.2.3Подсчет


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

Этап можно условно разделить на 2 части:

  1. Преобразование информации о геометрических примитивов в информацию о бинах узла дерева.

  2. Применение к этим данным классического алгоритма параллельной редукции

Для реализации первой части нами был применен подход, схожий с примененными в [2] и [4] — примитивы каждой рабочей группы деляться на части по 16( по количеству использованных при построении дерева бинов ) и каждая из этих частей обрабатывается 16-ю последовательными потоками( полуварп в терминологии NVIDIA CUDA ). Это можно описать следующим псевдокодом:

for i in 1 to 16 do

if bin(triangle[i])=threadId bin[threadId].append(triangle[i])

Использование 16 проходов на 16 элементов может показаться излишним, но оно обладает следующими достоинствами:

  1. Практически идеально ложиться на SIMD архитектуру GPU.

  2. Сводит к минимуму конфликты при работе с памятью( bank conflincts, coaliasing ).

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

5.2.4Редукция

6.ПРОХОД ДЕРЕВА (traversing)

6.1Базовые алгоритмы прохода


Существует два основных подхода к реализации прохода дерева на GPU: стековый(stack based?) и безстековый (stackless). Безстековый подход был широко распространён когда для целей трассировки(raytracing?) были доступны только шейдеры (shaders). Поскольку запись данных из ядра (kernel) была возможна только в текущий элемент(texel?) выходной текстуры, для реализации полноценного стека приходилось использовать малоэффективные многопроходные(multipass) схемы работы. С появлением таких инструментов как CUDA и OpenCL стало возможным использование стека, так как мы можем легко получить доступ к глобальной памяти устройства на чтение/запись. Однако, для сравнения производительности мы рассмотрели и реализовали оба варианта.

6.1.1Безстековый


Безстековые алгоритмы, как правило, основаны на предварительной обработке дерева и предоставлении дополнительной информации для прохода по дереву. Примером такого подхода для BVH дерева является алгоритм, основанный на использовании escape index [5]. Для каждого узла (node) рассчитывается и хранится информация о том, какой узел проходится следующим. Алгоритм показал хорошие результаты на простых сценах, но на больших повёл себя значительно хуже чем стековый. Кроме того, в ситуации, когда дерево строится на каждом кадре, необходимо учитывать любую дополнительную обработку дерева.

[Можно ещё картинку и псевдокод]

6.1.2Стековый


Для прохода по дереву со стеком необходимо организовать отдельные стеки для каждого потока. Для этого необходимо выделить массив фиксированного размера в приватной (в терминологии OpenCL) памяти достаточный для хранения стека максимально возможной длинны как и в [6].

[Псевдокод]

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

7.РЕЗУЛЬТАТЫ

8.ЗАКЛЮЧЕНИЕ

9.AkNOLEDGMENTS


This work was supported by grant XXX.

10.References


  1. I. Wald, “On fast Construction of SAH-based Bounding Volume Hierarchies,” in Proceedings of the 2007 IEEE/Eurographics Symposium on Interactive Ray Tracing, 2007, pp. 33–40.

  2. C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, and D. Manocha, “Fast BVH Construction on GPUs,” Computer Graphics Forum, vol. 28, no. 2, pp. 375–384, 2009.

  3. J. Goldsmith and J. Salmon, “Automatic Creation of Object Hierarchies for Ray Tracing,” IEEE Computer Graphics and Applications, vol. 7,no. 5, pp. 14–20, 1987.

  4. Ingo Wald, “Fast Construction of SAH BVHs on the Intel Many Integrated Core (MIC) Architecture”.

  5. Thrane N., Simonsen L., “A Comparison of Acceleration Structures for GPU Assisted Ray Tracing”, 2005.

  6. ZHOU, K., HOU, Q., WANG, R., AND GUO, B. 2008. Real-time KD-tree construction on graphics hardware. ACM Trans. Graph. 27, 5, 1–11.