Распараллеливание сортировки по основанию для чисел с плавающей запятой с использованием библиотеки pthread в C

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

Чтобы создать гистограмму параллельно, вы можете заполнить локальные гистограммы в каждом потоке, а затем выполнить (на основе дерева) сокращение гистограмм для построения глобальной гистограммы. Эта стратегия хорошо масштабируется, если гистограмма мала по сравнению с фрагментами данных, вычисляемыми каждым потоком. Альтернативный способ распараллелить этот шаг — использовать атомарные добавления для непосредственного заполнения общей гистограммы. Этот последний метод практически не масштабируется, когда поток записи обращается к конфликтам (что часто происходит с небольшими гистограммами и многими потоками). Обратите внимание, что в обоих решениях входной массив равномерно распределяется между потоками.

Что касается части заполнения корзины, одно из решений состоит в том, чтобы использовать атомарные добавления для заполнения корзин: 1 атомарный счетчик на корзину необходим, чтобы каждый поток мог безопасно возвращать элементы. Это решение масштабируется только тогда, когда потоки не часто обращаются к одному и тому же сегменту (конфликты сегментов). Это решение не очень хорошее, поскольку масштабируемость алгоритма сильно зависит от содержимого входного массива (в худшем случае последовательного). Существуют решения для уменьшения конфликтов между потоками (лучшая масштабируемость) за счет увеличения объема работы (медленнее с небольшим количеством потоков). Один из них заключается в заполнении сегментов с обеих сторон: потоки с четным идентификатором заполняют сегменты в порядке возрастания, а потоки с нечетным идентификатором заполняют их в порядке убывания. Обратите внимание, что важно учитывать ложное совместное использование, чтобы максимизировать производительность.

Простой способ распараллелить сортировку по основанию для всех, кроме первого прохода, состоит в том, чтобы использовать проход старшего разряда (MSD) для разделения массива на ячейки, каждую из которых затем можно сортировать одновременно. Этот подход основан на относительно равномерном распределении значений, по крайней мере, в отношении старшей значащей цифры, так что ячейки имеют разумно равный размер.

Например, используя размер цифры 8 бит (основание 256), используйте проход MSD, чтобы разделить массив на 256 ячеек. Предполагая, что есть t потоков, затем сортируйте t интервалов за раз, используя сортировку по основанию с наименьшими значащими цифрами.

Для больших массивов может помочь использование большего начального размера разряда, чтобы разбить массив на большее количество бинов, чтобы t бинов поместились в кэше.

Ссылка на непараллельную сортировку по основанию, которая использует MSD для первого прохода, а затем LSD для следующих 3 проходов. Цикл в конце RadixSort() для сортировки 256 ячеек можно распараллелить:

Оптимизация сортировки по основанию