Автоматика и телемеханика, № 1, 2014
А втоматизированные информационно-управляющие системы, системы управления производством
© 2014 г. С.Н. ГРИГОРЬЕВ, д-р техн. наук (Московский государственный технологический университет "Станкин"), А.В. ТОЛОК, д-р техн. наук (Институт проблем управления им. В.А. Трапезникова РАН, Москва)
ДИХОТОМИЧЕСКОЕ ИНДЕКСИРОВАНИЕ МАССИВА В РЕКУРСИВНОМ ПОСТРОЕНИИ ВОКСЕЛЬНО-ГРАФИЧЕСКИХ ОБРАЗОВ
Быстрое развитие многопроцессорных вычислительных систем кластерного типа позволяет ставить перед разработчиками компьютерно-графических систем задачи по организации графической информации, позволяющей эффективно применять параллельные алгоритмы. В работе рассматривается применение дихотомического принципа двоичного построения числовой последовательности для построения последовательной индексации элементов многомерного массива в задачах рекурсивного разбиения многомерного пространства. Такой принцип находит полезное применение в организации рекурсивного построения воксельной графической информации с дальнейшим применением в программных ускорителях графической обработки на основе распараллеливания алгоритма и частичной сортировки графического выходного потока по глубине рекурсии.
1. Введение
Организация хранения рекурсивно определяемых данных в ходе дихотомического деления относится к задачам представления массивов динамически возрастающих в размерах. Такая задача часто возникает при потребности упорядоченного деления пространства в статистических исследованиях, медицине, социологическом анализе и т.п. [1, 2].
Процесс дихотомического деления определяется как раздвоенность, последовательное деление на две части, не связанные между собой. Одним из наглядных представлений дихотомического деления является построение полного бинарного дерева.
В задачах геометрического моделирования для построения графических образов достаточно сложно представить приложение бинарных деревьев. В основном можно говорить о квадродеревьях и октановых деревьях, применяемых для представления растровых и воксельных графических данных.
Однако применение структурных представлений графических образов предполагает использование рекурсивного принципа дихотомического деления области изображения. В последнее время применение воксельного типа графических данных вызывает интерес в компьютерно-графических исследованиях как способ отображения сложных конструкций, представляемых аналитическими функциями. Например, при создании систем графического автоматизированного аналитического моделирования (ГСААМ) [3-5]. Это связано с ростом производительности компьютеров и появлением все более мощных графических ускорителей, открывающих новые возможности для компьютерной графики.
ГСААМ, работающие над построением воксельных графических данных, применяя способ рекурсивного деления, сталкиваются с проблемами кодирования индексации кубических массивов, предназначенных для заполнения и хранения воксельного графического образа [6]. Особенно остро эти вопросы возникают с применением подобных приемов в построении гиперкубических областей для графических образов многомерного аналитически заданного объекта [7].
Если представить куб в евклидовом пространстве Е3 прямоугольной решеткой, состоящей из отрезков (ребер куба), то разбиение куба на восемь равных кубов делит пополам все имеющиеся отрезки. По сути, выполняется дихотомическое деление отрезков в пространстве. Таким образом, можно говорить о таком делении куба как дихотомическом.
Алгоритмы дихотомического деления, как многие рекурсивные алгоритмы, с трудом находят применение в современных системах, поскольку требуют от компьютеров больших ресурсных затрат и сложно распараллеливаются.
Распараллеливание процесса рекурсивного построения дихотомического деления гиперкуба требует сохранения последовательного порядка индексации ячеек кубической сетки по мере удвоения ее размеров. Введение дополнительных процедур индексной сортировки пространственного массива приводит к усложнению алгоритмов и дополнительным временным затратам.
Очевидно, что распараллеливание рекурсивного процесса в целом не простой вопрос, поскольку древовидная структура рекурсии предусматривает поуровневое распределение потоков с захватом "ожидающих узлов", увеличивающееся на каждом уровне итерации [8, 9].
2. Постановка задачи
Рассмотрим некоторые примеры последовательностей нумерации элементов дихотомического деления для квадрата. Пронумеруем полученные элементы соответственно последовательности разбиения. Результат представлен на рис. 1,а.
На рисунке наблюдается отсутствие индексно возрастающей упорядоченной структуры элементов, как требуется при организации двумерного массива. Задача состоит в определении структуры рекурсивного разбиения, которая позволит получить последовательную индексацию элементов. Рас-
а
3 1 4
- 3 -1 2
3 4 - 1 -1 I 2
34
— 4 —
1
2
3 4 - 2 -1 I 2
43
— 4 —
1
2
4 3 - 1 -1 I 2
43
-3 -1 2
4 3 — 2 -1 I 2
23 - 2 -1 4
2 3 - 1 -1 I 4
23
- 3 -
1 4
2 3
- 4 — 1 I 4
0,3 I 1,3 — 0,1 —
0,2 1,2
0,1 1,1 — 0,0 —
0,0 I 1,0
2,3 3,3 — 1,1 —
2,2 3,2
2,1 3,1 — 1,0 —
2,0 I 3,0
Рис. 1. а - Примеры некоторых последовательностей заполнения элементов при дихотомической рекурсии разбиения квадратной области, б - упорядоченное расположение элементов массива.
смотрим пример индексации, представленной на рис. 1,б. Первое значение в каждой делимой ячейке отражает адрес расположения г-го элемента вдоль оси Ох, а второе значение (после точки) - индекс ^-го элемента вдоль оси Оу.
Такая организация индексов формируемого массива соблюдает рекурсивный порядок дихотомического деления, обеспечивая при этом последовательное распределение индекса по сторонам массива. Задачу можно сформулировать исходя их основных требований, относящихся к работе рекурсивных алгоритмов в процессе организации автоматизированных решений:
1. Получение удобной организации данных для дальнейшего применения распараллеливания вычислительных процессов.
2. Обеспечить достаточность имеющейся оперативной памяти для работы с 3Б-массивом информации.
3. Максимально использовать вычислительный ресурс, выделяемый под распараллеливание работы рекурсивного алгоритма.
Чтобы получить такую организацию массива в процессе работы рекурсивного алгоритма за основу берется дихотомический принцип построения полного бинарного дерева, и рассматриваются свойства организации бинарного значения на ветвях этого дерева.
3. Принцип бинарной дихотомии в числовой последовательности
Утверждение. Существующая двоичная организация числовой последовательности имеет дихотомический принцип построения.
(0000) (0001) (0010) (0011) (0100) (0101) (0110) (0111) (1000) (1001) (1010) (1011) (1100) (1101) (1110) (1111) Рис. 2. Бинарное дерево трехэтапного удвоения единичного отрезка.
0,1 1,1 — 0,1 —
0,0 1,0
0,1 1,1 —1,1 —
0,0 1,0
0,1
1,1
0,0 /\
0,1 — 1,0 /\
1,1
0,0 1,0 0,0 1,0
00 01 10 11
0 1 2 3
Рис. 3. Бинарное представление адресации элементов массива в процессе дихотомического деления квадратной области.
Доказательство. Построим полное бинарное дерево дихотомического деления, как показано на рис. 2.
Рисунок 2 наглядно изображает последовательность возрастания двоичного кода при последовательном переборе путей по всем ветвям полного бинарного дерева слева направо. Каждый битовый элемент битовой комбинации, указанной в скобках, своим значением характеризует начало или конец отрезка пути на каждом этапе удвоения. Все множество битовой комбинации, указанной в скобках, представляет двоичную последовательность десятичных чисел. Например, нижний ряд ветвей дерева содержит битовую информацию о десятичной последовательности [0 ... 15]. При окончательном рассмотрении можно говорить о том, что полное бинарное дерево на концах ветвей любого иерархического уровня формирует последовательное возрастание числового
значения битовой комбинации, отражающей признак узловых точек проделанного пути. Что и требовалось показать.
Вернемся к примеру дихотомического разбиения квадрата (рис. 1,б). Пример последовательности определения потомков дихотомического деления можно представить в виде четырех вариантов двухразрядных бинарных сочетаний (рис. 3). Выбирая последовательность первых разрядов всех уровней разбиения, получаем двоичное представление г-го индекса элемента вдоль оси Ох (как показано на рис. 3 стрелками). Не трудно заметить, что такая последовательность по г сохраняется для каждой j-й строки.
Аналогично получаем последовательность второго разряда на всех уровнях разбиения для ^-го индекса образуемого массива. Таким образом, левый нижний элемент приобретает адрес элемента (00.00) или (0.0) в десятичном представлении, а верхний правый элемент получает адрес (11.11) или (3.3). Любое последующее разбиение добавит по разряду каждому двоичному адресу (например, 000.000 или 111.111).
4. Принцип бинарной организации дихотомически делимого 3Б-массива данных
Определимся, что количество подобластей при одном половинном делении области равно 2П, где п - размерность разбиения. Рассмотрим случай дихотомического разбиения куба в евклидовом пространстве Е3, принципы которого легко переносимы на более низкие, а также на более высокие размерности пространства Е.
Число элементов I для трехмерного массива, полученное в результате дихотомического разбиения, зависит от количества половинных делений (в) и рассчитывается как I = 22ая. Определим индексную организацию формируемого массива в трех направлениях (г^,к) (рис. 4). Число элементов массива по одному из индексов составляет у/2пя единиц. Таким образом, пространство массива определяется произведением индексов г х ] х к, где г = ] = к и их значения лежат на промежутке [0,..., у/2пз — 1]. При организации таких данных основной интерес представляет процесс заполнения массива на каждом шаге дихотомического разбиения, который должен содержать в себе сохраненные данные предшествующего шага до этапа заполнения последнего элемента. Для этого возможно применение известных методов организации иерархического дерева, позволяющих хранить информаци
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.