Разработка методов и алгоритмов использования графических процессоров в задачах моделирования геофизических данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Трибис, Дмитрий Юрьевич

• Трибис, Дмитрий Юрьевич
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Трибис, Дмитрий Юрьевич

ВВЕДЕНИЕ

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

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

1.1 Введение

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

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

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

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

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

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

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

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

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

1.5 Выводы

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

2.1 Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

2.7 Выводы

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

3.1 Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.5 Выводы

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

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

4.1 Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Разработка методов и алгоритмов использования графических процессоров в задачах моделирования геофизических данных»

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

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

В области вычислительной геометрии имеется большое количество работ отечественных и зарубежных авторов, посвященных вопросу разработки новых алгоритмов, таких как Ф. Препарата, М. Шеймос [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. Разработана РПП методология решения задач на GPU, не требующая глубокого знания его устройства и умения программировать на CUDA.

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Трибис, Дмитрий Юрьевич, 2011 год

1. Автоматическая система высокоразрешающей обработки, интерпретации, анализа и моделирования сейсмических полей, Новосибирск, ОАО Сибнефтегеофизика,1ЖЬ:http://www.sibngf.ru/technology .html#ASPIS-W/

2. Алексеев A.A., Куликов А.И., Старушкин В.Г. Визуальный построитель геологических сред «Seismic Model Manager» // М.: Бурение&Нефть, №9, 2007, 48-49.

3. Абдулмазитов Р.Г., Саттаров Р.З. Комплексный анализ автоматизированной интерпретации материалов ГИС и геолого-промысловых данных с использованием программы «PROMGEO» // М.: Бурение&Нефть, №2, 2009, 3842.

4. Анисимов В.А., Малышкин В.Э. Средства параллельного программирования для крупноблочных многопроцессорных вычислительных комплексов // Теория и методы параллельной обработки информации, Новосибирск, 1988, 98-109.

5. Арустамов Х.А. Сборник задач по начертательной геометрии, М.: Машиностроение, 1978.

6. Беликов Д. А., Каминская Е.В. ИНФОРМАТИКА. Основы алгебры высказываний Учебно-методический комплекс. Томск, ТГУ, 2007.

7. Вершинин В.В., Завьялов Ю.С, Павлов Н.Н.Экстремальные свойства сплайнов и задача сглаживания, Новосибирск, Наука, 1988.

8. Вольхин К.А. Начертательная геометрия, Учебное пособие , Новосибирск, Новосибирский государственный технический университет,

9. Кафедра «Инженерная графика», URL: http://graph.power.nstu.ru/wolchin/umm/Graphbook/index.htm

10. Гильберт Д. Основания геометрии, М.:, Гостехиздат, 1948.

11. Гордон В. О., Семенов-Огиевский М. А. Курс начертательной геометрии, М.: Высшая школа, 2002.

12. Дискретная математика: алгоритмы, Санкт-Петербургский Государственный Университет Информационных Технологий Механики и Оптики, URL:http://rainjfmo.ru/cat/view^hp/theory/math/geometry-2005/

13. Обзоры и тестирования. Журнал iXBT.com, URL: http://www.ixbt.com

14. Иванов Е.Г. Автоматическая параллельная генерация неструктурированных расчетных сеток для задач вычислительной механики // автореф. канд. дис., Новосибирск, ИВТ СО РАН, 2007.

15. С. М. Алейников, А. А. Седаев Алгоритм генерации сетки в методе граничных элементов для плоских областей // М.: Математическое моделирование, №7, 1995, 81-93

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

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

18. Козлов В. И., Юдин А. Н. Теоретико-множественное описание геометрии трёхмерных областей с внутренней структурой для задач автоматизированного проектирования. // Новосибирск, Автометрия, №2, 1999, 78-82.

19. Кормен Т. X., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Вычислительная геометрия. Алгоритмы: построение и анализ, М.: «Вильяме», 2005.

20. Кострикин А.И., Манин Ю.И. Линейная алгебра и геометрия, М.: Наука, 1986

21. Крупский В.Н., Сложность вычислений, МГУ, URL: http://lpcs.math.msu.su/~krupski/Complexity/input/t2.html

22. Ласло М. Вычислительная геометрия и компьютерная графика на С++. М.: БИНОМ, 1997.

23. Левин Д., Малюх В., Ушаков Д., The PLM Encyclopedia, Новосибирск, Издательский дом «Азия», 2008.

24. Малов В.Ю., Бандман М.К., Есикова Т.Н., Трибис Д.Ю. Математические методы исследования территориально-производственных систем: учет условий переходного периода и изменения геополитического положения России //

25. М: Информационный бюллетень РФФИ, Т. 5, № 6, 1997, 136.

26. Монж Г. Начальное основание статики, СПб, 1803.

27. Монж Г. Начертательная геометрия. М.: Изд. АН СССР, 1947.

28. Монж Г. Приложение анализа к геометрии. M.JL: ОНТИ, 1936.

29. Новости Newsru.com, Военный бюджет США, URL: http://www.newsru.com/world/07oct2009/budget.html

30. Описание формата BMP, URL: http ://j enyay.net/Programming/Bmp/

31. Официальный сайт OpenGL, URL: http://www.opengl.org/

32. Официальный сайт компании Landmark, URL:http://www.lgc.ru/products/ds/wp/

33. Пилюгин В.В., Сумароков JI.H. Математические модели и вычислительный эксперимент. Геометрическое моделирование // Математическое моделирование, Т.6, N5, 1994, 123

34. Потишко А. В., Крушевская Д. П. Справочник по инженерной графике, Киев, Изд. Будивэльнык, 1976.

35. Препарата Ф., Шеймос М. Вычислительная геометрия: введение, М.: Мир, 1989.

36. Прохоров A.M. Физическая энциклопедия, М.: Большая Российская энциклопедия, 1998.

37. Рвачев В. JI. Теория R-функций и некоторые её приложения, Киев, Наукова думка, 1982.

38. Роджерсон Д., Основы СОМ, Изд. Forbidden Reality, New-York, 2002.

39. Скворцов A.B. Триангуляция Делоне и ее применение, Томск, Изд. Томского университета, 2002.

40. Скопин И.Н., Множественное структурирование данных, // Программирование, т.32, № 1, 2006, 125-131.

41. Тозик В.Т. Электронный учебник по начертательной геометрии, Кафедра Инженерной и Компьютерной Графики Санкт-Петербургского государственного университета ИТМО, URL: http://traffic.spb.ru/geom/

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

43. Ушаков Д.М. Введение в математические основы САПР , Новосибирск, Издательский дом «Азия», 2006.

44. Хартсхорн Р., Основы проективной геометрии, М.: Мир, 1970.

45. Шикин Е.В., Плис Л.И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей, М.: ДИАЛОГ-МИФИ, 1996.

46. Юдин А. Н. Система визуального объемного геометрического моделирования. Часть I. // Новосибирск, ИВМиМГ, Препринт 1122, 1998.

47. Berg М., Kreveld М., Overmars М., Schwarzkopf О., Computational Geometry: Algorithms and Applications, New-York, Springer, 2000.

48. Chen J., Computational Geometry: Methods and Applications, Texas A&M University, 1996.

49. Extensible Markup Language (XML), URL: http://www.w3 .org/XML/

50. Goodman J.E., O'Rourke J. Handbook of Discrete and Computational Geometry, New York, CRC Press LLC, 1997.

51. Heath T.L. A History of Greek Mathematics, Oxford, Oxford University Press, 1921.

52. IGDA International game developers organization, URL: http://www.igda.org/

53. Langetepe E., Zachmann G., Geometric Data Structures for Computer Graphics, Bonn, University of Bonn, 2003.

54. Leibniz G. W. Opuscules et fragments inédits de Leibniz, Paris, 1903.

55. Lemoin E. Geometrographie, C. Naud, Paris, 1902.

56. Microsoft System Development Network Library, URL: http://msdn.microsoft.com/

57. Mikhailenko B.G. Seismic fields in complex media: Atlas of Snapshots and Synthetic Seismograms. Novosibirsk, Computing Center SB RAS USSR, 1988.

58. Mount D. M., Computional Geometry, University of Maryland, 2002.

59. Nvidia Tesla, URL: http://ru.wikipedia.org/wiki/NVIDIATesla

60. NVidia, SeismicCity, URL: http://www.nvidia.ru/obiect/seismiccityru.html

61. Object Linking and Embedding, URL:http://ru.wikipedia.org/wiki/ObjectLinking and Embedding^ActiveX

62. O'Rourke J. Computational Geometry in C, Cambridge University Press, England, 1998.

63. Pirzadeh H., Computational Geometry with the Rotating Calipers, Montreal, McGill University, 1999.

64. Pricewaterhouse Coopers, Research & insights, URL: http://www.pwc.com/gx/en/research-insights/index.jhtml

65. Ruppert J., A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation // NASA Ames Research Center, 1994.

66. Schlumberger Information Solutions, URL: http://www.slb.ru/sis/

67. Subsia oil & Gas directory, URL: http://www.subsea.org/index.html

68. The JPEG committee home page, URL: http://www.ipeg.org/

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

70. 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, Novosibirsk, ICM&MG SB RAS, 2011, T. 15, 85-90.

71. Wolfram Research: Mathematica, URL: http ://www. wolfram, com/

72. Алгоритмы методы исходники, Пересечение: Два выпуклых многоугольника, URL:http://algolist.manual.ru/maths/geom/intersect/convex intersect.php