Конспект раздела: параллельные и внешние алгоритмы

Одна мысль на весь раздел

RAM-модель считает операции и предполагает, что они идут по одной и любая ячейка стоит единицу. Раздел шесть раз менял это предположение, и каждый раз менялось то, что считают: шаги и работа при многих процессорах, порядок операций при общей памяти, сообщения при сети, блоки при диске. Алгоритм, лучший в одной модели, бывает плохим в другой - поэтому первый вопрос к задаче: что здесь дорого?

Дерево решений

что дорого в задаче?
├── много исполнителей, общая память, счёт шагов
│   ├── сколько неизбежно последовательных шагов?  → глубина T∞
│   ├── сколько всего работы?                      → работа T₁
│   └── хватит ли ядер?  T₁/p против T∞; Брент: Tₚ ≤ T₁/p + T∞
├── исполнители пишут в одну память без общего такта
│   ├── хватит ли атомарной операции?  → fetch_add, CAS-цикл
│   ├── нужен замок?  → TTAS / талоны / MCS; общий порядок захвата
│   ├── что значит «правильно»?  → линеаризуемость, проверка истории
│   └── нельзя зависеть от медленного потока?  → lock-free / wait-free
├── узлы связаны сетью
│   ├── короткие сообщения → дерево, log₂ p задержек
│   ├── длинные данные → конвейер, кольцо: передача ≈ βn
│   └── неизвестные размеры задач → кража работы
└── данные больше памяти
    ├── читается подряд? → проход N/B
    ├── нужен поиск → B-дерево, log_B N
    ├── нужна сортировка → прогоны + слияние по M/B путей
    └── поток вставок → LSM-дерево

Как части связаны

величина	где появляется	чем её уменьшают
глубина	PRAM, граф задач, скан, сети	дерево вместо цепочки: log n вместо n
работа	лишняя работа, порог, слияние рангами	работоэффективные схемы, крупные задачи
число чередований	гонка, замки	атомарные операции, критическая секция
трафик кеша	спин-блокировки, кеш	ожидание чтением, своя ячейка, блоки
задержка α	сообщения, all-reduce	деревья, склейка мелких сообщений
передача β	рассылка, all-reduce	конвейер, кольцо, разбиение на куски
блок B	диск, кеш, внешние структуры	проходы, ветвление B, прогоны

Одна и та же идея повторяется в разных одеждах: дерево вместо цепочки (сумма деревом, скан, рассылка, B-дерево) и крупные порции вместо мелких (порог задачи, склейка сообщений, кольцо по кускам, прогоны, LSM).

Числа раздела, которые стоит помнить

сумма 1000 чисел деревом - 10 шагов; сборка: работа 44, глубина 22
слияние с обычным слиянием: параллелизм log₂ n / 2 (6 на 4096)
Амдал: 5% последовательного кода - потолок 20
скан Блеллоха: 2(n − 1) сложений; Хиллис - Стил: n log n
битонная сеть на 8 входов: 6 слоёв, 24 компаратора; минимум - 19
c = c + 1 двумя потоками: правильно в 2 чередованиях из 20
Петерсон: 26 состояний; на TSO без барьера - двое в секции
16 ядер: TAS ~47 обращений к шине на захват, TTAS ~33, MCS ~5
порог α / β = 200 КБ при α = 20 мкс и 10 ГБ/с
all-reduce 100 МБ на 64 узлах: кольцо 22 мс, гиперкуб 60
двоичный поиск на 10⁸ ключах - 18 блоков, B-дерево - 3
внешняя сортировка - один проход слияния, пока N ≤ M² / B

Границы, общие для всех результатов

Модели нарочно грубые: PRAM не знает про синхронизацию и кеши, перебор состояний верен только в моделируемой модели памяти, α + β · n не знает про перегрузку сети, а модель внешней памяти - про предвыборкуРазбирается в разделе 25, глава «Память, локальность и честный замер»: Иерархия памяти: одна и та же сумма в шесть раз медленнее и ассоциативность кеша. Модель отвечает на вопрос «какой алгоритм лучше и почему», точные числа даёт только замер - об этом следующий раздел.

Ловушки джокера

Делить работу на число ядер. Время не меньше глубины.

Малая глубина ценой работы. На восьми ядрах обычно решает работа, а не глубина: пока глубина много меньше работы, делённой на число ядер.

Гонку проверять тестами. Плохие чередования редки; протокол доказывают перебором состояний.

Перебор не в той модели памяти. На x86 протоколу из чтений и записей нужен барьер.

Ждать записью в общую ячейку. Трафик когерентности тормозит и ожидающих, и владельца.

Замки в разном порядке. Цикл ожидания и вечная взаимоблокировка.

Мелкие сообщения и один координатор. Задержки и узкое место; сбор - деревом.

Дерево для больших данных. Каждый раунд гонит весь объём; нужен конвейер или кольцо.

Случайный доступ к диску. В B раз дороже прохода; сортируют слиянием, ищут B-деревом.

Цена синхронизации и перемещения данных

Задача	Инструмент	Условие или граница
Ранг списка	Независимое множество	Ожидаемая работа O(n); сравнивай работу и глубину отдельно.
Ожидание условия	Монитор и RW-lock	wait проверяет предикат в while; предпочтение писателей не равно FIFO.
Конкурентные чтения	Backoff и атомарный снимок	Откат нагрузки не обещает справедливость; снимку нужны версии и помощь.
Три внешних файла	Многофазное слияние	Фибоначчи - выбранное расписание, а не единственная возможная раскладка.
Рёбра на диске	Полувнешний Крускал	DSU помещается в памяти; инициализация стоит Θ(n), сортировка оплачивается отдельно.

Проверь, что можешь объяснить

Почему у суммы деревом параллелизм n / log n, а у сортировки слиянием с обычным слиянием - log n / 2?
Почему жадный планировщик не хуже лучшего расписания больше чем вдвое?
Как скан превращает упаковку массива в одновременную запись без очереди?
Почему двух флагов мало для замка, а флага и жертвы - достаточно?
Что ломает Петерсона на x86 и где ставить барьер?
Чем линеаризуемость отличается от последовательной согласованности - на примере очереди?
Почему цикл CAS - lock-free, но не wait-free?
Когда all-reduce делают гиперкубом, а когда кольцом, и почему?
Почему вор в краже работы берёт задачу из начала дека?
Сколько проходов делает внешняя сортировка терабайта при 16 ГБ памяти, и почему не семь?
Почему блок транспонирования 8 × 8 бывает не лучше обычного цикла?
Почему LSM-дерево пишет каждый элемент много раз и всё же быстрее B-дерева на вставках?