Алгоритм внешней сортировки имеет две фазы:
1) Фаза последовательной кусочной сортировки
2) Фаза слияния отсортированных кусков
Мы хотим его оптимизировать, эффективно используя многоядерность процессора.
Первая фаза паралелится очевидным образом: после того как мы загрузили кусок файла в память будем его сортировать в несколько потоков. Как это сделать наилучшим образом?
Вариант первый - натурально паралеллить алгоритм QuickSort().
Коротенько, как устроен сам quickSort: берётся некий элемент массива в качестве опорного (в простом варианте - первый элемент), и все остальные элементы массива перекидываются так, что все меньшие опорного размещаются левее его, а все большие - правее. Далее этот же алгоритм применяется к левой и правой частям рекурсивно. Т.е. сразу видно, как только у нас образовалась левая и правая часть, после первого прохода - их можно сортировать независимо друг от друга, параллельно.
Мне это вариант не очень понравился во-первых из-за "не синхронного" старта: первый проход может происходить не более чем в один поток, второй не более чем в два потока, третий - четыре. Во-вторых возникают простои - например, после первого прохода, "правый" поток, отработав, например, быстрее, вынужден ждать пока закончит работу левый, не в состоянии ничем ему помочь.
Вариант второй - Parallel Sorting with Regular Sampling (PSRS). Подробное описание с картинками есть здесь
Суть такая:
0) Нам нужно распараллелить сортировку загруженного в память массива A из n элементов на p потоков
1) Делим исходный массив на p подмассивов A_p приблизительно одинаковой размерности
2) Запускаем p потоков сортировки каждого подмассива A_p.
3) Параллельно выбираем из каждого отсортированного подмассива p чисел - сэмплы. Выборка делается по принципу :
sample_p[i] = A_p[j(i)], i = 0 .. p-1, j(i) = i * n / p^2;
4) Сливаем все sample_p в один массив sample и сортируем его.
5) Выбираем опорные точки pivot.
pivot[i] = sample[j(i)], i = 0 .. p-2, if (i < p - 2) j(i) = i * p + p + [p/2] - 1 else j(i) = (p-1) * p + [p/2]
6) Параллельно разбиваем Ap на подмассивы App так, что все элементы Ap0 не больше pivot[0], все элементы Ap1 не больше pivot[1], но больше pivot[0] и т.д.
7) Собираем все первые кусочки всех Ap в массив B1, все вторые кусочки всех Ap в массив B2 и т.д.
Полученные массивы Bp обладают тем свойством, что pivot[p-1] < любой элемент Bp <= pivot[p]
8) Параллельно сортируем Bp.
9) Сконкатенированные, отсортированные Bp дают отсортированный массив A.
Так как Bp состоят из кусочков отсортированных Ap, то пункт 8 существенно эффективнее производить сортировкой слиянием, хотя это требует в два раза больше памяти,чем инплейс сортировка.
Этот алгоритм я реализовал распараллелив его с операциями чтения\записи данных с диска.
Т.е. пока производится сортировка считанного в память чанка, идёт запись на диск результатов предыдущей сортировки и вычитывание следующего чанка.
Что не получилось. Совершенно не получилось как-то распараллелить вторую фазу. И хотелосьбы услышать какие-нибудь идеи по этому поводу.
А вот исходники
Комментариев нет:
Отправить комментарий