Разработка вычислительных алгоритмов для решения задач геоинформатики

Выходные данные Reducer-а считываются Mapper-ом, соединяются со статическими данными, хранящимися в локальной файловой системе, затем выполняется тело функции Map.

Рисунок 5. Поток данных для итерационного алгоритма кластеризации

 

Реализация алгоритма кластеризации и анализ результатов. Для тестирования разработанного приложения была настроена инфраструктура, которая включала в себя 6 компьютеров Core i-5 с объемом оперативной памяти 8Gb RAM, 2 сервера HP Blade с 4 Core Intel Xeon процессорами, коммутатор с подключением к гигабитной сети.

На всех компьютерах была установлена 64-битная операционная система Ubuntu 12.10 и платформа Hadoop 2.0. Тестирование проводилось на различных объемах входных данных: рассматривались объемы изображений в 100´100, 200´200, 300´300, 400´400, 500´500 пикселей. Для сравнения результатов проводилось тестирование без использования комбинатора и с использованием комбинатора.

Результаты выполнения кластеризации на платформе Hadoop показаны на рис. 6-10.

 

Рисунок 6. Время выполнения кластеризации с MapReduce без комбинатора

 

Рисунок 7. Время выполнения кластеризации с MapReduce с комбинатором

Рисунок 8. Сравнение времени выполнения кластеризации с MapReduce без комбинатора и MapReduce с комбинатором

 

Как видно на рис. 8, включение функции комбинатора улучшает время выполнения алгоритма. Причем с увеличением объема обрабатываемой информации заметнее выражается выигрыш во времени.

Для сравнительного анализа эффективности применения технологии MapReduce для задач кластеризации были проведены тесты с применением технологии MPI на тех же объемах данных (рис. 9). На рис. 10 представлены результаты времени выполнения алгоритмов кластеризации MapReduce без комбинатора, MapReduce с комбинатором, а также с применением MPI.

Рисунок 9. Время выполнения кластеризации c применением технологии MPI

Рисунок 10. Сравнение времени выполнения кластеризации с MapReduce без комбинатора, MapReduce с комбинатором, MPI

 

Экспериментальные результаты показывают (рис. 10), что алгоритмы кластеризации с применением технологии MapReduce могут эффективно обрабатывать большие объемы данных.  

Для визуализации результатов был разработан графический интерфейс в среде Eclipse (рис. 11). На рис. 12 показано изображение до кластеризации, а на рис. 13 – изображение после кластеризации. Выполнение задачи кластеризации было распределено на 6 вычислительных узлов.

Рисунок 11. Графический интерфейс для задач кластеризации

 

Рисунок 12. Изображение до кластеризации	Рисунок 13. Изображение после кластеризации

 

Заключение. В работе предложен параллельный итерационный алгоритм кластеризации с использованием комбинаторов, реализованный на платформе MapReduce Hadoop. Повышение производительности достигается за счет управления процессом обработки данных. Особенностью данной работы является то, что а) обрабатываемые данные делятся на два вида: статические, которые хранятся в локальной файловой системе, и данные состояния, которые участвуют в обмене между функциями Mapи Reduce; б) итерационный алгоритм использует комбинаторы, которые позволяют уменьшить объем данных, участвующих в обмене MapReduce процессов.

Представленные в данной работе результаты доказывают эффективность применения технологии MapReduce для обработки данных ДДЗ. Парадигма MapReduce может быть применена для других алгоритмов обработки данных ДЗЗ, при этом ожидается получение значительного выигрыша в производительности.

Данная работа выполнялась в рамках научно-технического проекта по грантовому финансированию «Разработка моделей и приложений высокопроизводительной  распределенной обработки данных на основе технологии MapReduce – Hadoop для задач нефтедобычи».

Список использованной литературы

1. Шовенгердт Р.А. Дистанционное зондирование. Модели и методы обработки изображений. – М.: Теносфера, 2010. – 560 с.
2. Antonio J. Plaza and Chein-I Chang High Performance Computing in Remote Sensing. – Chapman and Hall/CRC, 2007. – 496 p.
3. J. Dean, S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. Communications of The ACM, 2008. – 51(1). – p. 107-113.
4. Дж. Ту, Р. Гонсалес. Принципы распознавания образов. М.: «Мир», 1978 г., 411 с.
5. C. Pughineanu, I. Balan Parallel Algorithm Evaluation in the Image and Clustering Processing // Electronics and electrical engineering. system engineering, computer technology T 120 No. 4(110). 2011. P. 89-92.
6. A. Plaza, Chein-I Chang, Javier Plaza, David Valencia. Commodity cluster and hardware-based massively parallel implementations of hyperspectral imaging algorithms // Algorithms and Technologies for Multispectral, Hyperspectral, and Ultraspectral Imagery XII. Proc. of SPIE Vol. 6233, 623316. 2006.
7. Ping ZHOU, Jingsheng LEI, Wenjun YE. Large-Scale Data Sets Clustering Based on MapReduce and Hadoop // Journal of Computational Information Systems 7: 16 (2011) 5956-5963.
8. Bo Li, Hui Zhao, ZhenHua LV. Parallel ISODATA Clustering of Remote Sensing Images Based on MapReduce // Proceedings of the International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, 2010. pp. 380-383.
9. Mohamed H. Almeer. Cloud Hadoop Map Reduce For Remote Sensing Image Analysis // Journal of Emerging Trends in Computing and Information Sciences. VOL. 3, NO. 4, April 2012. P. 637-644.
10. Z. Lv, Y. Hu, H. Zhong, J. Wu, B. Li, and H. Zhao, 2010. “Parallel K-means clustering of remote sensing images based on MapReduce,” in Proc. 2010 Int. Conf. Web Information Systems and Mining (WISM ’10), pp. 162-170.
11. Satish Narayana Srirama, Pelle Jakovits, Eero Vainikko Adapting scientific computing problems to clouds using MapReduce // Future Generation Computer Systems 28 (2012) 184–192.
12. Чак Лэм. Hadoop в действии. М.: ДМК Пресс, 2012. – 424 с.
13. White T. Hadoop: The Definitive Guide. Stamford: O'Reilly Media, Inc. 2012. 625 p.
14. Мансурова М.Е., Шоманов А., Тулепбергенов Б. Параллельный алгоритм кластеризации для обработки гиперспектральных изображений на основе MapReduce Hadoop // Международная конференция "ИКТ: образование, наука, инновации", Алматы, 20-21 мая 2013 г. – с. 56-61.
15. Мансурова М.Е., Ахмед-Заки Д.Ж., Шоманов А.С., Ихсанов С.С. Параллельная обработка гиперспектральных изображений на основе технологии MapReduce Hadoop // Тезисы Всероссийской конференции «Обработка пространственных данных и дистанционный мониторинг природной среды и масштабных антропогенных процессов». г. Барнаул, 2013 г., стр. 43.
16. Yanfeng Zhang, Qinxin Gao, LixinGao, and Cuirong Wang. imapreduce: A distributed computing frameworkfor iterative computation. J. Grid Comput,10(1): 47-68, 2012.