Введение 3
1. Теоретике - методологические основы интерполяции и программно -
аппаратных архитектур параллельных вычислений в недропользовании 9
1.1. Пространственная интерполяция геоданных 9
1.2. Методы пространственной интерполяции 13
1.3. Идея распараллеливания алгоритмов интерполяции в системах
недропользования 20
2. Анализ существующих методов и инструментов для параллельных вычислений пространственной интерполяции в системе недропользования. 28
2.1. Ускоренный алгоритм интерполяции с адаптивным обратным расстояниям с применением параллельных технологий 28
2.2. Параллельные технологии в алгоритме интерполяции Кригинга.. 37
2.3. Определение принципов универсального алгоритма пространственной интерполяции Кригинга 44
3. Разработка алгоритма интерполяции на основе OpenCL 54
3.1. Определение путей интеграции с OpenCL для проведения гетерогенных вычислений 54
3.2. Реализация алгоритма последовательного универсального Кригинга. Разработка кода для стандарта разработки приложений OpenCL 63
3.3. Апробация программно - алгоритмического обеспечения систем недропользования 69
Заключение 79
Список использованных источников 82
Приложения 88
В цепи операций, включающей этапы от анализа исходных данных опробования до принятия решений, выполняются многочисленные расчеты в циклах статистической обработки первичных данных, интерполяции, оптимизации и планирования добычи, что требует значительных вычислительных мощностей. В этой связи, задача ускорения расчетов за счет распараллеливания вычислений на многоядерных компьютерах и GPU с интеграцией программных решений в программном коде системы моделирования недропользования является весьма актуальной.
Типичные примеры методов, основанные на геостатистических концепциях (Кригинг), локальность (ближайший сосед и конечные элементные методы), гладкость и напряжение (сплайны) или специальные функциональные формы (полиномы, мульти - полиномы). Выбор дополнительного условия зависит от характера моделируемого явления и типа применения.
Поиск подходящих методов интерполяции для задач географических информационных систем предполагает несколько проблем. Моделируемые объекты, как правило, очень сложны, пространственные данные неоднородны и часто основаны на оптимальной выборке и значительном шуме, также могут присутствовать разрывы. Кроме того, наборы данных очень большие.
Исходя из различных источников с различной точностью, надежные инструменты интерполяции, подходящие для ГИС-приложений, должны удовлетворять нескольким важным требованиям:
• точность и прогностическую мощность,
• надежность и гибкость в описании различных типов явлений,
• сглаживание для шумных данных,
• n-мерная формулировка,
• непосредственная оценка производных (градиенты, кривизна),
• применимость к крупным наборов данных,
• вычислительной эффективности и простоты использования.
В настоящее время трудно найти способ, который выполняет все вышеупомянутые требования для широкого диапазона данных с привязкой. Следовательно, выбор адекватного метода с соответствующими параметрами для конкретного приложения имеют решающее значение. Различные методы могут давать совершенно разные пространственные представления. Детальное знание всех нюансов горной добычи, а также опыт накопленный людьми необходимы для оценки метода и выбора самого точного и близкого к реальности. Использование непригодного метода или неуместных параметров могут привести к искаженной модели карьера, что приведет к потенциально неправильным решениям при добычи полезных ископаемых основанной на вводящей в заблуждение пространственной информации.
Неуместная интерполяция может иметь еще больше последствий, если результат используется как вход для симуляции, где небольшая ошибка или искажение могут создавать модели для основанные на ложных пространственных шаблонах.
Проблема исследования заключается в использовании эффективных технологий параллельного программирования, которые появились относительно недавно и еще не нашли широкого применения, для обработки больших объемов данных по методам пространственной интерполяции. Традиционно используемые библиотеки не используют параллельные технологии. Решение этой проблемы обозначило новый фронт работ.
Актуальность решения проблемы для науки и практики информационных систем недропользования состоит в решении задач текущего и стратегического планирования добычи и выполнения оперативного подсчета запасов сырья. При эксплуатации месторождений полезных ископаемых строятся масштабные сеточные и блочные горно-геологические модели.
Цель исследования состоит в том, чтобы повысить эффективность и быстродействие (производительность) систем управления запасами горнорудных предприятий при добыче и переработке путем интеграции новых технологий параллельного программирования в методы пространственной интерполяции.
Выдвижение данной цели обусловило постановку следующих исследовательских задач:
1. Рассмотреть процесс пространственной интерполяции в системах недропользования, определить механизмы реализации интерполяции и методы оценки ее эффективности;
2. Изучить два наиболее используемых в современной науке и практике метода пространственной интерполяции - метод обратных взвешенных расстояний и метод Кригинга;
3. Изучить возможности программно-аппаратных архитектур параллельного программирования OpenCL и CUDA;
4. Провести анализ методов интерполяции и обозначить подходы, принципы интеграции технологий параллельного программирования ;
5. Исследовать возможность применения технологий параллельного программирования для создания механизма увеличения производительности алгоритмов интерполяции при обработке больших данных;
6. Выполнить проектирование и реализацию алгоритма пространственной интерполяции Кригинга с применением технологии параллельного программирования;
7. Разработать программный код OpenCL для метода пространственной интерполяции Кригинга;
8. Проанализировать результаты выполненной работы и сделать выводы.
Предметом исследования является процесс распараллеливания алгоритмов интерполяции с целью повысить быстродействия. Объектом исследования являются методы моделирования карьеров.
Гипотеза исследования заключается в решении проблемы увеличения быстродействия путем внедрения технологий параллельного
программирования, которая использовала бы вычислительные ресурсы центрального процессора совместно с графическим. Классические методы осуществления распараллеливании программ на центральных процессорах не учитывают все нюансы работы с памятью графических процессоров. Поэтому возможность объединения вычислительных ресурсов центрального и графического процессора сможет дать увеличение производительности существующих алгоритмов. Кроме того, обладая кроссплатформенностью такая реализация сможет с легкостью портироваться на различные вариации платформ и аппаратных устройств.
Теоретико-методологическая основа исследования базируется на работах отечественных специалистов Васильева П.В., Петина А.Н., Каневского М.Ф., Демьянова В.В., а также на многочисленных научных работах западных специалистов Fang Huang, Shuanshuan Bu, Jian Tao, Xicheng Tan, Gisele Goulart Tavaresa, Leonardo Goliatta, Marcelo Lobosco и многих других ученых. Список научных трудов всех специалистов представлен в советующем разделе выпускной квалификационной работы, который называется «список используемой литературы».
Эмпирическую базу исследования составили результаты экспериментов на центральном процессоре от Intel и графических процессорах от NVIDIA и AMD, а также на центральных процессорах от Intel. Исходные данные были взяты с сайта http://github.com.
Научная новизна: впервые на основе анализа существующих примеров использования параллельных технологий был спроектирован и реализован алгоритм пространственной интерполяции Кригинга для обработки больших данных, который обладает кроссплатформенностью, одновременном использовании на разного рода процессорах и может быть встроен в системы подсчета запасов полезных ископаемых.
Научно-практическая значимость исследования. Материалы исследования, а также его общие выводы свидетельствуют о возможности использования технологий параллельного программирования в методах пространственной интерполяции для гетерогенных систем недропользования.
Материал, представленный в диссертации, может быть использован при преподавании и изучении ряда дисциплин посвященным математике и компьютерным наукам: геостатистика, компьютерное и математическое моделирование, вариационные и дифференциальные вычисления, математическая статистика, параллельное программирование.
Практическое значение диссертационного исследования заключено в возможности разработки библиотек для существующих приложений обработки и анализа запасов месторождений. Библиотеки, основанные на научных исследованиях и практической реализации пространственной интерполяции, которые приведены в выпускной квалификационной работе, позволят горнодобывающим предприятиям оптимизировать свою работу на этапах анализа и проектирования с точки зрения экономики, рабочего времени и использования ресурсов организации.
Структура диссертации состоит из введения, трех глав, каждая глава имеет три раздела и общий вывод, в которых решаются поставленные исследовательские задачи, заключения, списка источников и литературы, а также приложений, необходимо дополняющих основной текст.
Первая глава посвящена изучению теоретико - методологическим основам пространственной интерполяции и программно - аппаратным архитектурам параллельных вычислений. Так же собраны идеи и уже существующие на данный момент современные системы, в которых применена концепция распараллеливания методов пространственной
интерполяции.
Во второй главе проведен анализ двух методов пространственной интерполяции, к которым была применена технология параллельных вычислений OpenCL. На основе этих разработок происходит планирование разработки алгоритма пространственной интерполяции Кригинга для гетерогенных систем недропользования на основе технологии параллельных вычислений OpenCL.
В третьей главе приведено развернутое описание реализации последовательного универсального алгоритма пространственной
интерполяции Кригинга на кроссплатформенном стандарте OpenCL. Представлены сведения о проведенных исследовательских экспериментах с использованием аппаратных возможностей центрального вычислительного процессора Intel Xeon Phi, графических процессорах NVIDA GeForce 1080Ti и AMD Radeon RX 580.
В ходе исследования в выпускной квалификационной работе изучена возможность увеличения эффективности и быстродействия
(производительности) систем управления запасами горнорудных предприятий при добыче и переработке путем интеграции новых технологий параллельного программирования в методы пространственной интерполяции.
В некоторых цифровых инженерных приложениях для обработки и анализа больших объемов данных требуются алгоритмы пространственной интерполяции. В этом исследовании изучено проектирование и реализация алгоритма параллельной универсальной пространственной интерполяции Кригинга с использованием модуля программирования OpenCL на гетерогенных вычислительных платформах для массивной обработки геопространственных данных. В этом исследовании основное внимание уделяется преобразованию точек в последовательных алгоритмах, т.е. универсальной функции интерполяции Кригинга, в соответствующую функцию ядра в OpenCL. Также используются методы распараллеливания и оптимизации в реализации для улучшения производительности кода. Наконец, на основе результатов экспериментов, выполненных на двух разных высокопроизводительных гетерогенных платформах, то есть с графической системой NVIDIA, AMD и системой Intel Xeon Phi, показано, что алгоритм параллельного универсального Кригинга может достичь наивысшего ускорения в 4 раза на единичных вычислительных устройствах и ускорения в 8 раз с несколькими устройствами.
Результаты данного исследования можно свести к следующим основным положениям:
1. Применение технологий параллельного программирования к существующим алгоритмам пространственной интерполяции положительно влияет на быстродействие в процессах анализа и подсчета запасов полезных ископаемых;
2. Анализируя практические результаты можно понять, что полученное ускорение вычислений получилось далеко не идеальным. Оно не сможет тотально уменьшить время построения графических моделей, однако, рассматривая процесс интерполяции отдельно, ускорение в 8 раз можно считать отличным результатом;
3. Объединение вычислительных ресурсов центрального и графического процессоров в единые гетерогенные платформы экономически выгодное решение для предприятий. Использование по максимуму имеющихся аппаратных ресурсов без состояния простоя позволяет быстрее получать обработанные итоговые данные. Такая концепция развития предприятий в целом сможет существенно уменьшить этап вычислений и анализа в планировании горно-добывательных работ;
4. Этап компьютерного моделирования, а именно графическая обработки и визуализация, не затронуты данным исследованием. Основная задача была в произведении расчетов без графической обработки, но использование гетерогенных систем для визуализации сможет также ускорить этот процесс. Обработка изображений как правило ведется только на процессорах графических карт и зачастую число кадров в секунду проседает при развертывании крупномасштабных моделей. Использование центральных процессоров также повысит плавность графики и построения большей детализации.
Данные результаты исследования позволили сделать и обосновать следующие проектно-практические рекомендации:
1. Для использования описанных в выпускной квалификационной работе технологий и практического их применения следует подробно изучить все нюансы и специфику как самих методов пространственной интерполяции, так и технологий параллельного программирования OpenCL и CUDA;
2. Специалистам, занимающихся анализом и обработкой проб месторождений полезных ископаемых, которые выполняют данные работы находясь на аутсорсинге или в целях научных исследований, чтобы достичь результатов необходимо обладать достаточно мощными аппаратными ресурсами для сложных вычислений;
3. Исследования дают возможности масштабирования и кроссплатформенной разработки при условии, что будут соблюдены особенности интеграции в системы недропользования.
Перспективы исследования данной проблемы состоят в том, что современная горнодобывающая промышленность Российской Федерации не использует все имеющиеся новейшие технологии для экономической оптимизации процесса добычи. Мощнейшие ресурсы, которыми обладают ГОКи, как показывает практика, не дают ощутимого результата при обработке и анализе проб, потому как используются обособлено. Гетерогенные системы позволят выявить экономическую выгоду и сократить простой как оборудования, так и человеческих рабочих ресурсов. Научные исследования методов интерполяции с точки зрения параллельного программирования смогут обеспечить импульс к экономическому прорыву в области недропользовании. Оптимальное освоение огромных запасов полезных ископаемых, сосредоточенных на территории государства, глобально влияет на экономику Российской Федерации, которая добывает 18% сырья во всей мировой экономике. По оценкам экспертов страна обладает неосвоенными ресурсами на 2000 трлн. рублей.
Таким образом, поставленная во введении цель исследования в выпускной квалификационной работе достигнута, а исследовательские задачи выполнены. Их выполнение в итоге подтвердило и гипотезу о решении проблемы увеличения быстродействия путем внедрения технологий параллельного программирования, которая использовала бы вычислительные ресурсы центрального процессора совместно с графическим.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
