Параллельная сортировка

Стратегии параллельной сортировки с менее чем линейной вычислительной сложностью

Существует несколько десятков алгоритмов сортировки. Их можно классифицировать по таким критериям, как: назначение (внутренняя и внешняя сортировки), вычислительная сложность (алгоритмы с вычислительными сложностями O(n²), O(n*log(n)), O(n), O(n/log(n))), емкостная сложность (алгоритмы, требующие и не требующие дополнительного массива), возможность распараллеливания (не распараллеливаемые, ограниченно распараллеливаемые, полностью распараллеливаемые), принцип определения порядка (алгоритмы, использующие парные сравнения и не использующие парные сравнения. Среди известных алгоритмов не выделено однозначного лидера, выполняющего сортировку чисел любой разрядности за минимальное время с минимальной емкостной сложностью. Считается, что хорошие результаты обеспечивает алгоритм внутренней сортировки QuickSort, имеющий вычислительную сложность в среднем O(n*log(n)) и O(n²) в худшем. Теоретически доказано, что алгоритмы, использующие парные сравнения не могут иметь вычислительную сложность меньшую, чем O(n*lon(n)).

Особый интерес представляют алгоритмы внутренней сортировки, не использующие парные сравнения: Counting Sort, Radix Sort и другие. В работе [1] предложен алгоритм, являющийся сочетанием алгоритмов Counting Sort (сортировка подсчетом) и Radix Sort (поразрядная сортировка), лишенный некоторых присущих им недостатков. В [1,2] получены оценки вычислительной сложности такого алгоритма (O(n/log(n))), то есть она менее чем линейна. Однако, вычислительная сложность алгоритма существенно зависит от его настройки на определенную разрядность чисел и размерность массивов. Кроме этого, для выполнения сортировки на многопроцессорных ЭВМ требуется использовать стратегию сортировки, учитывающую количество процессоров.

В связи с этим в данной работе предпринята попытка разработки таких стратегий параллельной сортировки с помощью алгоритмов с менее чем линейной вычислительной сложностью, которые позволили бы для конкретной вычислительной системы сортировать массивы чисел за минимальное время.

Алгоритм, предложенный в [1], основан на алгоритме поразрядной сортировки. Сортировка же по конкретному разряду выполняется с помощью алгоритма сортировки подсчетом. Код программы на языке Pascal представлен ниже. Исходный массив A состоит из 64-разрядных чисел и для удобства поразрядной сортировки представлен в программе двумерным массивом. Для хранения промежуточных результатов необходим дополнительные массивы B и C. Размерность всех разрядов выбрана одинаковой (8 бит).

     W:=@A;     {W – указатель на исходным массив}
     T:=@B;      {T – указатель на временный массив}
 
     for i:=7 downto 0 do {i – номер разряда в числе, j- номер числа}
     begin
          for j:=0 to 255 do C[j]:=0;        {заполнить массив с нулями}
          for j:=0 to n-1 do C[W^[j,i]] := C[W^[j,i]]+1; {накопить в массиве C количества повторений разрядов}
          for j:=1 to 255 do C[j] := C[j] + C[j-1]; {сохранить в массиве C количество чисел, меньших данного}
          for j:=n-1 downto 0 do
          begin
               C[W^[j,i]] := C[W^[j,i]]-1;   {Модифицировать массив C для данного значения разряда}
               T^[C[W^[j,i]]] := W^[j];                   {Записать число из исходного массива во временный массив}
 
          end;
          TMP:=W;          {Подготовиться к сортировке по следующему разряду}
          W:=T;
          T:=TMP;
     end;

Помимо этого следует заметить, что в современных ЭВМ чтение оперативной памяти производится в пакетном режиме, при котором процессор, даже при указании в команде однобайтового операнда, получает целый блок расположенных по последовательным адресам данных. Для процессоров Pentium III такой блок составляет 32 байта, а для Pentium IV — 128 байт. Таким образом, без учета пакетной передачи в алгоритме сортировки массивов большой размерности неизбежно будет происходить несвоевременная передача данных из ОЗУ в процессор, что существенно влияет на время сортировки. Также важно, что представленный «классический» вариант реализации алгоритма не приспособлен для выполнения на нескольких процессорах.

Первая стратегия сортировки призвана разделить выполнение программы на отдельные не зависимые друг от друга процессы, а также ускорить доступ к элементам массива. Исходный массив можно представить в виде двумерной матрицы чисел, каждое из которых является одним разрядом числа и строки которой располагаются в памяти последовательно.

Как видно из текста программы основой работы данной сортировки является последовательное составление вспомогательных массивов С для каждого разряда чисел, что производится за счет чтения столбца из «матрицы разрядов». Значит, с точки зрения чтения данных из памяти, удобнее помещать в память не числа массива подряд а матрицу которая является результатом транспонирования вышеприведенной. В случае если имеется достаточно много памяти, то можно использовать другой вариант оптимизации, не требующий преобразований массива. Этот способ предусматривает хранить в памяти единовременно вспомогательный массив не для одного, а для всех разрядов, что позволяет произвольное число потоков, считывающих по одной или несколько строк из матрицы и заполняющих массив С.

Вторая стратегия является очевидной реализацией разбиения циклов на потоки. Она предполагает разделить на потоки операции которые выполняются с данным конкретным массивом Сі, такие как начальное обнуление массива и последовательное суммирование его элементов. Эту стратегию удобно использовать в случае применения 2 варианта первой стратегии оптимизации, так как в этом случае все вспомогательные массивы уже находятся в памяти, тогда как при 1 варианте считается что памяти не достаточно для всех С.

Третья стратегия заключается в том, чтобы не выполнять перестановку элементов после получения для него С. Вместо массива такой же размеренности как и А предлагается использовать массив перестановок, i-тому элементу которого будет соответствовать номер позиции i-того элемента массива А в отсортированном.

Четвертая стратегия оптимизации. Идеей оптимизации служит отказ от принципа Radix Sort о том, что сортировка производится от младшего к старшему разрядам. Предлагается производить сортировку от старшего к младшим разрядам, таким образом: оценивая массив С который должен получиться после сортировки А по данному разряду, выявляются числа с одинаковым данным разрядом и для них создается отдельный поток сортировки по следующему разряду. Таким образом каждый поток изменяет лишь заданную часть массива. Данная стратегия поднимает требования к количеству памяти на ЭВМ для вспомогательных массивов, но обладает значительным превосходством над оригинальным алгоритмом сортировки, так как последовательно происходит уменьшение числа сортируемых элементов, а также она не требует одновременного выделения в памяти под все вспомогательные массивы, они создаются динамически.