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

э 3121

^* На гтоавах рукописи

ТРИБИС Дмитрий Юрьевич

РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ИСПОЛЬЗОВАНИЯ ГРАФИЧЕСКИХ ПРОЦЕССОРОВ В ЗАДАЧАХ МОДЕЛИРОВАНИЯ ГЕОФИЗИЧЕСКИХ ДАННЫХ

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Новосибирск - 2011

Работа выполнена в Учреждении Российской академии наук Институте вычислительной математики и математической геофизики Сибирского отделения РАН.

Научный руководитель:

доктор физико-математических наук профессор Ильин Валерий Павлович

Официальные оппоненты:

доктор физико-математических наук Лаврентьев Михаил Михайлович доктор технических наук Дебелов Виктор Алексеевич

Ведущая организация:

Учреждение Российской академии наук Институт систем информатики Сибирского отделения РАН

Защита состоится «14» февраля 2012 года в 15:00 часов на заседании диссертационного совета Д 003.061.02 при Учреждении Российской академии наук Институте вычислительной математики и математической геофизики Сибирского отделения РАН, по адресу: 630090, г. Новосибирск, проспект академика Лаврентьева, д.6.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Институте вычислительной математики и математической геофизики Сибирского отделения РАН.

Автореферат разослан 31 декабря 2011 года.

Ученый секретарь Диссертационного совета д.ф.-м.н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

Актуальность для вычислительной геометрии. В области вычислительной геометрии имеется большое количество работ отечественных и зарубежных авторов, таких как: В.А. Рвачев, Ф. Препарата, М. Шеймос, М. Ласло, A.B. Скворцов, Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн, М. Berg, М. Kreveld, М. Overmars, О. Schwarzkopf, D. Mount, Е. Langetepe, G. Zachmann, H. Pirzadeh, J. O'Rourke, J. Chen, посвященных вопросу разработки новых алгоритмов. К таким задачам можно отнести триангуляцию области, построение выпуклой оболочки множества точек, определение принадлежности одного объекта другому, поиск их пересечения и т.д. Интерес к этим алгоритмам обусловлен тем, что методы вычислительной геометрии используются в системах автоматизированного проектирования, в задачах математического моделирования и визуализации результатов научных расчетов, в геоинформационных системах (ГИС), в комплексах обработки и интерпретации данных сейсморазведки, во многих других областях науки и техники. В отличие от классических алгоритмов, применяемых в вышеуказанных приложениях, предлагаемый в работе подход ориентирован на использование возможностей высокопроизводительных графических процессоров (GPU).

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

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

Земле, моделирование вулканической активности, поиск предвестников землетрясений и т.д.

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

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

РПП методы основаны на использовании простых графических операций и не требуют глубокого знания параллельного программирования или устройства графических процессоров, показывая при этом высокую производительность (в эксперименте были получены ускорения более 700 раз, подробнее п.3.4.3) на ряде задач. Связано это с тем, что графические процессоры изначально разработаны и оптимизированы для параллельного выполнения именно графических операций.

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

Цели диссертационной работы. Разработка подхода организации параллельных вычислений на GPU на основе РПП методов. Создание РПП алгоритмов вычислительной геометрии: взаимных включений, пересечений, сечений фигур, построение выпуклой оболочки конечного множества точек, поиск точек, попадающих в окрестность, триангуляция, вычисление площадей и объемов. Исследование вопросов применимости предлагаемых технологий для решения ряда негеометрических задач, таких как операции над множествами и доказательства алгебры высказываний.

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

анализа научных и полевых сейсмических данных в двух- и трехмерных случаях, включая промышленные форматы хранения результатов сейсмической разведки (SEG-Y и СДС) РПП методами. Предпринята попытка расширения предлагаемого подхода для поддержки численных экспериментов в широкой области физического моделирования.

Научная новизна работы.

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

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

• Показана принципиальная применимость методов РПП для решения негеометрических задач, таких как операции над множествами.

• В области поддержки параллельных вычислений на GPU предложена модель бит-цветной алгебры и системы подстановок цветов.

Прикладная ценность работы. Полученные результаты позволили создать Систему Геометрического Моделирования в Геофизике, предназначенную для промышленного и научного использования. В частности, реализованы программные компоненты визуализации 2-3 D сейсмических разрезов с возможностью изменения масштаба, синхронизации изображений нескольких разрезов и визуализации трехмерных срезов параллельно осям XYZ. Это позволяет работать с широким диапазоном данных, в том числе с форматами SEG-Y, СДС-3,5, синтетическими сейсмограммами, результатами прямого численного эксперимента, в частности, мгновенными снимками, полученными в результате решения прямых задач геофизики. Компонент более 10 лет промышленно используется при обработке полевых сейсмических данных (имеется справка о внедрении).

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

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

Апробация результатов диссертации. Основные результаты работы докладывались на Конференции Молодых Ученых (Новосибирск, 1997), на геофизическом семинаре University of Alberta (Университет Альберты, Эдмонтон, Канада, 1998), на 18-ой Международной Конференции по Компьютерной Графике и Зрению (Москва 2008), на заседаниях семинаров отдела Математических Задач Геофизики ИВМиМГ СО РАН в 2007-2008 годах, на семинаре в Сибирском Суперкомпьютерном Центре (2010), на семинаре кафедры прикладной математики Новосибирского Государственного Технического Университета (2011).

Работы по тематике диссертации выполнялись по гранту РФФИ № 96-05-65944-а «Поиск физических предвестников землетрясений на основе трехмерного численного моделирования распространения сейсмических волн через очаг ожидаемого землетрясения».

Публикации по теме диссертации. По материалам диссертации было опубликовано 7 работ, из них 1 по перечню ВАК Минобрнауки России, также имеется справка о внедрении в ОАО «Сибнефтегеофизике» (ранее «Сибирская Геофизическая Экспедиция»).

Структура и объем работы. Диссертация общим объемом 142 станицы, включая 12 страниц приложений, состоит из введения, 4 глав, заключения, приложений и списка литературы из 71 наименования. В работе содержится 47 рисунков и 4 таблицы.

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

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

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

Для анализа возможностей существующих систем в §3 рассмотрены информационные системы Schlumberger Information Solutions (SIS) и GeoGraphics фирмы Landmark. Приводится список их основных компонентов с кратким описанием. В §4 дан аналитический обзор систем автоматического проектирования CAD/CAE, демонстрирующий более универсальный подход в геометрическом моделировании. Даются примеры систем геометрического моделирования, более подробно рассматривается продукт фирмы SolidWorks, рассмотрены архитектура и функциональные возможности. В §5 содержатся выводы, полученные автором в обзорной части.

Во второй главе дается понятие о РПП методе и методологии решения задач с его помощью. §1 содержит введение и обоснование необходимости введения новых методов программирования для GPU. В §2 обсуждается место и роль РПП методов в вычислительной математике, объясняется смысл основных терминов, понимание которых имеет принципиальное значение. В §3 дается развернутое описание Метода Раскрашенных Приоритетных Проекций на примере задачи принадлежности точки двум произвольным многоугольникам. Потребуем, чтобы фигуры рисовались в порядке их приоритета разными цветами. Очевидно, что последняя нарисованная фигура будет видна полностью, а остальные могут быть частично или полностью скрыты. Понятно также, что если на результирующем изображении не будет присутствовать цвет, соответствующий точке, то она скрыта одной из фигур. Данный метод будет работать для любой произвольной замкнутой

фигуры. Таким же образом можно решать задачу о взаимных пересечениях произвольных фигур, если использовать растровые операции, комбинирующие цвета, например операцию побитового исключающего «или». Такой способ решения задач, при котором фигуры рисуются последовательно, в зависимости от их приоритета, уникальным цветом, а для решения используются цвета, получаемые на изображении, мы будем называть Методом Раскрашенных Приоритетных Проекций (РПП). Рассматривается двухмерный случай вычисления границ подобластей. В результате мы получаем матрицу, содержащую булевские значения для каждой точки. Для получения границы изменения параметра среды должна быть определена булевская функция f (У7, £г, п) —> В, где Г -

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

• Получим решение задачи принадлежности РПП методом на произвольной, расчетной сетке.

• Для каждой точки в полученном решении применим функцию f (F, Ar, ri) —> В ■ В результате получим матрицу, содержащую булевские значения для каждой точки.

Эта матрица и является решением задачи. В зависимости от определения функции f мы получим более или менее тонкие «линии» границ изменения параметров, соответствующие значению true в матрице.

В §4 рассматривается конкурентная вымещающая модель для представления данных сплошной среды. Геометрия расчетной области может быть представлена объединением подобластей Q = ii, U ii2 с границей Г и замыканием

Q = QUr. Под сплошной средой мы будем понимать часть континуального

пространства Q = Q U Г, в каждой точке которого определено множество

величин S = {S],S2,...,Sn}, где Sk е R, однозначно характеризующих среду,

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

• Сплошная среда представляется множеством замкнутьк подобластей, которые могут пересекаться.

• С каждой подобластью связан свой набор характеристик среды, неизменный в ее пределах.

• Для однозначного определения параметров среды в точках, принадлежащих нескольким областям, вводится дополнительное «конкурентное правило».

Конкурентная Вымещающая Модель Среды (КВМС) полностью определена если.

1. Задано множество замкнутых подобластей Qt = П U Tt такое, что для VA е N,

где N множество натуральных чисел, 3 Sk - множество параметров среды.

2. Для VQ CZ d, Ь € N - называемая «базовая фигура», задающая начальные параметры среды такая что для \/k (Е N Гц 6 С1И и

QtcQfl

3. Каждой подобласти сопоставлен уникальный номер Np е N. называемый ее приоритетом.

4. Выполняется конкурентное правило: при пересечении в пространстве нескольких подобластей точка считается принадлежащей подобласти с большим приоритетом.

Для КВМС несущественно, как представлена среда с точки зрения данных. Это могут быть любые представления, включая каркасные, твердотельные, поверхностные модели или функциональные уравнения и неравенства.

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

Определение. Цвет в терминах РПП - это произвольное целое число, имеющее смысл обычного в программировании битового представления цвета, например в RGB формате.

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

Определение. Бит-цветной алгеброй мы будем называть пару: алфавит, состоящий из бит-цветов, и множество операций над ними.

1. Алфавитом бит-цветной алгебры являются бит-цвета. Бит-Цветом называется такой цвет, где все биты, кроме одного, равны нулю. Например, для четырех-битового цвета бит-цветами будут: 1000,0100,0010,0001.

2. Разрешена только операция побитового «или» (OR).

3. Можно перемешивать обычные цвета и бит-цвета, если в цвете отсутствует бит бит-цвета.

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

Т.е. если а.Ь&С, где С - множество бит-цветов, то для любой операции F(a,b)=>C будет существовать такая операция R{d) => С,d е С, что если F(a,b) = d, то R(d) = {a,b}.

Приводятся примеры решения одновременно для двух задач принадлежности точки произвольному многоугольнику в одной и той же графической области. При этом только за счет использования бит-цветов было достигнуто 12-ти кратное ускорение, а полное ускорение, показанное на модельной задаче, достигало 700 раз (см. §3 третьей главы).

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

В §6 обсуждаются вопросы, связанные с точностью вычислений РПП методами, рассматриваются понятия динамической точности, искажения изображений на устройствах, накопление ошибок при вычислениях, результирующая точность при изменении масштаба в процессе вычисления. Далее под точностью S понимается максимальное отклонение значений истинных

границ модели (Г1гце) от получаемых с помощью РПП методов (Грпп ), т.е. д = тах|г1гш - гРПП |. для Vr 6 Q^. = Q f| ГА, такое, что для V& е N, где N

множество натуральных чисел, а Г54 имеет смысл, данный в определении

обобщенной модели для представления данных сплошной среды §5 второй главы. В §7 приведены выводы с полученными в главе результатами.

В третьей главе приводятся алгоритмы решения ряда задач РПП методами. В §1 дается введение описывающее перечень и особенности алгоритмов приводимых в главе. В §2 приведены так называемые «основные РПП алгоритмы на плоскости», что включает: принадлежность точки произвольной замкнутой фигуре, взаимные пересечения произвольных фигур, сечение произвольной фигуры произвольной кривой, поиск точек, попадающих в заданную окрестность, проверка планарности графа, триангуляция, построение выпуклой оболочки конечного множества точек, вычисление определенных интегралов и площадей. В §3 даются дополнительные РПП алгоритмы. Пункт 3.1 содержит описание возможности использования алгоритмов начертательной геометрии в РПП постановке, таких как сечение фигур плоскостью, пересечение прямой с поверхностью, пересечение двух круглых цилиндров, проекции разнообразных фигур. В п.3.2 описывается алгоритм, позволяющий РПП методами производить операции над множествами.

Диаграммы Эйлера - Венна изображают все 2" комбинаций п свойств, то есть конечную булеву алгебру. В п.3.3 приводится метод доказательства законов алгебры высказываний РПП методами, использующий ту же технику. Этот механизм лежит в основе битовых операций, т.е. имея набор этих операций, мы можем организовать любые другие вычисления. В п.3.4 описана общая математическая задача моделирования сплошных сред. Геометрия расчетной области может быть представлена объединением подобластей

О = О, с Фаницей Г и замыканием О = ПиГ . Объединение

сеточных элементов СУ будем называть сеточной областью: а* = , а ее

I

замыкание обозначим через П*=СУиГА, где ГЛ=иГ* есть множество

т

граничных сеточных граней. Каждая сеточная грань Г^ имеет свою (состоящую из ребер) границу Е^ и замыкание Г^ = Г^ и Е^ . Сеточная расчетная область

Q включает в себя расчетную область (QcQ ) и может состоять из сеточных

подобластей ( ÇÏ' =(Jfi£), в каждой из которых строится сетка своего вида.

*

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

В §4 приводятся данные численного эксперимента по определению сравнительной производительности CPU/GPU на массовых задачах принадлежности множества точек произвольным покрытиям. В качестве модельной задачи выбрано представление реальной модели среды под океанским дном. Хотя в приведенном примере аппаратные возможности GPU были крайне ограниченными, были достигнуты значительные ускорения (до 700 раз), по сравнению с вариантом исполнения на CPU. Это позволяет ожидать получения еще больших ускорений при решении подобных задач на более современных GPU.

В четвертой главе в §1 описывается практическое применение РПП методов с помощью построения открытой системы визуализации, анализа и геометрического моделирования на примере геофизических данных (сейсмическая разведка, модели Земли). Обсуждаются используемые на сегодняшний день методы и их недостатки. В §2 дается архитектура и компонентная концепция, примененная при создании описываемой системы, и ее преимущества: простота адаптации библиотеки компонентов, быстрая разработка приложений, распределенные вычисления, динамическая компоновка, инкапсуляция, независимость от языка программирования, возможность иметь несколько версий компонентов. Далее приводятся описания созданных программных компонент Открытой Системы Геометрического Моделирования в Геофизике, включающей средства построения и визуализации геофизической информации, построения геофизических моделей и моделей сплошных сред в так называемом 2.5 - мерном случае, а также программ, демонстрирующих принципы построения трехмерных моделей с возможностью их построения в виде задания графических примитивов в текстовом файле, трехмерной визуализацией и изменением масштаба средствами OpenGL. В §3 описывается компонент SeismoView, предназначенный для визуализации и высокоразрешающего анализа 2D- и 3D- полевых сейсмических

данных, записанных в форматах СДС-3. СДС-5, SEG-Y. В §4 описывается компонент VectorModel, представляющий собой развитую программную систему, предназначенную, прежде всего, для построения сложных геофизических моделей Земли, хотя компонент может быть эффективно использован для подготовки данных для моделирования произвольных сплошных сред. В §5 описывается компонент ImageModel для работы на больших потоках данных с растровыми моделями. Компонент дает возможность работы с самым широким спектром двухмерных физико-математических пространственных моделей, где геометрия среды представлена графическим образом (BMP, JPG) и раскрашена в соответствии с правилами РПП. Сюда включены все виды физических сред (гладких и разрывных), сплошные среды и поля, механические системы без сочленений. В §6 содержатся выводы о полученных в главе результатах.

В заключении приводятся основные выводы и результаты, полученные в диссертации.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1. Разработана РПП методология решения задач на GPU, не требующая глубокого знания устройства GPU и умения программировать на CUDA, которая может рассматриваться как альтернатива CUDA для ряда задач.

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

13

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

4. Предложена методика, позволяющая объединять различные виды геометрических моделей в рамках Конкурентной Вымещающей Модели среды. На основе этого построена геофизическая модель Земли.

5. Реализована Открытая Система Геометрического Моделирования в Геофизике включающая программные компоненты визуализации сейсмических полей, построения геофизических моделей Земли.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Ильин В.П., Трибис Д.Ю., Геометрическая информатика моделей сплошных сред // Вычислительные методы и программирование, Т. 10, 2009, 306-313.

[2] Ильин В.П., Трибис Д.Ю. Геометрическая информатика моделей сплошных сред // Труды 18-ой Международной Конференции по Компьютерной Графике и Зрению: GraphiCon 2008, Москва, МГУ, 2008, 313.

[3] Трибис Д.Ю. Пакет для визуализации и высокоразрешающего анализа данных сейсмической разведки // Труды конференции молодых ученых, Новосибирск, ИВМиМГ СО РАН. 1997. 188-196.

[4] Михайленко Б.Г., Конюх Г.В., Кривцов Ю.В., Мартынов В.Н., Соболева О.Н., Трибис Д.Ю., Фатьянов Г.А., Чимаева Е.В., Шишкин Г.В. Поиск физических предвестников землетрясений на основе 3-х мерного численного моделирования распространения сейсмических волн через очаг ожидаемого землетрясения // М.: Информационный бюллетень РФФИ: Т. 4, № 5, 1996, 645.

[5] Tribis D.Y. A program system for seismic fields visualization, Bulletin of the Novosibirsk Computing Center. Series: Mathematical Modeling in Geophisics , Novosibirsk. 1CM&MG SB RAS. Т. 12. 2008, 73-81.

[6J Малов В.Ю., Бандман M.K., Есикова Т.Н., Трибис Д.Ю. Математические методы исследования территориально-производственных систем: учет условий

переходного периода и изменения геополитического положения России // М.: Информационный бюллетень РФФИ, Т. 5, № 6, 1997, 136.

[7] Tribis D.Y. A method for solving of mass problem of determination accessory set of points to arbitrary coverings on GPU, Bulletin of the Novosibirsk Computing Center, Series: Numerical Analysis, ICM&MG SB RAS. T. 15. 2011, 85-90.

Подписано в печать 28.12.2011г. Формат 60x84 1\16 Усл. печ. л. I. Объем 16 стр. Тираж 100 экз. Заказ № 244

Отпечатано Омет Принт 630090, г Новосибирск, пр. ЛкЛаврентьевиб email: omegaptaiyandex.ni

2010281456

2010281456