ParallelSort: Tier-1b Bucket

Общий принцип блочной сортировки можно описать двумя словами «scatter-gather». В нашем случае сортировки чисел производятся следующие операции.

  1. Найти min и max сортируемой последовательности N чисел, размах r = max — min.
  2. Положим, что зафиксирован «целевой» размер блока b, создадим 1 + [N/b] блоков размера cb, где c ≥ 1 (избыточное резервирование).
  3. Пройдёмся по сортируемой последовательности, пусть x – число, положим его в блок с индексом [[N/b] (x — min) / r].
  4. Отсортируем каждый блок независимо.
  5. Конкатенируем блоки по порядку в результирующую последовательность.

Код базового варианта (bucket sort 1) вычисляет размер блока, используя шаблон BucketSize<тип элемента>::value. Текущий размер взят с прицелом на то, чтобы блок помещался (в случае равномерного распределения входной последовательности) в L2-кэш машины Deneb (512kb), что должно положительно сказаться на скорости сортировки блока. Собственно сортировка блока может выполняться как рекурсивно (к блоку снова применяется блочная сортировка, пока блоки не станут совсем маленькими), либо может использоваться любая другая сортировка, здесь используется std::sort. Пожалуй, наиболее логичным вариантом было бы применять блочную сортировку до достижения размера блока < L2-кэша (256кб – 2Мб в распространённых ЦП, можно остановиться на 256кб), после чего переключаться на std::sort.

В качестве блоков в базовом варианте используются объекты std::vector, автоматически увеличивающие свой размер при необходимости. Впрочем, как показал опыт, полезнее заранее посчитать размеры блоков, так как операции с памятью (особенно выделение в несколько потоков) обходятся дорого. Поэтому был написан вариант 2 (bucket sort 2), который заранее определяет размеры блоков и потом размечает под них массив размера N. Кроме увеличения скорости, это гарантирует использование количества вспомогательной памяти, равного размеру входной последовательности, в то время как вариант 1 может «съесть» гораздо больше памяти в случае «неудачного» распределения исходной последовательности.

Далее, было рассмотрено два способа распараллеливания алгоритма блочной сортировки.

Вариант распараллеливания 1 (bucket sort 1/p на основе bucket sort 1 и bucket sort 2/p на основе bucket sort 2). Каждый этап распараллеливается отдельно, входная последовательность разбивается на примерно равные куски, обрабатываемые каждый своим потоком. Каждый поток «разбрасывает» элементы по своей группе блоков (но блоки покрывают одинаковые поддиапазоны, не зависящие от потока). Блоки сортируются параллельно. В конце производится (последовательное) слияние групп блоков (обобщение слияния двух упорядоченных последовательностей).

Вариант распараллеливания 2 (bucket sort 3/p и bucket sort 4/p). Каждому потоку отводится своя часть диапазона значений входной последовательности. Все потоки пробегают входную последовательность целиком, но берут только те значения, которые попадают в поддиапазон потока. Опять же, сортировка блоков производится параллельно. Слияние групп блоков в конце уже не требуется. Вариант 4 отличается от варианта 3 так же, как вариант 2 отличается от варианта 1 (т.е. блоки размещаются не в отдельных векторах, а в общем буфере, и их размер вычисляется заранее).

Результаты тестирования показывают, что bucket sort 2 и bucket sort 4 способны обеспечить большую эффективность задействования дополнительных ядер, и лишний проход по входной последовательности для вычисления размеров блоков оправдывается. С другой стороны, вариант распараллеливания 1 выглядит более эффективным (практически всегда – сравните результаты bucket sort 4/p vs bucket sort 2/p) нежели вариант распараллеливания 2.

Далее: tier-1c radix, tier-1b.1 SSE2, tier-1b.2 bucket size varying (планируется продолжение изучения блочной сортировки, как одного из наиболее эффективных алгоритмов сортировки чисел)

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: