Sample sort и почему quicksort плохо параллелится

Урок про практичную параллельную сортировку больших данных и про слабое место quicksort.

Sample sort — параллельная сортировка: выбрать опорные точки (splitters) по выборке данных, разложить элементы по корзинам между этими точками, отсортировать корзины независимо и склеить.

Беда параллельного quicksort

Quicksort рекурсивно разбивает массив вокруг опорного элемента. Первое разбиение обрабатывает весь массив и по сути последовательно — пока оно не закончилось, параллелить нечего. Только глубже появляются независимые подзадачи. Хуже того, размеры частей зависят от данных: неудачный опорный элемент даёт перекос (одна часть огромная, другая крошечная) и дисбаланс нагрузки. На p процессорах верхние уровни рекурсии оставляют большинство ядер без работы.

Идея sample sort

Sample sort решает обе проблемы. Сначала берём небольшую выборку элементов и по ней выбираем p-1 опорных точек, которые делят весь диапазон значений на p примерно равных корзин. Затем каждый процессор раскладывает свои элементы по корзинам (по тому, между какими опорными точками значение попадает). Корзины перераспределяются между процессорами, и каждый сортирует свою корзину локально — независимо. В конце корзины уже упорядочены между собой, осталось склеить.

def sample_sort(data, buckets):
    s = sorted(data)
    n = len(s)
    # опорные точки по равномерной выборке отсортированных данных
    splitters = [s[(i * n) // buckets] for i in range(1, buckets)]
    print("опорные точки:", splitters)
    # раскладываем по корзинам
    bins = [[] for _ in range(buckets)]
    for x in data:
        b = 0
        while b < len(splitters) and x >= splitters[b]:
            b += 1
        bins[b].append(x)
    # каждую корзину сортируем независимо (параллельно на ядрах)
    for i in range(buckets):
        bins[i].sort()
        print(f"корзина {i}: {bins[i]}")
    # склейка: корзины уже упорядочены между собой
    result = []
    for b in bins:
        result += b
    return result

data = [9, 3, 7, 1, 8, 2, 6, 4, 5, 0, 11, 10]
print("итог:", sample_sort(data, 3))

Вывод:

опорные точки: [4, 8]
корзина 0: [0, 1, 2, 3]
корзина 1: [4, 5, 6, 7]
корзина 2: [8, 9, 10, 11]
итог: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Корзины упорядочены между собой (всё в корзине 0 меньше всего в корзине 1), поэтому склейка — простая конкатенация, без слияния. Главная работа — локальная сортировка корзин — идёт параллельно и сбалансированно, потому что опорные точки выбраны по выборке так, чтобы корзины были примерно равны.

Почему это масштабируется

Как работает под капотом

В кластере sample sort — стандарт. Стадия перераспределения корзин — это all-to-all обмен (каждый шлёт каждому его долю), дорогая по сети, зато единственная. После неё процессоры сортируют локально без коммуникации. Качество балансировки целиком зависит от выборки опорных точек: чем она репрезентативнее, тем ровнее корзины. На практике берут «oversampling» — больше точек, чем нужно, и из них выбирают равномерные.

Sample sort иллюстрирует мощный общий приём: заплатить один раз за дорогую коммуникацию, чтобы потом считать совсем без неё. Naивный параллельный quicksort размазывает коммуникацию по всем уровням рекурсии — она вплетена в каждый шаг. Sample sort, наоборот, концентрирует весь обмен в одну стадию перераспределения корзин, после которой каждый процессор автономен. Такая «концентрация коммуникации» — повторяющийся мотив в алгоритмах для кластеров: лучше один большой, заранее спланированный обмен, чем россыпь мелких и непредсказуемых, потому что сеть наказывает именно за частоту и неравномерность пересылок.

Частые ошибки

• Выбрать плохие опорные точки — корзины перекосятся, и баланс пропадёт.
• Ждать от параллельного quicksort хорошего масштабирования — верхние уровни рекурсии последовательны.
• Забыть, что перераспределение корзин — дорогой all-to-all обмен; его делают один раз.

Итоги

• Sample sort выбирает опорные точки по выборке, раскладывает по корзинам, сортирует их независимо и склеивает.
• Корзины упорядочены между собой — финал это конкатенация без слияния.
• Масштабируется лучше quicksort: сразу p сбалансированных независимых задач.