ParallelSort: Tier-1a Bitonic

Битоническая сортировка является самой популярной сортировкой на основе сортирующих сетей. Исходный код однопоточного нерекурсивного варианта. Тип Index является синонимом библиотечного типа std::ptrdiff_t и используется для представления индексов и размеров массивов. Если присмотреться к коду, то можно заметить, что а) всего производится O(N (log N)2) сравнений и их количество зависит только от N, а не от содержимого (от него уже зависит количество обменов); б) итерации внутренних циклов (по k и p) независимы друг от друга и могут выполняться параллельно. Благодаря указанным свойствам битоническая сортировка может быть реализована аппаратно (для фиксированного N) в виде сети компараторов, может эффективно выполняться параллельно на устройствах с высокой степенью параллелизма, например, графических процессорах.

Для распараллеливания битонической сортировки на ЦП было применено расширение языка C OpenMP. MSVC поддерживает OpenMP 2.0. При использовании OpenMP низкоуровневым управлением потоками исполнения занимается компилятор, программист же размечает исходный код директивами OpenMP, основанными на директиве препроцессора pragma. Это весьма удобно, пока код укладывается в ограничения OpenMP, например, если достаточно параллельного исполнения итераций цикла for. Последнее делается следующим образом:

#pragma omp parallel for
for (SignedIntegerType i = i0; i < i1; i += di)
  // code

Ограничения, накладываемые директивой parallel for:

  • тип переменной-счётчика должен быть целым со знаком;
  • количество итераций должно быть известно и фиксировано на момент входа в цикл;
  • инкремент счётчика должен выполняться простой формулой (удалить или добавить константу);
  • тело цикла не должно содержать break или выход из цикла по goto.

Так как ядер в современных массовых ЦП относительно немного, то решено сделать ветвление, которое распараллеливает либо цикл по k, либо цикл по p: исходный код и результаты тестирования. К сожалению, реальная эффективность распараллеливания оказалась довольно низкой, видимо, из-за большого количества промахов кэшей (в пользу этого говорит и то, что оценка parallelism на основе congestion довольно хорошо описывает реальную эффективность параллельной версии). В случае использования битонической сортировки на ГП указанный фактор уже не должен оказывать заметного влияния.

Далее: tier-1b bucket.

Реклама

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

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

Логотип WordPress.com

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

Фотография Twitter

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

Фотография Facebook

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

Google+ photo

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

Connecting to %s

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