PRAM: много процессоров, общая память и шаг на всех

Если ты знаешь, что такое PRAM, чем EREW отличается от CRCW и как сложить n чисел за логарифм шагов, листай до «Теперь сам».

Как думаешь, сколько шагов

В памяти лежат 1024 числа, и есть 512 исполнителей. За один шаг исполнитель может взять два числа из памяти, сложить их и записать результат обратно. Все исполнители работают одновременно, шаги общие, как удары метронома. За сколько шагов можно получить сумму всех 1024 чисел?

Ответь себе до чтения. Частые ответы - «два» (512 исполнителей, каждый складывает по паре, и ещё шаг на сведение) и «512» (кто-то же должен сложить 512 частичных сумм). Правильный ответ - 10, и он не зависит от того, что исполнителей ровно половина: при миллионе исполнителей быстрее всё равно не выйдет.

На что это похоже

Турнир на выбывание. 1024 команды, в первом туре 512 матчей идут одновременно на разных полях, и остаётся 512 победителей. Во втором туре 256 матчей, потом 128 и так далее. Финал - десятый тур. Добавить полей ничего не даст: во втором туре играют только победители первого, а они появляются лишь после первого тура.

Сложение работает так же. Сумма двух соседей - «победитель матча», и следующий уровень можно начать, только когда готов предыдущий. Число туров - сколько раз 1024 делится пополам до одного: это и есть логарифм по основанию два.

Механизм: синхронные шаги и общая память

PRAM (параллельная машина с произвольным доступом, Форчун и Уилли, 1978) - это p обычных процессоров RAM-модели, подключённых к одной общей памяти. У каждого процессора есть номер i, и все выполняют одну программу, глядя на свой номер. Время идёт общими шагами: за шаг каждый процессор читает несколько ячеек, делает над прочитанным постоянное число операций и записывает результат. Цена алгоритма - число шагов, и рядом с ним всегда указывают, сколько процессоров потребовалось.

Сумма деревом: на шаге с расстоянием d = 1, 2, 4, … процессор с номером i, кратным 2d, делает x[i] = x[i] + x[i + d]. После шага с расстоянием d в каждой ячейке с номером, кратным 2d, лежит сумма своего блока из 2d чисел. Расстояние удваивается, пока не дорастёт до n, - поэтому шагов ⌈log₂ n⌉, то есть логарифм, округлённый вверх: при n, не равном степени двойки, последний неполный уровень всё равно занимает шаг.

Дерево меняет порядок сложений: вместо ((x₀ + x₁) + x₂) + x₃ считается (x₀ + x₁) + (x₂ + x₃). Так можно, потому что сложение ассоциативно - результат не зависит от расстановки скобок. Тем же свойством обладают максимум, минимум, умножение, логические И и ИЛИ - для них дерево тоже работает. Для вычитания - нет: (8 − 3) − 2 = 3, а 8 − (3 − 2) = 7.

Главный вопрос модели - одновременный доступ к одной ячейке. Варианты называют тремя буквами:

Правило записи у CRCW бывает разным. Common - разрешено, только если все пишут одно и то же значение. Arbitrary - побеждает одно из значений, неизвестно какое. Priority - побеждает процессор с меньшим номером.

Правило

PRAM - p процессоров над общей памятью, работающие синхронными шагами; цена алгоритма - число шагов при указанном числе процессоров. Сумма, максимум и любая другая ассоциативная операция над n числами считаются деревом за ⌈log₂ n⌉ шагов на ⌈n / 2⌉ процессорах, и для этого хватает самой строгой модели EREW. CREW разрешает одновременное чтение одной ячейки, CRCW - ещё и запись, и на отдельных задачах они заметно быстрее.

Разбор: сумма 1000 чисел по шагам

Программа исполняет PRAM буквально: на каждом шаге сначала собирает все сложения шага, а потом применяет их разом. Так проверяется главное свойство шага - никто не видит записей соседей, сделанных в том же шаге.

def pram_summa(x):
    x = x[:]
    n = len(x)
    d = 1
    shag = 0
    while d < n:
        dela = []
        i = 0
        while i + d < n:
            dela.append([i, x[i] + x[i + d]])
            i = i + 2 * d
        for i, v in dela:
            x[i] = v
        shag = shag + 1
        print("шаг", shag, "d =", d, "сложений", len(dela))
        d = d * 2
    return [x[0], shag]

print(pram_summa([3, 1, 4, 1, 5, 9, 2, 11]))
s, shagov = pram_summa(list(range(1, 1001)))
print(s, shagov)

шаг 1 d = 1 сложений 4
шаг 2 d = 2 сложений 2
шаг 3 d = 4 сложений 1
[36, 3]
шаг 1 d = 1 сложений 500
шаг 2 d = 2 сложений 250
шаг 3 d = 4 сложений 125
шаг 4 d = 8 сложений 62
шаг 5 d = 16 сложений 31
шаг 6 d = 32 сложений 16
шаг 7 d = 64 сложений 8
шаг 8 d = 128 сложений 4
шаг 9 d = 256 сложений 2
шаг 10 d = 512 сложений 1
500500 10

Тысяча чисел - десять шагов: 2⁹ = 512 < 1000 ≤ 1024 = 2¹⁰, и логарифм округляется вверх. Процессоров на первом шаге нужно 500, дальше всё меньше: на десятом работает один, остальные 499 простаивают. Всего сложений 999 - ровно столько, сколько в обычном цикле. Дерево не сэкономило ни одной операции, оно переставило их так, что многие идут одновременно.

Обрати внимание на строки 62 и 31: тысяча не степень двойки, и на этих уровнях частичных сумм нечётное число - 125 и 63, так что одной не досталось пары. Такая ячейка просто ждёт следующего уровня - отсюда условие i + d < n.

Разбор: есть ли среди битов единица

Второй пример показывает, зачем различают варианты модели. У каждого из n процессоров есть бит, и нужно узнать, есть ли хоть одна единица - логическое ИЛИ всех битов.

На EREW и CREW это то же дерево: ⌈log₂ n⌉ шагов. Для CREW доказано, что быстрее нельзя (Кук, Дворк, Райшук, 1986). На CRCW с правилом common хватает одного шага: ячейка g заранее равна нулю, и каждый процессор, у которого бит 1, пишет в g единицу. Пишут все одно и то же значение - правило common соблюдено.

import random

def ili_derevom(bity):
    x = bity[:]
    d = 1
    shagov = 0
    while d < len(x):
        i = 0
        while i + d < len(x):
            x[i] = max(x[i], x[i + d])
            i = i + 2 * d
        d = d * 2
        shagov = shagov + 1
    return [x[0], shagov]

def ili_crcw(bity):
    g = 0
    pishut = 0
    # цикл перебирает процессоры; в модели все записи - один шаг
    for b in bity:
        if b == 1:
            g = 1
            pishut = pishut + 1
    return [g, 1, pishut]

random.seed(5)
for n in [16, 1000]:
    bity = []
    for i in range(n):
        bity.append(random.randint(0, 1))
    print(n, ili_derevom(bity), ili_crcw(bity))

16 [1, 4] [1, 1, 6]
1000 [1, 10] [1, 1, 505]

Третье число в ответе CRCW - сколько процессоров писали в одну ячейку в одном шаге: 505 из тысячи. В модели это бесплатно. На настоящих машинах одновременные записи в одну ячейку обычно выстраиваются в очередь, и такой шаг может стоить порядка числа пишущих. Сандерс и соавторы в своей книге 2019 года прямо советуют не строить алгоритмы на CRCW по этой причине. Ровно эта разница - модель против железа - тема следующего блока.

Что ломается без этого

Счётчик без правила. Два процессора одновременно делают c = c + 1 при c = 41: оба читают 41, оба пишут 42, и одно событие потеряно. PRAM честно говорит, что в одном шаге запись в одну ячейку - это отдельный вопрос модели, а не «как-нибудь сложится». Программа, которая молча предполагает CRCW, на настоящей машине теряет обновления.

Синхронность, которой нет. В PRAM все процессоры идут шаг в шаг. Настоящие ядра работают каждое в своём темпе, и сложение x[i] + x[i + d] может прочитать ячейку раньше, чем сосед закончил прошлый уровень. Дерево на настоящей машине требует барьера между уровнями - точки, где все ждут всех.

Бесплатный доступ к памяти. Модель не знает про кеши, задержку и пропускную способность. Она отвечает на вопрос «сколько зависимых шагов», а не «сколько секунд».

Зачем это в работе

Видеокарта складывает массив именно деревом: блок потоков сводит свой кусок за логарифм шагов с барьером между уровнями, потом сводятся результаты блоков. MPI_Reduce на кластере собирает сумму со всех узлов деревом. Даже однопоточный numpy.sum по непрерывному участку памяти складывает числа с плавающей точкой попарно, деревом, - ради точности: ошибка округления растёт как логарифм длины, а не как длина.

Модель PRAM нужна, чтобы задать первый вопрос о любой задаче: сколько у неё неизбежно последовательных шагов. Если ответ - логарифм, задача хорошо параллелится. Если ответ - n, никакое число ядер не поможет.

Теперь сам

1. Сколько шагов нужно дереву на 5000 чисел и сколько процессоров на первом шаге?
2. На CREW нужно найти максимум из 64 чисел. Сколько шагов, и почему CREW здесь не быстрее EREW?
3. Сто процессоров в одном шаге пишут свои номера в одну ячейку. Что окажется в ячейке на CRCW с правилом priority, arbitrary и common?