Организация параллельных вычислений рекурсивного построения воксельной графической структуры в системе РАНОК

А.В. Толок,
в.н.с., д.т.н., проф.,
ИПУ РАН, г. Москва,

Е.Н. Полякова,

магистр,

МГТУ «Станкин», г. Москва

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

This paper suggests a method of multisequencing the recursive algorithm of dividing a cube in order to build graphical voxel images on the analytical-design system RANOK. The method is based on the principle of increase of outer dimensions of the cube, using the reverse indices of filling, which provides both equal design load to the involved processors of the cluster and control over the calculated data within the cube.

Системы аналитического моделирования, работающие на основе построения воксельных графических структур, как правило, сталкиваются с двумя основными проблемами: скоростью обработки информации и ограниченной оперативной памятью (ОП) для хранения воксельного графического образа. Особенно остро эти вопросы возникают с применением рекурсивных алгоритмов по уточнению области определения исходного аналитического выражения [1, 2].

Система РАНОК (Рекурсивный Анализ На Образных Компонентах) относится к таким исследовательским системам математического моделирования, в основу которых заложены рекурсивные алгоритмы формирования воксельной графической информации, применяемой в изучении описываемой математической модели [3].

Спецификой подобных систем является активное применение ОП для загрузки 3D-массива графической информации, которое уже на относительно малой глубине рекурсивного уточнения области определения исследуемой функции требует гигабайты ОП. Решение проблемы «через жёсткий диск» приводит к увеличению и без того дефицитного времени обработки информации.

Задача организации параллельных вычислений рекурсивного построения воксельных графических структур в системе РАНОК должна придерживаться основных условий:

1. Обеспечивать достаточный ресурс ОП для работы с 3D-массивом графической информации;

2. Максимально использовать вычислительный ресурс, выделяемый под рекурсивное распределение параллельных расчётов;

3. Сохранить и использовать идеологию битового кодирования 3D-массива графической информации системы РАНОК для возможности «отката» рекурсивных процедур при сбоях оборудования и контроля сценария рекурсивного погружения.

Рассмотрим принципы организации динамически формируемого массива графических данных в системе РАНОК [4]. Количество подобластей для половинного деления области равно , где - размерность области разбиения. Рассмотрим случай обработки разбиением трёхмерной сцены , принципы которого легко переносимы на более низкие, а также на более высокие размерности сцен исследуемых объектов.

Количество элементов трёхмерного массива , содержащего результаты расчёта алгоритма итерационного уточнения посредством половинного деления, зависит от количества итераций и рассчитывается как . Определим индексную организацию формируемого массива в трёх направлениях . Длина индексного направления, выбранного вдоль одной из осей координат исследуемой сцены, составляет единиц. Таким образом, размер массива определяется как , где . Увеличение размера массива обратно пропорционально размеру конечного элемента области исследования. В ходе организации таких данных особый интерес представляет промежуточный этап – переход к следующей итерации уточнения, который должен содержать в себе как данные предшествующего этапа исследования области, так и данные исследуемой области на новом этапе уточняющего разбиения. При этом возможно применение известных методов организации динамических структур иерархического дерева, позволяющих хранить информацию каждого этапа на своём уровне иерархии [5, 6]. Недостатком таких структур является сложность восприятия целостности рассматриваемого объекта, а также избыточность информации, необходимая лишь для общей увязки структуры «сверху вниз». В действительности, в таких случаях нас интересует только текущая информация для перехода от одной итерации к другой, при этом все предшествующие этапы разбиения исключаются из рассмотрения.

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

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

рис.1 Пример первого уровня индексного разбиения динамического массива

На первом этапе трехмерный элемент (на рисунке - куб) подразделяется на восемь равных элементов (рис. 1). Таким образом, для организации индекса нам потребуется 3 бита (от 000 до 111). Проиндексируем массив так, чтобы последовательность нулей и единиц отражала трехмерное положение элементов объекта в соответствии с направлениями осей i, j, k. На рисунке видно, что нулевое значение соответствующего бита в значениях индексов определяет расположение куба непосредственно на координатной оси (подобно координатам единичного вектора). Логический номер поэлементного заполнения для рассмотренного случая можно определить как

,

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

На втором этапе уточнения трёхмерной сцены осуществляется разбиение областей, которым в массиве соответствуют элементы , на восемь равных элементов методом половинного деления. Рис.2 отображает динамическое развитие матрицы при переходе ко второму этапу уточнения трёхмерной области. При этом происходит увеличение размерности динамического массива в два раза вдоль каждой оси. Для наглядности на рис.2 логическая очередь заполнения массива отражена последовательным рядом значений, где с 9 по 16 - укрупнённые делимые элементы на последующей итерации рассматриваемой области определения. Элемент является «итерационным потомком» элемента , поскольку отражает ту же самую область, только уже в уточненном виде за счёт деления «итерационного предка» на восемь частей. Процесс итерационного уточнения трёхмерной области предусматривает последовательную обработку «итерационных предков» 1-8 с последовательным отражением результатов деления в «итерационных потомках» 9-16.

Такая организация заполнения позволяет сохранять данные, полученные на предыдущей итерации в первых ячейках матрицы до тех пор, пока не заполнятся все свободные ячейки значениями следующей итерации. Далее, элементы текущей итерации (16) «вытесняют» значения предыдущей итерации (1-8) в первых ячейках куба, и происходит переход к новой итерации с соответствующим увеличением массива. Это позволяет сохранять связь с предыдущей итерацией до требуемого предела.

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

рис.2 Организация логической последовательности заполнения динамического массива «от последнего элемента к первому»

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

Значения от до посредством трёхбитовой комбинации описывают разбиение элемента на подэлементы. Значения от до организуют шестизначный код, где первая тройка значений организует элементы глобального куба, а вторая тройка значений – элементы локальных кубиков, полученных в результате деления элемента глобального куба (рис..3.).

рис.3 Пример битового описания структуры динамического массива для трёх итераций разбиения

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

рис.4 Пример положения элемента при битовом сочетании 001 011 001

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

Рассмотрим переход от предлагаемого бинарного представления к индексному представлению и наоборот. Индексное представление элемента массива определяется как:

,

,

где - значения элементов для -ой трёхбитовой комбинации, - количество итераций алгоритма уточнения области, - размерность вектора бинарного представления элемента динамического массива. Например, для вектора элемента индексное представление можно получить в виде:

,

,

.

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

0 = 0 0 0

2 = 0 1 0

7 = 1 1 1 .

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

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

Для построения системы РАНОК в виде параллельной программы выбран подход организации распределения вычислительных ресурсов в виде «темпорированного» дерева алгоритма (Рис. 5). У такого дерева входные данные и результаты вычислений находятся в корневой вершине, а вычислительный процесс развивается от корня к листьям, а затем обратно. Задача сводится к разворачиванию графа полученного дерева на кластере с закреплением поддеревьев за отдельными процессорами.

рис. 5. Дерево алгоритма распараллеливания расчёта в системе РАНОК

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

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

, где

n = 3 – размерность пространства, i – количество итераций, k = 5 – количество компонент массива (признак принадлежности поверхности и четыре компоненты нормали), b = 2 – количество байт для каждой компоненты массива.

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

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

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

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

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

Литература

1. Tolok A.V. The way of automation of graphics method of the solution of mathematical modeling problems // The 19-th International Conference on Computer Graphics and Vision “GraphiCon’2009”, October 5-9, 2009, P. 313-314.

2. Мыльцев А.М., Толок А.В. Элементы математического анализа на основе воксельных отображений // СИСТЕМЫ ПРОЕКТИРОВАНИЯ, ТЕХНОЛОГИЧЕСКОЙ ПОДГОТОВКИ ПРОИЗВОДСТВА И УПРАВЛЕНИЯ ЭТАПАМИ ЖИЗНЕННОГО ЦИКЛА ПРОМЫШЛЕННОГО ПРОДУКТА (CAD/CAM/PDM - 2007). Тез. Докл., 7-й международной конференции. Под ред. Е.И. Артамонова. М.: Институт проблем управления РАН. – 2007. ISBN 5-201-14995-2. – С.13-14.

3. Толок А.В. Применение воксельных моделей в процессе автоматизации математического моделирования // Автоматика и телемеханика, №6, 2009. С. 167-180.

4. Толок А.В., Толок Н.Б. Математическая модель организации динамического формирования массива данных в процессе работы алго-ритма итерационного уточнения трехмерной области. // Фізико-матем. науки, Біологічні науки. Вісник Запорізького Державного університету: Збірник нау-кових статей. Запоріжжя: ЗДУ, N1, 2001 -С.101-104.

5. Max N., "Optical Models of Direct Volume Rendering", IEEE Transactions on Visualization and Computer Graphics, 1(2), June 1995.

6. Mundy J.L., and Ten G., The Image Understanding Environment: Overview, DARPA93(283-288).