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

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

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

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

Публикации.

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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