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

11-2 2684

На правах рукописи

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

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

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

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

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

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

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

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

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

доктор физико-математических наук Лаврентьев Михаил Михайлович кандидат физико-математических наук Скопин Игорь Николаевич

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

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

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

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

Автореферат разослан «4» апреля 2011 года.

Ученый секретарь Диссертационного совета

д.ф.-м.н.

Сорокин С.Б.

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

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

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

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

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

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

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

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

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

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

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

включая промышленные форматы хранения результатов сейсмической разведки БЕв-У и СДС методами геометрической информатики. Попытка расширения предлагаемого подхода для поддержки численных экспериментов в широкой области физического моделирования методами ГИ.

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

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

• На основе многообразных моделей построена обобщенная геометрическая модель для представления данных для представления данных сплошной среды и ее конкретизация - геофизическая модель Земли.

• Методами геометрической информатики приводятся решения негеометрических задач, таких как операции над множествами.

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

Прикладная ценность работы. Полученные результаты позволили создать Систему Геометрического Моделирования в Геофизике предназначенную для промышленного и научного использования. В частности, созданы:

Программные компоненты визуализации 2-3Б сейсмических разрезов с возможностью изменения масштаба, синхронизации изображений нескольких разрезов и визуализации трехмерных срезов параллельно осям Это позволяет работать с широким диапазоном данных, включая БЕС-У, СДС-3,5, синтетические сейсмограммы, результаты прямого численного эксперимента, в частности, мгновенные снимки получаемые в результате решения прямых задач геофизики. Данный компонент более 10 лет промышленно используется при обработке полевых сейсмических данных (имеется справка о внедрении).

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

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

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

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

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

Структура и объем работы. Диссертация общим объемом 158 станиц, включая 22 страницы приложений, состоит из введения, 4 глав, заключения, приложений и списка литературы из 70 наименований. В работе содержится 54 рисунка и 6 таблиц.

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

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

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

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

Во второй главе дается понятие о методах и технологиях геометрической информатики, описывается краткая история развития конкурирующих CPU и GPU (Graphics Processing Unit) процессоров с 2003г., приводятся цифры об их производительности, делается вывод о практической целесообразности использования графических вычислений, предлагается концепция геометрической информатики, использующая графические вычисления как метод решения задач. Вводятся основные понятия: Метод Раскрашенных Приоритетных Проекций (РПП), дающий основной принцип решения задач в ГИ, Конкурентная Вымещающая Модель Среды (КВМС) - абстрактное правило, определяющее

представление многообразий данных и принципов объединения моделей и пространстве для формирования обобщенной модели среды. Вводятся многообразные модели, позволяющие объединять несколько геометрических моделей в одну. Также приводятся методы оптимизации, распараллеливания и ускорения задач в ГИ - пространственный сдвиг, вычисления на бит-цветах и система подстановки цветов, позволяющие производить параллельные вычисления для нескольких задач в одной графической области. В §1 содержит введение и обоснование необходимости введения новых методов программирования для GPU. В §2 дается определение Геометрической Информатики, обсуждаются вопросы о ее возможной роли и месте, объясняется смысл основных терминов ГИ, понимание которых имеет принципиальное значение. В §3 дается развернутое описание Метода Раскрашенных Приоритетных Проекций на примере задачи принадлежности точки двум произвольным многоугольникам. Потребуем, чтобы эти фигуры рисовались в порядке их приоритета разными цветами. Очевидно, что последняя нарисованная фигура будет видна полностью, а остальные могут быть частично или полностью скрыты. Понятно также, что если на результирующем изображении не будет присутствовать цвет, соответствующий точке, то она скрыта одной из фигур. Данный метод будет работать для любой произвольной замкнутой фигуры. Таким же образом можно решать задачу о взаимных пересечениях произвольных фигур, если использовать растровые операции, комбинирующие цвета, например операцию побитового исключающего «или». Такой способ решения задач, при котором фигуры рисуются последовательно, в зависимости от их приоритета, уникальным цветом, а для решения используются цвета, получаемые на изображении, мы будем называть Методом Раскрашенных Приоритетных Проекций. Рассматривается двухмерный случай вычисления границ подобластей. В результате мы получаем матрицу, содержащую булевские значения для каждой точки. Для получения границы изменения параметра среды должна быть определена булевская функция f (г, AF, п) —> В, где V -

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

Далее используем следующий алгоритм:

8

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

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

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

В §4 дается формальное определение абстрактной графической машины. На основе этого строится модель вычислений ГИ. Приводится пример сравнения сложности классических алгоритмов вычислительной геометрии и ГИ.

Вычисления в ГИ для наглядности мы будем представлять в виде работы некоей Абстрактной Графической Машины (далее АГМ), производящей операции над пространственно упорядоченными множествами цветов (в случае 2D -квадратами, 3D - кубами, 4D - гиперкубами и т.д.).

Над цветами допустимы обычные битовые операции, описанные в §6. Определение. Пространственно упорядоченным множеством цветов (далее

ПУМЦ) мы будем называть множество q _ <

а,, ... сг,

, (тут С выписано для

ит\ "' "л

двухмерного случая), где для любых двух элементов в N- мерном пространстве существует операция ¿(а1 а~ ) = (0,1 К задающая частичный порядок но

индексам.

Для наглядности можно понимать ПУМЦ как N-мерные массивы, имеющие в качестве значений ГИ цвета.

Определение. Абстрактная Графическая Машина (АГМ) полностью определена, если:

1. Задано начальное состояние АГМ - ПУМЦ0.

2. Задано множество пар {/?=0 = {®ППУМЦ,} - где 0. - операция из списка допустимых над упорядоченными цветовыми множествами.

3. АГМ начинает свою работу с некоторого изначально заданного ПУМЦ0 состояния и последовательно применяет все операции ЛУМЦ0 = ПУМЦ0 ©,. ПУМЦ1, Н0...М, завершает свою работу, выполнив их все.

Смысл введения АГМ состоит, прежде всего, в том, что для каждой ©.

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

В §5 рассматривается обобщенная модель для представления данных сплошной среды. Геометрия расчетной области может быть представлена объединением подобластей

П = Л, и Ц-,иП* с границей Г и замыканием О = О и Г .

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

= ОиГ в каждой точке которого определено множество величин

£ = {б'р^,...,^}, где е Я , однозначно характеризующих среду, включая

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

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

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

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

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

1. Задано множество замкнутых подобластей о такое, что для

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

2. Для \/П ЗО^ е О, В Е N - называемая «базовая фигура» задающая начальные параметры среды, такая что для \/к, Ье. N Г( е Пй и с .

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

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

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

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

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

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

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

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

2. Разрешена только операция побитового исключающего «или» (ХОК).

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

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

Т.е. если а, Ъ е С. где С - множество цвет-битов, то для любой операции F(o,¿)=>C будет существовать такая операция /?(</) => С,с/ е С, что если = то Я(с1) = {а,Ь}.

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

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

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

границ модели () от получаемых с помощью методов ГИ (Г[И ), т.е.

5 = шах|т;гт, - гги |, для V/7 £ 0.к = £2 и Г*, такое, что для \/к е N , где N

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

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

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

доказательства законов алгебры высказываний методами ГИ, использующий ту же технику. Этот механизм лежит в основе битовых операций и делает модель вычислений ГИ полной, т.е. имея набор этих операций, мы можем организовать любые другие вычисления. В §3.4 описана общая математическая задача моделирования сплошных сред. Геометрия расчетной области может быть представлена объединением подобластей: Q = Q, U^Uv-^U^ с границей Г и

замыканием Q = Q U Г . Объединение сеточных элементов £У будем называть

сеточной областью: =(jQe, а ее замыкание обозначим через Q;' = QA Ijr'',

1

где ГА = иГА есть множество граничных сеточных граней. Каждая сеточная грань

т

Г* имеет свою (состоящую из ребер) границу и замыкание

Г^ = Г^ UE^ . Сеточная расчетная область включает в себя расчетную

область (Qc ) и может состоять из сеточных подобластей в

к

каждой из которых строится сетка своего вида.

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

В §4 приводятся данные численного эксперимента по определению сравнительной производительности CPU/GPU на массовых задачах принадлежности множества точек произвольным покрытиям. В качестве модельной задачи выбрано представление реальной модели среды под океанским дном. Полученные выводы: хотя в приведенном примере аппаратные возможности GPU были крайне ограниченными были достигнуты значительные ускорения (от 6 до 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, позволяющего работать с растровыми моделями. Приводится развитый пример экспорта данных на произвольной квадратной сетке,

написанной на языке Фортран в среде Compaq Visual Fortran. Приложение 3 детально описывает алгоритм вычислительной геометрии, позволяющий решать задачу о пересечении выпуклых многоугольников. В приложении 4 приведена таблица крупнейших компаний, занимающихся разведкой нефти и газа в мире. В приложении 5 описываются основные программные продукты компании Шлюмберже.

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

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

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

о Принадлежность точки произвольному многоугольнику,

о Взаимные пересечения произвольных фигур,

о Сечение произвольной фигуры произвольной кривой,

о Поиск точек попадающих в окрестность,

о Проверка планарности графа,

о Триангуляция.

о Построение выпуклой оболочки конечного множества точек,

о Вычисление площадей и интегрирование.

Также реализованы операции над множествами.

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

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

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

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

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

[3] Трибис Д.Ю., Пакет для визуализации и высокоразрешающего анализа данных сейсмической разведки // Труды конференции молодых ученых, Новосибирск, 1997. — с. 188-196. При поддержке РФФИ: 96-05-65944-а.

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

[5] Tribis D.Y., A program system for seismic fields visualization, Bulletin of the Novosibirsk Computing Center, Series: Mathematical Modeling in Geophisics, ICM&MG, 2008, T.12 —c.73-81.

[6] Малов В.Ю., Бандман M.K., Есикова Т.Н., Трибис Д.Ю., Математические методы исследования территориально-производственных систем: учет условий переходного периода и изменения геополитического положения России // Информационный бюллетень РФФИ. 1997. Т. 5. № 6. — с. 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, 2011, T.15 —c.23-28.

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

Отпечатано в типографии ООО « Омега Принт» 630090, г. Новосибирск, пр. Ак.ЛаврентьеваД оф.3-022 тел/факс ( 383) 335-65-23 email: omegap@yandex.ru

2010199349

2010199349

61 12-5/1405

Институт Вычислительной Математики и Математической Геофизики Сибирское отделение РОССИЙСКАЯ АКАДЕМИЯ НАУК

На правах рукописи

Трибис Дмитрий Юрьевич

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

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

Диссертация на соискание ученой степени кандидата технических наук

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

доктор физико-математических наук

профессор

В.П. Ильин

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

Оглавление

ВВЕДЕНИЕ 6

ГЛАВА I ГЕОФИЗИЧЕСКИЕ ИНФОРМАЦИОННЫЕ СИСТЕМЫ И

АЛГОРИТМЫ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ 21

1.1 Введение 21

1.2 Алгоритмы вычислительной геометрии 21

1.2.1 Построение выпуклой оболочки конечного множества точек 22

1.2.2 Проверка принадлежности точки многоугольнику 23

1.2.3 Пересечение двух выпуклых многоугольников 23

1.2.4 Триангуляция 25

1.3 Системы обработки и интерпретации геофизической информации 26

1.3.1 Обзор продуктов Schlumberger 27

1.3.2 Обзор продуктов Landmark 30

1.4 CAD/CAE/CAM системы 35

1.5 Выводы 38

ГЛАВА II ОСНОВЫ РПП МЕТОДОЛОГИИ 40

2.1 Введение 40

2.2 Место и роль РПП методологии 43

2.3 Метод раскрашенных приоритетных проекций 48

2.3.1 Двухмерный случай 48

2.3.2 Трехмерный случай 50

2.4 Конкурентная вымещающая модель сплошной среды 51

2.4.1 Постановка общей задачи моделирования сплошных сред 51

2.4.2 Вычисление изопараметрических линий 53

2.4.3 Конкурентная вымещающая модель сплошной среды 54

2.5 Параллельные вычисления в РПП методологии 58

2.5.1 Бинарная арифметика цветов 5 8

2.5.2 Параллельные вычисления на бит-цветах 60

2.5.3 Система подстановки цветов 64

2.6 Точность вычислений в РПП методологии 66

2.7 Выводы 69

ГЛАВА III РПП ЗАДАЧИ И АЛГОРИТМЫ 70

3.1 Введение 70

3.2 Геометрические алгоритмы на плоскости 71

3.2.1 Принадлежность точки произвольному многоугольнику 71

3.2.2 Сечение произвольной фигуры произвольной кривой 71

3.2.3 Поиск точек, попадающих в окрестность 71

3.2.4 Проверка, является ли граф плоским 71

3.2.5 Триангуляция 72

3.2.6 Построение выпуклой оболочки конечного множества точек 74

3.2.7 Вычисление определенных интегралов и площадей 75

3.2.8 Переход к пространствам размерности более двух 75

3.3 Другие алгоритмы и задачи 76

3.3.1 Алгоритмы начертательной геометрии 76

3.3.2 Операции над множествами с помощью РПП метода 77

3.3.3 Доказательства алгебры высказываний 79

3.4 Анализ производительности 81

3.4.1 Модельная задача 81

3.4.2 Численный эксперимент 83

3.4.3 Оценка производительности на модельной задаче 85

3.5 Выводы 86

ГЛАВА IV ОТКРЫТАЯ СИСТЕМА ВИЗУАЛИЗАЦИИ, АНАЛИЗА И ГЕОМЕТРИЧЕСКОГО МОДЕЛИРОВАНИЯ НА ПРИМЕРЕ

ГЕОФИЗИЧЕСКИХ ДАННЫХ 88

4.1 Введение 88

4.1.1 Слоистая геофизическая модель земли 90

4.1.2 Сейсмический разрез как растровая модель 90

4.1.3 Решеточные структуры, пространственная анизотропия 91

4.2 Архитектура и компонентная концепция системы 92

4.3 Реализация технологии визуализации сейсмических данных в SeismoView 96

4.3.1 Структура и функциональные возможности системы визуализации 97

4.3.2 Волновое поле 97

4.3.3 Амплитудная цветовая заливка 100

4.3.4 Цветовая карта 101

4.3.5 Редактирование палитр 101

4.3.6 Режим синхронизации изображений 102

4.3.7 Алгоритмы визуализации 104

4.3.8 Алгоритмы протяжения и зумирования 104

4.3.9 Алгоритм однопроходного рисования сейсмического поля 105

4.3.10 Трехмерные срезы 105

4.3.11 Практическое применение. Оценка эффективности 106

4.3.12 Реализация и принципы построения 107

4.3.13 Заключение 107

4.4 Принципы построения векторных моделей 108

4.5 Работа с растровыми моделями 115

4.6 Выводы 119

ЗАКЛЮЧЕНИЕ. ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧЕННЫЕ В

ДИССЕРТАЦИИ 121

ЛИТЕРАТУРА 122

ПРИЛОЖЕНИЯ 128

ПРИЛОЖЕНИЕ 1. ОПИСАНИЕ ОПЕРАЦИЙ И ДИАЛОГОВЫХ ОКОН

VECTORMODEL 128

ПРИЛОЖЕНИЕ 2. ШАОЕМОБЕЬ: УСТАНОВКА ПАРАМЕТРОВ МОДЕЛИ И ОСНОВНЫЕ ИНТЕРФЕЙСНЫЕ ФУНКЦИИ 132

ПРИЛОЖЕНИЕ 3. ПЕРЕСЕЧЕНИЕ ДВУХ ВЫПУКЛЫХ МНОГОУГОЛЬНИКОВ, ПОЯСНЕНИЯ К АЛГОРИТМУ 138

ВВЕДЕНИЕ

Актуальность работы

Актуальность для вычислительной геометрии

В области вычислительной геометрии имеется большое количество работ отечественных и зарубежных авторов, посвященных вопросу разработки новых алгоритмов, таких как Ф. Препарата, М. Шеймос [34], М. Ласло [21], A.B. Скворцов [38], Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн [18], М. Berg, М. Kreveld, М. Overmars, О. Schwarzkopf [46], D. Mount [57], Е. Langetepe, [52], Н. Pirzadeh [62], J. O'Rourke [49], [61], J. Chen [47]. К таким геометрическим задачам можно отнести триангуляцию области, построение выпуклой оболочки множества точек, определение принадлежности одного объекта другому, поиск их пересечения и т.д. Интерес к таким алгоритмам обусловлен тем, что методы вычислительной геометрии используются в системах автоматизированного проектирования, в задачах математического моделирования и визуализации результатов научных расчетов, в геоинформационных системах (ГИС), в комплексах обработки и интерпретации данных сейсморазведки, во многих других областях науки и техники. Наиболее широко используются инженерные системы геометрического моделирования (CAD/CAE), пришедшие на замену кульману. Они различаются как по функциональности, так и по области применения. Подробнее этот вопрос рассмотрен ниже. Особенно можно отметить разработки фирмы Autodesk (AutoCAD, AutoCAD Mechanical Desktop, Autodesk Inventor) и SolidWorks, включающие в себя различные расчеты и нормы механических систем. В отличие от классических алгоритмов, применяемых в вышеуказанных приложениях, предлагаемый в работе подход ориентирован на использование возможностей высокопроизводительных графических процессоров (GPU).

Актуальность для геометрического моделирования и практической геофизики

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

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

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

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

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

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

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

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

Цель диссертации

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

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

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

• в рамках этого подхода математическое определение геофизической модели земли и моделей сплошных сред, создание средств визуализации двух- и трехмерных сейсмических разрезов для форматов SEG-Y, СДС 3, СДС 5, разработка интегрированной системы геометрического моделирования в геофизике.

Научная новизна

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

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

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

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

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

Практическая ценность

• Полученные результаты позволили создать открытую Систему Геометрического Моделирования в Геофизике, предназначенную для промышленного и научного использования. В частности, созданы

о Программные компоненты построения геометрических моделей

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

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

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

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

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

Апробация работы

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

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

Публикации

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

Структура диссертации

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

Краткое содержание работы

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

В первой главе в п. 1.2 описываются задачи вычислительной геометрии, для которых впоследствии даются формулировки в предлагаемой РПП методологии. В п. 1.2.1 приведены краткие описания для следующих основных алгоритмов построения выпуклой оболочки конечного множества точек: Gift wrapping, Алгоритм Грэхема, Алгоритм Мелькмана, QuickHull, Разделяй-и-властвуй. В п.1.2.2 рассматриваются алгоритмы проверки принадлежности точки многоугольнику методом трассировки луча. В п. 1.2.3. рассмотрена задача пересечения двух выпуклых многоугольников. Далее в п. 1.2.4 кратко рассматривается определение и возможные решения задачи триангуляции.

Для анализа возможностей существующих систем в п. 1.3 рассмотрены информационные системы Schlumberger Information Solutions (SIS) (п. 1.3.1) и GeoGraphics фирмы Landmark (п. 1.3.2). Приводится список основных компонентов с кратким анализом функционального наполнения.

В п. 1.4 дан обзор систем автоматического проектирования CAD/CAE, демонстрирующий подход в геометрическом моделировании более

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

Во второй главе дается понятие о Р1111 методологии и технике решения задач, описывается краткая история развития конкурирующих CPU и GPU (Graphics Processing Unit) процессоров с 2003г., приводятся цифры об их производительности, делается вывод о практической целесообразности использования графических вычислений, описывается РПП методология, использующая графические вычисления как метод решения задач. Вводятся основные понятия: Метод Раскрашенных Приоритетных Проекций (РПП), дающий основно�