В статье рассмотрен алгоритм плавающего конуса для решения задачи поиска предельных границ карьеров. Предложена схема построения параллельной версии данного алгоритма, описана программная реализация параллельного алгоритма плавающего конуса. Приведены результаты вычислительных экспериментов по проверке адекватности разработанного алгоритма и масштабирования вычислительного процесса. Ключевые слова: поиск границ карьеров, алгоритм плавающего конуса, параллельные алгоритмы, компьютерное моделирование.
Решение задачи поиска предельных границ открытых карьеров на основе параллельного алгоритма плавающего конуса* На рисунке 1 приведен пример поперечного сечения блочной модели, красной линией отмечена оптимальная форма карьера в данном сечении.
Рис. 1. Пример поперечного сечения блочной модели месторождения Желтые блоки с положительным значением веса – блоки, которые содержат полезные элементы и их выгодно добывать, серые блоки с отрицательным значением веса – пустая порода, добывая которую предприятие только тратит средства.
Задача определения границ предельного карьера (оболочки карьера на конец срока жизни горного предприятия) состоит в нахождении множества извлекаемых трехмерных блоков руды и породы с целью максимизации прибыли при наличии прецедентных ограничений, связанных с устойчивостью откосов бортов.
Геометрические ограничения на последовательность извлечения блоков (рисунок 2) гарантируют, что откосы бортов карьера будут устойчивы, а горное оборудование будет иметь доступ к рабочим зонам. Прецедентные ограничения требуют выполнения условия, что при извлечении текущего блока на него непосредственно воздействуют вышележащие блоки, которые должны быть извлечены прежде, чем рассматриваемый блок. Прецедентная связь между блоками задается явно как связь транзитивного типа, то есть, если для извлечения блока A необходимо извлечь блок B, а для извлечения блока B необходимо извлечь блок C, то для извлечения блока A также необходимо извлечь и блок C. Эта транзитивность отражается в исходных прецедентных ограничениях. Можно использовать это свойство транзитивности для описания прецедентной связи как непосредственной или прямой, если на нее не влияет какая-либо иная пара предшественников, что позволяет моделировать прецедентные ограничения путем увеличения числа прямых предшественников в моделях.
a б Рис. 2. Схемы извлечения блоков, основанные на удалении пяти блоков выше заданного 6-го блока (а) или на удалении девяти блоков выше заданного 10-го блока (б) При удалении 10 блоков угол наклона бортов для блоков лежит в пределах от 35 до 45, тогда как при удалении 6 вышележащих блоков углы крутизны склонов будут меняться в диапазоне от 45 до 55. Переходя от кубических блоков к блокам в виде параллелепипедов с различными размерами по осям X, Y и Z можно добиться изменения величин в необходимом диапазоне углов. Эти правила последовательности выемки блоков трактуются как некое приближение моделей стратегического планирования к реальным процессам добычи, рассматриваемым при планировании продукции.
Существует насколько классов задач оптимизации границ карьеров в зависимости от учета в них тех или иных факторов (время, производственные ограничения и др.). В рамках данной статьи будет рассмотрены алгоритмы, решающие задачу нахождения предельных границ карьера, (UPIT), или задача поиска замыкания с максимальным весом. Эта задача определяет наиболее прибыльную оболочку из блоков внутри рудного тела и, следовательно, в ней не учитываются факторы времени и какие-либо производственные ограничения. Набор ограничений состоит только из прецедентных отношений между блоками. По сути, используя ценность каждого блока без всяких ограничений на необходимые производственные ресурсы по выемке, решение этой задачи показывает немедленную прибыль от карьера и, соответственно, устанавливает то, какие блоки должны быть извлечены согласно прецедентным ограничениям для получения данной прибыли. 3. Алгоритм плавающего конуса
В данном алгоритме элементарная фигура формирования границ карьера — перевернутый усеченный конус, меньшее основание которого имеет размеры, соответствующие минимальной ширине дна карьера. Плоскость, образующая боковую поверхность конуса, наклонена к горизонтальной плоскости под углом, равным углу откоса конечного борта карьера. Пример положительного конуса приведен на рисунке 3.
Этот метод имеет несколько вариантов, подробно рассмотренных в работе [
Такой алгоритм для модели, приведенной на рисунке 3 находит предельную форму карьера, показанную на рисунке 4. Порядок анализа блоков приведен в таблице 2 и на рисунках 5 и 6. В таблице 2 в скобках указаны значения в случае анализа блоков справа налево.
Таблица 2. Порядок анализа модели алгоритмом плавающего конуса Шаг 4. Параллельный алгоритм плавающего конуса
Для модификации алгоритма плавающего конуса, нами разработана эффективная схема распараллеливания. Анализ модели производится по уровням, начиная с ближайшего к поверхности. На каждом уровне операция вычисления суммы значений блоков, входящих в конус не зависима для непересекающихся конусов, поэтому можно одновременно рассчитывать сумму для нескольких конусов.
Для проверки пересечения двух конусов предлагается следующие условие: для угла наклона 45 градусов достаточно, чтобы расстояние между вершинами конусов по горизонтали было больше квадрата их высоты.
На рисунке 7 приведен псевдокод последовательной версии алгоритма для модели p размером m на n блоков.
for (int i = 1; i <= n; i++) for (int j = 2; j <= m; j++) if (p[i, j] > 0)
calcConeSumm(i, j); Рис. 7. Псевдокод последовательной версии алгоритма плавающего конуса На рисунке 8 приведен псевдокод параллельной версии алгоритма плавающего конуса для вычислительных систем с общей памятью. int idThread = номер потока, начиная с 1 int countThreads = общее количество потоков for (int i = 1; i <= n; i++) { int r = i*i; for (int shift = 0; shift<r; shift++) { for (int j = idThread + shift; j <= m; j += countThreads*r) if ((i <= n) && (j <= m) && (p[i, j] > 0))
calcConeSumm(i, j); } }
Barrier(); Рис. 8. Псевдокод последовательной версии алгоритма плавающего конуса 5. Вычислительные эксперименты
Параллельный алгоритм плавающего конуса, описанный в данной статье был реализован на языке C++ для вычислительных систем с общей памятью с использованием технологии OpenMP. В качестве технической платформы для проведения вычислительных экспериментов использовался суперкомпьютер «Нежеголь» Белгородского государственного национального исследовательского университета. Эксперименты проводились на одном вычислительном узле, технические характеристики приведены в таблице 3.
Таблица 3. Технические характеристики вычислительного узла кластера
Характеристика
Процессор
Частота процессора
Количество процессоров
Количество ядер
Объем ОЗУ
Значение
Intel(R) Xeon(R) CPU E5-2665
2.4ГГц
2
16
64Гбайт
В качестве исходных данных для тестирования алгоритма использовалась модель с ярко
выраженным рудным телом созданная на основе результатов моделирования и подсчета запасов
Жайремского месторождения в Казахстане, опубликованных в работах [
На рисунке 9 показана зависимость времени обсчета модели от количества вычислительных потоков.
Рис. 9. Зависимость времени расчетов от количества вычислительных потоков По замерам времени было рассчитано ускорение для различного числа вычислительных потоков. На рисунке 10 приведена зависимость ускорения от количества вычислительных потоков. Жирной линией показан график ускорения, тонкой – линейная ассимптота.
Рис. 10. Зависимость ускорения от количества вычислительных потоков 6. Заключение
Результаты суперкомпьютерного моделирования показали перспективность предложенного метода для выполнения расчетов на регулярных блочных моделях месторождений твердых полезных ископаемых, разрабатываемых открытым способом. Основные преимущества предложенного метода заключаются в предоставлении нового принципа решения задачи оптимизации карьеров, позволяющего работать напрямую с трехмерной моделью месторождения, что значительно повышает адекватность получаемой модели. Кроме того, возможности гибкого масштабирования вычислительного процесса позволяют сокращать время обсчета модели почти линейно с увеличением количества вычислительных узлов. Литература 3. A new algorithm for optimum open pit design: Floating cone method III. Elahi zeyni E., Kakaie
R., Yousefi A. 2 , 2011, Journal of Mining & Environment, Vol. 2 , pp. 118-125. 4. Carlson, T. R.; Erickson, J. D.; O’Brain D. T . and Pana, M. T.; 1966; “Computer techniques in mine planning”, Mining Engineering, Vol. 18, No. 5, p.p. 53-56. 5. Khalokakaie, R. 2006; “Optimum open pit design with modified moving cone II methods”,
Journal of engineering in Tehran university, Vol. 4, No. 3 p.p 297-307 (in Persian). 8. Петров Д.В., Михелев В.М. «Моделирование карьеров рудных месторождений на высокопроизводительных гибридных вычислительных системах», Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2014. Т. 3. № 3. С. 124-129. Optimum open pit design with parallel moving cone method
This article describes parallel moving cone method for design optimum open pit. A scheme of the parallel version of the algorithm described the software implementation of the parallel moving cone method described. The results of computational experiments to test the adequacy of developed algorithm and scaling of computational process.
Keywords: optimum open pit design, moving cone method, parallel algorithms, computer modeling. 4. Carlson, T. R.; Erickson, J. D.; O’Brain D. T . and Pana, M. T.; 1966; “Computer techniques in mine planning”, Mining Engineering, Vol. 18, No. 5, p.p. 53-56. 5. Khalokakaie, R. 2006; “Optimum open pit design with modified moving cone II methods”,
Journal of engineering in Tehran university, Vol. 4, No. 3 p.p 297-307 (in Persian). 6. Vasil'ev P.V. Uskorenie modelirovaniya i optimizatsii izvlecheniya zapasov rudnykh me-storozhdeniy na osnove parallel'nykh vychisleniy [Accelerate modeling and optimization of extraction reserves of ore deposits based on parallel computing] Gornyy informatsionno-analiticheskiy byulleten' [Mining informational and analytical bulletin] M.: MGGU, 2012, №3, P. 205-211.