Интеграция алгоритма параллельной сортировки Бэтчера и активной системы хранения данных
Автор: Тютляева Екатерина Олеговна
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем
Статья в выпуске: 4 (18) т.4, 2013 года.
Бесплатный доступ
В статье описан разработанный алгоритм сортировки больших объемов данных при помощи модифицированной версии алгоритма параллельной сортировки Бэтчера. Принципиальной новизной полученного решения является интеграция распространенного и доказавшего свою эффективность алгоритма параллельной сортировки Бэтчера и концепции системы активного хранения на базе библиотеки шаблонных классов TSim и кластерной файловой системы Lustre. В статье представлены результаты тестирования производительности разработанного алгоритма на реальной научной задаче обработки данных сейсмической разведки. Полученные результаты демонстрируют линейное ускорение на задаче, обрабатывающей большой (более 100 Гб) массив данных.
Активное хранилище, сортировка бэтчера, распределенная обработка данных, параллельная сортировка, обработка больших массивов данных
Короткий адрес: https://sciup.org/14335960
IDR: 14335960
Список литературы Интеграция алгоритма параллельной сортировки Бэтчера и активной системы хранения данных
- Кнут Д. Э., Козаченко Ю. В., Красиков И. В. Искусство программирования: Сортировка и поиск. Классический труд, Т. 3. М.: Вильямс, 2000. -824 c.
- Sorting Benchmarks, http://sortbenchmark.org/, Дата доступа: 12 ноября 2013.
- Тютляева Е. О., Московский А. А., Курин Е. А. Применение концепции активных хранилищ в задачах обработки данных сейсмических наблюдений//Труды Международной суперкомпьютерной конференции «Научный сервис в сети Интернет: поиск новых решений»/Новороссийск, Россия -М. -: Изд-во МГУ, 2012, c. 350-355.
- Якобовский М.В. Параллельные алгоритмы сортировки больших объемов данных//Фундаментальные физико-математические проблемы и моделирование технико-технологических систем: Сб. науч. тр.: Янус-К, 2004, c. 235249.
- O’Malley O. Terabyte Sort on Apache Hadoop/Yahoo, 2008, http://sortbenchmark.org/YahooHadoop.pdf, Дата доступа: 12 сентября 2013.
- Munavalli S. M Efficient Algorithms for Sorting on GPUs, Visveswaraiah Technological University, Belgaum, 2012. -47 p.
- 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.
- 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.
- Sohn A., Kodama Yu. Load Balanced Parallel Radix Sort//International Conference on Supercomputing, 1998, p. 305-312.
- Bilardi G., Nicolau A. Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines//SIAM J. Comput., 1989. Vol. 18, no. 2, p. 216228.
- 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.
- Московский А. А. Реализация библиотеки для параллельных вычислений на основе шаблонных классов языка С++//Труды Международной научной конференции «Параллельные вычислительные технологии (ПаВТ’2007)». -Челябинск: изд. ЮУрГУ, 2007, c. 256.
- 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.
