Конспект: PRAM, работа и глубина

Понятия

PRAM - p процессоров над общей памятью, синхронные шаги; цена - число шагов при указанном p. Варианты по одновременному доступу к ячейке: EREW (нельзя ничего), CREW (читать можно), CRCW (писать можно: common - одно значение, arbitrary - любое из записанных, priority - меньший номер).

Граф зависимостей - вершины-операции с длительностью, стрелка «эта ждёт ту», циклов нет.

Работа T₁ - сумма всех операций, время на одном процессоре. Глубина T∞ (span, критический путь) - самая длинная цепочка ожиданий, время при бесконечном числе процессоров. Параллелизм - T₁ / T∞.

Жадный планировщик - свободный процессор сразу берёт готовую задачу. Работоэффективный алгоритм делает работу того же порядка, что лучший последовательный. Порог - размер куска, ниже которого рекурсия идёт обычным циклом.

Что унести

ДЕРЕВО НАД n ЧИСЛАМИ                     EREW, ⌈log₂ n⌉ шагов
шаг с d = 1, 2, 4, …: x[i] += x[i + d] для i кратных 2d, i + d < n
работа n − 1 (как у цикла), глубина ⌈log₂ n⌉
1000 чисел - 10 шагов; на первом 500 процессоров, на десятом один
ИЛИ битов: CREW - Ω(log n) (Кук, Дворк, Райшук); CRCW common - 1 шаг

ДВА ЗАКОНА И ОДНА ГРАНИЦА
закон работы    Tₚ ≥ T₁ / p
закон глубины   Tₚ ≥ T∞
жадное          Tₚ ≤ T₁ / p + T∞   (точнее: + T∞ · (p − 1) / p)
жадное не хуже лучшего больше чем вдвое
T₁ / T∞ ≫ p  →  ускорение почти линейное
сборка из урока: работа 44, глубина 22, параллелизм 2
    2 машины: 23 (границы 22 и 33); с 3 машин - 22

РЕКУРСИЯ: РАБОТА СКЛАДЫВАЕТСЯ, ГЛУБИНА - ПО МАКСИМУМУ
сумма:      W = 2W(n/2) + 1 = n − 1,      D = D(n/2) + 1 = log₂ n
слияние:    W = 2W(n/2) + n = n log₂ n,   D = D(n/2) + n ≈ 2n
            параллелизм log₂ n / 2: на 4096 числах - 6
fib с параллельными вызовами: глубина n, работа ~ fib(n)
умножение матриц пополам: работа n³, глубина log² n

АМДАЛ И ГУСТАФСОН
последовательная доля f:
Амдал (та же задача)       S = 1 / (f + (1 − f) / p) → 1 / f
Густафсон (задача растёт)  S = f + (1 − f) · p
f = 5%: на 64 ядрах 15,4, на 1024 - 19,6, предел 20

ЛИШНЯЯ РАБОТА И ПОРОГ
CRCW-максимум за 2 шага: работа n²
    4096 чисел на 8 ядрах: 2 097 154 против 524 у дерева
порог g: задач 2n / g, накладные s · 2n / g, глубина g + s · log₂(n / g)
2²⁰ чисел, s = 50, 8 ядер: лучший порог около 4096 - 511 задач,
    6% от идеала n / p; пороги 256 и 65536 - в полтора раза хуже
правило: задач в разы больше, чем ядер, каждая заметно дороже
         своих накладных расходов

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

Делить работу на процессоры. «44 минуты на 100 машинах - меньше минуты». Время не меньше глубины: 22 минуты при любом числе машин.

Рекурсия - значит параллельно. Длинная последовательная склейка (слияние) оставляет параллелизм логарифмическим.

Барьер между уровнями. «Сначала всё первое, потом всё второе» - не жадно: следующий уровень ждёт самую долгую задачу предыдущего. На графе из 120 задач глубина «по уровням» 184 вместо 99.

Сравнение с самим собой. Ускорение считают относительно лучшего последовательного алгоритма, а не параллельной версии на одном ядре.

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

CRCW в железе. Одновременные записи в одну ячейку выстраиваются в очередь: шаг стоит порядка числа пишущих, а не единицу.

Порог без привязки к машине. 16 кусков были хороши на 8 ядрах и оставляют без дела три четверти машины на 64.