ParallelSort: Intro

Этим постом я открываю серию постов, посвящённых исследованию возможностей распараллеливания ряда алгоритмов сортировки. Одновременно планируется исследовать применимость некоторых средств SMT распараллеливания, доступных для языка C++, в связи с чем (механизм задействования параллелизма) алгоритмы сортировки разделены на три группы («tiers») плюс эталонная однопоточная группа «стандартных сортировок»:

  1. Алгоритмы стандартной библиотеки C++: std::sort, std::stable_sort, пирамидальная heap sort (std::make_heap + std::sort_heap).
  2. Алгоритмы, распараллеливание которых может быть эффективно осуществлено путём параллельного исполнения независимых итераций циклов for: битоническая bitonic sort (нерекурсивный вариант), блочная bucket sort (базовый размер блока, соизмеримый с L2 кэшем ядра), поразрядная radix sort (базовый вариант использует 4-битные разряды).
  3. Рекурсивные алгоритмы с параллельным исполнением ветвей рекурсии: слияниями merge sort, быстрая quick sort, рекурсивный вариант битонической сортировки rbitonic sort.
  4. Алгоритмы, разные стадии которых могут исполняться параллельно, т.е. удобно выполнить конвейеризацию: расчёской comb sort.

Далее: методика тестирования.

Реклама

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

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

Логотип WordPress.com

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

Фотография Twitter

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

Фотография Facebook

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

Google+ photo

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

Connecting to %s

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