Работа выполнена в рамках проекта «Методы и программные средства разработки параллельных приложений и обеспечения функционирования вычислительных комплексов и сетей нового поколения».
Введение
Сортировка является одной из базовых операций при обработке данных, которая используется в самом широком спектре задач, включая обработку коммерческих, сейсмических, космических и прочих данных. Часто сортировка является просто вспомогательной операцией для упорядочивания данных, упрощения последующих алгебраических действий над данными и т.п.
В классическом учебнике [1, стр. 21] Д. Кнута упоминается что «по оценкам производителей компьютеров в 60-х годах в среднем более четверти машинного времени тратилось на сортировку. Во многих вычислительных системах на нее уходит больше половины машинного времени. Исходя из этих статистических данных, можно заключить, что либо (i) сортировка имеет много важных применений, либо (ii) ею часто пользуются без нужды, либо (iii) применяются в основном неэффективные алгоритмы сортировки». В настоящее время, в связи с экспоненциально возросшими объемами данных, вопрос эффективной сортировки данных снова стал актуальным.
Эффективная обработка больших (в несколько десятков Гб) объемов данных на распределенных вычислительных установках требует переработки старых алгоритмов для решения задач минимизации пересылок данных между узлами, эффективного распределения данных по оперативной памяти доступных узлов и эффективного использования доступных вычислительных ресурсов. Наиболее эффективными являются архитектурно-зависимые решения, которые используют преимущества конкретной архитектуры.
В настоящее время разработкой эффективных распределенных алгоритмов и реализаций сортировки занимается значительное количество коммерческих и исследовательских команд. К примеру, на сайте [2] можно найти результаты производительности алгоритмов сортировки для ряда ведущих центров данных. При этом используются различные критерии оценки эффективности, например, «количество данных, которое может быть отсортировано за минуту», «время, затрачиваемое на сортировку 1 миллиона записей» и т.п.
В данной работе был проведен обзор наиболее популярных методов и алгоритмов параллельной сортировки больших объемов данных. На основании проведенного обзора был разработан новый, эффективный алгоритм сортировки интегрированный с системой активного хранения данных, позволяющей приближать вычисления к местам хранения данных [3].
