ПРОГРАММИРОВАНИЕ, 2014, No 6, с. 12-21
- ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ПРОГРАММИРОВАНИЯ
УДК 681.3.06
ЛОГИЧЕСКИЕ И МНОЖЕСТВЕННЫЕ ВЫЧИСЛЕНИЯ В
РАМКАХ ПАРАДИГМЫ ГЕОМЕТРИЧЕСКОЙ ИНФОРМАТИКИ *
© 2014 т. И.Н. Скопин1'2, Д.Ю. Трибис2
1 Институт вычислительной математики и математической геофизики, СО РАН
630090 Новосибирск, пр. Академика Лаврентьева, 6 2
630090 Новосибирск, ул. Пирогова, 2 E-mail: iskopin@gmail.com, dtribis@mail.ru Поступила в редакцию 26.02.2013
Обсуждаются возможности использования вычислительной модели геометрической информатики для решения задач, связанных с теоретико-множественными и логическими вычислениями. Предлагаются новые методы программирования для этих задач, которые отличаются высоким уровнем параллелизма при использовании современных графических процессоров.
1. ВВЕДЕНИЕ
Современные графические процессоры (GPU — Graphic Processor Unit и GPGPU — General Purpose Graphic Processor Unit) — это одни из самых высокопроизводительных средств вычислений, доступных на сегодняшний день [2]. Успешное продвижение таких технологий сильно ограничивается необходимостью перехода к новым методам программирования, поддерживающим массовый параллелизм, которые позволят в полной мере использовать потенциал таких устройств. Эта проблема гораздо шире, чем просто использование GPU или GPGPU. Чрезвычайно бурное развитие устройств, для которых основой вычислений являются графические операции, заставляет задуматься о практической полезности перехода к принципиально другой парадигме программирования и развития методов решения задач, основанных только на графических операциях. Развиваемая в течение последних лет [4, 5, 8, 14] концепция геометрической информатики
* Исследования, представление в статье, поддержаны грантом РФ РНФ № 14 — 11 00485 "Высокопроизводительные методы и технологии моделирования электрофизических процессов и устройств".
(ГИ) — одна из попыток формирования такой самостоятельной модели вычислений для подобных архитектур. Суть подхода заключается в формулировке задачи в графически пред-ставимом виде. Необходимо отметить, что ГИ не основывается и не обязательно использует технологии универсальных вычислений типа CUDA [12] или OpenCL [13]. Вместо этого предлагается применять элементарные функции рисования и оперирования с цветами, что делает концепцию независимой от GPU архитектуры и ее аппаратной реализации.
В наших предыдущих работах [8, 14] мы исследовали фактическую производительность ГИ на задачах принадлежности множества точек произвольным покрытиям, а также взаимных включений, пересечений фигур в 2-х, 3-х и N-мерных случаях. При их решении использовался метод раскрашенных приоритетных проекций (РПП), за счет которого достигалась впечатляющая производительность. Подробности метода РПП можно найти в [4, 14]. В предлагаемой работе обсуждаются возможности модели вычислений ГИ и, в частности, РПП метода для задач, использующих логические и множественные операции, которые в обычных постановках геометрическими не являются. Как показывает опыт,
в некоторых случаях применение ГИ для таких задач весьма эффективно.
2. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ
Диаграммы Венна или Круги Эйлера — геометрическая схема, позволяющая изобразить отношения между подмножествами. Важным частным случаем кругов Эйлера являются диаграммы Эйлера-Венна, изображающие все 2П комбинаций п свойств, то есть булеву алгебру. Еще до Эйлера такие геометрические схемы использовал Готфрид Вильгельм Лейбниц, для геометрической интерпретации логических связей между понятиями [10], однако именно Джон Венн подробно изложил графические методы в [3]. Круги — условный термин, вместо них могут быть использованы любые многомерные фигуры или отдельные точки. С учетом данного замечания далее мы говорим о кругах (и показываем их на иллюстрациях) и фигурах как о синонимах, понимая при этом возможность использования произвольных фигур.
Важным для нашего подхода является соглашение о том, что круги как объекты оперирования, появляются в результате выполнения операции рисования, которая рассматривается как атомарное действие, позволяющее интерпретировать появляющиеся на графической сцене фигуры как множества точек. Это соглашение буквально соответствует пониманию множеств в диаграммах Венна. Последовательное выполнение атомарных операций рисования позволяет говорить об иерархическом расположении фигур в пространстве, а совместное (параллельно выполняемое на программном или аппаратном уровне) рисование нескольких фигур следует рассматривать как оптимизационное преобразование. В многомерном случае обычное для двухмерного случая наложение фигур, реализующее последовательную проекцию на плоскость, заменятся механизмом рендеринга [7] и фигуры снова оказываются иерархически расположенными в пространстве.
Ниже приводятся РПП алгоритмы, реализующие все традиционные операции над множествами, сформулированные в геометрическом виде. Алгоритмы, реализующие множественные операции, чрезвычайно просты, поэтому проводятся с краткими комментариями, но без примеров
программ. Для наглядности, в начале, дается формальное математическое определение операции.
Определим РПП операции над множествами, тем самым устанавливая их связь с обычными множественными операциями.
• Объединение: и^2 = {х|х € Vх € ^2} — рисуем и одинаковым цветом, полученная фигура — это результат операции объединения.
• Пересечение: П ^2 = {х|х € Л х € ^2} — рисуем и ^2 разными цветами, используя комбинирующие растровые операции типа ХОЫ. Результатом операции пересечения является фигура, имеющая комбинированный цвет изображения ХОЫ ^2.
• Допишемие Р1 = {х|х € } — рисуем
цветом, отличным от цвета фона. Результатом операции дополнения является фигура цвета фона. Она занимает все пространство изображения без
• Разность: = П Ё2 = {х|х € Л х € ^2} — рисуем и ^2 разными цветами, используя комбинирующие растровые операции. Для ^2 цвет должен быть подобран так, чтобы растровая операция с цветом давала цвет Результатом операции разности на изображении является фигура, имеющая цвет
• Включение: С ^2 — рисуем и ^2 разными цветами. Отсутствие на изображении цвета фигуры говорит о том, что результат операции включения — истина.
С использованием этих операций любое вычисление над множествами может быть представлено как выражение, составленное из соответствующих РПП операций отрисовки фигур. По своей сути это то же самое, что рисование кругов Венна. Важно отметить, что графические процессоры допускают одновременное вычисление-рисование огромного числа РПП выражений, обеспечивая тем самым возможность очень быстрого вычисления значительного числа множественных выражений.
Рис. 1. Диаграмма Эйлора-Вонна. Отрицание, умножение и сложение.
Рис. 2. Доказательство на диаграммах Эйлора-Вонна.
3. ДОКАЗАТЕЛЬСТВА АЛГЕБРЫ ВЫСКАЗЫВАНИЙ
Доказать законы алгебры высказываний также можно с помощью диаграмм Эйлера-Венна [3]. Любое высказывание на диаграмме изображается кругом, а его отрицание частью плоскости, находящейся вне круга (рис. 1).
Если у нас есть два высказывания X и У, то их на диаграмме изображают двумя кругами, как правило, разного цвета. На рис. 1 слева показано отрицание X, в центре — логическое умножение (конъюнкция) высказываний X и У, а их логическое сложение (дизъюнкция) изображено справа. Другими словами, логическое умножение это пересечение кругов, а логическое сложение изображается как объединение кругов.
На рис. 2 показано, как с помощью диаграмм Эйлера-Венна можно доказать, что А Л В V А Л В = А.
В соответствии с приоритетом логических
АЛВ
(шаг 1), затем В (шаг 2), А Л В (шаг 3) и, наконец, выполнить сложение высказываний, полученных на шагах 1 и 3 (шаг 4).
На рис. 2. (шаг 2) заштрихована область ис-
В,
голубым цветом с белой штриховкой (шаг 3). Из последнего рисунка (шаг 4) непосредственно видно, что А Л В V А Л В = А.
Как и в случае вычислений над множествами,
логические выражения однозначно предетавимы как РПП выражения, и как следствие, для них допустимо параллельное вычисление, но здесь потенциал параллелизма значительно выше, поскольку атомарные элементы логических выражений не требуют для своего изображения более одного бита в точке-пикселе. О внутреннем представлении логических выражений в РПП речь пойдет в следующем разделе.
4. БИНАРНАЯ АРИФМЕТИКА ЦВЕТОВ
Приводимые ниже описания относятся к Windows GDI (Graphic Device Interface) [11], но эквивалентные средства имеются в любой операционной системе, поддерживающей работу пользователя с графикой. Они не требуют специального оборудования и работают на любом графическом процессоре.
Теоретически количество "чистых" цветов, которые можно использовать в вычислениях, никак не ограниченно, однако на практике это количество цветов, доступных системе. Фактически задача эквивалентна выбору основания системы исчисления. Цвет может кодироваться любым количеством бит. Для реалистичности мы примем 24-битное представление, и это вполне соответствует обычному современному компьютеру. В формате RGB мы фактически имеем трехпозиционную 256-ричную систему исчисления цветов, где каждая из трех позиций
Значение
Выбранное перо Битовый образ назначения
Побитовое II (AND)
Побитовое ОТРИЦАНИЕ (NOT) (жперсия)
Побитовое ИЛИ (OR)
Псйитотепе исключающее ИЛИ iXOR)
Колы двоичных растровых оперший
Растровая операция Логическая операция 1
К2_ BLACK a
Е2. COPYPEN P
Е2. MASKNOTPEN Ut>m
Е2_ MASKPEN Dpa
Е2. .MASKPENNOT Edna
К2_ MEROENOTFLN Dpna
Е2_ _MERGEPEN Dpy
Е2 MERGEPENNOT Шш
R2 NOP D
Е2 NOT to
К2 NOTCOPYPEN Bj
Е2 NOTMASKPEN Dpm
К2 NOTMERGEPEN Орда
К2 NOIXOKPEN Шш
Е2 _WHITE 1
Д2 XOEPEN liBs
Рис. 3. Аддитивное смещение цветов.
может меняться от 0 до 255. Цвет в RGB представлении кодируется тремя однобайтовыми значениями от 0 255, означающими вклад краежих) (Red), зележих) (Green) и ix).;iy6oix) (Blue), однако трехбайтовое слово не существует на большинстве компьютеров, поэтому цвет представляется двойным словом, четырехбайтовой переменной, в последнем байте которой чаще всего хранится параметр, соответствующий прозрачности {aRGB — коэффици
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.