ПРОГРАММИРОВАНИЕ, 2013, No 3, с. 58-63
— ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ
У л :
ОБ ОДНОМ МЕТОДЕ РЕШЕНИЯ МАССОВЫХ ЗАДАЧ ПРИНАДЛЕЖНОСТИ ТОЧЕК ПРОИЗВОЛЬНЫМ ПОКРЫТИЯМ НА GPU
© 2013 г. И.Н. Скопин, Д.Ю. Трибис
Институт вычислительной математики и математической геофизики СО РАН 630090 Новосибирск, пр-т Академика Лаврентьева, 6 E-mail: iskopin@gmail.com, dtribis@mail.ru Поступила в редакцию 09.02.2012
Приводятся результаты численных экспериментов решения массовых задач определения принадлежности множества точек множеству произвольных фигур, составляющих покрытие области, либо пересекающихся друг с другом в пространствах произвольной размерности. Задачи решаются методами геометрической информатики с использованием графических ускорителей. Сравнение предлагаемого решения с использованием наиболее быстрого из классических алгоритмов показывает, что на ряде задач получаемые ускорения расчетов могут достигать от 6 до 700 раз. В качестве модельной задачи выбрана геофизическая модель земли и построение расчетных сеток для последующих численных геофизических расчетов. Подобные задачи типичны для любых численных экспериментов, геометрического моделирования, там где используются покрытия, триангулированные оболочки или решаются задачи рендеринга.
1. ВВЕДЕНИЕ
Быстрый рост производительности GPU (Graphics Processor Unit) и увеличение разрыва между ироизводительностями GPU и CPU (Central Processor Unit), наблюдаемые в последние годы [1], порождает все возрастающий интерес к вычислениям на графических процессорах. Хотя такие решения как CUDA [2] дают в распоряжение программиста богатые возможности организации параллельных вычислений, они требуют фундаментального знания методов параллельного программирования, архитектуры вычислителя и новых алгоритмов, необходимых для устройств с массовым параллелизмом. Используя такие средства, при переходе к расчетам на новом оборудовании программист обязан переписывать алгоритмы полностью с учетом обменов и меняющихся аппаратных возможностей GPU. Получающиеся программы часто оказываются несовместимыми с разными графическими ускорителями и быстро стареют вследствие развития GPU.
В предлагаемом подходе, основанном на методике геометрической информатики (ГИ) [3], задача преобразуется к такому виду, чтобы ее решение можно было изобразить с помощью последовательности двух- или трехмерных изображений (сцен). В качестве примитивной иллюстрации идеи можно привести пример решения системы произвольных уравнений. В методике ГИ вместо алгебраического манипулирования формулами или приведения к системам линейных уравнений мы можем просто нарисовать каждую кривую уникальным цветом в режиме комбинирования цветов (например, используя исключающее „или"). Координаты пикселей, в которых получатся цвета, отличные от цветов кривых, и есть решение. На первый взгляд такой подход не имеет преимуществ по сравнению с традиционным решением. И это справедливо, когда решается только одна система, но если требуются массовые вычисления, то с учетом аппаратных возможностей GPU и методов распараллеливания ГИ, позволяющих организовывать параллельное выполнение множества операций
рисования, производительность резко возрастает с ростом числа решаемых задач.
С точки зрения распараллеливания, алгоритмы ГИ выгодно отличаются тем что, всегда имеют несколько уровней параллелизма. Очевидно, что далеко не всегда программы, реализуемые в парадигме ГИ, будут более эффективны, нежели классические, но с появлением сверхмощных графических ускорителей это направление стало интересным с практической точки зрения. ГИ наглядна, не требует высокой квалификации от программиста и понимания деталей функционирования GPU и даже фундаментального знания параллельного программирования. Она исходит из того факта, что GPU разрабатываются прежде всего для графических операций рисования, под которые оптимизирована вся их аппаратная архитектура, поэтому максимальную производительность GPU следует ожидать именно на операциях рисования.
Интуитивная понятность процесса программирования и распараллеливания ГИ основывается на том, что для решения задач используется ряд простых и наглядных методов. Одним из них, имеющим принципиальное значение для подхода, является метод Раскрашенных Приоритетных Проекций (далее РПП) [4], суть которого состоит в следующем: последовательное рисование различных фигур приводит к последовательному изменению цветовой картины, по которой можно судить о геометрических свойствах обрабатываемых данных. В свою очередь, эти свойства могут интерпретироваться для решения достаточно широкого круга содержательных задач. Как будет показано ниже на примере задач принадлежности точек покрытиям, которые реально используются при построении расчетных и прочих сеток, эти методы могут приводить к значительному ускорению по сравнению с традиционными подходами.
На сегодняшний день в терминах ГИ сформулированы многие классические вычислительные задачи. Среди них построение сечений произвольных фигур произвольными кривыми, взаимных пересечений, дополнений произвольных фигур, поиск точек, попадающих в окрестность, проверка планарности графа, триангуляция, построение выпуклой оболочки конечного множества точек, численное интегрирование. Метода-
ми ГИ решается множество задач из области начертательной геометрии и другие, геометрически интерпретируемые задачи. Кроме того, ГИ может служить основой для выработки альтернативных классическим подходов к решению задач теории множеств и математической логики. В частности, весьма перспективно применение подхода к задачам доказательства исчислений высказываний и выяснения вычислимости логических формул.
Данная статья посвящена детальному сравнению производительности классических алгоритмов и алгоритмов ГИ на задачах принадлежности множества точек множеству произвольных фигур на основе проведения численного эксперимента. Эти задачи занимают заметное место при построении сеток для математического моделирования разнообразных физических процессов.
2. МОДЕЛЬНАЯ ЗАДАЧА
В качестве модельной задачи выбрано представление реальной модели среды под океанским дном. На рис. 1 показана картина скоростей распространения волн, созданная по реальным геофизическим данным. На ее основе были построены модели для последующих численных расчетов в двух видах: грубом (рис. 2, число слоев 13) и более точном (рис. 3 число слоев 1400).
Каждый слой представляет собой многоугольник, число углов которого варьируется от 7 до 40 с преобладанием многоугольников с количеством вершин около 30. Этот размер мы и будем считать характеристическим. Примем, что в двухмерном случае, на этапе подготовки данных для дальнейшего численного моделирования, должна быть построена расчетная сетка с числом узлов 1000 на 1000 для грубых расчетов и 5000 на 5000 для уточненных случаев. Таким образом, для грубой модели, в самом „легком случае" с минимальной сеткой, нам нужно решить 1000 х 1000 = 1.000.000 задач принадлежности точки для 13 тридцатиугольников, а в точном случае 5000 х 5000 = 25.000.000 для 1400 тридцатиугольников.
3. ЧИСЛЕННЫЙ ЭКСПЕРИМЕНТ
Для решения модельной задачи мы сознательно выбрали максимально неблагоприятное
Рис. 2. Грубое слоистое представление с числом слоев 13.
для ГИ алгоритмов аппаратное окружение, а именно: старый и медленный графический процессор ATi Radeon Graphics Processor X700, 128 Мб против достаточно быстрого центрального процессора с тактовой частотой 3 Гц и памятью в 1 Гб под управлением Windows XT. Сделано это для того, чтобы в чистом виде продемонстрировать преимущества самого подхода к решению ряда задач методами ГИ, нежели
мощь современных графических процессоров. Все решения снабжены программам« на С++, которые достаточно просты для понимания. Все операции рисования синхронны, т.е. прежде чем рисовать следующий многоугольник, мы ожидаем полной отрисовки предыдущих). Мы покажем, как даже для таких условий, когда GPU на одиночной операции проигрывает CPU в десять и более раз, результирующее
Рис. 3. Уточненное; представление с числом слоев 1400.
время для GPU на полной модельной задаче лучше в те же десять раз.
Программы были написаны на языке С++ и откомпилированы Microsoft Visual Studio 2008 [5].
ГИ решение приведено в работе [3].
На рис. 4 представлены данные, полученные при решении одиночной задачи принадлежности точки мнох'оух'ольнику с разным числом вершин. Графики были построены с использованием пакета Wolfram Mathematiea [6]. Соотношение CPU/GPU времен выполнения одиночных задач принадлежности точки мнемчгугольнику в зависимости от числа вершин приведено в таблице 1.
Полученные зависимости времени выполнения от числа задач линейны. Производительность быстро надает с увеличением числа вершин мно-х'оух'ольников. Заметим, что CPU на этой задаче показывает огромную производительность, выполняя миллион задач вемх) за 0.656 секунды. GPU на одиночных задачах проигрывает примерно в 10 раз, даже операция получения пикселя (GctPixcl) происходит почти в два раза медленнее (миллион за 1,26 секунды). Хотя с увеличением числа вершин ситуация и меняет-
ся, но чрезвычайно медленно, производительности сравниваются для нескольких тысяч вершин, что для нашего случая не имеет практических) значения.
Итш'овое время решения задачи с использованием CPU определяется следующим образом:
Грубый случай: 1000 х 1000 задач для 13 трид-цатиугольников или 1.524 х 13 = 19.812 секунды.
Точный случай: 5000 х 5000 задач для 1400
25 х 1.523 х 1400 =
53340
При оценке времени решения задачи на GPU необходимо учитывать следующую существенную особенность массовых расчетов методами ГИ. В каждом случае, даже при решении одиночной задачи, решение получается не для одной точки, а для всей области. Таким образом, если нужно решать задачи принадлежности для разных точек, но одной и той же фигуре или даже нескольких одним и тем же фигурам, нет необходимости рисовать их каждый раз, и задача сводится только к относительно быстрому получению пикселя. Как было показано выше, даже в этом случае время вычислений все еще в два раза медленнее, нежели
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.