This paper describes a modified parallel Batcher sort algorithm for big data processing. The main novelty of implemented sort algorithm is to integrate effective parallel batcher sort and Active Storage concept. We use Active Storage based on Lustre File System and TSim C++ template library for parallelization. This paper presents experimental testing results for scientific processing real seismic data. Presented results indicate that described algorithm can reach linear acceleration on sorting big data sets (More then 100 Gb).
parallel sort, Batcher sort, Big data processing, Active Storage, Distributed data processing.
Работа выполнена в рамках проекта «Методы и программные средства разработки параллельных приложений и обеспечения функционирования вычислительных комплексов и сетей нового поколения».
Введение
Сортировка является одной из базовых операций при обработке данных, которая используется в самом широком спектре задач, включая обработку коммерческих, сейсмических, космических и прочих данных. Часто сортировка является просто вспомогательной операцией для упорядочивания данных, упрощения последующих алгебраических действий над данными и т.п.
В классическом учебнике [1, стр. 21] Д. Кнута упоминается что «по оценкам производителей компьютеров в 60-х годах в среднем более четверти машинного времени тратилось на сортировку. Во многих вычислительных системах на нее уходит больше половины машинного времени. Исходя из этих статистических данных, можно заключить, что либо (i) сортировка имеет много важных применений, либо (ii) ею часто пользуются без нужды, либо (iii) применяются в основном неэффективные алгоритмы сортировки». В настоящее время, в связи с экспоненциально возросшими объемами данных, вопрос эффективной сортировки данных снова стал актуальным.
Эффективная обработка больших (в несколько десятков Гб) объемов данных на распределенных вычислительных установках требует переработки старых алгоритмов для решения задач минимизации пересылок данных между узлами, эффективного распределения данных по оперативной памяти доступных узлов и эффективного использования доступных вычислительных ресурсов. Наиболее эффективными являются архитектурно-зависимые решения, которые используют преимущества конкретной архитектуры.
В настоящее время разработкой эффективных распределенных алгоритмов и реализаций сортировки занимается значительное количество коммерческих и исследовательских команд. К примеру, на сайте [2] можно найти результаты производительности алгоритмов сортировки для ряда ведущих центров данных. При этом используются различные критерии оценки эффективности, например, «количество данных, которое может быть отсортировано за минуту», «время, затрачиваемое на сортировку 1 миллиона записей» и т.п.
В данной работе был проведен обзор наиболее популярных методов и алгоритмов параллельной сортировки больших объемов данных. На основании проведенного обзора был разработан новый, эффективный алгоритм сортировки интегрированный с системой активного хранения данных, позволяющей приближать вычисления к местам хранения данных [3].
1. Knut D. E., Kozachenko Yu. V., Krasikov I. V. Iskusstvo programmirovaniya: Sortirovka i poisk. Klassicheskiy trud, T. 3. M. : Vil´yams, 2000. -- 824 c.
2. Sorting Benchmarks, http://sortbenchmark.org/, Data dostupa: 12 noyabrya 2013.
3. Tyutlyaeva E. O., Moskovskiy A. A., Kurin E. A. Primenenie kontseptsii aktivnykh khranilishch v zadachakh obrabotki dannykh seysmicheskikh nablyudeniy. Trudy Mezhdunarodnoy superkomp´yuternoy konferentsii «Nauchnyy servis v seti Internet: poisk novykh resheniy»/ Novorossiysk, Rossiya -- M. : Izd-vo MGU, 2012, c. 350-355.
4. Yakobovskiy M.V. Parallel´nye algoritmy sortirovki bol´shikh ob´´emov dannykh. Fundamental´nye fiziko-matematicheskie problemy i modelirovanie tekhniko-tekhnologicheskikh sistem: Sb. nauch. tr. : Yanus-K, 2004, c. 235-249.
5. O’Malley O. Terabyte Sort on Apache Hadoop/ Yahoo, 2008, http://sortbenchmark.org/YahooHadoop.pdf, Data dostupa: 12 sentyabrya 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. Moskovskiy A. A. Realizatsiya biblioteki dlya parallel´nykh vychisleniy na osnove shablonnykh klassov yazyka S++. Trudy Mezhdunarodnoy nauchnoy konferentsii «Parallel´nye vychislitel´nye tekhnologii (PaVT’2007)». -- Chelyabinsk : izd. YuUrGU, 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/, Data dostupa: 12 sentyabrya 2013.
