В статье описан разработанный алгоритм сортировки больших объемов данных при помощи модифицированной версии алгоритма параллельной сортировки Бэтчера. Принципиальной новизной полученного решения является интеграция распространенного и доказавшего свою эффективность алгоритма параллельной сортировки Бэтчера и концепции системы активного хранения на базе библиотеки шаблонных классов TSim и кластерной файловой системы Lustre. В статье представлены результаты тестирования производительности разработанного алгоритма на реальной научной задаче обработки данных сейсмической разведки. Полученные результаты демонстрируют линейное ускорение на задаче, обрабатывающей большой (более 100 Гб) массив данных.
параллельная сортировка, сортировка Бэтчера, обработка больших массивов данных, активное хранилище, распределенная обработка данных.
Работа выполнена в рамках проекта «Методы и программные средства разработки параллельных приложений и обеспечения функционирования вычислительных комплексов и сетей нового поколения».
Введение
Сортировка является одной из базовых операций при обработке данных, которая используется в самом широком спектре задач, включая обработку коммерческих, сейсмических, космических и прочих данных. Часто сортировка является просто вспомогательной операцией для упорядочивания данных, упрощения последующих алгебраических действий над данными и т.п.
В классическом учебнике [1, стр. 21] Д. Кнута упоминается что «по оценкам производителей компьютеров в 60-х годах в среднем более четверти машинного времени тратилось на сортировку. Во многих вычислительных системах на нее уходит больше половины машинного времени. Исходя из этих статистических данных, можно заключить, что либо (i) сортировка имеет много важных применений, либо (ii) ею часто пользуются без нужды, либо (iii) применяются в основном неэффективные алгоритмы сортировки». В настоящее время, в связи с экспоненциально возросшими объемами данных, вопрос эффективной сортировки данных снова стал актуальным.
Эффективная обработка больших (в несколько десятков Гб) объемов данных на распределенных вычислительных установках требует переработки старых алгоритмов для решения задач минимизации пересылок данных между узлами, эффективного распределения данных по оперативной памяти доступных узлов и эффективного использования доступных вычислительных ресурсов. Наиболее эффективными являются архитектурно-зависимые решения, которые используют преимущества конкретной архитектуры.
В настоящее время разработкой эффективных распределенных алгоритмов и реализаций сортировки занимается значительное количество коммерческих и исследовательских команд. К примеру, на сайте [2] можно найти результаты производительности алгоритмов сортировки для ряда ведущих центров данных. При этом используются различные критерии оценки эффективности, например, «количество данных, которое может быть отсортировано за минуту», «время, затрачиваемое на сортировку 1 миллиона записей» и т.п.
В данной работе был проведен обзор наиболее популярных методов и алгоритмов параллельной сортировки больших объемов данных. На основании проведенного обзора был разработан новый, эффективный алгоритм сортировки интегрированный с системой активного хранения данных, позволяющей приближать вычисления к местам хранения данных [3].
1. Кнут Д. Э., Козаченко Ю. В., Красиков И. В. Искусство программирования: Сортировка и поиск. Классический труд, Т. 3. М. : Вильямс, 2000. -- 824 c.
2. Sorting Benchmarks, http://sortbenchmark.org/, Дата доступа: 12 ноября 2013.
3. Тютляева Е. О., Московский А. А., Курин Е. А. Применение концепции активных хранилищ в задачах обработки данных сейсмических наблюдений // Труды Международной суперкомпьютерной конференции «Научный сервис в сети Интернет: поиск новых решений»/ Новороссийск, Россия -- М. : Изд-во МГУ, 2012, c. 350-355.
4. Якобовский М.В. Параллельные алгоритмы сортировки больших объемов данных // Фундаментальные физико-математические проблемы и моделирование технико-технологических систем: Сб. науч. тр. : Янус-К, 2004, c. 235-249.
5. O’Malley O. Terabyte Sort on Apache Hadoop/ Yahoo, 2008, http://sortbenchmark.org/YahooHadoop.pdf, Дата доступа: 12 сентября 2013.
6. Munavalli S. M Efficient Algorithms for Sorting on GPUs, Visveswaraiah Technological University, Belgaum, 2012. - 47 p.
7. Satish N., Kim Ch., Chhugani J., Nguyen A. D., Lee V.W., Kim D., Dubey P. Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort // Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. SIGMOD ’10 -- New York, NY, USA : ACM, 2010, p. 351-362, http: //doi.acm.org/10.1145/1807167.1807207.
8. Amato N., Iyer R., Sundaresan Sh., Wu Ya. A Comparison of Parallel Sorting Algorithms on Different Architectures/ Texas A & M University College Station. USA, 1998, Technical Report.
9. Sohn A., Kodama Yu. Load Balanced Parallel Radix Sort // International Conference on Supercomputing, 1998, p. 305-312.
10. Bilardi G., Nicolau A. Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines // SIAM J. Comput., 1989. Vol.18, no. 2, p. 216-228.
11. Frazer W. D., McKellar A.C. Samplesort: A Sampling Approach to Minimal Storage Tree Sorting // J. ACM, July 1970. Vol.17, no. 3, p. 496-507.
12. Московский А. А. Реализация библиотеки для параллельных вычислений на основе шаблонных классов языка С++ // Труды Международной научной конференции «Параллельные вычислительные технологии (ПаВТ’2007)». -- Челябинск : изд. ЮУрГУ, 2007, c. 256.
13. Cohen J. K., Stockwell J. J.W. CWP/SU: Seismic Unix Release 43R3: a free package for seismic research and processing, 2012, http://www.cwp.mines.edu/cwpcodes/, Дата доступа: 12 сентября 2013.
