Введение к работе
Актуальность темы.
Актуальность для вычислительной геометрии. В области вычислительной геометрии имеется большое количество работ отечественных и зарубежных авторов, таких как: В.А. Рвачев, Ф. Препарата, М. Шеймос, М. Ласло, А.В. Скворцов, Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн, М. 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-3D сейсмических разрезов с возможностью изменения масштаба, синхронизации изображений нескольких разрезов и визуализации трехмерных срезов параллельно осям 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 таблицы.
