Оглавление
Введение.Постановка задачи.
Параллельные алгоритмы.
Message Passing Interface.
Реализация параллельного алгоритма.
Заключение.
Список использованной литературы.
Введение
Современные спутники дистанционного зондирования земли (ДЗЗ) производят ежедневный мониторинг нашей планеты. Среди круга задач, возникающих в ходе таких исследований, стоит проблема обработки и распознавания многочисленного фактического материала, полученного со спутников. Должным образом обработанные данные позволят получать информацию о составе леса, рельефе местности, расположении месторождения полезных ископаемых и многом другом.
Развитие компьютерной архитектуры идет по пути увеличения количества вычислительных узлов и увеличения количества ядер в узле. Вычислительные кластеры позволяют уменьшить время расчетов по сравнению с одиночным компьютером, разбивая задание на параллельно выполняющиеся ветки, которые обмениваются данными по связывающей сети. В силу этого актуальны алгоритмы, пригодные для параллельной реализации. Наиболее популярными языками написания таких алгоритмов являются Си и Фортран.
Постановка задачи
В ходе выполнения задачи мы будем считывать наше изображение в условно трехмерный массив(пятимерный), где первые две размерности соответственно координаты x и y, а третья описывает цвет изображения. Третья размерность нашего массива состоит из трех элементов цветовой модели (R, G, B), значение которых для каждого полезного ископаемого свое. Следовательно, наша задача сводится к тому, чтобы как можно быстрее пробежать по этому массиву, профильтровать пиксель на предмет наличия полезного ископаемого( R, G, B элементы там будут значительно темнее), выделить его соответствующим цветом (пример: железо - желтый, уголь - черный, известняк - белый и тд.) и подсчет соответствующих пикселей с выведением статистики.
При работе с изображением, во время выполнения программы мы не видим само изображение. Области с полезными ископаемыми, на фотографии получаются значительно темнее, чем области без них. Цвета областей с полезными ископаемыми, их форма могут колебаться. Нам пришлось прибегнуть к параллельному программированию, так как если обрабатывать одним устройством наш массив, то перебрать и выдать результат потребует много времени, а также потому что размер изображения может быть очень большим.
Таким образом, целью данной работы является разработка и параллельная реализация вычислительного алгоритма обработки данных дистанционного зондирования для поиска месторождений полезных ископаемых.
Параллельные алгоритмы
В информатике параллельный алгоритм, противопоставляемый традиционным последовательным алгоритмам, — алгоритм, который может быть реализован по частям на множестве различных вычислительных устройств с последующим объединением полученных результатов и получением корректного результата.
Параллельные алгоритмы весьма важны ввиду постоянного совершенствования многопроцессорных систем и увеличения числа ядер в современных процессорах. Обычно проще сконструировать компьютер с одним быстрым процессором, чем с множеством медленных процессоров (при условии достижения одинаковой производительности). Однако производительность процессоров увеличивается главным образом за счет совершенствования техпроцесса (уменьшения норм производства), чему мешают физические ограничения на размер элементов микросхем и тепловыделение. Указанные ограничения могут быть преодолены путем перехода к многопроцессорной обработке, что оказывается эффективным даже для малых вычислительных систем.
Сложность последовательных алгоритмов выражается в объеме используемой памяти и времени (числе тактов процессора), необходимых для выполнения алгоритма. Параллельные алгоритмы требуют учета использования еще одного ресурса: подсистемы связей между различными процессорами. Существует два способа обмена между процессорами: использование общей памяти и системы передачи сообщений.
Системы с общей памятью требуют введения дополнительных блокировок для обрабатываемых данных, налагая определенные ограничения при использовании дополнительных процессоров.
Но «распараллеливание» алгоритма не всегда дает положительный результат, а иногда оно опросту невозможно. Некоторые задачи являются сугубо последовательными. Конкретно наша работа поддается распараллеливанию относительно легко, так как разбить все изображение на сектора и разослать на отдельные устройства не представляет особого труда. Следовательно, использование параллельного метода для нахождения полезных ископаемых по фотографии со спутника обосновано, и такая программа будет работать быстрее, нежели последовательная.
Message Passing Interface
Под средствами реализации параллельности понимаются языки программирования или библиотеки, обеспечивающие инфраструктуру параллельных программ. Таких систем достаточно много, в нашей же работе мы использовали библиотеку MPI.
MPI является сейчас самой развитой системой параллельного программирования с передачей сообщений. Наиболее важным свойством MPI является то, что он позволяет создавать переносимые параллельные программы, достаточно эффективные и надежные.
- MPI используется при разработке программ для кластеров и суперкомпьютеров. Основным средством коммуникации между процессами в MPI является передача сообщений друг другу. Стандартизацией MPI занимается MPI Forum. В стандарте MPI описан интерфейс передачи сообщений, который должен поддерживаться как на платформе, так и в приложениях пользователя. В настоящее время существует большое количество бесплатных и коммерческих реализаций MPI. Существуют реализации для языков Фортран 77/90, Си и Си++.
- В первую очередь MPI ориентирован на системы с распределенной памятью, то есть когда затраты на передачу данных велики, в то время как OpenMP ориентирован на системы с общей памятью (многоядерные с общим кэшем). Обе технологии могут использоваться совместно, дабы оптимально использовать в кластере многоядерные системы.
Переносимость информации обеспечивается:
• такими механизмами, как: определение виртуального компьютера (программно реализуемого) и возможностью задания произвольного количества таких виртуальных компьютеров в системе независимо от количества физических компьютеров.
•заданием виртуальных топологий (программно реализуемых). Отображение виртуальных коммуникационных топологий на физическую осуществляется системой MPI. Виртуальные топологии обеспечивают оптимальное приближение архитектуры системы к структурам задач при хорошей переносимости задач.
• тем, что тот же самый исходный текст параллельной программы на MPI может быть выполнен на ряде машин (некоторая настройка необходима, чтобы взять преимущество из элементов каждой системы). Программный код может одинаково эффективно выполняться, как на параллельных компьютерах с распределенной памятью, так и на параллельных компьютерах с общей памятью. Он может выполняться на сети рабочих станций, или на наборе процессоров на отдельной рабочей станции.
• способностью параллельных программ выполняться на гетерогенных системах, то есть на системах, состоящих из процессоров с различной архитектурой. MPI обеспечивает вычислительную модель, которая скрывает много архитектурных различий в работе процессоров. MPI автоматически делает любое необходимое преобразование данных и использует правильный протокол связи, посылается ли код сообщения между одинаковыми процессорами или между процессорами с различной архитектурой. MPI может настраиваться как на работу на однородной, так и на работу на гетерогенной системах.
• компиляторами для Fortran(a) и C.
Эффективность и надежность обеспечиваются:
• определением MPI операций не процедурно, а логически, т. е. внутренние механизмы выполнения операций скрыты от пользователя;
• использованием непрозрачных объектов в MPI (группы, коммуникаторы, типы и т. д.);
• хорошей реализацией функций передачи данных, адаптирующихся к структуре физической системы.
Реализация параллельного алгоритма
Вот как должна происходить реализация нашего параллельного алгоритма:
- Сначала программа считывает данные из файла изображения; Затем определяет способ самого оптимального распределения данных по вычислительным узлам; Далее она рассылает данные по вычислительным узлам. Тут и происходит распараллеливание программы; Каждый из вычислительных узлов принимает присланные данные, после этого каждый обрабатывает свою часть данных. В итоге каждый узел отправляет нам свой результат; Потом программа принимает все присланные результаты и обрабатывает их; На последнем этапе происходит сохранение всех результатов в файл.
Фотографии местности мы получали от радиометра RASTER.
Архив данных ASTER формируется в рамках совместного проекта Международного социально-экологического союза, Центра охраны дикой природы и ИТЦ СканЭкс при поддержке Института мировых ресурсов и участии ряда российских природоохранных организаций.
Радиометр ASTER (Advanced Spaceborne Thermal Emission and Reflection Radiometer) установлен на борту Terra, первого спутника серии EOS.
Прибор позволяет проводить съемку земной поверхности в 14 спектральных диапазонах от видимого до дальнего инфракрасного с пространственным разрешением от 15 до 90 м.
Одной из уникальных особенностей радиометра является возможность стереосъемки в ближнем инфракрасном (ИК) диапазоне, что обеспечивает получение стереоснимков высокого разрешения и позволяет создавать на их основе детальные цифровые модели местности.
Пример работы программы:
На данной фотографии изображена пирамида Хеопса. Допустим, нам надо найти самую темную её грань. Эта задача максимально приближена к нашей, так как на нашей фотографии месторождения полезных ископаемых тоже темнее, чем вся фотография.
Теперь посмотрим на увеличенный угол этой грани. Наша программа работает по такому принципу: если пиксель нам подходит (то есть RGB показатели меньше чем в фильтре), то мы этот пиксель выделяем красным цветом, а если не подходит( то есть RGB показатели выше чем в фильтре), то закрашиваем черным, или просто оставляем.
Таким образом, должно получиться что-то вроде этого: 
Заключение
Целью данной работы была разработка и параллельная реализация вычислительного алгоритма обработки данных дистанционного зондирования для поиска месторождений полезных ископаемых.
В результате проделанной работы были изучены различные материалы, поступающие от спутников дистанционного зондирования, выделены признаки присутствия на изображении полезных ископаемых по их цветовым характеристикам. Также был разработан алгоритм поиска месторождений на снимках со спутников и создана его параллельная реализация на основе технологии MPI.
Таким образом, в распоряжении коллектива исследователей появился алгоритм параллельной обработки данных дистанционного зондирования видимого диапазона спектра. Разработанную программу можно будет использовать для поиска месторождений полезных ископаемых или для мониторинга состава леса.
Список использованной литературы
, , . Программирование
многопроцессорных вычислительных систем. Ростов-на-Дону. Издательство
, 2003, 208 с., ISBN 5-94153-062-5
ифровая обработка изображений.
Издательство:Техносфера, 2006 г. Твердый переплет, 1072 стр. ISBN
5-94836-028-8
