ВВЕДЕНИЕ 3
1. ОБЗОР И АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 6
1.1. Задача поиска предельных границ открытых месторождений полезных
ископаемых 6
1.2. Обзор существующих методов 11
1.3. Постановка задачи 19
2. ОПТИМИЗАЦИЯ АЛГОРИТМА ЛЕРЧА-ГРОССМАНА ДЛЯ РАБОТЫ НА
ГРАФИЧЕСКИХ ПРОЦЕССОРАХ 21
2.1. Подходы в реализации параллельных программ 21
2.2. Математическая постановка задачи 29
2.3. Математическое представление алгоритма Лерча-Гроссмана 31
2.4. Разработка интерфейса ввода-вывода данных 40
2.5. Разработка алгоритма Лерча-Гроссмана для GPU 43
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ЛЕРЧА-ГРОССМАНА ДЛЯ
GPU И ТЕСТИРОВАНИЕ 47
3.1. Выбор среды разработки программного обеспечения 47
3.2. Реализация параллельной версии алгоритма Лерча-Гроссмана 48
3.3. Тестирование работы алгоритма 52
ЗАКЛЮЧЕНИЕ 54
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 56
ПРИЛОЖЕНИЯ
На данный момент компьютерные системы предоставляют большие вычислительные мощности. Для этих систем не составляет труда за короткий срок выполнить такой объём вычислений, который был бы не под силу одному человеку. В то время как возрастают вычислительные мощности, растут и сложности задач, которые необходимо решать. К одной из таких задач можно отнести нахождение предельных границ открытых карьеров по добыче полезных ископаемых.
Задача поиска предельных границ открытых карьеров по добыче полезных ископаемых представляет собой важный этап в процессе разработки открытых месторождений полезных ископаемых. С её помощью появляется возможность оценить такие важные вопросы, как экономический потенциал, процесс поиска оптимальной сети транспортных путей, а также расположение отвалов и фабрик по переработке сырья.
Благодаря вычислительным системам, способным обрабатывать большие объёмы информации за короткий промежуток времени, предоставляется возможность ускорить процесс горно-геометрических расчётов. Для достижения данной цели необходимо грамотно подойти к использованию вычислительных возможностей систем, предоставляющих возможность параллельного выполнения задачи. Так как системы, используемые для вычислений, могут отличаться не только мощностями, но и комплектующими, усложняется процесс реализации программы, которая будет работать эффективно для всех систем.
Для правильной организации параллельных вычислений необходима реструктуризация привычного последовательного кода в код с областями, содержащими инструкции для их распараллеливания. То есть, параллельные вычисления проектируются, как системы параллельных взаимодействующих между собой процессов. Стандарты, применяемые для параллельных вычислений, а также системное обеспечение должны предоставлять возможность:
- создавать параллельные программы;
- обеспечивать синхронизацию между выполняемыми процессами;
- исключать асинхронные вычисления;
- подстраивать вычислительные процессы под различные вычислительные системы.
Таким образом, объектом исследования является процесс оптимизации границ открытой разработки запасов в системе недропользования.
В качестве предмета исследования выступают геоинформационные модели объектов, разрабатываемых с применением метода открытого карьера и алгоритмы, используемые для осуществления горно-геометрических расчётов, с целью оптимизации границ карьеров по добыче полезных ископаемых в системе недропользования.
Цель работы - реализация программы оптимизации границ открытой разработки запасов в системе недропользования на основе теории графов с применением технологий параллельного вычисления. Исходя из цели, можно выделить задачи, которые необходимо решить:
- исследовать применение теории графов при оптимизации границ открытой разработки запасов в системе недропользования;
- рассмотреть алгоритмы, использующие теорию графов для оптимизации открытой разработки запасов в системе недропользования;
- рассмотреть методы реализации программ, использующих
параллельные вычисления.
В первой главе «Обзор и анализ предметной области» рассматривается задача поиска предельных границ карьера открытых месторождений полезных ископаемых, приводится обзор задач и проблем, связанных с добычей рудных тел, а также рассматриваются методы решения поставленной задачи.
Во второй главе «Оптимизация алгоритма Лерча-Гроссмана для работы на графических процессорах» описываются подходы для разработки параллельных программ, математическая постановка задачи, математическое представление алгоритма; рассматриваются теоретические особенности и программная реализации алгоритма Лерча-Гроссмана на графическом ускорителе с применением технологии параллельного программирования CUDA.
В третьей главе «Программная реализация алгоритма Лерча-Гроссмана для gpu и тестирование» освещаются основные этапы программной реализации рассматриваемого алгоритма, в том числе и параллельные части программы. Также рассматриваются и анализируются результаты тестирования и эффективность реализованного алгоритма на графическом ускорителе.
Данная магистерская диссертация выполнена на 74 страницах, содержит 28 рисунков, 1 приложение, 1 таблицу, 4 листинга, выполнена с использованием 40 источников литературы.
По результатам выполненной магистерской диссертации были решены следующие задачи.
Исследовано применение теории графов при оптимизации границ открытой разработки запасов в системе недропользования. Наиболее трудоёмким процессом является процесс горно-геометрических расчётов, по результатам вычисления которых строится план максимального контура карьера, прокладываются пути грузовых автомобилей и раковины под пустую породу. Весь карьер в памяти ЭВМ представляется как дерево графов со связанными вершинами. За счёт такого представления возможно осуществить поиск связных вершин, которые должны быть добыты одна за другой. В результате вычислений происходит отсев ненужных вершин, и получается конечный контур карьера.
Рассмотрены алгоритмы, использующие теорию графов для оптимизации открытой разработки запасов в системе недропользования. Были рассмотрены алгоритмы движущегося конуса, максимального сетевого потока, Лерча- Гроссмана. Все алгоритмы построены на теории графов и работают с блочными моделями карьеров. Большая часть алгоритмов является усовершенствованными версиями более ранних алгоритмов. От того, какая задача стоит перед добывающей компанией, зависит и выбор алгоритма.
Рассмотрены методы реализации программ, использующих параллельные вычисления. Существует несколько стандартов для реализации параллельных вычислений на ЭВМ: MPI (Message Passing Interface), OpenMP (Open Multi-Processing), Cuda и PPL. Каждый из них предоставляет свой уникальных подход для реализации параллельных программ. Каждый из методов актуален для определённых вычислительных систем, так как требования к системам у стандартов отличаются.
Реализован алгоритм Лерча-Гроссмана для видеоускорителей поддерживающих технологию Nvidia CUDA. Алгоритм работает с готовыми моделями открытых месторождений по добыче полезных ископаемых.
Были проведены вычислительные эксперименты, которые показали, что результат работы программы на центральном процессоре и видеоускорителе совпадает, что говорит о том, что параллельная реализация алгоритма на видеоускорителе имеет такую же эффективность работы, что и на центральном процессоре, однако алгоритм, выполняемый на видеоускрителе, имеет преимущества по скорости.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
