Счётные сети и дифракция: считать без одной горячей ячейки

Если механизм уже знаком - листай до «Теперь сам».

Как думаешь: что нужно сохранить

Обычный fetch-and-add даёт уникальные номера, но все ядра пишут одну кеш-линию. Если просто распределить обращения по четырём независимым счётчикам, получатся ли номера подряд без дыр? Один перегруженный счётчик может выдать 0,4,8,12, пока остальные ещё не выдали 1,2,3. Нужен инвариант распределения, а не только уникальность каждой полосы.

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

Представь четыре кассы, каждая печатает билеты своего остатка по модулю четыре. Первая печатает 0,4,8, вторая 1,5,9. Сеть направляет посетителей так, чтобы после завершения всех проходов заполненные билеты образовали начало общей последовательности. Балансир - развилка, которая попеременно отправляет следующего посетителя в верхний и нижний коридор, независимо от того, с какого входа он пришёл.

Механизм: от определения к алгоритму

Балансир атомарно переключает бит и попеременно выбирает два выхода. Когда все пришедшие токены вышли, верхний выход получил столько же токенов, сколько нижний, либо на один больше. Для показанной битонической сети допустима ширина w = 2^k при целом k ≥ 1. Для сети такой ширины свойство ступеньки означает: при любых i<j выполняется 0≤y[i]-y[j]≤1. Одного условия «максимум и минимум отличаются на один» недостаточно: лишние токены должны попадать именно в первые выходы.

Битоническая счётная сеть сначала пропускает половины входов через две сети ширины w/2, затем через Merger. Слияние соединяет чётные провода верхней половины с нечётными нижней, и наоборот; рекурсивные результаты попарно проходят завершающие балансиры. Merger сохраняет ступеньку при ступенчатых входных половинах. Его глубина log₂w, суммарная глубина рекурсии сети - O(log²w). Структура напоминает сортирующую сеть, но здесь узел переключает токены, а не сравнивает числа.

На выходе i стоит локальный атомарный счётчик, номера идут i+w·t. Разные остатки исключают дублирование. Свойство ступеньки гарантирует отсутствие дыр после завершения всей группы. Это согласованность в покое, а не обещание линеаризуемого счётчика. Пока токены ещё внутри, поздний вызов может вернуть меньший номер, чем уже завершившийся ранний; уникальность при этом не нарушена.

В дифракционном дереве перед горячим переключателем ставят призму - массив мест встречи. Два встретившихся токена отправляются в разные ветви без обращения к общему биту: два последовательных переключения всё равно вернули бы бит в исходное состояние. Токен без партнёра после ограниченного ожидания использует переключатель. Это разгрузка узла дерева, а не элиминация счёта: оба запроса сохраняются. Условие разного направления и атомарного подтверждения пары необходимо для баланса.

Правило

Разделяй уникальность номеров, ступеньку после покоя и порядок реального времени; счётная сеть не наследует автоматически линеаризуемость fetch-and-add.

Разбор: проследим вычисление

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

class Balancer:
    def __init__(self):
        self.bit = 0
    def route(self):
        answer = self.bit
        self.bit ^= 1
        return answer

class Merger:
    def __init__(self, width):
        if width < 2 or width & (width - 1):
            raise ValueError("width must be a power of two >= 2")
        self.w = width
        self.last = [Balancer() for _ in range(width // 2)]
        self.sub = ([Merger(width // 2), Merger(width // 2)]
                    if width > 2 else [])
    def route(self, wire):
        if self.w == 2:
            return self.last[0].route()
        k = self.w // 2
        half, local = divmod(wire, k)
        branch = local % 2 if half == 0 else 1-local % 2
        port = local // 2 + half * (k // 2)
        z = self.sub[branch].route(port)
        return 2*z + self.last[z].route()

class Network:
    def __init__(self, width):
        if width < 2 or width & (width - 1):
            raise ValueError("width must be a power of two >= 2")
        self.w = width
        self.merge = Merger(width)
        self.sub = ([Network(width // 2), Network(width // 2)]
                    if width > 2 else [])
    def route(self, wire):
        if self.sub:
            half, port = divmod(wire, self.w // 2)
            wire = half*(self.w // 2) + self.sub[half].route(port)
        return self.merge.route(wire)

net = Network(4)
counts = [0] * 4
numbers = []
for wire in [3, 3, 0, 2, 1, 0, 0, 3, 2, 2, 1]:
    i = net.route(wire)
    numbers.append(i + 4*counts[i])
    counts[i] += 1
assert sorted(numbers) == list(range(len(numbers)))
print("выходы", counts)
print("номера", sorted(numbers))

выходы [3, 3, 3, 2]
номера [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Разбор: где проходит граница

Пусть завершились токены выходов 0 и 2, а токен выхода 1 задержался перед локальным счётчиком. Уже видны номера 0 и 2, но 1 ещё не вернулся. Это не противоречит гарантии состояния покоя: сеть ещё не пуста. Если контракт приложения требует выдавать следующий номер строго после предыдущего завершённого вызова, недостаточно проверить только итоговое множество номеров. Нужна более сильная структура и доказательство её истории.

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

Случайное распределение по полосам даёт уникальность, но оставляет дыры. Соединение балансиров «на глаз» не гарантирует ступеньку: порядок проводов существенен. Неатомарное переключение теряет обновление и направляет два токена одинаково. Дифракция двух токенов в одну ветвь разрушает эквивалентность двум переключениям. Бесконечное ожидание пары делает продвижение зависимым от будущего запроса.

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

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

Теперь сам

Сеть ширины 4 пропустила и завершила 11 токенов. Какие количества должны быть на выходах? Какие номера выдаёт выход 2 при трёх посещениях?